Лабораторная работа № 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. Математическая модель задачи.
Для
решения задачи присвоим каждому пункту
маршрута определенный номер: дед и бабка
– 1, заяц – 2, волк – 3, медведь – 4 и лиса
– 5. Соответственно общее количество
пунктов
.
Далее введем
альтернативных переменных
,
принимающих значение 0, если переход из
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.
;
;
;
;
;
;
Оптимальное
решение:
.
.
Таким образом, маршрут колобка: дед и бабка – медведь – лиса – заяц – волк – дед и бабка.