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

06.02.2011 13:43

Исходная матрица имеет вид:

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

Интересная статья? Поделись ей с другими:

Adviss logistics - портал по логистике

Добавить комментарий