Филичев П.В. Математика для электромехаников / Задача 2 / Транспортная задача
.docДискретная задача транспортного типа
Задание:
Решить задачу коммивояжера по следующим данным:
Решение:
Приведем данную матрицу по строкам и по столбцам, получим:
Сложив приведение по строкам и по столбцам, получим: 6 + 2 = 8.
Следовательно, Min оценка = 8.
1. Оценим нули в полученной матрице:
Max оценка = 5.
Разбиваем на 5,5 и not 5,5.
Минор по 5,5.
2. Оценим нули в полученной матрице:
Max оценка = 3.
Разбиваем на 1,8 и not 1,8.
Минор по 1,8.
3. Оценим нули в полученной матрице:
Max оценка = 3.
Разбиваем на 7,7 и not 7,7.
Минор по 7,7.
4. Оценим нули в полученной матрице:
Max оценка = 2.
Разбиваем на 4,3 и not 4,3.
Минор по 4,3.
5. Оценим нули в полученной матрице:
Max оценка = 5.
Разбиваем на 2,2 и not 2,2.
Минор по 2,2.
5. Оценим нули в полученной матрице:
Max оценка = 1.
Разбиваем на 8,6 и not 8,6.
Минор по 8,6.
6. Оценим нули в полученной матрице:
Max оценка = 9.
Разбиваем на 6,1.
Минор по 6,1.
В итоге получим дереве ветвлений и длин путей:
По этому дереву можно определить, что оптимальным путем является последовательность:
1 8 6 1 7 7 2 2 4 3 5 5 1 и его длинна равна 40.
Вывод:
Путь является оптимальным, по методу «ветвей и границ», в данной модели нет строгого правила: обход каждой вершины по одному разу, поэтому допускается как переход из вершины в туже вершину, так и проход через одну вершину несколько раз.