Лабораторная работа № 7
Телешовой Елизаветы, гр. 726,
Решение задачи коммивояжера методом ветвей и границ.
1. Постановка задачи.
Испекла бабка колобок и поставила его остывать на окошко. И решил
колобок, что пока он остывает, он вполне может обежать лес, посмотреть
на лесных жителей и снова вернуться к деду и бабке. Сказано – сделано.
Спрыгнул колобок из окошка и покатился в лес. Помогите колобку найти
кратчайший маршрут его движения по лесу, если расстояния между норами
лесных жителей, а также домом деда и бабки даны в таблице.
Дед и бабка Заяц Волк Медведь Лиса
Дед и бабка 0 6 4 5 2
Заяц 6 0 3 3,5 4,5
Волк 4 3 0 5,5 5
Медведь 5 3,5 5,5 0 2
Лиса 2 4,5 5 2 0
2. Математическая модель задачи.
, принимающих значение 0, если переход из i-того пункта в j-тый не
входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт
и выхода из каждого пункта только по одному разу выражаются равенствами
(1) и (2).
(1)
(2)
дополнительных ограничений (3).
(3)
Суммарная протяженность маршрута F, которую необходимо минимизировать,
запишется в следующем виде:
(4)
В нашем случае эти условия запишутся в следующем виде:
(2);
(3)
(4)
3. Решение задачи методом ветвей и границ.
1) Анализ множества D.
Найдем оценку снизу Н. Для этого определяем матрицу минимальных
расстояний по строкам (1 где расстояние минимально в строке).
;
Аналогично определяем матрицу минимальных расстояний по столбцам.
;
;
. Тогда верхняя оценка:
.
означает переход из первого пункта в j-тый. Рассмотрим эти
подмножества по порядку.
2) Анализ подмножества D12.
;
;
;
;
;
3) Анализ подмножества D13.
;
;
;
;
4) Анализ подмножества D14.
;
;
;
;
;
5) Анализ подмножества D15.
;
;
;
;
;
6) Отсев неперспективных подмножеств.
;
, то далее будем рассматривать подмножество D14.
.
4) Анализ подмножества D142.
;
;
;
;
;
Дед и бабка Заяц Волк Медведь Лиса
Дед и бабка 0 6 4 5 2
Заяц 6 0 3 3,5 4,5
Волк 4 3 0 5,5 5
Медведь 5 3,5 5,5 0 2
Лиса 2 4,5 5 2 0
PAGE
PAGE 3
Нашли опечатку? Выделите и нажмите CTRL+Enter
