Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Прикладная математика. Задача коммивояжера. Системы массового обслуживания

Покупка
Основная коллекция
Артикул: 656938.01.99
Учебное пособие включает в себя краткое изложение таких разделов прикладной математики, как задача коммивояжера, потоки требований и элементы систем массового обслуживания. По каждой теме предложены задания различного уровня сложности для самостоятельного решения, приведены примеры с их подробным решением. Учебное пособие предназначено для бакалавров и магистров направлений «Технология транспортных процессов» и «Эксплуатация транспортно- технологических машин и комплексов».
Веневитина, С. С. Прикладная математика. Задача коммивояжера. Системы массового обслуживания: Учебное пособие / Веневитина С.С., Зенина В.В., Сапронов И.В. - Воронеж:ВГЛТУ им. Г.Ф. Морозова, 2014. - 47 с. - Текст : электронный. - URL: https://znanium.com/catalog/product/858465 (дата обращения: 28.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Министерство образования и науки Российской федерации 
Федеральное государственное бюджетное образовательное учреждение 
высшего профессионального образования  
«Воронежская государственная лесотехническая академия» 
 
 
 
 
 
 
 
 
 
ПРИКЛАДНАЯ МАТЕМАТИКА 

 
 
ЗАДАЧА КОММИВОЯЖЕРА 
СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
Воронеж  2014 

УДК 519.1+519.8 
М 34 
 
Одобрено решением учебно-методического совета ФГБОУ ВПО 
«ВГЛТА» (протокол № 5 от 31 января 2014 г.) 
 
 
 
М34 Прикладная математика. Задача коммивояжера. Системы массового 
обслуживания [Электронный ресурс] : учебное пособие / С.С. Веневитина, В. В. 
Зенина, И. В. Сапронов ; М-во образования и науки РФ, ФГБОУ ВПО 
«ВГЛТА». - Воронеж, 2014. – 47 с. 
 
 
 
     Учебное пособие включает в себя краткое изложение таких разделов 
прикладной математики, как задача коммивояжера, потоки требований и 
элементы систем массового обслуживания. По каждой теме предложены 
задания различного уровня сложности для самостоятельного решения, 
приведены примеры с их подробным решением. 
       Учебное пособие предназначено для бакалавров и магистров направлений 
«Технология 
транспортных 
процессов» 
и 
«Эксплуатация 
транспортнотехнологических машин и комплексов». 
УДК 519.1+519.8 
 
 
 
                             © Веневитина С. С., Зенина В. В.,  
                 Сапронов И. В., 2014  
                                                      © ФГБОУ ВПО «Воронежская государственная   
лесотехническая академия», 2014 
 
 
 

Оглавление 

1. Задача коммивояжера…………………………………………………...………..4 

1.1. Общее описание……………………………………………………...………....5 

1.2. Метод ветвей и границ……………………………………………..…………..7 

1.3. Практическое применение задачи коммивояжера…………………………..12 

1.4. Индивидуальные задания…………………………………………………......15 

2. Потоки требований………………………………………………………………16 

2.1. Простейшие потоки……………………………………………………………17 

2.2. Простейший поток с возможной нестационарностью……………………....18 

2.3. Простейший поток с возможной неординарностью………………………...18 

2.4. Простейшие потоки с возможным последействием………………………...19 

2.5. Потоки Пальма………………………………………………………………...19 

2.6. Потоки Эрланга………………………………………………………………..20 

2.7. Суммирование и разъединение простейших потоков………………………20 

2.8. Показательный закон распределения времени обслуживания……………..21 

Задание №1…………...…………………………………………………………….21 

3. Элементы теории систем массового обслуживания…………………………..25 

3.1. Классификация СМО………………………………………………………….25 

3.2. Уравнение Колмогорова для вероятностей состояний……………………..26 

3.3. СМО с отказами……………………………………………………………….28 

3.4. СМО с ограниченной длиной очереди…………………………………….....29 

3.5. СМО с ожиданием……………………………………………………………..31 

