Материалы сайта
Это интересно
Лабораторные работы по Основам теории систем
Лабораторная работа № 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. Соответственно общее количество пунктов [pic]. Далее введем [pic] альтернативных переменных [pic], принимающих значение 0, если переход из i- того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (1) и (2). [pic] (1) [pic] (2) Для обеспечения непрерывности маршрута вводятся дополнительно n переменных [pic] и [pic] дополнительных ограничений (3). [pic] (3) Суммарная протяженность маршрута F, которую необходимо минимизировать, запишется в следующем виде: [pic] (4) В нашем случае эти условия запишутся в следующем виде: [pic] (1); [pic] (2); [pic] (3) [pic] (4) 3. Решение задачи методом ветвей и границ. 1) Анализ множества D. Найдем оценку снизу Н. Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке). [pic] => [pic]; Аналогично определяем матрицу минимальных расстояний по столбцам. [pic] => [pic]; [pic]; Выберем начальный план: [pic]. Тогда верхняя оценка: [pic]. Очевидно, что [pic], где [pic] означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку. 2) Анализ подмножества D12. [pic]; [pic]; [pic]; [pic]; [pic]; 3) Анализ подмножества D13. [pic]; [pic]; [pic]; [pic]; [pic] 4) Анализ подмножества D14. [pic]; [pic]; [pic]; [pic]; [pic]; 5) Анализ подмножества D15. [pic]; [pic]; [pic]; [pic]; [pic]; 6) Отсев неперспективных подмножеств. [pic]; Подмножества D13 и D15 неперспективные. Т.к. [pic], но [pic], то далее будем рассматривать подмножество D14. [pic]. 7) Анализ подмножества D142. [pic]; [pic]; [pic]; [pic]; [pic]; 8) Анализ подмножества D143. [pic]; [pic]; [pic]; [pic] [pic]; 9) Анализ подмножества D145. [pic]; [pic]; [pic]; [pic]; [pic]; 10) Отсев неперспективных подмножеств. [pic]; Подмножество D143 неперспективное. Т.к. [pic], но [pic], то далее будем рассматривать подмножество D145. [pic]. 9) Анализ подмножества D1452. [pic]; [pic]; [pic]; [pic]; [pic]; 9) Анализ подмножества D1453. [pic]; [pic]; [pic]; [pic]; [pic]; [pic]; Оптимальное решение: [pic]. [pic]. Таким образом, маршрут колобка: дед и бабка – медведь – лиса – заяц – волк – дед и бабка. ----------------------- [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] D12 D D13 D14 D15 D142 D143 D145 D1452 D1453 [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic]