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

 

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

Фиксируем нулевое значение в клетке (1, 6). Другие нули в строке 1 и столбце 6 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 5)

Фиксируем нулевое значение в клетке (2, 3). Другие нули в строке 2 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 5)

Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 5)

В итоге получаем следующую матрицу. (Таблица 21)

 

Таблица 21 Поиск допустимого решения, матрица размерностью 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

 

Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 6-х независимых нулей (в матрице их только 3), то решение недопустимое.

Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 6, столбец 6, строку 2, столбец 2, строку 3. Получаем сокращенную матрицу (элементы выделены). (Таблица 22)

Таблица 22 Сокращённая матрица размерностью 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

 

Минимальный элемент сокращенной матрицы (min(M, 2, 1, 3, 3, 5, M, 1, 1, 2, 6, M) =1) вычитаем из всех ее элементов. (Таблица 23)

Таблица 23 Вычитание минимального элемента сокращённой матрицы размерностью 6´6 из всех её элементов

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

 

Продолжение таблицы 23 Вычитание минимального элемента сокращённой матрицы размерностью 6´6 из всех её элементов

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

 

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

Таблица 24 Суммирование минимального элемента с элементами на пересечениях вычеркнутых строк и столбцов, матрица размерностью 6´6

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

 

Проводим редукцию матрицы по строкам.

В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль. (Таблица 25)

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

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

 

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

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

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

 

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

Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

Фиксируем нулевое значение в клетке (1, 4). Другие нули в строке 1 и столбце 4 вычеркиваем. 

Фиксируем нулевое значение в клетке (2, 1). Другие нули в строке 2 и столбце 1 вычеркиваем. 

Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем. 

Фиксируем нулевое значение в клетке (4, 6). Другие нули в строке 4 и столбце 6 вычеркиваем. 

Фиксируем нулевое значение в клетке (5, 2). Другие нули в строке 5 и столбце 2 вычеркиваем. 

Фиксируем нулевое значение в клетке (6, 3). Другие нули в строке 6 и столбце 3 вычеркиваем. 

В итоге получаем следующую матрицу. (Таблица 27)

Таблица 27 Поиск допустимого решения, матрица размерностью 6´6

i j	1	2	3	4	5	6
1	M	4	1	[0]	2	[-0-]
2	[0]	M	[-0-]	3	4	7
3	5	4	M	2	[0]	3

 

Продолжение таблицы 27 Поиск допустимого решения, матрица размерностью 6´6

4	2	4	4	M	[-0-]	[0]
5	[-0-]	[0]	1	5	M	4
6	4	7	[0]	[-0-]	[-0-]	M