Используя венгерский метод, решить следующую задачу коммивояжера, если матрица затрат на переезд из города в город выглядит следующим образом:
Город Стоимость проезда
1 2 3 4 5 6
1 - 16 15 32 53 55
2 27 - 34 50 2 31
3 33 39 - 42 36 39
4 45 22 59 - 28 26
5 55 49 14 18 - 12
6 28 14 8 48 35 -
Решение
Шаг 1
Выполним редукцию матрицы затрат по строкам.
Найдем минимальный элемент каждой строки
MIN
- 16 15 32 53 55 15
27 - 34 50 2 31 2
33 39 - 42 36 39 33
45 22 59 - 28 26 22
55 49 14 18 - 12 12
28 14 8 48 35 - 8
Вычтем найденные минимальные из элементов соответствующей строки (в каждой строке матрицы будет как минимум один ноль):
- 1 0 17 38 40
25 - 32 48 0 29
0 6 - 9 3 6
23 0 37 - 6 4
43 37 2 6 - 0
20 6 0 40 27 -
Выполним редукцию матрицы затрат по столбцам.
Найдем минимальный элемент каждого столбца
- 1 0 17 38 40
25 - 32 48 0 29
0 6 - 9 3 6
23 0 37 - 6 4
43 37 2 6 - 0
20 6 0 40 27 -
MIN 0 0 0 6 0 0
Вычтем найденные минимальные из элементов соответствующего столбца. Получим полностью редуцированную матрицу:
- 1 0 11 38 40
25 - 32 42 0 29
0 6 - 3 3 6
23 0 37 - 6 4
43 37 2 0 - 0
20 6 0 34 27 -
Шаг 2
Проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 3). Другие нули в строке 1 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем ноль в клетке (6; 3).
Фиксируем нулевое значение в клетке (2, 5). Другие нули в строке 2 и столбце 5 вычеркиваем. Для данной клетки вычеркнутых нулей нет.
Фиксируем нулевое значение в клетке (3, 1). Другие нули в строке 3 и столбце 1 вычеркиваем. Для данной клетки вычеркнутых нулей нет.
Фиксируем нулевое значение в клетке (4, 2). Другие нули в строке 4 и столбце 2 вычеркиваем
. Для данной клетки вычеркнутых нулей нет.
Фиксируем нулевое значение в клетке (5, 4). Другие нули в строке 5 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем ноль в клетке (5,6).
В строке 6 не остается невычеркнутых нулей нет.
В итоге получаем следующую матрицу.
- 1 0 11 38 40
25 - 32 42 0 29
0 6 - 3 3 6
23 0 37 - 6 4
43 37 2 0 - 0
20 6 0 34 27 -
Т.к. получено только 5 независимых нулей (надо 6), то такое решение не является допустимым.
Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов, выполнив минимальное количество вычеркиваний: строки 2, 4 и 5, столбцы 1, 3. Получаем сокращенную матрицу:
- 1 0 11 38 40
25 - 32 42 0 29
0 6 - 3 3 6
23 0 37 - 6 4
43 37 2 0 - 0
20 6 0 34 27 -
Среди оставшихся элементов ищем минимальный (1), вычитаем его из оставшихся элементов (которые не зачеркнуты) и прибавляем к элементам, которые расположены на пересечении вычеркнутых строк и столбцов.
Получим следующую матрицу:
- 0 0 10 37 39
26 - 33 42 0 29
0 5 - 2 2 5
24 0 38 - 6 4
44 37 3 0 - 0
20 5 0 33 26 -
Проводим редукцию матрицы по строкам и столбцам. Поскольку минимальные в строках и столбцах равны 0, то вид матрицы не меняется.
Снова проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 2). Другие нули в строке 1 и столбце 2 вычеркиваем
Задать вопрос
на новый заказ в Автор24.
