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

S1. Привести матрицу весов W, при этом приведение осуществляется в два этапа: сначала в каждой строке ищут минимальный элемент, который вычитают из каждого элемента этой строки, Затем эта же процедура применяется к столбцам полученной матрицы. Пусть - стоимость приведения матрицы по строкам, равная сумме соответствующих минимальных элементов, - по столбцам, тогда стоимость приведения матрицы С определяется в виде . После приведения матрицы W получим матрицу Р, в каждой строке и в каждом столбце которой есть хотя бы один 0.

S2. Определить, существует ли решение в приведенной матрице Р, которое можно выписать, используя нулевые элементы. Для этого найдем нулевой элемент в первой строке – пусть это элемент , тогда перейдем к i-ой строке и выберем в ней произвольный нулевой элемент , затем перейдем к k-ой строке и т.д. Таким образом получаемое решение на нулевых элементах соответствует тому, что строится маршрут (l, i, k,…). Чтобы определить, есть ли в матрице Р решение, нужно перебрать все возможные комбинации нулевых элементов. Результат просмотра матрицы Р с целью поиска решений соответствует построению дерева поиска решений. Если в матрице Р можно получить решение, то оно и является решением задачи, иначе – перейти к следующему шагу.

S3. Для каждого нулевого элемента матрицы Р определить штраф как сумму минимальных элементов соответствующих строки и столбца

.

S4. Выделить в матрице Р нулевой элемент с максимальным штрафом и определить оценки затрат за включение и не включение соответствующей ему дуги в маршрут.

Оценка затрат за невключение дуги (h, k) в маршрут определяется в виде

,

где - стоимость приведения матрицы Р, содержащей нулевой элемент (h, k); - его штраф.

Оценка затрат за включение дуги (h, k) в маршрут имеет вид

,

где определяется так же, как и в предыдущем случае; - стоимость приведения матрицы , полученной из матрицы Р после вычеркивания h-ой строки и k-ого столбца, на пересечении которых стоит нулевой элемент (h, k).

Если в матрице существует несколько нулевых элементов, максимальным штрафом, то выбирается произвольный, при этом возможно возвращение к данной матрице и тогда следует выбирать другой нулевой элемент с максимальным штрафом, положив ранее выбранный элемент равным и осуществив приведение полученной матрицы.

Выбирая нулевой элемент с максимальным штрафом на месте (h,k), мы делим все множество маршрутов на два непересекающихся подмножества: то, которое содержит дугу (h,k), и то, которое не содержит этой дуги. Этой ситуации соответствует процесс ветвления в некоторой вершине дерева поиска решений с вычислением нижней границы суммарной стоимости маршрута.

S5. Из полученных двух оценок и выбрать минимальную. Если минимальной является , то на месте элемента (h,k) ставится и осуществляется приведение полученной матрицы, при этом стоимость приведения добавляется к нижней границе суммарной стоимости маршрута. Затем процесс продолжается, начиная с шага S3. Если минимальной оценкой является , то данная дуга включается в маршрут и уже к полученной стоимости строящегося маршрута добавляется стоимость приведения матрицы, полученной после вычерчивания строки h и столбца k, и процесс продолжается, начиная с шага S3. При включении данной дуги (h,k) в маршрут надо запретить дугу (k, h) и все дуги, которые ведут к образованию неполных маршрутов. Для этого соответствующие элементы матрицы полагаются равными . Затем полученная матрица приводится.

S6. Шаги S4-S6 повторяются до тех пор, пока, используя дерево поиска решений, не будет определен полный маршрут. Суммарная стоимость полного маршрута определяется по дереву поиска решений или как стоимость приведения всех матриц, используемых для получения решения. Кроме этого, эту величину можно определить как значение целевой функции, используя матрицы W и X.

Пусть с помощью метода ветвей и границ найдено решение задачи с длиной маршрута, равной некоторому числу L. Однако дерево поиска решений содержит ветку с оценкой <L, причем попытка получить решение по этой ветке приводит к маршруту длины <L, то есть решение может быть улучшено. Тогда значение называется рекордом, а маршрут, который ему соответствует, является оптимальным решением задачи.

Рассмотрим задачу с матрицей весов следующего вида:

С

