Лабораторная работа № 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. ; ; ; ; ; ; Оптимальное решение: . .
Таким образом, маршрут колобка: дед и бабка – медведь – лиса – заяц – волк – дед и бабка.