3.6. СМО с ограниченным временем ожидания………………………………….33 

3.7. Замкнутые СМО……………………………………………………………….35 

Задание № 2…………..……………………………………………………………..37 

Задание № 3……..…………………………………………………………………..43 

Задание № 4………………………………………………………………………....44 

Библиографический список……………………………………………………..…47 

 

1. ЗАДАЧА КОММИВОЯЖЕРА 
 
 
Комбинаторика – раздел математики, посвящённый решению задач 
выбора и расположения элементов некоторого, обычно конечного множества в 
соответствии с заданными правилами. 
 
Каждое такое правило определяет способ построения некоторой 
конструкции из элементов исходного множества, называемой комбинаторной 
конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа 
является изучение комбинаторных конфигураций. Это изучение включает в 
себя вопросы существования комбинаторных конфигураций, алгоритмы их 
построения, оптимизацию таких алгоритмов, а также решение задач 
перечисления, в частности определение числа конфигураций данного класса. 
Простейшим примером комбинаторных конфигураций являются перестановки, 
сочетания и размещения. 
 
Большой вклад в систематическое развитие комбинаторных методов был 
сделан Г. Лейбницем (диссертация «Комбинаторное искусство»), Я. Бернулли 
(работа «Искусство предположений»), Л. Эйлером. Можно считать, что с 
появлением работ Я. Бернулли и  Г. Лейбница комбинаторные методы 
выделились в самостоятельную часть математики. В работах Л.Эйлера по 
разбиениям и композициям натуральных чисел на слагаемые было положено 
начало  одному из основных методов перечисления комбинаторных 
конфигураций – методу производящих функций.    
 
Возвращение интереса к комбинаторному анализу относится к 50-м годам 
ХХ в. в связи с бурным развитием кибернетики и дискретной математики и 
широким использованием электронно-вычислительной техники. В этот период 
активизировался интерес к классическим комбинаторным задачам. 
 
Классические комбинаторные задачи – это задачи 
выбора и расположения элементов конечного множества, 
имеющие в качестве исходной некоторую формулировку 
развлекательного содержания типа головоломок. 
 
В 1859 г. У. Гамильтон придумал игру «Кругосветное 
путешествие», 
состоящую 
в 
отыскании 
такого 
пути, 
проходящего через все вершины (города, пункты назначения) графа, 
изображенного на рис. 1, чтобы посетить каждую вершину однократно и 

возвратиться в исходную. Пути, обладающие таким свойством, называются 
гамильтоновыми циклами. 
 
Задача о гамильтоновых циклах в графе получила различные обобщения. 
Одно из этих обобщений – задача коммивояжера, имеющая ряд применений в 
исследовании операций, в частности при решении некоторых транспортных 
проблем. 
 
 
1.1. Общее описание 
 
Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из 
знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и 
об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. 
В своей области (оптимизации дискретных задач) ЗК служит своеобразным 
полигоном, на котором испытываются всё новые методы. 
Постановка задачи следующая. 
Коммивояжер (бродячий торговец) должен выйти из первого города, 
посетить по разу в неизвестном порядке города 2,1,3,…,n и вернуться в первый 
город. Расстояния между городами известны. В каком порядке следует 
обходить города, чтобы замкнутый путь (тур) коммивояжера был 
кратчайшим? 
Чтобы привести задачу к научному виду, введём некоторые термины. Итак, 

города перенумерованы числами j∈Т=(1,2,3,…,n). Тур коммивояжера может 
быть описан циклической перестановкой t=(j1,j2,…,jn,j1), причём все j1,…,jn – 
разные номера; повторяющийся в начале и в конце j1, показывает, что 
перестановка зациклена. Расстояния между парами вершин  Сij образуют 
матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы 
минимизировать функционал 

 
Относительно математизированной формулировки ЗК уместно сделать два 
замечания. 
Во-первых, в постановке Сij означали расстояния, поэтому они должны быть 

