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

Допустимый маршрут х представим как множество упорядоченных пар городов:

х = .

Каждый допустимый маршрут представляет собой цикл, проходя по которому коммивояжер посещает каждый город ровно один раз и возвращается в исходный город. Каждая упорядоченная пара (i, j) является дугой маршрута. Длина F(х) маршрута х равна сумме соответствующих элементов C(i, j). Заметим, что множество всех допустимых маршрутов X содержит (n-1)! элементов.

Обозначим через матрицу расстояний. Чтобы запретить переезды вида (i,i) положим C(i, i) = +∞ (i = 1,…, n).

Пусть

.

Тогда – редуцированная матрица.

Пусть d(X) = – сумма констант редуцирования.

Тогда для любого маршрута

F(х) = =

= + d(X) ≥ d(X) (5.20)

Неравенство (5.20) показывает, что d(X) является оценкой снизу для множества Х. Кроме того, после редукции длины всех маршрутов уменьшаются на одну и ту же величину d(X) и, следовательно, оптимальный маршрут, найденный с использованием редуцированной матрицы, оптимален и для исходной задачи.