Лабораторная работа №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. Соответственно общее количество пунктов . Далее введем альтернативных переменных , принимающих значение 0, если переход из i-того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (1) и (2).
(1)
(2)
Для обеспечения непрерывности маршрута вводятся дополнительно n переменных и дополнительных ограничений (3).
(3)
Суммарная протяженность маршрута F, которую необходимо минимизировать, запишется в следующем виде:
(4)
В нашем случае эти условия запишутся в следующем виде:
(1); (2);
(3)
(4)
3. Решение задачи методом ветвей и границ.
1) Анализ множества D.
Найдем оценку снизу Н. Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).
=> ;
Аналогично определяем матрицу минимальных расстояний по столбцам.
=> ;
;
Выберем начальный план: . Тогда верхняя оценка:
.
Очевидно, что , где означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку.
|
;
;
;
;
;
|
;
;
;
;
|
;
;
;
;
;
|
;
;
;
;
;
6) Отсев неперспективных подмножеств.
;
Подмножества D13 и D15 неперспективные. Т.к. , но , то далее будем рассматривать подмножество D14.
.
|
;
;
;
;
|
8) Анализ подмножества D143.
;
;
;
|
9) Анализ подмножества D145.
;
;
;
;
;
10) Отсев неперспективных подмножеств.
;
Подмножество D143 неперспективное. Т.к. , но , то далее будем рассматривать подмножество D145.
.
|
;
;
;
;
;
|
;
;
;
;
;
;
Оптимальное решение: .
.
Таким образом, маршрут колобка: дед и бабка – медведь – лиса – заяц – волк – дед и бабка.
Больше работ по теме:
Не выбран
Лабораторная работа №4 по "Основам теории систем" (Послеоптимизационный анализ задач линейного прогр...
Не выбран
Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного програм...
Не выбран
Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс...
Не выбран
Лабораторная работа №6 по "Основам теории систем" (Решение задачи о ранце методом ветвей и границ)
Не выбран
Предмет: Информатика, ВТ, телекоммуникации
Тип работы: Не выбран
Новости образования
22 Июля 2016 16:26
Более 70 представителей крупных вузов АСЕАН подтвердили участие в форуме во Владивостоке
22 Июля 2016 12:51
Абызов: публикация первичных статсведений снизит бюрократическую нагрузку на школы
22 Июля 2016 11:53
В Чечне свыше 200 школьников сдали ЕГЭ с результатом свыше 90 баллов - министр
22 Июля 2016 05:36
Замглавы Минобрнауки РФ: задача сократить число людей с высшим образованием не стоит
21 Июля 2016 20:19
КОНТАКТНЫЙ EMAIL: [email protected]
Скачать реферат © 2017 | Пользовательское соглашение
ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