Используя венгерский метод, решить задачу коммивояжера, если матрица затрат на переезд из города в город выглядит следующим образом
Город Стоимость проезда
1 2 3 4 5 6
1 - 6 5 2 1 5
2 10 - 6 11 3 5
3 1 10 - 12 15 1
4 2 12 4 - 5 6
5 7 8 3 5 - 3
6 2 12 10 10 5 -
Решение
М 6 5 2 1 5
10 М 6 11 3 5
1 10 М 12 15 1
2 12 4 М 5 6
7 8 3 5 М 3
2 12 10 10 5 М
Шаг 1
Проведем редукцию матрицы по строкам – найдем в каждой строке минимальный элемент и вычтем его из каждого элемента строки
М 5 4 1 0 4 1
7 М 3 8 0 2 3
0 9 М 11 14 0 1
0 10 2 М 3 4 2
4 5 0 2 М 0 3
0 10 8 8 3 М 2
Проведем редукцию матрицы по столбцам – найдем в каждом столбце минимальный элемент и вычтем его из каждого элемента столбца
М 0 4 0 0 4
7 М 3 7 0 2
0 4 М 10 14 0
0 5 2 М 3 4
4 0 0 1 М 0
0 5 8 7 3 М
0 5 0 1 0 0
Получили полностью редуцированную матрицу
Методом проб и ошибок проводим поиск допустимого решения
Фиксируем нулевое значение в ячейке (1,5), другие нули в первой строке и пятом столбце вычеркиваем – это ячейки (1,2), (1,4), (2,5)
М 0 4 0 0 4
7 М 3 7 0 2
0 4 М 10 14 0
0 5 2 М 3 4
4 0 0 1 М 0
0 5 8 7 3 М
Расположение нулевых элементов в матрице не позволяет образовать систему из 6-х независимых нулей, значит решение недопустимое.
Проведем модификацию матрицы – вычеркнем строки и столбцы с возможно большим количеством нулевых элементов – строку 1, строку 3, строку 5, столбец 1, столбец 5
Получим сокращенную матрицу
М 0 4 0 0 4
7 М 3 7 0 2
0 4 М 10 14 0
0 5 2 М 3 4
4 0 0 1 М 0
0 5 8 7 3 М
Минимальный элемент сокращенной матрицы равен 2, вычтем его из всех элементов сокращенной матрицы
М 0 4 0 0 4
7 М 1 5 0 0
0 4 М 10 14 0
0 3 0 М 3 2
4 0 0 1 М 0
0 3 6 5 3 М
Сложим минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов
М 0 4 0 2 4
7 М 1 5 0 0
2 4 М 10 16 0
0 3 0 М 3 2
6 0 0 1 М 0
0 3 6 5 3 М
Шаг 2
Необходимо редуцировать матрицу по строкам и столбцам, но так как в каждой строке и в каждом столбце есть 0, проводим поиск допустимого решения
Фиксируем нулевое значение в ячейке (1,2), другие нули в первой строке и четвертом столбце вычеркиваем – это ячейки (1,4), (5,1)
М 0 4 0 2 4
7 М 1 5 0 0
2 4 М 10 16 0
0 3 0 М 3 2
6 0 0 0 М 0
0 3 6 5 3 М
Фиксируем нулевое значение в ячейке (2,5), другие нули во второй строке и пятом столбце вычеркиваем – это ячейки (2,6)
Фиксируем нулевое значение в ячейке (3,6), другие нули в третьей строке и шестом столбце вычеркиваем – это ячейки (5,6)
М 0 4 0 2 4
7 М 1 5 0 0
2 4 М 10 16 0
0 3 0 М 3 2
6 0 0 0 М 0
0 3 6 5 3 М
Фиксируем нулевое значение в ячейке (3,4), другие нули в третьей строке и четвертом столбце вычеркиваем – это ячейки (4,1), (5,3)
М 0 4 0 2 4
7 М 1 5 0 0
2 4 М 10 16 0
0 3 0 М 3 2
6 0 0 0 М 0
0 3 6 5 3 М
Фиксируем нулевое значение в ячейке (5,4), другие нули в пятой строке и четвертом столбце вычеркиваем
Фиксируем нулевое значение в ячейке (6,1), другие нули в шестой строке и первом столбце вычеркиваем
М 0 4 0 2 4
7 М 1 5 0 0
2 4 М 10 16 0
0 3 0 М 3 2
6 0 0 0 М 0
0 3 6 5 3 М
Получаем путь (1,2)-(2,5)-(5,4)-(4,3)-(3,6)-(6,1)
Длина пути 6+3+5+4+1+2=21
Задать вопрос
на новый заказ в Автор24.
