Лабораторнаяработа № 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