Пример решения задачи коммивояжера венгерским методом
Исходная матрица имеет вид:| M | 3 | 4 | 2 | 7 |
| 5 | M | 8 | 4 | 3 |
| 2 | 3 | M | 7 | 5 |
| 3 | 2 | 9 | M | 1 |
| 1 | 2 | 3 | 5 | M |
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
| M | 1 | 2 | 0 | 5 | 2 |
| 2 | M | 5 | 1 | 0 | 3 |
| 0 | 1 | M | 5 | 3 | 2 |
| 2 | 1 | 8 | M | 0 | 1 |
| 0 | 1 | 2 | 4 | M | 1 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
| M | 0 | 0 | 0 | 5 |
| 2 | M | 3 | 1 | 0 |
| 0 | 0 | M | 5 | 3 |
| 2 | 0 | 6 | M | 0 |
| 0 | 0 | 0 | 4 | M |
| 0 | 1 | 2 | 0 | 0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
| M | [-0-] | [-0-] | [0] | 5 |
| 2 | M | 3 | 1 | [0] |
| [0] | [-0-] | M | 5 | 3 |
| 2 | [0] | 6 | M | [-0-] |
| [-0-] | [-0-] | [0] | 4 | M |
В результате получаем эквивалентную матрицу Сэ:
| M | 0 | 0 | 0 | 5 |
| 2 | M | 3 | 1 | 0 |
| 0 | 0 | M | 5 | 3 |
| 2 | 0 | 6 | M | 0 |
| 0 | 0 | 0 | 4 | M |
4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
| M | [-0-] | [-0-] | [0] | 5 |
| 2 | M | 3 | 1 | [0] |
| [0] | [-0-] | M | 5 | 3 |
| 2 | [0] | 6 | M | [-0-] |
| [-0-] | [-0-] | [0] | 4 | M |
Cmin = 2 + 3 + 2 + 2 + 3 = 12 Скачать в формате doc
Пример 2. Исходная матрица имеет вид:
| M | 69 | 15 | 41 | 46 | 62 |
| 22 | M | 77 | 43 | 41 | 60 |
| 57 | 78 | M | 13 | 27 | 82 |
| 61 | 61 | 53 | M | 43 | 68 |
| 38 | 54 | 34 | 22 | M | 43 |
| 2 | 8 | 78 | 81 | 52 | M |
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
| M | 54 | 0 | 26 | 31 | 47 | 15 |
| 0 | M | 55 | 21 | 19 | 38 | 22 |
| 44 | 65 | M | 0 | 14 | 69 | 13 |
| 18 | 18 | 10 | M | 0 | 25 | 43 |
| 16 | 32 | 12 | 0 | M | 21 | 22 |
| 0 | 6 | 76 | 79 | 50 | M | 2 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
| M | 48 | 0 | 26 | 31 | 26 |
| 0 | M | 55 | 21 | 19 | 17 |
| 44 | 59 | M | 0 | 14 | 48 |
| 18 | 12 | 10 | M | 0 | 4 |
| 16 | 26 | 12 | 0 | M | 0 |
| 0 | 0 | 76 | 79 | 50 | M |
| 0 | 6 | 0 | 0 | 0 | 21 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
| M | 48 | [0] | 26 | 31 | 26 |
| [0] | M | 55 | 21 | 19 | 17 |
| 44 | 59 | M | [0] | 14 | 48 |
| 18 | 12 | 10 | M | [0] | 4 |
| 16 | 26 | 12 | [-0-] | M | [0] |
| [-0-] | [0] | 76 | 79 | 50 | M |
В результате получаем эквивалентную матрицу Сэ:
| M | 48 | 0 | 26 | 31 | 26 |
| 0 | M | 55 | 21 | 19 | 17 |
| 44 | 59 | M | 0 | 14 | 48 |
| 18 | 12 | 10 | M | 0 | 4 |
| 16 | 26 | 12 | 0 | M | 0 |
| 0 | 0 | 76 | 79 | 50 | M |
4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
| M | 48 | [0] | 26 | 31 | 26 |
| [0] | M | 55 | 21 | 19 | 17 |
| 44 | 59 | M | [0] | 14 | 48 |
| 18 | 12 | 10 | M | [0] | 4 |
| 16 | 26 | 12 | [-0-] | M | [0] |
| [-0-] | [0] | 76 | 79 | 50 | M |
Cmin = 15 + 22 + 13 + 43 + 43 + 8 = 144