Используя венгерский метод, решить следующую задачу коммивояжера, если матрица затрат на переезд из города. 2

Используя венгерский метод, решить следующую задачу коммивояжера, если матрица затрат на переезд из города в город выглядит следующим образом: Город Стоимость проезда 1 2 3 4 5 6 1 - 26 15 12 18 10 2 21 - 16 21 13 15 3 11 10 - 12 15 11 4 12 12 14 - 15 16 5 27 18 13 25 - 13 6 12 12 10 10 15 -

Шаг 1
Выполним редукцию матрицы затрат по строкам.
Найдем минимальный элемент каждой строки
MIN
- 26 15 12 18 10 10
21 - 16 21 13 15 13
11 10 - 12 15 11 10
12 12 14 - 15 16 12
27 18 13 25 - 13 13
12 12 10 10 15 - 10
Вычтем найденные минимальные из элементов соответствующей строки (в каждой строке матрицы будет как минимум один ноль):
- 16 5 2 8 0
8 - 3 8 0 2
1 0 - 2 5 1
0 0 2 - 3 4
14 5 0 12 - 0
2 2 0 0 5 -
Выполним редукцию матрицы затрат по столбцам.
Найдем минимальный элемент каждого столбца
- 16 5 2 8 0
8 - 3 8 0 2
1 0 - 2 5 1
0 0 2 - 3 4
14 5 0 12 - 0
2 2 0 0 5 -
MIN 0 0 0 0 0 0
Вычтем найденные минимальные из элементов соответствующего столбца. Получим полностью редуцированную матрицу:
- 16 5 2 8 0
8 - 3 8 0 2
1 0 - 2 5 1
0 0 2 - 3 4
14 5 0 12 - 0
2 2 0 0 5 -
Шаг 2
Проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 6). Другие нули в строке 1 и столбце 6 вычеркиваем. Для данной клетки вычеркиваем ноль в клетке (5; 6).
Фиксируем нулевое значение в клетке (2, 5)

. Другие нули в строке 2 и столбце 5 вычеркиваем. Для данной клетки вычеркнутых нулей нет.
Фиксируем нулевое значение в клетке (3, 2). Другие нули в строке 3 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем ноль в клетке (4; 2).
Фиксируем нулевое значение в клетке (4, 1). Другие нули в строке 4 и столбце 1 вычеркиваем. Для данной клетки вычеркнутых нулей нет (с учетом ранее вычеркнутых).
Фиксируем нулевое значение в клетке (5, 3). Другие нули в строке 5 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем ноль в клетке (6,3) (с учетом ранее вычеркнутых).
В строке 6 остается единственный невычеркнуый ноль – в клетке (6.4).
В итоге получаем следующую матрицу.
- 16 5 2 8 0
8 - 3 8 0 2
1 0 - 2 5 1
0 0 2 - 3 4
14 5 0 12 - 0
2 2 0 0 5 -
Найденная система независимых нулей не позволяет получить допустимое решение, т.к. она не образует гамильтонов цикл: (2,5)(5,3)(3,2) – получили подцикл; (1,6)(6,4)(4,1) – получили подцикл.
Избавимся от подцикла (2,5)(5,3)(3,2) – запретим заезд в клетку (3,2).
Получим следующую матрицу, которая не содержит 6 независимых нулей:
- 16 5 2 8 0
8 - 3 8 0 2
1 - - 2 5 1
0 0 2 - 3 4
14 5 0 12 - 0
2 2 0 0 5 -
Проводим модификацию матрицы