неотрицательными, т.е. для всех j∈Т:  

Сij≥0; Cjj=∞ 
(1)

(последнее равенство означает запрет на петли в туре), симметричными, т.е.  
для всех i,j:  
Сij= Сji. 
(2)
и удовлетворять неравенству треугольника, т.е. для всех: 

Сij+ Сjk≥Cik 
(3)

В математической постановке говорится о произвольной матрице. Сделано 
это потому, что имеется много прикладных задач, которые описываются 
основной моделью, но всем условиям (1)-(3) не удовлетворяют. Особенно часто 
нарушается условие (2) (например, если Сij – не расстояние, а плата за проезд: 
часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем 
различать два варианта ЗК: симметричную задачу, когда условие (2) 
выполнено, и несимметричную - в противном случае. Условия (1)-(3) по 
умолчанию мы будем считать выполненными. 
Второе замечание касается числа всех возможных туров. В несимметричной 
ЗК все туры t=(j1,j2,…,jn,j1) и t’=(j1,jn,…,j2,j1) имеют разную длину и должны 
учитываться оба. Разных туров очевидно (n-1)!. 
Зафиксируем на первом и последнем месте в циклической перестановке 
номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными 
способами. В результате получим все несимметричные туры. Симметричных 
туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’. 
Можно представить, что С состоит только из единиц и нулей. Тогда С 
можно интерпретировать, как граф, где ребро (i,j)  проведено, если Сij=0 и не 
проведено, если Сij=1. Тогда, если существует тур длины 0, то он пройдёт по 
циклу, который включает все вершины по одному разу. Такой цикл называется 
гамильтоновым 
циклом. 
Незамкнутый 
гамильтонов 
цикл 
называется 
гамильтоновой цепью (гамильтоновым путём). 
В терминах теории графов симметричную ЗК можно сформулировать так: 
Дана полная сеть с n  вершинами, длина ребра (i,j)= Сij. Найти гамильтонов 
цикл минимальной длины. 
В несимметричной ЗК вместо «цикл» надо говорить «контур», а вместо 
«ребра» - «дуги» или «стрелки». 
Некоторые прикладные задачи формулируются как ЗК, но в них нужно 
минимизировать длину не гамильтонова цикла, а гамильтоновой цепи. Такие 

задачи называются незамкнутыми. Некоторые модели сводятся к задаче о 
нескольких коммивояжерах, но мы здесь их рассматривать не будем. 
 
1.2. Метод ветвей и границ 
 
 
К идее метода ветвей и границ приходили многие исследователи, но 
Литтл с соавторами на основе указанного метода разработали удачный 
алгоритм решения ЗК и тем самым способствовали популяризации подхода. С 
тех пор метод ветвей и границ был успешно применен ко многим задачам, для 
решения ЗК было придумано несколько других модификаций метода, но в 
большинстве учебников излагается пионерская работа Литтла. 
 
Общая идея тривиальна: нужно разделить огромное число перебираемых 
вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху 
– в задаче максимизации) для этих классов, чтобы иметь возможность 
отбрасывать варианты не по одному, а целыми классами. Трудность состоит в 
том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), 
чтобы процедура была эффективной. 
         Изложим алгоритм Литтла на примере. 
Пример 1. Дана полная сеть, показанная на рисунке. Найти тур. 

 
 
 
Решение.  
Нам будет удобнее трактовать Сij как стоимость проезда из города i в 
город j. Допустим, что добрый мэр города j издал указ выплачивать каждому 
въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур 
подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но 
поскольку все туры равномерно подешевели, то прежний минимальный тур 

1 
2 
3 
4 5 6 

1
- 
6 
4 
8 7 14

2
6 
- 
7 11 7 10

3
4 
7 
- 
4 3 10

4
8 11
4 
- 
5 11

5
7 
7 
3 
5 
- 
7 

6 14 10 10 11 7 
- 

табл. 1 

