Специальные задачи математического  программирования. Задача  о коммивояжере.Метод  ветвей и границ.

Задача  о коммивояжере

Пусть имеется n маленьких городов. Коммивояжер, выходящий из какого-нибудь города должен посетить оставшиеся n-1 город и вернуться к исходному. Известны расстояния между каждой парой городов. Требуется установить порядок посещения причем так, чтобы общее пройденное расстояние (общая стоимость проезда) было минимальным.

Пусть C_ij – стоимость проезда из грода i в город j.

Введем  неизвестные X_ij – 0 или 1:

      X_ij= 1, в маршруте есть переезд из города I в город j

      0, else

      

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

      1.   2.

Здесь А – собственное  подмножество множества  городов; - количество элементов.

Если просуммировать все идентификации въезда и выезда - не должно быть больше общего количества городов-1.

 

Это комбинаторная  задача.

Всего вариантов  отхода (n-1)  !

Применение в  моделях сходных с этой:

• сбор по тревоге
• энергоснабжение
• телефоны
• определение оптимизационной последовательности обработки деталей
• балансирование сборочных линий.

Метод ветвей и границ

Относится к комбинаторным методам и  исходит из того, что число планов в задаче конечно. Центральная идея - замена полного перебора всех допустимых планов частично направленным.

Характерные черты:

• простая арифметика
• сложная логика
• нет ошибок округления.

Общие идеи:

Каждый раз  мы будем находиться в ситуации 

                 
 
 

Если  множество Х=множество, содержащее все циклы, то множество  - это все циклы, не содержащие пути (k,l), а множество Y – все циклы, содержащие пути (k,l).

При проверке признака оптимальности и выявлении множества ветвления сравниваются обязательно все нижние границы концевых вершин.  Как получить нижние границы?

Замечание:

• Гамильтонов контур – конечный путь, у которого начальная вершина совпадает с конечной и этот путь содержит все вершины.
• Элементарный путь – Путь, в котором никакая вершина не встречается дважды .
• Гамильтонов путь – Элементарный путь, проходящий через все вершины.

Граф  считается полным, если 2 любые вершины соединены хотя бы в одном направлении.

Таким образом, задача коммивояжера – задача отыскания Гамильтонова пути кратчайшей длины.

Пусть имеется некоторая матрица расстояний для задачи коммивояжера с 6 городами. 
 

            1 2 3 4 5 6 C_ij

1

2

3

4

5

6 

Замечание: Понимаем, что C_ij=0, но будем ставить вначале по диагонали.

  - запрет путешествия из города  I в город I–запрет цикла

      Также будем ставить запрет:

• C_ij             полагать равных , если в процессе решения отсутствие запрета дает цикл длины меньше, чем n.
• С_ji     
1. Предварительная операция: приведение матрицы.

Матрица приводится по строкам и по столбцам. Выделим  в каждой строке минимальный элемент.

            1 2 3 4 5 6 C_ij

1

2

3

4

5

6 

      

приведенных констант по строкам = 43

2. Приведем матрицу по столбцам.

Типичный  цикл исходной матрицы.

1 –  3 – 2 – 5 – 6 – 4 – 1

L=43+13+30+5+9+21=121 – Гамильтонов контур не кратчайшей длины, так как:

• каждый город повторяется 1 раз
• связность
• возвращаемся в город.

h – сумма приведенных констант. h=48   (43+5)

Никогда не может быть Гамильтонов контур < 48.

Замечание: Приведенная матрица содержит по крайней мере один 0 в каждом столбце и в каждой строке.

Около Y всегда выписывается оценка – сумма приведенных констант очередной интеграции (при движении вправо – h – нижняя граница издержек цикла при страой матрице).

3. Выбор (k,l) для предстоящего ветвления.

k,l – выбираются там, где максимальная оценка , то есть:

и этот max вычисляется для каждой строки.

При выявлении очередного участка Гамильтонова контура каждый раз следует запретить появление частичных контуров. Это запрещение осуществляется зачеркиванием соответствующего числа в матрице С и записыванием на его место .

Например, забегая вперед первой выбранной  парой городов будет 1 – 4. Естественно, запрещается путь 4 – 1, следовательно, поставим в эту клетку . В дальнейшем появится связка 1 – 4 – 5 – 6. Ясно, что нужно запретить 6 – 1. При появлении несвязанной пары городов 2 – 3(части будущего Гамильтонова контура) опять же запрещается элементарный цикл. При 2 – 3 запрещается 3 – 2.

Эти запреты, т.е. появление символов вместо чисел, существенно изменяют как вычисление h, так и особенно   на каждой итерации.

Сравнивая на концевых вершинах приписанные им ошибки и не делая разницы между  природой этих оценок ( или h) всегда выбирается наименьшее и ветвление идет там, где она достигается.

Возможен  возврат на более высокий уровень. 
 

            1 2 3 4 5 6 C_ij

1              10+0=10                                                                                                                                                                             

2   1+0=1

3   5+0=5

4   0+1=1, 0+0=0

5   2+0=2

6  0+0=0, 0+9=9, 0+2=2 

- наименьшая величина издержек  в строке I за исключением C_ij + наименьшая величина издержек в столбце j за исключением C_ij.

В левую  ветвь всегда прибавляется , в правую – h.

 W(x)=48 

    48+10=58       W(x)=W(x)+h

 

 
 

 48+1=49