- •Глава 9. Динамическое программирование
- •9.1. Как работает метод дп
- •Функциональное уравнение дп
- •Распределение одного вида ресурса
- •Задача организации выпуска m видов продукции
- •9.5. Задача о кратчайшем пути
- •9.6. Задача с мультипликативным критерием
- •9.7. Усложненная задача
- •9.8. Многомерные задачи динамического программирования
- •9.9. Снижение размерности с помощью множителей Лагранжа
- •9.10. Задания для самостоятельной работы
- •Варианты 1.1 - 1.3
- •Варианты 2.1 - 2.3
- •Варианты 3.1 - 3.3
- •Варианты 4.1 - 4.3
- •Варианты 5.1 - 5.3
- •Варианты 6.1 - 6.3
- •Варианты 7.1 - 7.3
- •Варианты 8.1 - 8.3
- •Варианты 9.1 - 9.3
- •Варианты 10.1-10.3
- •Варианты 11.1 - 11.3
- •Варианты 12.1 - 12.3
- •Варианты 13.1 - 13.3
- •Варианты 19.1 - 19.3
- •Варианты 15.1 - 15.3
- •Варианты 16.1 - 16.3
- •Варианты 17.1 - 17.3
- •Варианты 18.1 - 18.3
- •Варианты 19.1 - 19.3
- •Варианты 20.1 - 20.3
- •Варианты 21.1 - 21.3
- •Варианты 22.1 - 22.3
- •Варианты 23.1 - 23.3
- •Варианты 24.1 - 24.3
- •Варианты 25.1 - 25.3
- •Варианты 26.1 - 26.3
- •Варианты 27.1 - 27.2
- •Варианты 28.1 - 28.3
- •Варианты 29.1 - 29.3
- •Варианты 30.1 - 30.2
Варианты 19.1 - 19.3
Обработка информации осуществляется пятью последовательно включенными вычислительными устройствами (ВУ). Известна продолжительность однократного счета на каждом из ВУ - ti (табл. 20). Для повышения достоверности обработки применяется повторный счет на отдельных ВУ. Зависимость вероятности получения правильного результата от числа повторностей счета Р(к) дана в аналитическом виде (табл. 21).
Определить вариант обработки информации, обеспечивающий вероятность получения правильного результата не хуже за минимальное время счета.
Вывести функциональное уравнение для случая максимизации при заданном общем времени счета.
Таблица 20
Вариант |
t1 |
t2 |
t3 |
t4 |
t5 |
|
19.1 |
7 |
2 |
5 |
3 |
4 |
0,7-0,9 |
19.2 |
3 |
8 |
6 |
2 |
7 |
0,8-0,95 |
19.3 |
5 |
1 |
9 |
8 |
6 |
0,9-0,97 |
Таблица 21
Вариант |
Р1(к) |
Р2(к) |
Р3(к) |
Р4(к) |
Р5(к) |
19.1 |
1- 0,1к |
1- 0,5к |
1- 0,82к |
1- е -к |
1- 0,2к |
19.2 |
1- 20,6 к + 0,8кк |
1- е -2к |
1- 0,1к |
1- 0,2к |
1- |
19.3 |
1- 0,5кк |
1- 0,2к |
1- е -1,5 к |
1- 40,1к |
1- е -к |
Варианты 15.1 - 15.3
Проектируется строительство дороги с четырьмя перегонами (табл. 22). Капитальные (приведенные) и эксплуатационные затраты зависят от длины перегона li: с уменьшением li первые возрастают из-за увеличения объема земляных работ, а вторые снижаются .
Спроектировать дорогу общей длиной не более L с минимальными затратами.
Записать функциональное уравнение для случая минимизации длины при заданном уровне затрат.
Примечание: для упрощения расчетов считать, что эксплуатационные затраты даны на весь период эксплуатации дороги.
Таблица 22
Ва- |
Перегоны |
L, км | |||
риант |
1 |
2 |
3 |
4 | |
|
Ск=200/ |
Cк=50+400/l |
Cк=120-3l |
Cк=20l-0,5l2 |
40-50 |
15.1 |
Cэ=40+2l |
Cэ=60(1-e -0,1l ) |
Cэ=70+8 |
Cэ=40 | |
|
5 l 10 |
10 l 16 |
4 l 10 |
20 l 26 | |
|
Cк=180-2l |
Cк=580/ |
Cк=630/l |
Cк=120/(1-e -0,1l ) |
60-70 |
15.2 |
Cэ=90(1-е -0,2l ) |
Cэ=110+2l |
Cэ=80+9 |
Cэ=40+2 | |
|
10 l 16 |
21 l 27 |
14 l 20 |
7 l 12 | |
|
Cк=20+15l-0,5l2 |
Cк=200/(2+0,1l) |
Cк=70+350/l |
Cк=170-10 |
55-65 |
15.3 |
Cэ=240l/(l+36) |
Cэ=30+12 |
Cэ=30+5l |
Cэ=130(1-e -0,1l ) | |
|
18l 25 |
10 l 16 |
8 l 14 |
16 l 23 |