Решение задачи о коммивояжере методом ветвей и границ

Лабораторная работа 2

Постановка задачи. Бродячий торговец должен посетить п горо­дов и вернуться в исходный. Маршрут должен проходить через ка­ждый город, причем один и только один раз. Расстояния (транспорт­ные издержки, время на переезд и т.д.) между городами известны — . Требуется отыскать самый короткий (либо самый дешевый, либо самый быстрый и т.д.) маршрут.

Математическая модель:

(1)

(2)

(3)

— некоторый маршрут, L(x) — суммарные из­держки; (2) означает, что из каждого города торговец выезжает только раз; (3) означает, что в каждый город он въезжает один раз. К математи­ческой модели надо добавить дополнительное ограничение, исключающее замкнутые подциклы (подмаршруты) в маршрутах

Реализация метода ветвей и границ.

Рассмотрим дерево всевозможных маршрутов (см, рис.1, n = 5). Так как маршрут замкнут, то все равно из какого города начинать. Каждому маршруту соответствует ветвь дерева, начинающаяся на 1 уровне дерева в городе 1 и заканчивающаяся на последнем уровне в одном из городов. Ясно, что всего маршрутов (п — 1)!.

· С помощью дерева любое подмножество маршрутов можно раз­бить на более мелкие подмножества. Например, (см.рис.1), все множе­ство маршрутов можно разбить на четыре подмножества с начальными участками: {1, 2}, {1,3}, {1,4} и {1,5}. Причем каждое такое подмножество включает (5-2)!=3!=6 маршрутов дальнейших продолжений начального участка.

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

Например, пусть задана матрица транспортных издержек

Для нахождения оценки начального участка {1,2} — {1,2} строим под­матрицу матрицы С вычеркивая в ней первую строку и второй столбец. У полученной подматрицы находим минимальные элементы у строк. Отнимаем их от элементов соответствующих строк и получаем подматрицу . Находим у нее минимальные элементы у столбцов. В качестве оценки берется сумма минимальных элементов строк подматрицы и столбцов и длины начального участка

{1,2}=(7+8+5+4+0+7+0+4)+8=43

Для нахождения оценки для участка {1,5,3} у матрицы С вычеркиваются строки 1 и 5 и столбцы 5 и 3.

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

· Для вычисления рекорда итерации выбираются один либо несколько маршрутов. Вычисляются их длины. Рекордом r будет длина самого короткого из них. Соответствующий маршрут будет рекордным. На итерациях рекорд может быть улучшен.

· Если для некоторого подмножества маршрутов , то его (и соответствующую ветвь дерева) можно исключить как заведомо не содержащую лучшего маршрута, чем рекордный. Решение задачи заканчивается когда будут отсечены все ветви.

Пример (для матрицы (4)).

0итерация. .

Вычислим . Вычислим длину одного из маршрутов . Он и будет пока рекордным. Так как , то разбиваем X на 4 подмножества с начальными участками: (1,2), (1,3),(1,4),(1,5).

Вычислим их оценки:

Строим список множеств для 1 итерации: . Множество (1,4) отсекается, так как .

1 итерация. Вычислим .

Так как то продолжим итерации. Разбиваем множество с наименьшей оценкой (1,5) на 3 подмножества: (1,5,2), (1,5,3),(1,5,4). Вычислим их оценки: . Имеем

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

3итерация. .Разбиваем (1,2): (1,2,3), (1,2,4), (1,2,5). Имеем .

4 итерация. . Разбиваем (1,2,4): (1,2,4,3), (1,2,4,5). Вычислим . Новый рекорд 43.

5 итерация. Так как , то маршрут (1,2,4,3,5,1) — оптимальный, .

Дерево вариантов этой задачи имеет вид (см. рис. 2):

Рис.1

Рис.2.Дерево вариантов метода.

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

1) 2) 3)

4) 5) 6)

7) 8) 9)

10) 11) 12)

13) 14) 15)

16) 17) 18)

19) 20) 21)

22) 23) 24)

25) 26) 27)

28) 29) 30)