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

Найдем нижнюю границу φ(Z) = 15+1+0+16+5+5+5 = 47.

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, найдем степени Θij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу). Θ14 = 10 + 0, Θ24 = 1 + 0, Θ36 = 5+0, Θ41 = 0 + 1, Θ42 = 0 + 0, Θ56 = 2 + 0, Θ62 = 0 + 0, Θ63 = 0 + 9, Θ

;65 = 0 + 2. Наибольшая степень Θ14 = 10. Ветвление проводим по дуге (1, 4).

Нижняя граница для множества остается равной 47. Для всех маршрутов множества из города A мы не перемещаемся в город D. В матрице это обозначается выставлением в ячейку (1, 4) знака ∞. В этом случае выход из города A добавляет к оценке нижней границы по крайней мере наименьший элемент первой строки. φ () = 47 + 10.

В матрице, соответствующей полагаем c14= ∞.

После проведения процедуры приведения с r1=10 получим новую нижнюю границу 57 + 10 = 67.

В матрице, соответствующей , вычеркиваем первую строку и четвертый столбец и положим c41= ∞, чтобы предотвратить появления цикла 1→ 4 → 1. Получим новую платежную матрицу {c1ij}:

Для приведения надо вычесть минимум по первому столбцу: h1=1. При этом нижняя граница станет равной 47+1 = 48. Сравнивая нижние границы φ () = 67 и φ () = 48 < 67 выделяем подмножество маршрутов , которое с большей вероятностью содержит маршрут минимальной длины.

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

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

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