Лабораторная работа № 6

Лабораторная работа 7Телешовой Елизаветы, гр. 726,Решение задачи коммивояжера методом ветвей и границ.1. И решил колобок, что пока он остывает, он вполне может обежать лес, посмотретьна лесных жителей и снова вернуться к деду и бабке. Сказано сделано. Спрыгнулколобок из окошка и покатился в лес. Помогите колобку найти кратчайший маршрутего движения по лесу, если расстояния между норами лесных

жителей, а такжедомом деда и бабки даны в таблице. Дед и бабка Заяц Волк Медведь Лиса Дед и бабка 2 Заяц 6 0 3 3,5 4,5 Волк 4 3 0 5,5 Медведь 5 3,5 5,2 Лиса 2 4,2.Математическая модель задачи.Для решения задачи присвоим каждому пункту маршрутаопределенный номер дед и бабка 1, заяц 2, волк 3, медведь 4 и лиса 5.

Соответственно общее количество пунктов . Далее введем альтернативныхпеременных , принимающих значение 0, если переход из i-того пункта в j-тый не входит в маршрут и 1 в противном случае.Условия прибытия в каждый пункт и выхода из каждого пункта только по одномуразу выражаются равенствами 1 и 2 . 1 2 Для обеспечения непрерывности маршрута вводятсядополнительно n переменных и дополнительныхограничений 3 . 3 Суммарная протяженность маршрута F, которую необходимо минимизировать, запишется вследующем виде 4

В нашем случае эти условия запишутся в следующем виде 3. Решениезадачи методом ветвей и границ.1 Найдем оценку снизу Н. Для этого определяемматрицу минимальных расстояний по строкам 1 где расстояние минимально встроке . gt Аналогичноопределяем матрицу минимальных расстояний по столбцам. gt Выберемначальный план . Тогда верхняя оценка .Очевидно,что , где означает переход изпервого пункта в

j-тый. Рассмотрим эти подмножествапо порядку. 2 Анализ подмножества D3 Анализ подмножества D4 Анализ подмножества D5 Анализ подмножества D6 Отсев неперспективных подмножеств. Подмножества D13 и D15неперспективные. Т.к но , то далее будем рассматривать подмножество D7 Анализ подмножества D8 Анализ подмножества

D9 Анализ подмножества D10 Отсев неперспективных подмножеств. Подмножество D143 неперспективное. Т.к но , то далее будем рассматривать подмножество D9 Анализ подмножества D9 Анализ подмножества D1453. Оптимальноерешение Таким образом, маршрутколобка дед и бабка медведь лиса заяц волк дед и бабка.