Перейдем к приведенной матрице (далее при вычислениях получаемые приведенные матрицы будем обозначать буквой Р с индексом, а неприведенные - или также с индексом). Для этого в каждой строке найдем минимальный элемент и вычтем его из всех элементов строки, а затем ту же самую процедуру применим к столбцам. В результате получим следующие матрицы.

С

Минимальный элемент

Р1

Таким образом, стоимость приведения исходной матрицы равна 8+14=12. Проверим, существует ли решение в полученной приведенной матрице . Для этого попытаемся построить решение на нулевых элементах. Дерево поиска решения будет иметь вид

Начало поиска 1 5 4 1

2 4 1 5 4

6 2 4 1 5 4

3 2 4 1 5 4

5 4 1 5

3 2 4 1 5 4

4 1 5 4

5 4 1 5

6 2 4 1 5 4

3 2 4 1 5 4

5 4 1 5

Посчитаем штрафы на нулевых элементах в матрице Р1.

Р1

Максимальный штраф на нуле имеет элемент (4,1), поэтому необходимо определить стоимость включения и невключения дуги (4,1) в маршрут. =12+2=14. Построим матрицу, которая соответствует случаю включения данной дуги в маршрут, при этом необходимо запретить все неполные маршруты, поэтому положим элемент (1,4) равным .

Р2

Так как в каждой строке и в каждом столбце матрицы существует хотя бы один нуль, то она является приведенной, а стоимость включения дуги (4,1) в маршрут (4,1)=12+0=12. Заметим, что (4,1)> , поэтому дуга (4,1) включается в маршрут и теперь в качестве текущей рассматривается матрица . Для нее посчитаем штрафы на нулевых элементах, выберем элемент с максимальным штрафом и определим стоимость включения и невключения соответствующей ему дуги в маршрут. Результат выполнения этих действий представлен ниже.

Р2

Р3

Матрица является приведенной. Максимальный штраф на нуле в матрице имеет элемент (3,2), поэтому дуга (2,3) запрещается, а соответствующий ей элемент в матрице полагается равным . (3,2)=12+0=12, =12+2=14. Так как (3,2)< , то дуга (3,2) включается в маршрут. Теперь будем рассматривать матрицу . Аналогичные действия приводят к тому, что дуга (5,4) включается в маршрут, при этом можно заметить, что в матрице элемент с максимальным штрафом не является единственным. Матрица нуждается в приведении, а стоимость ее приведения добавляется к стоимости включения дуги (5,4) в маршрут.

Р3

				Минимальный элемент

=12+1=13, (5,4)=12+1=13, то есть получили, что стоимости включения и невключения дуги (5,4) в маршрут совпадают, поэтому здесь нужно рассмотреть оба случая. Вначале включим дугу (5,4) в маршрут и перейдем к матрице , в которой для запрещения неполных маршрутов положим элемент (1,5) равным .

Таким образом, получен следующий маршрут: 1®3®2®6®5®4®1.

Вернемся теперь к случаю, когда дуга (5,4) не включается в маршрут. Для этого матрице положим элемент (5,4) равным и приведем полученную матрицу, а затем посчитаем в ней штрафы на нулевых элементах.

						Минимальный элемент

Выберем в качестве элемента с максимальным штрафом (1,5) и посчитаем стоимости включения и невключения дуги (1,5) в маршрут. Для этого перейдем к матрице . Она является приведенной, поэтому в ней можно определить штрафы на нулевых элементах. В матрице в качестве нуля с максимальным штрафом выберем элемент (2,4) и для него также произведем расчет, который позволит завершить построение нового маршрута.

=12+1+1=14, (1,5)=12+1=13;

=13+1=14, (2,4)=13+0=13.

Заметим, что и в том, и в другом случае в матрице решение выписывается с помощью нулевых элементов. Второй маршрут имеет следующий вид: 1®5®6®3®2®4®1.

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

Начало решения

14 12

(4,1) (4,1)

12 14

(3,2) (3,2)

13 13

(5,4) (5,4)

13

14 19 13

(1,5) (1,5) (2,6) (2,6)

13

14 13

(2,4) (2,4) (1,3) (1,3)

13 13

(6,3) (6,3) (6,5) (6,5)

13

(5,6) (5,6)

Рис.2. Дерево решения задачи