ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 28.03.2024
Просмотров: 12
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
,aj), а ребро (ai,aj) называется инцидентным каждой из вершин ai,aj. Если вершина ai и ребро bj инцидентны, то пишут ai є bj. Количество ребер, инцидентных данной вершине а называется ее степенью или локальной степенью графа в вершине а; степень вершины а обозначается через d(a). Вершины со степенью 0 называются изолированными. В любом графе количество вершин нечетной степени обязательно четно. Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные. Подграфом графа Г называется граф, в который входит лишь часть вершин графа Г вместе с дугами их соединяющими. Матрицей смежности M порядка n называется матрица, состоящая из чисел mij, равных сумме чисел ориентированных ребер, идущих из аi в аj (или чисел неориентированных ребер, соединяющих эти вершины). m[i,j]=1, вершина с номером i смежна с вершиной с номером j, или 0, вершина с номером i не смежна с вершиной с номером j. В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. 2 обозначение (х1 ,х3) относится к дуге а1. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(Х, Г). Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например приведенные выше пути (1) и (2) являются орцепями, а путь (3) не является таким, т.к. дуга а
6 в нем используется дважды. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) – нет.
25. Задача о коммивояжере.
Задача о коммивояжере явл-ся одной из самых знаменитых задач теории комбинаторики (раздел мат-ки, посвящённый реш-ю задач выбора и располож-я эл-тов некоторого, обычно конечного множ-ва в соотв-и с задан.правилами). Она была поставлена в 1934 году. Задача о К. выглядит след.образом: имеется N городов, ктр должен обойти К. с min затратами. При этом на его маршрут накладыв-ся 2 огранич-я: 1)маршрут должен быть замкнутым, т.е. К. должен вернуться в тот город, из ктр он начал движение; 2)в каждом из городов К. должен побывать точно 1 раз. Сейчас реш-е дан.задачи прим-ся во многих обл-тях, имеющих дело с замкнутыми и при этом жестко связанным по времени сис-ми, такими как: конвейерное произв-во, многооперацион.обрабатывающие комплексы, судовые и ж/д погрузоч.сис-мы, перевозки грузов по замкнутому маршруту, расчет авиационных линий. Критерий:
Огранич-я: 
, i = 1..N (2). 
, j = 1..N (3). Ui - Uj + N × Xi j £ N-1, i, j = 1...N, i ¹ j. (4) Усл-е (2) означает, что К. из кажд.города выезжает только 1раз; (3) - въезжает в кажд.город только 1раз; (4) – обеспеч-ет замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутрен.петель. Методы решения задач: 1)метод локал.оптимизации – просматрив-ся только соседние вершины графа (города) найден.пути. Шаг 1. Получить приближен.реш-е (I оценку). Шаг 2. Пока происходит улучш-е реш-я, выполнять след.шаг, иначе перейти на шаг 4. Шаг 3. Д/всех пар № городов i,j, удовлетворяющих нерав-ву 
, проверить: 
д/смежных городов, т.е. 
д/смежн.городов. Если одно из нерав-в выполн-ся, то найдено лучшее реш-е. Следует откорректир-ть ранее найден.реш-е и вернуться на шаг 2. Шаг 4. Закончить работу алг-ма. 2)Алгоритм Эйлера - работоспособен в том случае, если выполн-ся нерав-во треугольника. Его суть в том, что д/любой тройки городов i, j, k(между ктр есть связь)выполн-ся нерав-во. Шаг 1. Построение каркаса min веса (алг-мы Прима или Краскала). Шаг 2. Путем дублирования кажд.ребра каркас преобраз-ся в эйлеров граф. Шаг 3. Нахожд-е в построен.графе эйлерова цикла. Шаг 4. Преобразов-е эйлерова цикла в гамильтонов цикл (или маршрут К.). Метод преобразов-я: послед-ть вершин эйлерова цикла сокращ-ся так, чтобы кажд.вершина графа в получившимся цикле встречались ровно 1раз. Шаг 5. Закончить работу алг-ма. Получено приближен.реш-е задачи К. 3)Алгоритм Кристофидеса. Шаг 1. Строится каркас min веса. Шаг 2. На мн-ве вершин каркаса, имеющих нечетное число ребер каркаса, нах-ся паросочетание min веса. Таких вершин в любом каркасе четное число. Метод поиска паросоч-я – чередующиеся цепочки. Шаг 3. Каркас преобраз-ся в Эйлеров граф путем присоедин-я ребер, соотв-щих найден.паросоч-ю. Шаг 4. В построен.графе нах-ся Эйлеров маршрут. Шаг 5. Эйлеров маршрут преобраз-ся в маршрут К.
26. Понятие системы массового обслуживания, классификация систем массового обслуживания. Простейшие системы массового обслуживания и их параметры.
При исследовании операций часто приход-ся сталкив-ся с сис-мами, предназнач-ными д/многоразового использ-я при решении однотипных задач. Возникающие при этом процессы получили назв-е процессов обслуживания, а сис-мы – систем масс.обслужив-я (СМО). #телефон.сис-мы, билетные кассы, магазины. Кажд.СМО состоит из опр.числа обслужив-щих ед-ц, ктр наз-ся каналами обслужив-я. Ими могут быть линии связи, рабочие точки, продавцы… По числу каналов СМО подразделяют на одноканальные и многоканальные. Заявки поступают в СМО обычно не регулярно, а случайно, образуя так называемый случ.поток заявок (требований). Предметом теории масс.обслужив-я явл-ся построение мат.моделей, связывающий задан.условия работы СМО с показ-лями эф-ти СМО, описывающими ее способ-ть справляться с потоком заявок. В кач-ве показ-лей эф-ти СМО использ-ся: сред.число заявок, обслуживаемых в ед-цу времени; сред.число заявок в очереди… СМО делят на 2типа: СМО с отказами и СМО с ожиданием (очередью). В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслужив-я не участвует (#заявка на телеф.разговор в момент, когда все каналы заняты, получает отказ и покидает СМО необслуженной). В СМО с ожиданием заявка, пришедшая в момент, когда все канала заняты, не уходит, а становится в очередь на обслужив-е. СМО с ожиданием подразд-ся на разные виды в завис-ти от того, как организована очередь: с огранич.или неогранич.длиной очереди, с огранич.временем ожидания… Д/класс-ции СМО важное знач-е имеет дисциплина обслужив-я, опр-щая порядок выбора заявок из числа поступивших и порядок распред-я их между свобод.каналами. По этому признаку обслужив-е заявки может быть организовано по принципу «первая пришла – первая обслужена», «послед.пришла – первая обслужена» (такой порядок может прим-ся, #при извлечении д/обслужив-я изделий со склада, ибо последние из них оказыв-ся часто более доступными) или обслужив-е с приоритетом (когда в I очередь обслужив-ся наиболее важные заявки). Приоритет может быть абсолютным (когда более важная заявка «вытесняет» из-под обслужив-я обычную заявку) и относительным (когда более важная заявка получает лишь «лучшее» место в очереди).
27. Осн-е по-я теории марковских процессов: случайный процесс, марковский процесс, граф состояний, поток событий, вероятность состояния, уравнения Колмогорова, финальные вероятности состояний.
При исследов-и операций часто приход-ся сталкив-ся с сис-ми, предназначенными д/многоразового использ-я при реш-и однотипных задач. Возникающие при этом процессы наз-ся процессами обслужив-я, а сис-мы – сис-мы масс.обслуж-я (СМО). Процесс работы СМО предст-ет собой случ.процесс. Случ.процесс – процесс изменения во времени сост-я к.-либо сис-мы в соотв-и с вер-тными закономер-тями. Процесс наз-ся процессом с дискрет.сост-ями, если его возможные сост-я s1, s2, s3 можно заранее перечислить, а переход сис-мы из сост-я в сост-е происходит скачком. Процесс наз-ся процессом с непрерыв.временем, если моменты возможных переходов сис-мы из сост-я в сост-е не фиксированы заранее, а случайны. Мат.анализ работы СМО сущ-но упрощ-ся, если процесс этой работы – Марковский. Случ.процесс наз-ся Марковским (случ.процессом без последствия), если д/любого момента времени вер-тные хар-ки процесса в будущем зависят только от его сост-я в дан.момент и не зависят от того, когда и как сис-ма пришла в это сост-е (# счетчик в такси). При анализе случ.процессов с дискрет.сост-ями удобно польз-ся геометрич.схемой – графом сост-й. Обычно сост-я сис-мы изображ-ся прямоуг-ками (кружками), а возмож.переходы из сост-я в сост-е – стрелками (ориентирован.дугами), соед-щими сост-я. Поток соб-й – послед-ть однород.соб-й, следующих одно за др. в какие-то случ.моменты времени (#поток вызовов на телефон.станции, поток покупателей). Регуляр.поток соб-й, если соб-я следуют одно за др. через опр.равные промежутки времени (поток изделий на конвейере сборочного цеха). Стац.поток соб-й, если его вер-тные хар-ки не зависят от времени (поток автомобилей в течение суток в часы пик). Поток без последействия, если д/любых 2х непересек-щихся участков времени, попадающих на один из них, не зависит от числа соб-й, попадающих на др. (поток пассажиров в метро). Ординар.поток, если вер-ть попадания на малый участок времени 2х и более соб-й пренебрежимо мала по сравнению с вер-тью попадания одного соб-я (т.е.поток соб-й ординарен, если соб-я появл-ся в нем поодиночке, а не группами). Простейший (стац.пуассоновский), если он одновр-но стационарен, ординарен и не имеет последействия. Закон Пуассона:
. Вер-ть того, что за время
не произойдет ни одного соб-я (m=0), = 
. Вер-ть того, что на участке времени длиной t не появится ни одного из последующих соб-й = 
, а вер-ть противополож.соб-я, т.е. f-я распред-я случ.величины Т, = 
. Рассмотрим #. Устр-
во S состоит из 2х узлов, каждый из ктр в случ.момент времени может выйти из строя, после чего мгновенно начин-ся ремонт узла, продолж-щийся заранее неизв.случ.время. Возможны 4исхода: S0 – оба узла исправны, S1 – Iузел ремонтир-ся, II-исправен, S2 – Iiузел ремонтир-ся, I-исправен, S3 – оба ремонтир-ся. Если начертить граф, то он наз-ся размеченным, т.е. у стрелок проставлены интенсив-ти. Д/этого составл-ся и решаются ур-я Колмогорова – особого вида диф.ур-я, в ктр неизв.f-ями явл-ся вер-ти сост-й. Пр-ло составл-я ур-й Колмогорова: В лев.части каждого из них стоит производная вер-ти i-го сост-я. В прав.части – сумма произведений вер-тей всех сост-й (из ктр идут стрелки в дан.сост-е) на интенсив-ти соотв-щих потоков соб-й – Сум.интенсив-ть всех потоков, выводящих сис-му из дан.сост-я, * на вер-ть дан. (i-го сост-я). Особен-ть решения диф.ур-й состоит в том, что требуется задать так называемые нач.условия. Эту сис-му можно составить по размеч.графу сост-й по след.правилу: слева в ур-ях стоит предельная вер-ть дан.сост-я pi, * на Сум.интенсив-ть всех потоков, ведущих из дан.сост-я, а справа – сумма произведений интенсив-тей всех потоков, входящих в i-е сост-е, на вер-ти тех сост-й, из ктр эти потоки исходят. А что будет происходить с вер-тями сост-й при t→? Если эти пределы сущ-ют и не зависят от нач.сост-я сис-мы, то они наз-ся финал.вер-тями сост-й. Если число n сост-й сис-мы конечно и из кажд.из них можно перейти в любое др., то фин.вер-ти сущ-ют.
28. Предмет и задачи теории игр. Основные понятия теории игр: игра, игроки, партия, выигрыш, проигрыш, ход, личные и случайные ходы, стратегические игры, стратегия, оптимальная стратегия.
Теория игр – научно-обоснованные методы, разработанные теорией конфликтных ситуаций. Математ.модель конфликт.ситуации наз-ся игрой, стороны, участвующие в конфликте, - игроками, а исход конфликта – выигрышем. Д/кажд.формализован.игры вводятся правила, т.е. сис-ма условий, опр-щая: 1)варианты действий игроков; 2)объем i-ции кажд.игрока о поведении партнеров; 3)выигрыш, к ктр приводит кажд.совок-ть действий. Как пр-ло, выигрыш можно обозначить 1, проигрыш – 0, ничью – ½. Игра наз-ся парной, если в ней участвуют 2игрока, и множ-венной, если число игроков больше 2х. В них участвуют 2игрока А и В, интересы ктр противоположны, а под игрой поним-ся ряд действий со стороны А и В. Игра наз-ся игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков = проигрышу др., т.е.д/полного задания игры достаточно указать величину одного из них. Выбор и осущ-е одного из предусмотренных правилами действий наз-ся ходом игрока. Ходы могут быть личными и случайными. Личный ход – сознательный выбор игроком одного из возможных действий. Случ.ход – случайно выбранное действие. Стратегией игрока наз-ся совок-ть правил, опр-щих выбор его действия при кажд.личном ходе в завис-ти от сложившейся ситуации. Обычно в процессе игры при кажд.личном ходе игрок делает выбор в завис-ти от конкрет.ситуации. Однако в принципе возможно, что все решения приняты игроком заранее. Это означает, что игрок выбрал опр.стратегию, ктр может быть задана в виде списка правил или пр-мы. Игра наз-ся конечной, если у кажд.игрока имеется конечное число стратегий, и бесконечной – в против.случае. Д/того чтобы решить игру, или найти решение игры, следует д/кажд.игрока выбрать стратегию, ктр удовлетворяет условию оптимальности, т.е. один из игроков должен получать мах выигрыш, когда II придерж-ся своей стратегии. В то же время II игрок должен иметь min проигрыш, если I придерж-ся своей стратегии. Такие стратегии наз-ся оптимальными. Они должны удовлетворять условию устойчивости , т.е. любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре. Если игра повтор-ся достаточно много раз, то игроков может интересовать не выигрыш и проигрыш в кажд.конкрет.партии, а сред.выигрыш (проигрыш) во всех партиях. Целью теории игр явл-ся опр-е оптим.стратегии д/кажд.игрока. При выборе оптим.стратегии естественно предполагать, что оба игрока ведут себя разумно с т.зрения своих интересов. Важнейшее огранич-е теории игр – единствен-ть выигрыша как показ-ля эф-ти, в то время как в больш-ве реальных экономич.задач имеется более одного показ-ля эф-ти.
29. Антагонистические матричные игры: чистые и смешанные стратегии. Методы решения конечных игр: сведение игры mxn к задаче линейного программирования.
Игра наз-ся антагонистической (противоположной) или игрой с нулевой суммой, если выигрыш одного из игроков = проигрышу др., т.е. д/полного задания игры достаточно указать величину одного из них. А1, А2,…, Аm – стратегии игрока А. В1, В2,.., Вn – стратегии игрока В. Размер-ть игры mxn. Платежной матрицей (матрицей игры) наз-ся матрица Р=(aij), где i=1,2,…,m и j=1,2,…,n. Строки в этой таблице соотв-ют стратегиям игрока А, столбца – игрока В. =maxI – нижн.цена игры (max выигрыш), максимин, потому что =max min aij. Стратегия, соотв-щая максимину, наз-ся максиминной стратегии. j=max aij – стратегия игрока В. =min j – верх.цена игры. =min max ij – min выигрыш. - гарантирован.проигрыш игрока В. Если нижн.и верх.цены игры не =, то Седловой точки нет. Значит, оптимал.реш-е можно получить случ.образом, чередуя чистые стратегии. Смешан.стратегией Sа игрока А наз-ся прим-е чистых стратегий А1, А2, …, Аm с вер-тями р1, р2, …, рm (Sa=(p1, p2,…, pm). Тогда смешан.стратегия игрока В обознач-ся Sв=(q1, q2,…, qn). Оптим.реш-е игры – пара опт.стратегий Sa*, Sв*, в общ.случае, смешан. и обладающих св-вом: если один из игроков придерж-ся своей опт.стратегии, то др.не может быть выгодно отступать от своей. Выигрыш (цена игры) (), где - нижн.граница, - верх.граница. Т.Неймана: кажд.конечная игра имеет, по кр.мере, одно опт.реш-е возможно среди смешан.стратегий (Sa*=(p1*, p2*, …, pm*)). Т.об актив.стратегиях: если один из игроков придерж-ся своей опт.смешан.стратегии, то выигрыш остается неизменным и = цене игры, если II игрок не выходит за пределы своих актив.стратегий. Актив. считается стратегия, если она входит в опт.смешан.стратегию с отличной от 0 вер-тью. Приведение mxn к ЗЛП. Пусть игра mxn задана платежной матрицей Р=(аij), где i=1, …, m, j=1,…,n. Игрок А обладает стратегиями А1, …, Аm, игрок В В1, …, Вn. При этом необх-мо опр-ть опт.стратегию Sa* = (р1*, …, рm), Sв* = (q1, …, qn). Д/опт.стратегии Sa* все сред.выигрыши не меньше цены игры, поэтому получаем сис-му нерав-в:
а11р1+а21р2+…+аm1pm …………….
a1np1+a2np2+…+amnpm
Разделим кажд.нерав-во на , при этом введем нов.пер-ные: х1=р1/; х2=р2/; хm=pm/. Аналогично д/игрока В д/опт.стратегии Sв* составим сис-му нерав-в: (как и предыдущая, только вместо р ставим q). Также делим на и вводим нов.пер-ные. При этом пер-ные хi удовлетворяют усл-ю х1+х2+…+хm=1/ и пер-ные у1+у2+…+уn=1/. Формулируем задачу: необх-мо опр-ть знач-я пер-ных хi0 т.о., чтобы они удовлетворяли сис-ме огранич-й, и при этом лин.f-я Z=x1+x2+…+xm→min. В рез-те пришли к задаче ЛП.
30. Назначение и области применения сетевого планирования и управления. Сетевая модель и её основные элементы. Порядок и правила построения сетевых графиков.
Сис-ма методов СПУ – сис-ма методов планиров-я и упр-я разработкой крупных н/хоз-ных комплексов, научными исследов-ями, нов.видов изделий, строительством и реконструкцией, капитал.ремонтом осн.фондов путем прим-я сет.графиков. Первые сис-мы, использ-щие сет.графики, были применены в США в конце 50-х и получили назв-е СРМ (метод критич.пути), ктр впервые была применена при упр-и строительными работами, и PERT (метод оценки и обзора пр-мы) – при разработке систем «Поларис». Сис-ма СПУ позволяет: 1)формировать календарный план реализации некоторого комплекса работ; 2)выявлять и мобилизовывать резервы времени, трудовые, мат. и денеж.ресурсы; 3)осущ-ть упр-е комплексом работ по принципу «ведущего звена» с прогнозиров-ем и предупрежд-ем возможных срывов в ходе работ; 4)повышать эф-ть упр-я в целом при четком распред-и ответ-ти между рук-лями разных уровней и исполнителями работ. Сет.модель – план выполнения некоторого комплекса взаимосвязан.работ, заданного в специфич.форме сети, графич.изображ-е ктр наз-ся сет.графиком. Глав.эл-тами сет.модели явл-ся события и работы. Работа использ-ся в СПУ в широком смысле: 1)действительная работа – протяженный во времени процесс, требующий затрат ресурсов #сборка изделия. 2)ожидание – протяженный во времени процесс, не требующий затрат труда #процесс сушки после покраски. 3)завис-ть (фиктивная работа) – логич.связь между 2мя или неск-кими работами не требующими затрат труда, мат.ресурсов или времени. Она указывает, что возмож-ть одной работы непоср-венно зависит от рез-тов другой. Событие – момент завершения какого-либо процесса, отражающий отдел.этап выполнения проекта. Соб-е может явл-ся частным рез-том отд.работы или суммарным рез-том неск-ких работ. Соб-е может свершиться только тогда, когда закончатся все работы, ему предшествующие. Последующие работы могут начаться только тогда, когда соб-е свершится. Отсюда двойствен.хар-р соб-я: д/всех непоср-венно предшествующих ему работ оно явл-ся конечным, а д/всех следующих за ним – начальным. Среди соб-й сет.модели выделяют исходное и завершающее соб-я. Исх.соб-е не имеет предшествующих работ и соб-й, заверш.соб-е не имеет последующих работ и соб-й. Сет.графики составл-ся на начал.этапе планиров-я. Вначале планируемый процесс разбив-ся на отд.работы, составл-ся перечень работ и соб-й, продумыв-ся их логич.связи и послед-ть выполн-я, оценив-ся длит-ть кажд.работы. Затем составл-ся сет.график. После рассчитыв-ся пар-ры соб-й и работ, опр-ся резервы времени и критич.путь. При построении сет.графика необх-мо соблюдать ряд правил: 1)в сет.модели не должно быть «тупиковых» соб-й, т.е. соб-й, из ктр не выходит ни одна работы, за исключ-ем завершающего соб-я. 2)в сет.графике не должно быть «хвостовых» соб-й (кроме исходного), ктр не предшествует хотя бы одна работа. 3)в сети не должно быть замкнутых контуров и петель, т.е. путей, соед-щих некоторые соб-я с ними же самими. 4)любые 2соб-я должны быть непоср-венно связаны не более чем одной работой-стрелкой. 5)в сети рекоменд-ся иметь одно исходное и одно заверш.соб-е.
6 в нем используется дважды. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) – нет.
25. Задача о коммивояжере.
Задача о коммивояжере явл-ся одной из самых знаменитых задач теории комбинаторики (раздел мат-ки, посвящённый реш-ю задач выбора и располож-я эл-тов некоторого, обычно конечного множ-ва в соотв-и с задан.правилами). Она была поставлена в 1934 году. Задача о К. выглядит след.образом: имеется N городов, ктр должен обойти К. с min затратами. При этом на его маршрут накладыв-ся 2 огранич-я: 1)маршрут должен быть замкнутым, т.е. К. должен вернуться в тот город, из ктр он начал движение; 2)в каждом из городов К. должен побывать точно 1 раз. Сейчас реш-е дан.задачи прим-ся во многих обл-тях, имеющих дело с замкнутыми и при этом жестко связанным по времени сис-ми, такими как: конвейерное произв-во, многооперацион.обрабатывающие комплексы, судовые и ж/д погрузоч.сис-мы, перевозки грузов по замкнутому маршруту, расчет авиационных линий. Критерий:
Огранич-я: , i = 1..N (2). , j = 1..N (3). Ui - Uj + N × Xi j £ N-1, i, j = 1...N, i ¹ j. (4) Усл-е (2) означает, что К. из кажд.города выезжает только 1раз; (3) - въезжает в кажд.город только 1раз; (4) – обеспеч-ет замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутрен.петель. Методы решения задач: 1)метод локал.оптимизации – просматрив-ся только соседние вершины графа (города) найден.пути. Шаг 1. Получить приближен.реш-е (I оценку). Шаг 2. Пока происходит улучш-е реш-я, выполнять след.шаг, иначе перейти на шаг 4. Шаг 3. Д/всех пар № городов i,j, удовлетворяющих нерав-ву , проверить: д/смежных городов, т.е. д/смежн.городов. Если одно из нерав-в выполн-ся, то найдено лучшее реш-е. Следует откорректир-ть ранее найден.реш-е и вернуться на шаг 2. Шаг 4. Закончить работу алг-ма. 2)Алгоритм Эйлера - работоспособен в том случае, если выполн-ся нерав-во треугольника. Его суть в том, что д/любой тройки городов i, j, k(между ктр есть связь)выполн-ся нерав-во. Шаг 1. Построение каркаса min веса (алг-мы Прима или Краскала). Шаг 2. Путем дублирования кажд.ребра каркас преобраз-ся в эйлеров граф. Шаг 3. Нахожд-е в построен.графе эйлерова цикла. Шаг 4. Преобразов-е эйлерова цикла в гамильтонов цикл (или маршрут К.). Метод преобразов-я: послед-ть вершин эйлерова цикла сокращ-ся так, чтобы кажд.вершина графа в получившимся цикле встречались ровно 1раз. Шаг 5. Закончить работу алг-ма. Получено приближен.реш-е задачи К. 3)Алгоритм Кристофидеса. Шаг 1. Строится каркас min веса. Шаг 2. На мн-ве вершин каркаса, имеющих нечетное число ребер каркаса, нах-ся паросочетание min веса. Таких вершин в любом каркасе четное число. Метод поиска паросоч-я – чередующиеся цепочки. Шаг 3. Каркас преобраз-ся в Эйлеров граф путем присоедин-я ребер, соотв-щих найден.паросоч-ю. Шаг 4. В построен.графе нах-ся Эйлеров маршрут. Шаг 5. Эйлеров маршрут преобраз-ся в маршрут К.
26. Понятие системы массового обслуживания, классификация систем массового обслуживания. Простейшие системы массового обслуживания и их параметры.
При исследовании операций часто приход-ся сталкив-ся с сис-мами, предназнач-ными д/многоразового использ-я при решении однотипных задач. Возникающие при этом процессы получили назв-е процессов обслуживания, а сис-мы – систем масс.обслужив-я (СМО). #телефон.сис-мы, билетные кассы, магазины. Кажд.СМО состоит из опр.числа обслужив-щих ед-ц, ктр наз-ся каналами обслужив-я. Ими могут быть линии связи, рабочие точки, продавцы… По числу каналов СМО подразделяют на одноканальные и многоканальные. Заявки поступают в СМО обычно не регулярно, а случайно, образуя так называемый случ.поток заявок (требований). Предметом теории масс.обслужив-я явл-ся построение мат.моделей, связывающий задан.условия работы СМО с показ-лями эф-ти СМО, описывающими ее способ-ть справляться с потоком заявок. В кач-ве показ-лей эф-ти СМО использ-ся: сред.число заявок, обслуживаемых в ед-цу времени; сред.число заявок в очереди… СМО делят на 2типа: СМО с отказами и СМО с ожиданием (очередью). В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслужив-я не участвует (#заявка на телеф.разговор в момент, когда все каналы заняты, получает отказ и покидает СМО необслуженной). В СМО с ожиданием заявка, пришедшая в момент, когда все канала заняты, не уходит, а становится в очередь на обслужив-е. СМО с ожиданием подразд-ся на разные виды в завис-ти от того, как организована очередь: с огранич.или неогранич.длиной очереди, с огранич.временем ожидания… Д/класс-ции СМО важное знач-е имеет дисциплина обслужив-я, опр-щая порядок выбора заявок из числа поступивших и порядок распред-я их между свобод.каналами. По этому признаку обслужив-е заявки может быть организовано по принципу «первая пришла – первая обслужена», «послед.пришла – первая обслужена» (такой порядок может прим-ся, #при извлечении д/обслужив-я изделий со склада, ибо последние из них оказыв-ся часто более доступными) или обслужив-е с приоритетом (когда в I очередь обслужив-ся наиболее важные заявки). Приоритет может быть абсолютным (когда более важная заявка «вытесняет» из-под обслужив-я обычную заявку) и относительным (когда более важная заявка получает лишь «лучшее» место в очереди).
27. Осн-е по-я теории марковских процессов: случайный процесс, марковский процесс, граф состояний, поток событий, вероятность состояния, уравнения Колмогорова, финальные вероятности состояний.
При исследов-и операций часто приход-ся сталкив-ся с сис-ми, предназначенными д/многоразового использ-я при реш-и однотипных задач. Возникающие при этом процессы наз-ся процессами обслужив-я, а сис-мы – сис-мы масс.обслуж-я (СМО). Процесс работы СМО предст-ет собой случ.процесс. Случ.процесс – процесс изменения во времени сост-я к.-либо сис-мы в соотв-и с вер-тными закономер-тями. Процесс наз-ся процессом с дискрет.сост-ями, если его возможные сост-я s1, s2, s3 можно заранее перечислить, а переход сис-мы из сост-я в сост-е происходит скачком. Процесс наз-ся процессом с непрерыв.временем, если моменты возможных переходов сис-мы из сост-я в сост-е не фиксированы заранее, а случайны. Мат.анализ работы СМО сущ-но упрощ-ся, если процесс этой работы – Марковский. Случ.процесс наз-ся Марковским (случ.процессом без последствия), если д/любого момента времени вер-тные хар-ки процесса в будущем зависят только от его сост-я в дан.момент и не зависят от того, когда и как сис-ма пришла в это сост-е (# счетчик в такси). При анализе случ.процессов с дискрет.сост-ями удобно польз-ся геометрич.схемой – графом сост-й. Обычно сост-я сис-мы изображ-ся прямоуг-ками (кружками), а возмож.переходы из сост-я в сост-е – стрелками (ориентирован.дугами), соед-щими сост-я. Поток соб-й – послед-ть однород.соб-й, следующих одно за др. в какие-то случ.моменты времени (#поток вызовов на телефон.станции, поток покупателей). Регуляр.поток соб-й, если соб-я следуют одно за др. через опр.равные промежутки времени (поток изделий на конвейере сборочного цеха). Стац.поток соб-й, если его вер-тные хар-ки не зависят от времени (поток автомобилей в течение суток в часы пик). Поток без последействия, если д/любых 2х непересек-щихся участков времени, попадающих на один из них, не зависит от числа соб-й, попадающих на др. (поток пассажиров в метро). Ординар.поток, если вер-ть попадания на малый участок времени 2х и более соб-й пренебрежимо мала по сравнению с вер-тью попадания одного соб-я (т.е.поток соб-й ординарен, если соб-я появл-ся в нем поодиночке, а не группами). Простейший (стац.пуассоновский), если он одновр-но стационарен, ординарен и не имеет последействия. Закон Пуассона:
. Вер-ть того, что за время не произойдет ни одного соб-я (m=0), = . Вер-ть того, что на участке времени длиной t не появится ни одного из последующих соб-й = , а вер-ть противополож.соб-я, т.е. f-я распред-я случ.величины Т, = . Рассмотрим #. Устр-во S состоит из 2х узлов, каждый из ктр в случ.момент времени может выйти из строя, после чего мгновенно начин-ся ремонт узла, продолж-щийся заранее неизв.случ.время. Возможны 4исхода: S0 – оба узла исправны, S1 – Iузел ремонтир-ся, II-исправен, S2 – Iiузел ремонтир-ся, I-исправен, S3 – оба ремонтир-ся. Если начертить граф, то он наз-ся размеченным, т.е. у стрелок проставлены интенсив-ти. Д/этого составл-ся и решаются ур-я Колмогорова – особого вида диф.ур-я, в ктр неизв.f-ями явл-ся вер-ти сост-й. Пр-ло составл-я ур-й Колмогорова: В лев.части каждого из них стоит производная вер-ти i-го сост-я. В прав.части – сумма произведений вер-тей всех сост-й (из ктр идут стрелки в дан.сост-е) на интенсив-ти соотв-щих потоков соб-й – Сум.интенсив-ть всех потоков, выводящих сис-му из дан.сост-я, * на вер-ть дан. (i-го сост-я). Особен-ть решения диф.ур-й состоит в том, что требуется задать так называемые нач.условия. Эту сис-му можно составить по размеч.графу сост-й по след.правилу: слева в ур-ях стоит предельная вер-ть дан.сост-я pi, * на Сум.интенсив-ть всех потоков, ведущих из дан.сост-я, а справа – сумма произведений интенсив-тей всех потоков, входящих в i-е сост-е, на вер-ти тех сост-й, из ктр эти потоки исходят. А что будет происходить с вер-тями сост-й при t→? Если эти пределы сущ-ют и не зависят от нач.сост-я сис-мы, то они наз-ся финал.вер-тями сост-й. Если число n сост-й сис-мы конечно и из кажд.из них можно перейти в любое др., то фин.вер-ти сущ-ют.
28. Предмет и задачи теории игр. Основные понятия теории игр: игра, игроки, партия, выигрыш, проигрыш, ход, личные и случайные ходы, стратегические игры, стратегия, оптимальная стратегия.
Теория игр – научно-обоснованные методы, разработанные теорией конфликтных ситуаций. Математ.модель конфликт.ситуации наз-ся игрой, стороны, участвующие в конфликте, - игроками, а исход конфликта – выигрышем. Д/кажд.формализован.игры вводятся правила, т.е. сис-ма условий, опр-щая: 1)варианты действий игроков; 2)объем i-ции кажд.игрока о поведении партнеров; 3)выигрыш, к ктр приводит кажд.совок-ть действий. Как пр-ло, выигрыш можно обозначить 1, проигрыш – 0, ничью – ½. Игра наз-ся парной, если в ней участвуют 2игрока, и множ-венной, если число игроков больше 2х. В них участвуют 2игрока А и В, интересы ктр противоположны, а под игрой поним-ся ряд действий со стороны А и В. Игра наз-ся игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков = проигрышу др., т.е.д/полного задания игры достаточно указать величину одного из них. Выбор и осущ-е одного из предусмотренных правилами действий наз-ся ходом игрока. Ходы могут быть личными и случайными. Личный ход – сознательный выбор игроком одного из возможных действий. Случ.ход – случайно выбранное действие. Стратегией игрока наз-ся совок-ть правил, опр-щих выбор его действия при кажд.личном ходе в завис-ти от сложившейся ситуации. Обычно в процессе игры при кажд.личном ходе игрок делает выбор в завис-ти от конкрет.ситуации. Однако в принципе возможно, что все решения приняты игроком заранее. Это означает, что игрок выбрал опр.стратегию, ктр может быть задана в виде списка правил или пр-мы. Игра наз-ся конечной, если у кажд.игрока имеется конечное число стратегий, и бесконечной – в против.случае. Д/того чтобы решить игру, или найти решение игры, следует д/кажд.игрока выбрать стратегию, ктр удовлетворяет условию оптимальности, т.е. один из игроков должен получать мах выигрыш, когда II придерж-ся своей стратегии. В то же время II игрок должен иметь min проигрыш, если I придерж-ся своей стратегии. Такие стратегии наз-ся оптимальными. Они должны удовлетворять условию устойчивости , т.е. любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре. Если игра повтор-ся достаточно много раз, то игроков может интересовать не выигрыш и проигрыш в кажд.конкрет.партии, а сред.выигрыш (проигрыш) во всех партиях. Целью теории игр явл-ся опр-е оптим.стратегии д/кажд.игрока. При выборе оптим.стратегии естественно предполагать, что оба игрока ведут себя разумно с т.зрения своих интересов. Важнейшее огранич-е теории игр – единствен-ть выигрыша как показ-ля эф-ти, в то время как в больш-ве реальных экономич.задач имеется более одного показ-ля эф-ти.
29. Антагонистические матричные игры: чистые и смешанные стратегии. Методы решения конечных игр: сведение игры mxn к задаче линейного программирования.
Игра наз-ся антагонистической (противоположной) или игрой с нулевой суммой, если выигрыш одного из игроков = проигрышу др., т.е. д/полного задания игры достаточно указать величину одного из них. А1, А2,…, Аm – стратегии игрока А. В1, В2,.., Вn – стратегии игрока В. Размер-ть игры mxn. Платежной матрицей (матрицей игры) наз-ся матрица Р=(aij), где i=1,2,…,m и j=1,2,…,n. Строки в этой таблице соотв-ют стратегиям игрока А, столбца – игрока В. =maxI – нижн.цена игры (max выигрыш), максимин, потому что =max min aij. Стратегия, соотв-щая максимину, наз-ся максиминной стратегии. j=max aij – стратегия игрока В. =min j – верх.цена игры. =min max ij – min выигрыш. - гарантирован.проигрыш игрока В. Если нижн.и верх.цены игры не =, то Седловой точки нет. Значит, оптимал.реш-е можно получить случ.образом, чередуя чистые стратегии. Смешан.стратегией Sа игрока А наз-ся прим-е чистых стратегий А1, А2, …, Аm с вер-тями р1, р2, …, рm (Sa=(p1, p2,…, pm). Тогда смешан.стратегия игрока В обознач-ся Sв=(q1, q2,…, qn). Оптим.реш-е игры – пара опт.стратегий Sa*, Sв*, в общ.случае, смешан. и обладающих св-вом: если один из игроков придерж-ся своей опт.стратегии, то др.не может быть выгодно отступать от своей. Выигрыш (цена игры) (), где - нижн.граница, - верх.граница. Т.Неймана: кажд.конечная игра имеет, по кр.мере, одно опт.реш-е возможно среди смешан.стратегий (Sa*=(p1*, p2*, …, pm*)). Т.об актив.стратегиях: если один из игроков придерж-ся своей опт.смешан.стратегии, то выигрыш остается неизменным и = цене игры, если II игрок не выходит за пределы своих актив.стратегий. Актив. считается стратегия, если она входит в опт.смешан.стратегию с отличной от 0 вер-тью. Приведение mxn к ЗЛП. Пусть игра mxn задана платежной матрицей Р=(аij), где i=1, …, m, j=1,…,n. Игрок А обладает стратегиями А1, …, Аm, игрок В В1, …, Вn. При этом необх-мо опр-ть опт.стратегию Sa* = (р1*, …, рm), Sв* = (q1, …, qn). Д/опт.стратегии Sa* все сред.выигрыши не меньше цены игры, поэтому получаем сис-му нерав-в:
а11р1+а21р2+…+аm1pm …………….
a1np1+a2np2+…+amnpm
Разделим кажд.нерав-во на , при этом введем нов.пер-ные: х1=р1/; х2=р2/; хm=pm/. Аналогично д/игрока В д/опт.стратегии Sв* составим сис-му нерав-в: (как и предыдущая, только вместо р ставим q). Также делим на и вводим нов.пер-ные. При этом пер-ные хi удовлетворяют усл-ю х1+х2+…+хm=1/ и пер-ные у1+у2+…+уn=1/. Формулируем задачу: необх-мо опр-ть знач-я пер-ных хi0 т.о., чтобы они удовлетворяли сис-ме огранич-й, и при этом лин.f-я Z=x1+x2+…+xm→min. В рез-те пришли к задаче ЛП.
30. Назначение и области применения сетевого планирования и управления. Сетевая модель и её основные элементы. Порядок и правила построения сетевых графиков.
Сис-ма методов СПУ – сис-ма методов планиров-я и упр-я разработкой крупных н/хоз-ных комплексов, научными исследов-ями, нов.видов изделий, строительством и реконструкцией, капитал.ремонтом осн.фондов путем прим-я сет.графиков. Первые сис-мы, использ-щие сет.графики, были применены в США в конце 50-х и получили назв-е СРМ (метод критич.пути), ктр впервые была применена при упр-и строительными работами, и PERT (метод оценки и обзора пр-мы) – при разработке систем «Поларис». Сис-ма СПУ позволяет: 1)формировать календарный план реализации некоторого комплекса работ; 2)выявлять и мобилизовывать резервы времени, трудовые, мат. и денеж.ресурсы; 3)осущ-ть упр-е комплексом работ по принципу «ведущего звена» с прогнозиров-ем и предупрежд-ем возможных срывов в ходе работ; 4)повышать эф-ть упр-я в целом при четком распред-и ответ-ти между рук-лями разных уровней и исполнителями работ. Сет.модель – план выполнения некоторого комплекса взаимосвязан.работ, заданного в специфич.форме сети, графич.изображ-е ктр наз-ся сет.графиком. Глав.эл-тами сет.модели явл-ся события и работы. Работа использ-ся в СПУ в широком смысле: 1)действительная работа – протяженный во времени процесс, требующий затрат ресурсов #сборка изделия. 2)ожидание – протяженный во времени процесс, не требующий затрат труда #процесс сушки после покраски. 3)завис-ть (фиктивная работа) – логич.связь между 2мя или неск-кими работами не требующими затрат труда, мат.ресурсов или времени. Она указывает, что возмож-ть одной работы непоср-венно зависит от рез-тов другой. Событие – момент завершения какого-либо процесса, отражающий отдел.этап выполнения проекта. Соб-е может явл-ся частным рез-том отд.работы или суммарным рез-том неск-ких работ. Соб-е может свершиться только тогда, когда закончатся все работы, ему предшествующие. Последующие работы могут начаться только тогда, когда соб-е свершится. Отсюда двойствен.хар-р соб-я: д/всех непоср-венно предшествующих ему работ оно явл-ся конечным, а д/всех следующих за ним – начальным. Среди соб-й сет.модели выделяют исходное и завершающее соб-я. Исх.соб-е не имеет предшествующих работ и соб-й, заверш.соб-е не имеет последующих работ и соб-й. Сет.графики составл-ся на начал.этапе планиров-я. Вначале планируемый процесс разбив-ся на отд.работы, составл-ся перечень работ и соб-й, продумыв-ся их логич.связи и послед-ть выполн-я, оценив-ся длит-ть кажд.работы. Затем составл-ся сет.график. После рассчитыв-ся пар-ры соб-й и работ, опр-ся резервы времени и критич.путь. При построении сет.графика необх-мо соблюдать ряд правил: 1)в сет.модели не должно быть «тупиковых» соб-й, т.е. соб-й, из ктр не выходит ни одна работы, за исключ-ем завершающего соб-я. 2)в сет.графике не должно быть «хвостовых» соб-й (кроме исходного), ктр не предшествует хотя бы одна работа. 3)в сети не должно быть замкнутых контуров и петель, т.е. путей, соед-щих некоторые соб-я с ними же самими. 4)любые 2соб-я должны быть непоср-венно связаны не более чем одной работой-стрелкой. 5)в сети рекоменд-ся иметь одно исходное и одно заверш.соб-е.