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

Лабораторнаяработа № 7
ТелешовойЕлизаветы, гр. 726,Решение задачи коммивояжера методомветвей и границ.1. Постановка задачи.
Испекла бабка колобок и поставила его остывать наокошко. И решил колобок, что пока он остывает, он вполне может обежать лес,посмотреть на лесных жителей и снова вернуться к деду и бабке. Сказано –сделано. Спрыгнул колобок из окошка и покатился в лес. Помогите колобку найтикратчайший маршрут его движения по лесу, если расстояния между норами лесныхжителей, а также домом деда и бабки даны в таблице.
Дед и бабка
Заяц
Волк
Медведь
Лиса
Дед и бабка
6
4
5
2
Заяц
6
3
3,5
4,5
Волк
4
3
5,5
5
Медведь
5
3,5
5,5
2
Лиса
2
4,5
5
2 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-тый. Рассмотрим эти подмножества по порядку.

2) Анализподмножества D12.
;





3) Анализ подмножества D13.
;





4) Анализ подмножества D14.
;





5) Анализ подмножества D15.
;





6) Отсев неперспективных подмножеств.

Подмножества D13и D15 неперспективные. Т.к. D14.
.

7) Анализ подмножества D142.
;





8) Анализ подмножества D143.
;





9) Анализ подмножества D145.
;




10) Отсев неперспективных подмножеств.

Подмножество D143неперспективное. Т.к. D145.
.

9) Анализ подмножества D1452.
;





9) Анализ подмножества D1453.
;






Оптимальное решение:

Такимобразом, маршрут колобка: дед и бабка – медведь – лиса – заяц – волк – дед ибабка.

D
D12
D13
D14
D15
D142
D143
D145
D1452
D1453