Ci j , i, j=1..N - матрица затрат, где Ci j - затраты на переход из i-го города в j-й.

Xi j - матрица переходов с компонентами:

Xi j = 1, если коммивояжер совершает переход из i-го города в j-й,

Xi j = 0, если не совершает перехода,

где i, j = 1..N и i¹j.

Критерий:

(1)

Ограничения:

, i = 1..N (2)

, j = 1..N (3)

Ui - Uj + N × Xi j£ N-1, i, j = 1..N, i ¹ j. (4)

Доказательство, что модель (1-4) описывает задачу о коммивояжере:

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.

Рассмотрим условие (4). Применим метод доказательства от противного, то есть предположим, что условие (4) выполняется для некоторого подцикла T из R городов, где R<N. Сложив все неравенства (4) вдоль этого подцикла получим

.

Так как

,

то N × R £ (N -1), где R<N, R ¹ 0.

Следовательно, не существует замкнутого подцикла с числом городов меньшим, чем N.

Покажем, что существует Ui, которое для замкнутого цикла, начинающегося в некотором начальном пункте, удовлетворяют условию (4). При всех Xi j (j-й город не посещается после i-го) в (4) имеем Ui - Uj£ N - 1, что допустимо в силу произвольных Ui и Uj.

Пусть на некотором R-ом шаге i-й город посещается перед j-м, то есть Xi j = 1. В силу произвольности значений Ui и Uj положим Ui = R, а Uj = R + 1, тогда из (4) имеем:

Ui - Uj + N × Xi j£ R - (R - 1) + N = N - 1

Итак, существуют такие конечные значения для Ui и Uj, что для маршрута, содержащего N городов, условие (4) удовлетворяется как неравенство или строгое равенство. А следовательно, модель (1-4) описывает задачу о коммивояжере.

Описание программной реализации алгоритма

В программе реализован классический вариант метода ветвей и границ, то есть алгоритм решения следующий:

При этом предусмотрена возможность смены направления критерия, то есть возможность решения задачи на максимум.

Наибольший выбор программа предоставляет в шаге 3, где реализовано четыре метода расчета нижней оценки множества и три метода расчета верхней оценки множества. Сначала рассмотрим методы нахождения нижней оценки, то есть решения релаксированной задачи:

Метод 1: "Из каждого города".

Рассчитывается цена маршрута по зафиксированным для данной вершины городам. Затем в каждой строке матрицы, в которой нет фиксированных элементов, находится минимальный элемент (в программе реализовано функцией Min_Col) и прибавляется к общей сумме, то есть берутся ближайшие города для выхода из всех еще не пройденных городов. Программная реализация ‑ VHCOUNT. H_1

Метод 2: "В каждый город".