будет и теперь стоить меньше всех. Добрый же поступок мэра можно 
представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы 
мэр хотел спровадить коммивояжеров из  j-го города и установил награду за 
выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из 
всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, 
но минимальный тур остался бы минимальным. Итак, доказана следующая 
лемма. 
 
Вычитая любую константу из всех элементов любой строки или столбца 
матрицы С, мы оставляем минимальный тур минимальным. 
 
Для алгоритма нам будет удобно получить побольше нулей в матрице С, 
не получая там, однако, отрицательных чисел. Для этого мы вычтем из каждой 
строки ее минимальный элемент (это называется приведением по строкам, см. 
табл. 2), а затем вычтем из каждого столбца матрицы, приведенной по строкам, 
его минимальный элемент, получив матрицу, приведенную по столбцам, см. 
табл. 3). 
- 1 2 3
4 5 6 
 

1 - 2 0
4 3 10 4

2 0 - 1
5 1 4 6

3 1 4 - 1 0 7 3

4 4 7 0
- 1 7 4

5 4 4 0
2 - 
4 3

6 7 3 3
4 0 
- 
7

табл. 2 

 
 
Прочерки по диагонали означают, что из города i в город i ходить нельзя. 
Заметим, что сумма констант приведения по строкам равна 27, сумма по 
столбцам 7, сумма сумм равна 34. 
 
  Тур можно задать системой из шести подчеркнутых (выделенных 
другим цветом) элементов матрицы С, например, такой, как показано на табл. 1. 
Подчеркивание элемента означает, что в туре из i-го элемента идут именно в jтый. Для тура из шести городов подчеркнутых элементов должно быть шесть, 
так как в туре из шести городов есть шесть ребер. Каждый столбец должен 
содержать ровно один подчеркнутый элемент  (в каждый город коммивояжер 
въехал один раз), в каждой строке должен быть ровно один подчеркнутый 

- 
1 
2 
3 
4 
5 
6 

1
- 
0 
0 
3 
3 
6 

2
0 
- 
1 
4 
1 
0 

3
1 
2 
- 
0 
0 
3 

4
4 
5 
0 
- 
1 
3 

5
4 
2 
0 
1 
- 
0 

6
7 
1 
3 
3 
0 
- 

 
 
2 
 
1 
 
4 

табл. 3 

элемент (из каждого города коммивояжер выехал один раз); кроме того, 
подчеркнутые элементы должны описывать один тур, а не несколько меньших 
циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. На табл. 1 
стоимость 
равна 
36, 
это 
тот 
минимальный 
тур, 
который 
получен 
лексикографическим перебором. 
 
Теперь будем рассуждать от приведенной матрицы на табл. 3. Если в ней 
удастся построить правильную систему подчеркнутых элементов, т.е. систему, 
удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми 
элементами будут только нули, то ясно, что для этой матрицы мы получим 
минимальный тур. Но он же будет минимальным и для исходной матрицы С, 
только для того, чтобы получить правильную стоимость тура, нужно будет 
обратно прибавить все константы приведения, и стоимость тура изменится с 0 
до 34. Таким образом, минимальный тур не может быть меньше 34. Мы 
получили оценку снизу для всех туров. 
 
Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. 
Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена 
перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в 
город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором 
столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать 
из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. 
Суммируя эти два минимума, имеем 1+0=1: если не ехать «по нулю» из города 
1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки 
всех нулей поставлены на табл. 4 правее и выше нуля (оценки нуля, равные 
нулю, не ставились). 
 
Выберем максимальную из этих оценок (в примере есть несколько 
оценок, равных единице, выберем первую из них, в клетке (1,2)). 
 
Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса – 
включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно 
сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или 
больше.  
 
Что касается первого класса, то в нем надо рассмотреть матрицу на табл. 
5 с вычеркнутой первой строкой и вторым столбцом. 
 
 

1 
2 
3 
4 
5 6 

1 - 01 0 
3 
3 6 

2 01 
- 
1 
4 
1 0 

3 1 
2 
- 01 0 3 

