Применение методов решения задачи коммивояжера на практике

Таблица 13 Приведение матрицы расстояний для подмножества (6*,3*), матрица размерностью 4´4

i  j	3	4	5	6	di
1	2	1	M	0	0
3	M	2	0	2	0
4	5	M	1	0	0
6	M	0	0	M	0
dj	2	0	0	0	2

 

Включение ребра (6,3) проводится путем исключения всех элементов 6-ой строки и 3-го столбца, в которой элемент d36 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 1

После операции приведения сокращенная матрица будет иметь вид: (Таблица 14)

Таблица 14 Сокращённая матрица размерностью 3´3

i  j	4	5	6	di
1	1	M	0	0
3	2	0	M	0
4	M	1	0	0
dj	1	0	0	М

 

Нижняя граница подмножества (6,3) равна:

H(6,3) = 8 + 1 = 9  ≤  10

Чтобы исключить подциклы, запретим следующие переходы: (1,5), 

Поскольку нижняя граница этого подмножества (6,3) меньше, чем подмножества (6*,3*), то ребро (6,3) включаем в маршрут с новой границей H = 9

Шаг №4. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках. (Таблица 15)

Таблица 15 Определение ребра ветвления (6,3) матрица размерностью 3´3

i  j	4	5	6	di
1	0(1)	M	0(0)	0
3	1	0(2)	M	1
4	M	1	0(1)	1
dj	1	1	0	М

 

d(1,4) = 0 + 1 = 1; d(1,6) = 0 + 0 = 0; d(3,5) = 1 + 1 = 2; d(4,6) = 1 + 0 = 1; 

Наибольшая сумма констант приведения равна (1 + 1) = 2 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(3*,5*) = 9 + 2 = 11

Исключение ребра (3,5) проводим путем замены элемента d35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу. (Таблица 16)

Таблица 16 Приведение матрицы расстояний для подмножества (3*,5*) матрица размерностью 3´3

i  j	4	5	6	di
1	0	M	0	0
3	1	0	M	1
4	M	1	0	0
dj	0	1	0	2

 

Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d53 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы: ∑di + ∑dj = 0

После операции приведения сокращенная матрица будет иметь вид: (Таблица 17)

Таблица 17 Сокращённая матрица размерностью 2´2

i  j	4	6	di
1	0	М	0
4	M	0	0
dj	0	0	0

 

Нижняя граница подмножества (3,5) равна:

H(3,5) = 9 + 0 = 9  ≤  11

Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 9

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (1,4) и (4,6).

Cmin = 2+1+2+2+1+1=9

Путь: (1,4); (4,6); (6;3); (3,5); (5,2); (2,1)

1→4→6→3→5→2→1

Оптимальный путь Дерево ветвлений (Приложение А).

 

 

3.2 Решение задачи коммивояжера венгерским методом.

 

Фирма по производству новогодних игрушек должна доставить заказ в 6 городов: Кирсанов (1); Котовск (2); Рассказово (3); Мичуринск (4) Инжавино (5); Уварово (6). Нужно найти кротчайший путь, объездив все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город 1.

Расстояния между городами заданы следующей матрицей. (Таблица 18)

Математическая модель:

 

 

 

Таблица 18 Исходная матрица размерностью 6´6

i j	1	2	3	4	5	6
1	M	5	4	2	4	1
2	1	M	2	4	5	7
3	7	5	M	4	2	4
4	4	5	7	M	2	1
5	2	1	4	7	M	5
6	5	7	2	1	1	M

 

Проводим редукцию матрицы по строкам, для чего в каждой строке находим минимальный элемент и вычитаем его из элементов этой же строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль. (Таблица 19)

Таблица 19 Приведение матрицы по строкам, матрица размерностью 6´6

i j	1	2	3	4	5	6
1	M	4	3	1	3	0
2	0	M	1	3	4	6
3	5	3	M	2	0	2
4	3	4	6	M	1	0
5	1	0	3	6	M	4
6	4	6	1	0	0	M

 

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент. (Таблица 20)

Таблица 20 Приведение матрицы по столбцам, матрица размерностью 6´6

i j	1	2	3	4	5	6
1	M	4	2	1	3	0
2	0	M	0	3	4	6
3	5	3	M	2	0	2
4	3	4	5	M	1	0
5	1	0	2	6	M	4
6	4	6	0	0	0	M