электронный учебник

"Экономико-математические методы"

 

На главную страницу

Целочисленное программирование

В конец страницы

13.4.1. Алгоритм Литтла, Мурти, Суини и Кэрел для задачи коммивояжера 

Идея метода ветвей и границ применительно к задаче о коммивояжере довольно прозрачна. Ветвление основано на следующем элементарном соображении: переезд из любого данного города i в любой другой город j может либо принадлежать оптимальному циклу коммивояжера, либо не принадлежать ему. При вычислении же границ используется тот факт, что изменение длин всех путей, приводящих в данный город, или всех путей, выводящих из данного города, на одну и ту же величину приводит к новой задаче, оптимальный план которой совпадает с оптимальным планом исходной задачи.

Формализуем теперь отдельные этапы общей схемы метода ветвей и границ.

1оЗадание множества . Множество  состоит из всех циклов.

2оЗадание множеств . Каждое из множеств   состоит из всех циклов, подчиненных дополнительным условиям следующих двух типов:

1) из i следует идти непосредственно в j – для всех упорядоченных пар (i, j), входящих в некоторое множество ;

2) из i запрещается идти непосредственно в j – для всех упорядоченных пар (i, j), входящих в некоторое множество .

3оВычисление оценки для Go. Приведение. Рассмотрим некоторый цикл . Пройденное по нему расстояние равно

.

Пусть .

Тогда

                                            (13.38)

и  

Далее, пусть     .

Тогда

(13.39)

и     (13.40)

Из (13.38), (13.39) и (13.40) получаем

Положим

(13.41)

Заметим, что

Описанное выше преобразование, позволяющее получить из исходной неотрицательной матрицы  новую неотрицательную матрицу  называется приведением, а сумма  - суммой приведенных констант. В каждой строке и в каждом столбце матрицы  содержится по крайней мере по одному нулю. Такую неотрицательную квадратную матрицу будем называть приведенной.

При этом имеет место следующая теорема.

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

.                        (13.42)

Доказательство непосредственно следует из соотношений (13.40) и (13.41).

Каждой вершине  дерева, которое строится в процессе решения, будет соответствовать своя оценка  и своя приведенная матрица .

4оРазбиение на подмножества (ветвление). Множество  при ветвлении разбивается ровно на два подмножества. По некоторому правилу (указанному ниже) выбирается пара городов  не входящая в множества  и , после чего производится ветвление:

.

Здесь  получается из  добавлением условия: “из r следует идти непосредственно в , а  получается из  добавлением условия: “из r запрещается идти непосредственно в . Формализуем это:

 Выбор пары (r ,l) при ветвлении базируется на следующих соображениях. Необходимо действовать таким образом, чтобы  с “наибольшей вероятностью” содержало оптимальный цикл, а  его не содержало. Естественно для этого выбрать (r, l) так, чтобы . Здесь через  обозначен элемент приведенной матрицы, отвечающий множеству , стоящий в строке r и столбце l.

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

.

Выбираем (r, l) так, что  было наибольшим:

,

где максимум берется по всем парам p, q, для которых .

5оВычисление планов (циклов). Если множество  состоит ровно из (n-1) элементов, то тем самым уже задан цикл, n-й элемент которого определен однозначно. В этом случае оценка  совпадает с длиной единственного цикла, входящего в .

6оПреобразование матрицы расстояний при ветвлении. Пересчет оценок. Рассмотрим разветвление

,

описанное в пункте 4о.

1) Рассмотрим сначала множество  и укажем правило перехода от матрицы  к матрице . Эта матрица содержит те же строки и столбцы, что и . Положим

Применяя к матрице  описанную выше процедуру приведения, получим матрицу .

При этом сумма приводящих констант равна , поэтому оценкой для  будет

.

2) Обратимся теперь к множеству  и оценим правило перехода от матрицы  к матрице . По определению  заведомо содержит непосредственный переход из r в l. Поэтому при переходе от матрицы  к матрице  можно, не внося никаких поправок в оценку, вычеркнуть строку r и столбец l. В результате получим матрицу .

Далее следует проверить, не состоит ли  ровно из одного цикла. Если это так, то следует применить к матрице процесс приведения и, получив сумму приводящих констант h, пересчитать оценку:

.

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

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

Теперь, применив к матрице  процесс приведения и найдя сумму приводящих констант h, пересчитаем оценку по прежнему правилу:

.

