Дискретная оптимизация - 6 стр.

                                                      6
§ 2. Метод ветвей и границ для решения задачи коммивояжера

Постановка задачи коммивояжера состоит в следующем. Имеется n городов.
Задана матрица расстояний между ними: C =(cij ), i, j =1, n . Cчитаем, что
cij ≥0, ∀i, j . В общем случае возможно, что cij ≠c ji . Кроме того, будем пола-
гать, что cii =+∞, ∀i . Ищется кратчайший замкнутый маршрут (цикл), прохо-
дящий через каждый город ровно один раз и минимизирующий суммарное
пройденное расстояние. Математическая постановка задачи может быть запи-
сана, например, следующим образом.
                                           n   n
                                   L =∑ ∑ cij xij → min
                                          i =1 j =1
                                    n
                                   ∑ xij =1,                  j =1, n,
                                   i =1
                                    n
                                   ∑ xij =1,              i =1, n,
                                   j =1

                              xij ∈{0,1}, i, j =1, n.
В этой постановке не учитывается естественное требование связности маршру-
та (отсутствия подциклов), но в дальнейшем оно будет выполняться алгорит-
мически.
Определение. Матрица C называется приведенной, если все ее элементы неот-
рицательны, а каждая строка и каждый столбец содержит по крайней мере по
одному нулевому элементу.
Приведение матрицы может быть осуществлено следующим образом. Пусть
имеется матрица C =(cij ), cij ≥0, i, j =1, n . Найдем min cij =α i , cij ' =cij −α i ,
                                                                             j
∀i, j. Получим матрицу C ' =(cij ' ) , которая в каждой строке содержит нулевые
элементы. Найдем далее min cij =β j , cij ' ' =cij '−β j , ∀i, j. Полученная матрица
                               i
C ' ' является приведенной, а сумма S =∑ α i +∑ β j называется суммой приво-
                                                          i              j
дящих констант.
Матрица C ' определяет новую задачу коммивояжера, которая в качестве опти-
мального решения будет иметь ту же последовательность городов. Между ве-
личинами L и L ' ' (длинами оптимальных маршрутов) будет существовать сле-
дующее соотношение: L =L ' '+S . Отсюда следует очевидное неравенство:
L ≥S , то есть сумма приводящих констант является нижней оценкой целевой
функции исходной задачи коммивояжера.
Конкретизируем теперь основные этапы метода ветвей и границ применитель-
но к данной задаче.
Пусть Ω 0 - множество всех возможных маршрутов.
1) Ветвление. При ветвлении очередное множество Ω k разбивается на два
   подмножества следующим образом. В матрице Ck , соответствующей раз-