Раздел 7. Теория оптимального управления и оптимизация на графах
Тема 26. Задача динамического программирования
Задача 1. Туристическая компания “Супертранс” предлагает билеты на авиарейсы:
Рейс Цена (в условных единицах)
1. Москва – Новосибирск 105
2. Москва – Иркутск 175
3. Москва – Алма-Ата 210
4. Москва – Рим 200
5. Новосибирск – Якутск 85
6. Новосибирск – Иркутск 75
7. Новосибирск – Хабаровск 80
8. Новосибирск – Владивосток 130
9. Иркутск – Якутск 80
10. Иркутск – Хабаровск 35
11. Якутск – Хабаровск 40
12. Якутск – Владивосток 50
13. Хабаровск – Владивосток 25
14. Хабаровск – Пекин 120
15. Алма-Ата – Иркутск 60
16. Алма-Ата – Токио 280
17. Алма-Ата – Пекин 150
18. Рим – Пекин 250
19. Рим – Токио 300
20. Пекин – Токио 110
21. Владивосток – Токио 160
Начертите граф авиалиний компании и найдите в нём минимальный по стоимости маршрут из Москвы в Токио.
Задача 2. Инвестиционная компания “Русский Клондайк” намерена вложить 6 миллионов рублей в нефтяной проект, производство напитков и строительство коттеджей. Зависимость ожидаемой прибыли от вложенной в дело суммы, установленная в результате маркетинговых исследований фирмы, представлена в таблице (по вариантам). Найдите оптимальную схему капитальных вложений.
Таблица 1.3.а.
-
Вложенная сумма (млн. руб.)
Нефтяной проект
Произв-во напитков
Строит-во коттеджей
1
0,14
0,9
0,11
2
0,26
0,17
0,20
3
0,39
0,22
0,29
4
0,45
0,26
0,37
5
0,50
0,27
0,44
6
0,53
0,28
0,48
Таблица 1.3.б.
-
Вложенная сумма (млн. руб.)
Нефтяной проект
Произв-во напитков
Строит-во коттеджей
1
0,10
0,12
0,8
2
0,17
0,22
0,15
3
0,25
0,29
0,21
4
0,31
0,34
0,26
5
0,40
0,40
0,30
6
0,50
0,49
0,33
Литература: [4, 5]
Учебно-методическая литература: [8]
Тема 27. Теория оптимального управления
Решить задачи:
3.a
;
x(0) = 0;u
1.
3.б
g = – k x1(2) + x2(2) min
0 u 1
Литература: [5, 14, 15]
Тема 28. Основы теории графов
Основные понятия
4. Для графов, приведенных на рис.1., выполните следующие задания:
1) определите степени и полустепени вершин;
2) укажите содержащиеся в них:
а) контуры (циклы),
б) петли,
в) узлы,
г) висячие вершины;
3) определите, какие из графов являются:
а) ориентированными,
б) однородными,
в) полными,
г) мультиграфами.
1
.
х2
х3 2.
х2
х3
х1 х4 х1 х4
х3
3. 4.
х2
х3
х2
х4
х4
х1 х5 х1 х5
5. По заданным полустепеням вершин постройте, если это возможно, ориентированный граф:
1) Р+(хi)=1, P_(xi)=1, i=1,…,4;
2) P+(x1)=P+(x2)=P_(x2)=P_(x3)=1,
P+(x3)=P_(x1)=2;
3) P+(xi)=i, P_(xi)=6-i, i=1,…,5.
6. По данной матрице смежности постройте ориентированный граф и, если это возможно, неориентированный граф. Определите степени и полустепени вершин.
1
) 0
1 0 2) 0 1 1 3) 0 1 1 1 4) 0 1 1 1
1 0 1 1 0 0 0 0 0 0 1 0 0 0
1 0 0 1 0 0 0 1 0 1 0 1 0 1
0 1 1 0 1 0 0 1
Литература: [15, 19]
Учебно-методическая литература: [8]