Практическая часть. Решение задачи о коммивояжере методом ветвей и границ
Постановка задачи
Имеется n городов коммивояжере нужно проехать все n городов, начиная с первого, побывать в каждом городе ровно один раз и вернуться в первый город. Известны издержки переезда cij из города i в j.
Требуется найти такой маршрут переезда, который бы минимизировал бы суммарные издержки от переезда
-
называется гамельктоновым циклом – замкнутый цикл с прибыванием в каждом городе 1 раз.
T – все возможные гамельктоновые циклы.
Математическая задача будет ставится следующим образом:
Найти 
, который минимизировал бы
т.к. T – конечное множество, следовательно это задача дискретного программирования, поэтому можно методом ветвей и границ.
Дискретное программирование. Метод ветвей и границ
Постановка задачи дискретного программирования
на 
– конечное несчетное множество.
Общая схема метода ветвей и границ решения ЗДП
. В начале процесса 
разбивается на 
подмножеств:
В начале должна быть вычислена величина 
– нижняя оценка оптимального значения 
на , т.е. если 
- решение ЗДП, то
(1)
.
Для всех подмножеств в 
, полученных в результате разбиения, должна быть вычислена верхняя оценка 
функции 
на .
Величины и 
используются для сужения области поиска решения ЗДП. А именно если выполняется условие 
(2).
(2)
означает, что 
на множестве функция не достигает своего максимума, следовательно в дальнейшем подмножество можно не рассматривать при решении задачи.
Предположим (2) выполнено для 
, т.е. их нужно выбросить из рассмотрения. Потом корректируем 
, на графе они просто вычеркиваются. Рассматриваем только оставшиеся висячие вершины подмножества. Для продолжения решения выбираем для разбиения следующее подмножество.
Выбираем следующее для разбиения подмножество из условия:
(4)
Пусть 
разбивается на 
, переобозначим
Для каждого из этих подмножеств вычисляем:
(5)
Проверяем условие (5).
Пусть условие (5) выполняется для 
(6).
Нужно скорректировать два подмножества и 
В дальнейшем будем рассматривать только те подмножества, которые на графе являются висячими вершинами, т.е. нерассмотренные.
Дальнейший процесс решения задачи можно построить двумя способами.
Граф:
Первый способ:
Для дальнейшего разбиения выбирается подмножество из подмножеств, полученных в результате последнего разбиения 
, например:
