Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)

Лабораторная работа № 7

Телешовой Елизаветы, гр. 726,

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

1. Постановка задачи.

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

2. Математическая модель задачи.

Для решения задачи присвоим каждому пункту маршрута определенный номер: дед и бабка – 1, заяц – 2, волк – 3, медведь – 4 и лиса – 5. Соответственно общее количество пунктов  альтернативных переменных i-того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (1) и (2).

                                                     (1)

                                                       (2)

Для обеспечения непрерывности маршрута вводятся дополнительно n переменных  и  дополнительных ограничений (3).

                                                 (3)

Суммарная протяженность маршрута F, которую необходимо минимизировать, запишется в следующем виде:

                                             (4)

В нашем случае эти условия запишутся в следующем виде:

  (1);                   (2);

                (3)

 (4)

3. Решение задачи методом ветвей и границ.

1) Анализ множества D.

Найдем оценку снизу Н. Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).

 =>

Аналогично определяем матрицу минимальных расстояний по столбцам.

 =>

;

Выберем начальный план:

Очевидно, что  означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку.

;

;

;

;