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

Далее продолжаем процесс ветвления. Найдем степени Θij нулевых элементов этой матрицы Θ21 =16, Θ36 = 5, Θ42 = 2, Θ56 = 2, Θ62 = 0, Θ63 =9, Θ65 = 2. Наибольшая степень Θ21. Затем множество разбивается дуге (2, 1) на два новых и .

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

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

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

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

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

Степени Θij нулевых элементов этой матрицы Θ36 = 5, Θ45 = 0, Θ56 = 22, Θ62 = 13, Θ63 =7, Θ65 = 0. Наибольшая степень Θ56. Затем множество разбивается дуге (2, 1) на два новых и .

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

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

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

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

Степени Θij нулевых элементов этой матрицы Θ35 = 8, Θ45 = 7, Θ62 = 8, Θ63 =7. Выбираем Θ35 = 8. Разбиваем на и .

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

 Скачать реферат