ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
СБОРНИК
ЗАДАНИЙ ДЛЯ ПРАКТИЧЕСКИХ ЗАНЯТИЙ
по дисциплине
м«Анализ и моделирование систем Математическими методами»
для специальности 080802 (2205)
«Прикладная информатика»
(по отраслям)
Ульяновск
Мардамшина А.А.
Сборник заданий для практических занятий по дисциплине «Анализ и моделирование систем математическими методами». Методические указания для студентов. Ульяновск, 2011; УАвиаК, - стр.
Сборник предназначен для специальности 080802 (2205) «Прикладная информатика» (по отраслям).
Одобрен на заседании комиссии «Программирование и ИТ».
(Протокол № )
Печатается по решению редакционно-издательского совета
Ульяновского авиационного колледжа
Рецензенты:
| Камышова Г.А. | Преподаватель высшей категории Ульяновского авиационного колледжа |
| Кондратьев А.Е. | кандидат физико-математических наук, доцент кафедры Информационных Технологий факультета Математики и Информационных Технологий Ульяновского Государственного Университета |
Отзывы и предложения направлять по адресу:
432067, г. Ульяновск, проспект Созидателей, 13
телефон (8-422) 20-15-72,20-15-85
факс: 54-54-63
E-mail: aircol@mv.ru
© А.А. Мардамшина, 2011.
© Ульяновский авиационный колледж, 2011.
СОДЕРЖАНИЕ
ПРАКТИЧЕСКИЕ ЗАНЯТИЯ
№ 1 Симплексный метод.................................................................... 5
№ 2 Двойственный симплекс-метод.................................................. 8
№ 3 Транспортная задача................................................................. 11
№ 4 Метод множителей Лагранжа.................................................... 14
№ 5 Градиентные методы.................................................................. 17
№ 6-7 Теория игр............................................................................... 33
№ 8 Динамическое программирование............................................ 31
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №1
СИМПЛЕКСНЫЙ МЕТОД
(2 часа)
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №2
ДВОЙСТВЕННЫЙ СИМПЛЕКСНЫЙ МЕТОД
(2 часа)
1. F=5x1+2x2+6x3 max
x1+x2+x3<=6
2x1-x2+3x3<=9
3x1+x2+2x3>=1
2. F=7x1+13x2+8x3 max
x1+2x2<=3
x1+x3<=4
x1+3x2+2x3<=2
x1+x2<=5
3. F=x1+2x2+5x3+6x4 min
2x1+x2-x3+5x4>=5
3x1-2x2+x3-11x4>=4
4. F=x1+x2+x3 max
2x1+x2+x3<=2
4x1+2x2+x3<=2
5. F=27x1+10x2+15x3+28x4 max
3x1+2x2+x3+2x4<=2
3x1+x2+2x3+4x4<=5
6. F=6x1+8x2+x3 max
x1+x2+x3<=3
x1+2x2<=4
7. F=27x1+10x2+15x3 max
-2x1-3x2-2x3<=12
4x1-4x2-3x3<=4
5x1+5x2+3x3<=15
8. F=6x1+8x2+x3 max
x1+3x3-x4<=5
x2+2x3+x4<=7
x1+x2+x4<=3
9. F=2x1+6x2 min
x1+3x2-x3>=6
x2+3x3>=4
x1+x2+x3>=1
10. F=x1+4x4 max
x2+x3<=4
x1-x2+x3+x4<=3
x1-x2+2x3>=5
11. F=-x1+x2-x3 min
x1+2x2-x3<=5
2x2+x4<=3
x3+2x4<=6
12. F=3x1+2x2-6x3 max
x1-x2+x3<=1
3x1-2x2+2x3<=4
x1+3x2-4x3<=5
13. F=x1-x2+3x3+x4 min
x1-x2+2x3+3x4<=7
x1+2x2-x3+x4<=5
14. F=-2x1-x2-x3+x4 max
x1-2x2+x3+3x4<=4
-x1-x2+3x3+2x4<=10
15. F=4x1-2x2+x3-x4 max
x1+x2+4x3+2x4=2
x1+2x2-x3+3x4=3
16. F=x1+2x2+x3-x5-6 min
-x1+5x2+x3+x4+5=10
2x1-x2+x3-3x4=6
10x2+x3+2x4+3x5=24
17. F=-4x1+2x2-3x4-x5 max
3x1+x2+x3-x4=2
4x1-x2+x4+x5=21
4x1-x2+x5=15
18. F=4x1-x2-9x3+x4 max
x1+x2-2x3+2x4=2
x1+2x2-x3+3x4=3
19. F=x1-x2 max
4x1-3x2-x3+x4+x5=6
x1+4x2+x3+x5=15
2x1-4x2-x3+x4=-3
20. F=x1-x2+x3-x4 max
x1-2x2-x3+3x4=4
x2+2x3+x4=1
x1+4x3+x4=6
21. F=3x2+x3+2x4 max
3x1+x2+x3-x4=5
3x1-x2+2x3+4x4=1
22. F=x1-4x2+2x3-3x4+x5 min
x1+x2+x3+x4+x5=2
x1-x2+x4=1
x1-9x2+x3=5
23. F=x1+x2-15x3+x4 max
x1+x2+x3=4
3x2+2x3-x4+x5=6
x1-x2-6x3+x4=12
24. F=x1-x2+2x3 min
x1+x2+2x3+x5=3
x1-x2-4x3+x4=0
x1+x2-x3=2
25. F=x1-2x2+5x3 max
2x1+2x2+4x3<=18
2x1+x2-3x3<=20
5x1-3x2+6x3>=19
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №3
ТРАНСПОРТНАЯ ЗАДАЧА
(2 часа)
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №4
МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА
(2 часа)
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №5
ГРАДИЕНТНЫЕ МЕТОДЫ
(2 часа)
1. 
max при условиях 
и 
2. 
max при условиях 
и
3. 
max при условиях 
и 
4. 
max при условиях 
5. 
и
6. 
и
7. 
и
8. 
при условиях 
9. 
при условиях 
10. 
при условиях 
11. 
при условиях 
12. 
при условиях 
13. 
при условиях 
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №6-7
ТЕОРИЯ ИГР
(6 часов)
1. Два игрока одновременно показывают один, два или три пальца. Если общее количество чётное, то второй игрок платит первому это количество в рублях, а если нечётное, то первый платит второму это количество в рублях.
2. У стороны A имеется три типа вооружения, у стороны B – три типа самолётов. Первый тип вооружения поражает типы самолётов соответственно с вероятностями 0,5, 0,6 и 0,8, второй тип – с вероятностями 0,9, 0,7 и 0,8, третий тип – с вероятностями 0,7, 0,5 и 0,6. Сторона A может выбрать только один тип вооружения, а сторона B – один тип самолётов. Какие типы вооружения и самолёта следует выбрать сторонам?
3. Сторона A посылает в район противника B два бомбардировщика, один летит впереди другого. Один из бомбардировщиков (неизвестно какой) несёт бомбу, второй его прикрывает. В районе противника самолёты атакуются одним истребителем. Если истребитель атакует задний бомбардировщик, то его обстреливают пушки только этого бомбардировщика, а если истребитель атакует передний бомбардировщик, то его обстреливают пушки обоих бомбардировщиков. Один бомбардировщик поражает истребитель с вероятностью 0,3, а оба – с вероятностью 0,51. Если истребитель не сбит, то он сбивает бомбардировщик с вероятностью 0,8. Цель стороны A уничтожить объект, а стороны B защитить объект.
4. Сторона A двумя самолётами атакует объект, который сторона B защищает тремя орудиями. Самолёты могут выбирать для атаки только одно из трёх направлений, не меняя его в дальнейшем. Любое орудие может быть размещено на любом из трёх направлений. Каждое орудие простреливает только область пространства, относящуюся к направлению, на которое оно установлено. Каждое орудие может обстрелять только один самолёт, который достоверно сбивается. Прорвавшийся к объекту любой из самолётов уничтожает его. Цель стороны A уничтожить объект, а стороны B защитить объект.
5. Вариант игры № 4. Условия игры те же, что и в игре № 4, но для стороны A возможны четыре направления подхода, а у сторона B обладает четырьмя орудиями.
6. Сторона A тремя батальонами атакует объект, который сторона B защищает четырьмя батальонами. Каждый из наступающих батальонов может быть направлен к объекту по любой из двух дорог, сторона B может разместить свои батальоны на любой из дорог. Если на дороге атакующих батальонов больше, то они прорывают оборону и уничтожают объект, если обороняющихся батальонов больше, то они отбивают нападение, если же на дороге встречаются одинаковое количество батальонов, то нападающие с вероятностью 0,4 прорывают оборону и уничтожают объект, а с вероятностью 0,6 атака отбивается. Требуется дать рекомендации сторонам по количеству батальонов, которое следует направить на каждую из дорог.
7. Сторона A располагает тремя видами вооружения A1, A2 и A3, а сторона B – тремя видами помех B1, B2 и B3. Вероятность решения боевой задачи стороной A при различных видах вооружения и помех задаётся матрицей
| B A | B1 | B2 | B2 |
| A1 | 0,8 | 0,2 | 0,4 |
| A2 | 0,4 | 0,5 | 0,6 |
| A3 | 0,1 | 0,7 | 0,3 |
Сторона A стремится решить боевую задачу, сторона B воспрепятствовать этому.
8. Двое игроков в тайне друг от друга пишут на листке бумаги натуральное число от 1 до 5, после чего листки открываются. Если написанные числа оказались равными, то ничью (оба выигрывают по 0 рублей), если числа отличаются на 1, то тот, у которого число больше, выигрывает 2 рубля, в остальных случаях выигрывает 1 рубль тот, у кого число меньше.
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №8
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
(4 часа)