Лабораторная работа 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. Оптимальноерешение Таким образом, маршрутколобка дед и бабка медведь лиса заяц волк дед и бабка.
| ! |
Как писать рефераты Практические рекомендации по написанию студенческих рефератов. |
| ! | План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом. |
| ! | Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач. |
| ! | Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты. |
| ! | Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ. |
| → | Виды рефератов Какими бывают рефераты по своему назначению и структуре. |