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

Министерство образования и науки Российской федерации 
Федеральное государственное бюджетное образовательное учреждение 
высшего профессионального образования  
«Воронежская государственная лесотехническая академия» 
 
 
 
 
 
 
 
 
 
ПРИКЛАДНАЯ МАТЕМАТИКА 

 
 
ЗАДАЧА КОММИВОЯЖЕРА 
СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
Воронеж  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)