4 4 
5 01 
- 
1 3 

5 4 
2 
0 
1 
- 0 

6 7 
1 
3 
3 01 - 

табл. 4 

            
 
 
 
 
 
 
 
 
Дополнительно в уменьшенной матрице поставлен запрет в клетке (2,1), 
т. к. выбрано ребро (1,2) и замыкать преждевременно тур ребром (2,1) нельзя. 
Уменьшенную матрицу можно привести на 1 по первому столбцу, так что 
каждый тур, ей отвечающий, стоит не меньше 35. Результат наших ветвлений и 
получения оценок показан на рис.3. 
Кружки представляют классы: верхний кружок – класс всех 
туров; нижний левый – класс всех туров, включающих ребро 
(1,2); нижний правый – класс всех туров, не включающих ребро 
(1,2). Числа над кружками – оценки снизу. 
 
Продолжим ветвление в положительную сторону: влево - 
вниз. Для этого оценим нули в уменьшенной матрице C[1,2] на 
табл. 6. Максимальная оценка в клетке (3,1) равна 3. Таким 
образом, оценка для правой нижней вершины на рис. 3 есть 
35+3=38. Для оценки левой нижней вершины на рис. 4 нужно 
вычеркнуть из матрицы C[1,2] еще строку 3 и столбец 1, 
получив матрицу C[(1,2),(3,1)] на табл. 7. В эту матрицу нужно 

 
1 
3 
4 
5 6

2 01
1 
4 
1 0

3
1
- 01
0 3

4
4 01
- 
1 3

5
4 
0 
1
- 0

6
7 
3 
3 01

табл. 5 

 
1 
3 
4 
5 6 

2 01 1 
4 
1 0 

3 03 
- 01 0 3 

4 3 01 
- 
1 3 

5 3 
0 
1 
- 0 

6 6 
3 
3 01 - 

табл. 6 

 
3 4
5 6

2
1
4
1 0

4 01
1 3

5
0 1
- 0

6
3 3
01

табл. 7 

поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер 
(1,2) и (3,1), т.е. [3,1,2], и нужно запретить преждевременное замыкание (2,3). 
Эта матрица приводится по столбцу на 1 (табл. 8), таким образом, каждый тур 
соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и 
более. 
 
 
3 
4 
5 
6 
 
 
3 
4 
6 
 
 
3 
4 
 

2 
1 
3 
1 
0 
 
2 
1 
3 
03 
 
4 
0
- 
 

4 
01 
- 
1 
3 
 
4 
03 
- 
3 
 
5 
0 
0 
 

5 
0 
02 
- 
0 
 
5 
0 
03 
0 
 
табл. 10 
 

6 
3 
2 
03 
- 
 
табл. 9 
 
 
 
 
 

табл. 8 
 
 
 
 
 
 
 
 
 
 

 
Оцениваем 
теперь 
нули 
в 
приведенной 
матрице 
C[(1,2),(3,1)] нуль с максимальной оценкой 3 находится в 
клетке (6,5). Отрицательный вариант имеет оценку 
38+3=41. Для получения оценки положительного варианта 
убираем строчку 6 и столбец 5, ставим запрет в клетку 
(5,6), 
см. 
табл. 
9. 
Эта 
матрица 
неприводима. 
Следовательно, оценка положительного варианта не 
увеличивается (рис.5). 
 
Оценивая нули в матрице на табл. 9, получаем 
ветвление по выбору ребра (2,6), отрицательный вариант 
получает оценку 36+3=39, а для получения оценки 
положительного варианта вычеркиваем вторую строку и шестой столбец, 
получая матрицу на табл. 10. 
 
В матрицу надо добавить запрет в клетку (5,3), ибо уже построен 
фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3). 
Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур 
ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. 
Сейчас получен тур: 1→2→6→5→4→3→1 стоимостью в 36. При достижении 
низа по дереву перебора класс туров сузился до одного тура, а оценка снизу 
превратилась в точную стоимость.