Реферат: Решение задачи коммивояжера методом ветвей и границ

Рис. 1 Ветвление на первом шаге

Приведенная платежная матрица для

1	2	3	5	6
2	0	∞	15	29	24
3	14	13	∞	5	0
4	∞	0	9	2	2
5	1	41	22	∞	0
6	12	0	0	0	∞

Далее продолжаем процесс ветвления. Найдем степени Θ_ij нулевых элементов этой матрицы Θ₂₁ =16, Θ₃₆ = 5, Θ₄₂ = 2, Θ₅₆ = 2, Θ₆₂ = 0, Θ₆₃ =9, Θ₆₅ = 2. Наибольшая степень Θ₂₁ . Затем множество разбивается дуге (2, 1) на два новых и .

В матрице для вычеркиваем строку 2 и столбец 1. дуги (1, 4) и (2, 1) образуют связный путь (2, 1, 4), положим c ₄₂ = ∞, чтобы предотвратить появления цикла 2→1→ 4 → 2.

2	3	5	6
3	13	∞	5	0
4	∞	9	2	2
5	41	22	∞	0
6	0	0	0	∞

Для приведения надо вычесть минимум по строке 4: r₄ =2. При этом нижняя граница станет равной 48+2 = 50.

Нижняя граница для, полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ () = 64 и φ () = 50 < 64 выбираем для дальнейшего разбиения подмножество маршрутов .

Рис. 2 Ветвление на втором шаге

Приведенная платежная матрица для

2	3	5	6
3	13	∞	5	0
4	∞	7	0	0
5	41	22	∞	0
6	0	0	0	∞

Степени Θ_ij нулевых элементов этой матрицы Θ₃₆ = 5, Θ₄₅ = 0, Θ₅₆ = 22, Θ₆₂ = 13, Θ₆₃ =7, Θ₆₅ = 0. Наибольшая степень Θ_56. Затем множество разбивается дуге (2, 1) на два новых и .

Нижняя граница дляравна 50 + 22 = 72. В матрице для вычеркиваем строку 5 и столбец 6 и полагаем c ₆₅ = ∞. Получим матрицу:

2	3	5
3	13	∞	5
4	∞	7	0
6	0	0	∞

Для приведения надо вычесть минимум по строке 3: r₃ =5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов .

Рис. 3 Ветвление на третьем шаге

Приведенная платежная матрица для

2	3	5
3	8	∞	0
4	∞	7	0
6	0	0	∞

Степени Θ_ij нулевых элементов этой матрицы Θ₃₅ = 8, Θ₄₅ = 7, Θ₆₂ = 8, Θ₆₃ =7. Выбираем Θ₃₅ = 8. Разбиваем на и .

Нижняя граница дляравна 55 + 8 = 64. В матрице для вычеркиваем строку 3 и столбец 5 и полагаем c ₆₃ = ∞. Получим

2	3
4	∞	7
6	0	∞

Для приведения надо вычесть минимум по строке 4: r4=7. При этом нижняя граница станет равной 55+7 = 62. После приведения получим

2	3
4	∞	0
6	0	∞

Из матрицы 2´2 получаем два перехода с нулевой длинной: (4, 3) и (6, 2).

Рис. 4 Ветвление на четвертом шаге

Рис. 5 Дерево ветвления с оценками

Полученный маршрутом коммивояжера z ₀ = (1, 4, 3, 5, 6, 2, 1) или (A-D-C-E-F-B-A).