- •Глава 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
Варианты 24.1 - 24.3
Самолет имеет максимальную грузоподъемность G(т). Предметы, загружаемые в самолет, имеют различные веса и стоимости: wi(т), Сi (руб.) соответственно (табл. 32).
Определить оптимальную загрузку самолетов с грузоподъёмностью от G до 1,3G. Показать, как изменится решение, если j-х предметов нужно погрузить не меньше k.
Таблица 32
|
№ |
G |
W1 |
C1 |
W2 |
C2 |
W3 |
C3 |
W4 |
C4 |
W5 |
C5 |
W6 |
C6 |
j |
k |
|
24.1 |
20 |
0,8 |
12 |
3,2 |
60 |
4,0 |
72 |
6,5 |
11 |
2,8 |
50 |
2,1 |
15 |
1; 6 |
2 |
|
24.2 |
12 |
1,1 |
9,2 |
2,3 |
15 |
0,7 |
5,5 |
3,1 |
12 |
1,5 |
11 |
0,5 |
4 |
2; 4 |
1 |
|
24.3 |
15 |
2 |
4,5 |
1,2 |
3 |
0,6 |
2 |
1,5 |
5 |
3,0 |
4,2 |
1,1 |
3 |
3; 5 |
2 |
Варианты 25.1 - 25.3
На обработку информации выделено Т единиц времени. Обработка производится пятью последовательно включенными вычислительными устройствами (ВУ). Известна продолжительность однократного счета на каждом из ВУ - ti (табл. 33). Для повышения достоверности обработки применяется повторный счет на отдельных ВУ. Зависимость вероятности искажения информации от числа повторностей счета Pi(k) приведена в табл. 34.
Определить оптимальный вариант обработки информации.
Вывести функциональное уравнение для случая, когда задана общая допустимая вероятность искажения и необходимо минимизировать время обработки.
Таблица 33
|
Вариант |
t1 |
t2 |
t3 |
t4 |
t5 |
T, с |
|
25.1 |
2 |
1 |
5 |
3 |
7 |
45-50 |
|
25.2 |
6 |
3 |
1 |
8 |
4 |
52-60 |
|
25.3 |
4 |
2 |
7 |
3 |
5 |
50-55 |
Таблица 34
|
k |
P1(k) |
P2(k) |
P3(k) |
P4(k) |
P5(k) |
|
1 |
0,1 |
0,07 |
0,08 |
0,1 |
0,12 |
|
2 |
0,05 |
0,03 |
0,04 |
0,07 |
0,08 |
|
3 |
0,02 |
0,015 |
0,02 |
0,05 |
0,06 |
|
4 |
0,01 |
0,01 |
0,012 |
0,02 |
0,03 |
|
5 |
0,004 |
0,002 |
0,005 |
0,01 |
0,012 |
|
6 |
0,001 |
0,0005 |
0,002 |
0,003 |
0,005 |
Варианты 26.1 - 26.3
Потерпевший аварию самолет может находиться в одном из n районов с вероятностями р1,...,рn. Если на поиск в i-м районе затрачивается t единиц времени, то вероятность обнаружения самолета равна 1-е-t (если самолет окажется в данном районе).
Определить оптимальную стратегию поиска при условии ограничения времени поиска величиной Т. Необходимые данные приведены в табл. 35.
Таблица 35
-
Ва-риант
Пара
метры
Район
Т
1
2
3
4
5
26.1
Рi
0,1
0,4
0,2
0,1
0,2
20-25
i
0,2
0,1
0,5
0,4
1,0
26.2
Рi
0,25
0,1
0,3
0,2
0,15
3-6
i
2
1
0,5
2,5
0,4
26.3
Рi
0,3
0,1
0,2
0,15
0,25
15-20
i
0,1
0,2
0,5
0,4
0,3