Тесты. Динамическое программирование
1. Динамическое программирование применяют для решения задач:
а) дискретных;
б) блочных;
в) дробно-линейных;
г) оптимизационных, связанных с многошаговыми процессами.
2. Основной принцип метода динамического программирования:
а) разработка управленческого решения;
б) введение функции Беллмана;
в) если на первом шаге принято решение, то дальнейшее решение должно приниматься таким образом, чтобы за оставшееся число шагов достичь максимального (минимального) результата.
3. Смысл функции Беллмана:
а) максимальная прибыль;
б) минимальные затраты;
в) максимальная эффективность многошагового процесса, состоящего из к шагов;
г) максимальное количество продукции.
4. Математическая модель задачи:
при ограничениях:
х1+х2+…+хn = А
хj ≥ 0, j= 
является моделью (указать соответствие программирования), если функции 
заданы
| а) линейного б) нелинейного в) динамического | 1) таблично 2) дробно-линейные 3) нелинейные |
5. При решении задачи о распределении ресурсов смысл функции Беллмана fk (x):
а) максимальное количество продукции, которое может выпустить одно k-тое предприятие;
б) максимальное количество продукции, которое могут выпустить к предприятий, когда между ними распределено х единиц ресурса;
в) максимальное количество продукции, которое могут выпустить к предприятий, когда k-му предприятию выделено х единиц ресурса.
6. В задаче об оптимальном распределении ресурсов смысл выражения 
:
а) k+1 – е предприятие, получив 0 ≤ t ≤ x единиц ресурса, выпускает 
единиц продукта;
б) на долю первых k предприятий остается x – t единиц ресурса;
в) общий выпуск продукции k+1 – м предприятиями, когда k+1 – му выделено t единиц ресурса и остатки (x – t) остальным k предприятиям.
7. Для проверки правильности расчетов (самоконтроль) находят количество:
а) общих ресурсов;
б) выпускаемой продукции каждым предприятием при распределении ресурсов между ними по исходной информации;
в) суммарной выпускаемой продукции всеми предприятиями при данном распределении ресурса между ними по исходной информации.
8. В задаче об оптимальной эксплуатации оборудования основной принцип:
а) если оборудование не вышло из строя, то «сохранить»;
б) решение «сохранить» или «заменить» принимать в начале года;
в) если доход от действующего оборудования больше чем от нового, то решение «сохранить», в противном случае - «заменить».
9. В задаче об оптимальной эксплуатации оборудования функция Беллмана fk (t) имеет смысл:
а) доход от эксплуатации оборудования за t лет в k – том году;
б) максимальный доход, который может быть получен от эксплуатации оборудования возраста t за k лет его эксплуатации при оптимальной политике замены;
в) максимальный доход от эксплуатации оборудования возраста t в k –том году.
10. Доход, который можно получить от эксплуатации нового оборудования за 1 год, равен:
а) 
; б) 
; в) 
; г) 
.
11. Смысл функции Беллмана 
:
а) максимальный доход от эксплуатации оборудования возраста t за один k + 1 год;
б) доход, который можно получить от эксплуатации оборудования за один (k + 1) год;
в) максимальный доход от эксплуатации оборудования возраста t за все (k + 1) год эксплуатации.
12. Выражение 
имеет смысл:
а) максимальный доход который можно получить от эксплуатации оборудования за один год;
б) максимальный доход, который можно получить либо от действующего, либо от нового оборудования по истечении года эксплуатации;
в) .
13. Смысл выражения 
:
а) доход от нового оборудования;
б) максимальный доход, от нового оборудования за первый год эксплуатации;
в) доход от нового оборудования по истечении года эксплуатации.
14. Смысл выражения 
:
а) максимальный доход от эксплуатации нового оборудования за все (k + 1) лет;
б) доход от эксплуатации нового оборудования по истечении одного k + 1 года;
в) доход, который можно получить от нового оборудования за k + 1 год эксплуатации.
15. Если в начале года сохранить оборудование возраста t лет, то доход от его эксплуатации за k+1 год составит сумму:
а) 
; б) 
;
в) 
; г) 
.
16. Если в начале года заменить действующее оборудование на новое, то за k+1 год его эксплуатации доход от него будет равен:
а) 
; б) ;
в) 
; г) 
.
17. Известна оптимальная шкала эксплуатации оборудования
С С С З С З С t (возраст)
0 1 2 3 4 5 6 7
пер вто- тре- четве пя шес седь
вый рой тий ртый тый той мой
год
оптимальная политика эксплуатации оборудования, соответствующая функции Беллмана f2(3):
а) зам., сохр., зам.; б) сохр., зам., сохр.;
в) зам., сохр.; г) сохр., зам.
18. Получена шкала оптимальной эксплуатации оборудования в течении 7 лет
С С С З С З С t (возраст)
0 1 2 3 4 5 6 7
Пер- вто- тре- четвер- пя - шес- седь
вый рой тий тый тый той мой
год
указанному промежутку эксплуатации оборудования соответствует функция Беллмана:
а) 
; б) 
; в) 
; г) 
19. При планировании удовлетворения потребности с минимальными затратами на перспективу методом динамического программирования функция Беллмана fi(x) имеет смысл:
а) минимальные затраты на удовлетворение x единиц потребности по i- му варианту;
б) минимальные затраты максимального удовлетворения потребности;
в) минимальные затраты удовлетворения потребности в x единиц за счет расширения действующего предприятия и строительства i новых.
20. Удовлетворить потребность региона в 100 ед. продукта можно за счет двух действующих предприятий и трех новых, но тогда min затраты составят:
а) 
;
б) 
;
в) 
.
21. Смысл функции Беллмана f4(500) задачи планирования минимальных затрат на перспективу:
а) минимальные затраты на удовлетворение 500 единиц потребности по четвертому варианту, т.е. за счет четвертого предприятия;
б) минимальные затраты на удовлетворение 500 единиц потребности за счет всех четырех предприятий;
в) затраты на удовлетворение потребности в 500 единицах продукта всеми четырьмя предприятиями.
22. Модель расчета минимального времени передачи управления из любого i – го пункта в конечный N – й за k шагов имеет вид:
а) 
;
б) 
;
в) 
;
г) 
.
23. Получены маршруты
инцидентные цепи этих маршрутов
а) 3 – 4 – 5 – 7;
б) 1 – 3 – 4;
в) 2 – 3 – 4;
г) 4 – 5 – 7.
24. Математическая модель оптимального распределения А единиц ресурсов между k предприятиями имеет вид:
а) 
;
б) 
;
в) 
;
г) 
.
25. Смысл функции Беллмана f3(5) задачи выбора оптимальных маршрутов:
а) min время перехода из пятого пункта в конечный за третий шаг;
б) время перехода из пятого пункта в десятый за 3 шага;
в) min время перехода за 3 шага из пятого пункта в конечный 10;
г) min время перехода из пятого пункта в третий за один шаг.
ПРАКТИКУМ
Задание 1. Оптимальное распределение ресурсов.
На авторемонтном предприятии имеются 7 постов ремонта автомобилей. Известно, что i – тый пост (i = 
), получив хединиц комплектов запчастей, отремонтирует φi (х) единиц автомобилей (табл. 6.12).
Требуется распределить А единиц комплектов запчастей между указанными в таблице 6.13 пятью постами предприятия так, чтобы общее количество отремонтированных ими автомобилей было максимальным.
Таблица 6.12
Исходная информация
| Х ед. φi (х) усл. ед. | ||||||||||
| φ1(х) | ||||||||||
| φ2(х) | ||||||||||
| φ3(х) | ||||||||||
| φ4(х) | ||||||||||
| φ5(х) | ||||||||||
| φ6(х) | ||||||||||
| φ7(х) |
Таблица 6.13
Варианты заданий
| № варианта | Кол-во комплектов А | Посты ремонта |
| 1, 2, 3, 5, 7 | ||
| 1, 3, 4, 5 ,7 | ||
| 2, 1, 4, 5, 6 | ||
| 3, 4, 5, 6, 7 | ||
| 4, 5, 6, 7, 3 | ||
| 3, 5, 6, 4, 7 | ||
| 4, 3, 2, 7, 6 | ||
| 5, 4, 3, 7, 1 | ||
| 1, 2, 3, 4, 5 | ||
| 2, 3, 4, 5, 7 | ||
| 1, 2, 3, 6, 7 | ||
| 1, 3, 6, 5, 7 | ||
| 2, 3, 4, 7, 6 | ||
| 2, 6, 5, 4, 7 | ||
| 3, 7, 6, 2, 1 | ||
| 1, 2, 7, 6, 4 | ||
| 2, 1, 5, 6, 4 |
продолжение таблицы 6.13
| 3, 2, 5, 6, 7 | ||
| 1, 2, 3, 4, 5 | ||
| 2, 3, 4, 5, 6 | ||
| 3, 4, 2, 1, 6 | ||
| 5, 6, 7, 4, 3 | ||
| 2, 3, 4, 7, 5 | ||
| 6, 7, 5, 3, 4 | ||
| 4, 5, 6, 3, 1 | ||
| 1, 2, 5, 4, 7 | ||
| 2, 7, 6, 5, 4 | ||
| 3, 4, 6, 7, 5 | ||
| 2, 6, 7, 5, 3 | ||
| 7, 6, 5, 1, 2 |
Задание 2. Планирование минимальных затрат на перспективу
Пусть необходимо удовлетворить потребность Q в некотором виде продукции. Для этого существуют действующие предприятия с мощностью Ni , но они не в состоянии полностью обеспечить всю потребность. Возникает вопрос о строительстве новых предприятий и расширении или реконструкции старых. Известны затраты на расширение старых предприятий (табл. 6.14) и строительство новых (табл. 6.15). Требуется выбрать оптимальный вариант строительства объектов таким образом, чтобы с минимальными затратами удовлетворить потребность в продукции.
Таблица 6.14
Затраты (ден. ед.) на расширение действующих предприятий
| Мощность предприятия (тыс.т) Номер действующего предприятия | ||||||
| - - - - - | - - | - - |
Таблица 6.15
Затраты (ден. ед.) на строительство новых предприятий
| Мощность предприятий (тыс.т) Номер предприятия | |||||
| - - - | - - - |
Таблица 6.16
Варианты заданий
| № варианта | Q потребность (тыс. т) | Ni – мощность i- ого действующего предприятия (тыс.т) | Предприятия | |||||
| N1 | N2 | N3 | N4 | N5 | действующие | новые | ||
| 1,5 2,4 3,5 1,2 1,3 2,3 2,5 3,4 1,4 1,5 2,4 3,5 1,2 1,3 2,3 2,5 3,4 1,4 1,5 2,4 3,5 1,2 1,3 2,3 2,5 3,4 1,4 1,5 2,4 3,5 | 1,2,3 1,2,4 1,3,4 1,2,5 1,3,4 2,3,4 1,3,5 2,3,5 3,4,5 3,4,5 2,3,5 1,3,5 2,3,4 1,3,4 1,2,5 1,3,4 1,2,4 1,2,3 1,2,4 1,3,4 1,2,5 1,3,4 2,3,4 1,3,5 2,3,5 3,4,5 2,3,5 1,3,5 2,3,4 1,3,4 |
Задание 3. Задача о замене оборудования
Известна стоимость нового оборудования С денежных единиц. Эксплуатация оборудования возраста t лет в течение одного года приносит доход 
денежных единиц. (Табл.6.17). Требуется определить оптимальную политику замены оборудования таким образом, чтобы доход, полученный при эксплуатации нового оборудования в течение n лет, был максимальным.
Таблица 6.17
Варианты заданий
| № Вар. | n лет | С ден. ед. | Доход за год φ(t) (ден. ед.) | ||||||||||||||||
| j(0) | j(1) | j(2) | j(3) | j(4) | j(5) | j(6) | j(7) | j(8) | j(9) | j(10) | j(11) | j(12) | j(13) | j(14) | j(15) | ||||
Задание 4. Выбор оптимальных маршрутов и инцидентных цепей
Построить граф коммуникаций из восьми вершин (пунктов). На ребрах графа указать время возможного перехода между пуктами tij (Табл.6.18). Методом динамического программирования найти оптимальные маршруты из любого i –го (i= 
) пункта в восьмой конечный пункт и указать инцидентные цепи.
Таблица 6.18
Варианты заданий
| № вар. | t12 | t13 | t14 | t25 | t27 | t34 | t36 | t38 | t47 | t57 | t58 | t68 | t78 |