Задача коммивояжера

i  j	1	2	3
1	M	0	22
2	33	M	0
3	0	31	M

 
   
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:  
d_j = min(i) d_ij

i  j	1	2	3
1	M	0	22
2	33	M	0
3	0	31	M
dj	0	0	0

 
   
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d_i и d_j называются константами приведения.

i  j	1	2	3
1	M	0	22
2	33	M	0
3	0	31	M

 
   
Сумма констант приведения определяет нижнюю границу H:  
H = ∑d_i + ∑d_j  
H = 22+22+12+0+0+0 = 56  
Элементы матрицы d_ij соответствуют расстоянию от пункта i до пункта j.  
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d_ij >=0  
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.  
Длина маршрута определяется выражением:  
F(M_k) = ∑d_ij  
Причем каждая строка и столбец входят в маршрут только один раз с элементом d_ij .  
Шаг №1.  
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).  
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i  j	1	2	3	di
1	M	0(53)	22	22
2	33	M	0(55)	33
3	0(64)	31	M	31
dj	33	31	22	0

 
   
d(1,2) = 22 + 31 = 53; d(2,3) = 33 + 22 = 55; d(3,1) = 31 + 33 = 64;  
Наибольшая сумма констант приведения равна (31 + 33) = 64 для ребра (3,1), следовательно, множество разбивается на два подмножества (3,1) и (3*,1*).  
Нижняя граница гамильтоновых циклов этого подмножества:  
H(3*,1*) = 56 + 64 = 120  
Исключение ребра (3,1) проводим путем замены элемента d₃₁ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,1*), в результате получим редуцированную матрицу.

i  j	1	2	3	di
1	M	0	22	0
2	33	M	0	0
3	M	31	M	31
dj	33	0	0	64

 
   
Включение ребра (3,1) проводится путем исключения всех элементов 3-ой строки и 1-го столбца, в которой элемент d₁₃ заменяем на М, для исключения образования негамильтонова цикла.  
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.  
Сумма констант приведения сокращенной матрицы:  
∑d_i + ∑d_j = 0  
После операции приведения сокращенная матрица будет иметь вид:

i  j	2	3	di
1	0	M	0
2	M	0	0
dj	0	0	0

 
   
Нижняя граница подмножества (3,1) равна:  
H(3,1) = 56 + 0 = 56  <  120  
Поскольку нижняя граница этого подмножества (3,1) меньше, чем подмножества (3*,1*), то ребро (3,1) включаем в маршрут.  
Поскольку 56 ≥ 56, исключаем подмножество (3,1) для дальнейшего ветвления.  
Возвращаемся к прежнему плану X₂.  
В результате по дереву ветвлений гамильтонов цикл образуют ребра:  
для первого плана X₀. F(X₀) = 56

 

 

Выводы

 

В данной работе мы познакомили читателя с основными понятиями теории графов, дали представление о задаче коммивояжера, описали метод ветвей и границ. Также привели пример использования метода ветвей и границ для решения задачи коммивояжера.

Еще раз отметим, что задача коммивояжера является одной из самых важнейших  задач в теории графов. Возможность  представления (записи) различных производственных процессов на языке теории графов и умение решить сформулированную математическую задачу позволяют найти оптимальную стратегию ведения хозяйства, сэкономить ресурсы, выполнить поставленную задачу в более короткие сроки. Очевидно, что изучение методов теории графов, методов математического программирования, системного анализа и пр. – является важным этапом подготовки инженеров в МГСУ.

 

 

 

Список литературы

 

1. Н.М. Новикова «Основы оптимизации», курс лекций. М. 1998.

2. Н. Кристофидес «Теория графов. Алгоритмический подход», М., Мир, 1978.

3. С.Е. Канторер. «Методы обоснования эффективности применения машин в строительстве». М. 1969.

4. Институт математики им. С.Л. Соболева СО РАН Лаборатория «Математические модели принятия решений», статья «Метод ветвей и границ». Адрес в интернете: http://math.nsc.ru/AP/benchmarks/index.html.

5. Е.А. Тишкин «Эвристический алгоритм решения задачи коммивояжера». Публикация на сайте http://nit.itsoft.ru. Самарский государственный аэрокосмический университет, Россия.