Читайте также:
|
Решим ту же задачу, что и в методе динамического программирования
Тогда матрица выглядит следующим образом:
0 3 4 1
S= 2 0 2 3
5 2 0 4
2 2 5 0
| 11/9 |
| 11/9 |
| 10/7 |
| 10/7 |
| 10/10 |
| 10/7 |
| 3 |
| 3 |
Будем обозначать Vn (ijk) - нижнюю оценку, проходящую через путь i-j-k
И Vv (ijk) - верхнюю оценку, проходящую через путь i-j-k
Найдем нижнюю оценку по строкам Vn = 1+2+2+2=7 и по столбцам Vn =2+2+2+1 =7
Тогда будем считать Vn=7
Используя Жадный алгоритм, найдем Vv = 1+2+2+5 =10 маршрут 1 ® 4 ® 2 ® 3® 1
Начнем ветвление из вершины 1 в вершины 2 3 4.
Vn (12)=3+2+2+2=9 Vn (13)=4+2+2+2=10 Vn (14)=1+2+2+2=7
Vv (12) =3+2+4+2=11 Vv (13)=4+2+3+2=11 Vv (14)=1+2+2+5=10
Начнем ветвление из вершины 2 в вершины 3 4.
Vn (123) =9 Vn (124) =10
Vv (123) = 11 Vv (124) =16
Начнем ветвление из вершины 3 в вершины 2 4.
Vn (132) =10 Vn (134) =12
Vv (132) = 11 Vv (134) =12
Начнем ветвление из вершины 4 в вершины 2 3.
Vn (142) =7 Vn (143) =10
Vv (142) = 1+2+2+5=10 Vv (143) =1+5+2+2=10
В нашем случае, получается 2 равнозначных маршрута, оба они являются оптимальными – 1 ® 4 ® 2 ® 3® 1 или: 1 ® 4 ® 3 ® 2® 1
Бикритериальная задача коммивояжера.
0 3 4 1
S= 2 0 2 3
5 2 0 4
2 2 5 0
0 4 2 1
Т= 2 0 3 3
1 3 0 2
2 4 2 0
Будем обозначать Vn (ijk) и Un (ijk) - нижние оценки, проходящие через путь i-j-k,
а Vv (ijk) и Uv (ijk) - верхние оценки, проходящие через путь i-j-k.
Из решения однокритериальной задачи мы знаем все Vn и Vv, остается найти Un и Uv.
Найдем нижнюю оценку по строкам Un = 1+2+1+2=6 и по столбцам Un =1+3+2+1 =7
Тогда будем считать Un=7
Используя Жадный алгоритм, найдем Uv = 1+2+3+2 =8
Начнем ветвление из вершины 1 в вершины 2 3 4.
Un (12)=4+2+1+2=9 Un (13)=2+2+1+2=7 Un (14)=1+3+2+1=7
Uv (12) =4+3+2+2=11 Uv (13)=2+2+4+2=10 Uv (14)=1+2+3+1=8
Начнем ветвление из вершины 3 в вершины 2 4.
Un (132) =2+2+3+2=9 Un (134) =2+2+2+2=8
Uv (132) = 2+3+3+2=10 Uv (134) =2+2+3+2=9
Начнем ветвление из вершины 4 в вершины 2 3.
Un (142) =1+4+2+1=8 Un (143) =1+3+2+1=7
Uv (142) = 1+4+3+5=9 Uv (143) =1+2+3+2=8
| 11/9
|
| 11/9
|
| 10/7 8/7 |
| 10/7 8/7 |
| 10/10 8/7 |
| 10/7 9/8 |
| (10;8) |
| 3 |
Оценка (10,8) определяет маршрут: 1 ® 4 ® 3 ® 2® 1
Список используемой литературы
Коган Д. Задачи и методы конечномерной оптимизации. –Н.Н: Издательство Нижегородского Университета, 2004.
Методическое пособие по курсу "Математические основы информатики" для студентов факультета ВМК специальности "Прикладная информатика"
Часть 3. /Нжег.гос.ун-т, 2004.
Таха Х. Введение в исследование операций.–М.: Мир,1985.
Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1987.
Акоф Р., Сасиени М. Основы исследования операций. –М.: Мир,1971.
Вентцель Е. С. Исследование операций: задачи, принципы, методология. –М.: Наука,1988.
Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. –М.: Наука,1965.
Дата добавления: 2015-10-26; просмотров: 203 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Практическое применение решения задачи Коммивояжера | | | Желінің компьютермен байланысы ....кабель түрлері арқылы жүреді |