Конечность алгоритма непосредственно следует из конечности числа всех циклов в рассматриваемой задаче.

        Пример. Имеется 6 пунктов, которые должен посетить коммивояжер по одному разу, минимизируя пройденный путь, и вернуться в исходный город. Расстояния между городами заданы матрицей

 Запишем математическую модель задачи:

Требуется минимизировать

при условиях

        Условимся вершину, из которой осуществляется ветвление, обозначать через Х. Вершину, которая, наиболее вероятно, принадлежит перспективной ветви, обозначим через Y, а вершину с запрещенной парой городов

1. Осуществим vNachале приведение по строкам, затем по столбцам, записав приводящие константы соответственно справа и снизу.

 

Находим минимальный элемент в каждой строке и вычитаем его из всех элементов соответствующей строки. Получим матрицу :

 Находим минимальный элемент в каждом столбце и вычитаем его из всех элементов соответствующего столбца. Получим матрицу :

 В матрице  в каждой строке и каждом столбце есть по крайней мере один “нуль”. Этим “нулям” соответствуют кратчайшие расстояния.

 2. Вычислим сумму приводящих констант

 3. Выбираем пару претендентов на ветвление, т.е. те , для которых

3.     Для выделенных претендентов на включение в Y подсчитаем

 5. Выберем . Пара (1,4) включается в множество Y и является запретной для множества .

6. Подсчитаем оценку для множества :

.

7. Так как из каждого города можно выезжать только один раз, то естественно первую строку из дальнейшего рассмотрения исключить. Так как в каждый город можно въезжать только один раз, то четвертый столбец исключается. Вычеркиваем 1-ю строку и 4-й столбец в матрице . Расставим запреты, которые могут привести к подциклам; в клетке (4,1) поставим “”.

8. Произведем приведение полученной матрицы и, определив сумму приводящих констант, найдем оценку для множества Y:

    

 Сумма приводящих констант: .

Полученная матрица не является матрицей 2 х 2, поэтому, не проверяя условие оптимальности, получим оценку для Y:

Процесс повторяется с пункта 4. Так как матрица приведенная, то выделим претендентов на ветвление:

По известной формуле подсчитаем для выделенных пар  и найдем :

.

9. Пара (2,1) выбирается для ветвления, после чего строка с номером 2 и столбец с номером 1 вычеркиваются. Расставим запреты, которые могут привести к подциклам; в клетке (4,2) поставим “” ((1,4), (2,1)).

Произведем приведение полученной матрицы и определим сумму приводящих констант:

           

. Найдем оценку множества Y: .

Вновь полученная матрица является приведенной. Снова повторим весь процесс. Выделим претендентов на ветвление:

Вычислив

найдем  .

Отсюда  .

Выполнив пункты 7 и 8, получим матрицу и оценку для множества Y, а именно:

        

 .

Повторим процесс - ветвление и выделение новых претендентов:

Выберем для ветвления пару (3,5); оценка для

.

В результате уже известных преобразований находим:

        

;   .

Полученная матрица 2 х 2 допускает включение только двух пар (4,3) и (6,2). Получили цикл

t ={(1,4), (2,1), (5,6), (3,5), (4,3), (6,2)}

Итак, имеем маршрут , длина которого l(t)=63.

Значение целевой функции F(X)=16+25+5+5+5+7=63.

Мы получили допустимый маршрут. Проверим его на оптимальность:

 

 

 

 

 

 


 

 Анализируя полученные ранее оценки для неветвленных множеств, видим, что неветвленное множество  имеет меньшую оценку. Это множество может привести к образованию цикла с меньшей оценкой, поэтому должно быть подвергнуто анализу. Остальные же подмножества имеют оценки, не меньшие, чем 63 и поэтому рассматривать их не будем.

Подмножество  является левым, поэтому для его анализа следует:

а) записать матрицу , поставить запрет в клетке (1, 4) и произвести приведение;

б) проводить анализ по уже описанной схеме.

Исходная матрица с запретом пары (1, 4) имеет вид

C=      

 Сумма приводящих констант

Выявим претендентов на ветвление:

Так как , то для ветвления выбирается пара (6,3); .

Вычеркиваем 6-ю строку и 3-й столбец, в клетке (3,6) ставим запрет:

     

Имеем

Не являясь полным циклом, полученный маршрут имеет оценку, равную оценке замкнутого маршрута t. Так как элементы матрицы  неотрицательные, нельзя, исходя из , получить маршрут меньшей длины.

Следовательно, найденный цикл t является оптимальным.

 

Назад     К началу страницы    Вперед