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-го сост-я). Особен-ть решения диф.ур-й состоит в том, что требуется задать так называемые нач.условия. Эту сис-му можно составить по размеч.графу сост-й по след.правилу: слева в ур-ях стоит предельная вер-ть дан.сост-я p_i, * на Сум.интенсив-ть всех потоков, ведущих из дан.сост-я, а справа – сумма произведений интенсив-тей всех потоков, входящих в i-е сост-е, на вер-ти тех сост-й, из ктр эти потоки исходят. А что будет происходить с вер-тями сост-й при t→? Если эти пределы сущ-ют и не зависят от нач.сост-я сис-мы, то они наз-ся финал.вер-тями сост-й. Если число n сост-й сис-мы конечно и из кажд.из них можно перейти в любое др., то фин.вер-ти сущ-ют.