Рефераты по теме Теория систем управления
Реферат Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ) ) скачать бесплатно
Скачать реферат ↓ [280.63 KB]
Текст реферата Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ) )
Лабораторная работа № 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. Соответственно общее количество пунктов альтернативных переменных i-того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (1) и (2).(1)
(2)
Для обеспечения непрерывности маршрута вводятся дополнительно n переменных и дополнительных ограничений (3).
(3)
Суммарная протяженность маршрута F, которую необходимо минимизировать, запишется в следующем виде:
(4)
В нашем случае эти условия запишутся в следующем виде:
(1); (2);
(3)
(4)
3. Решение задачи методом ветвей и границ.
1) Анализ множества D.Найдем оценку снизу Н. Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).
=>
Аналогично определяем матрицу минимальных расстояний по столбцам.
=>
;
Выберем начальный план:
Очевидно, что означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку.
© Copyright 2011-2015 nReferat.ru - All Rights Reserved |