Тесты. Динамическое программирование

 

1. Динамическое программирование применяют для решения задач:

а) дискретных;

б) блочных;

в) дробно-линейных;

г) оптимизационных, связанных с многошаговыми процессами.

2. Основной принцип метода динамического программирования:

а) разработка управленческого решения;

б) введение функции Беллмана;

в) если на первом шаге принято решение, то дальнейшее решение должно приниматься таким образом, чтобы за оставшееся число шагов достичь максимального (минимального) результата.

3. Смысл функции Беллмана:

а) максимальная прибыль;

б) минимальные затраты;

в) максимальная эффективность многошагового процесса, состоящего из к шагов;

г) максимальное количество продукции.

4. Математическая модель задачи:

при ограничениях:

х₁+х₂+…+х_n = А

х_j ≥ 0, j=

является моделью (указать соответствие программирования), если функции заданы

 

а) линейного б) нелинейного в) динамического

1) таблично 2) дробно-линейные 3) нелинейные

 

5. При решении задачи о распределении ресурсов смысл функции Беллмана f_k (x):

а) максимальное количество продукции, которое может выпустить одно k-тое предприятие;

б) максимальное количество продукции, которое могут выпустить к предприятий, когда между ними распределено х единиц ресурса;

в) максимальное количество продукции, которое могут выпустить к предприятий, когда k-му предприятию выделено х единиц ресурса.

6. В задаче об оптимальном распределении ресурсов смысл выражения :

а) k+1 – е предприятие, получив 0 ≤ t ≤ x единиц ресурса, выпускает единиц продукта;

б) на долю первых k предприятий остается x – t единиц ресурса;

в) общий выпуск продукции k+1 – м предприятиями, когда k+1 – му выделено t единиц ресурса и остатки (x – t) остальным k предприятиям.

 

7. Для проверки правильности расчетов (самоконтроль) находят количество:

а) общих ресурсов;

б) выпускаемой продукции каждым предприятием при распределении ресурсов между ними по исходной информации;

в) суммарной выпускаемой продукции всеми предприятиями при данном распределении ресурса между ними по исходной информации.

8. В задаче об оптимальной эксплуатации оборудования основной принцип:

а) если оборудование не вышло из строя, то «сохранить»;

б) решение «сохранить» или «заменить» принимать в начале года;

в) если доход от действующего оборудования больше чем от нового, то решение «сохранить», в противном случае - «заменить».

 

9. В задаче об оптимальной эксплуатации оборудования функция Беллмана f_k (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

пер вто- тре- четве пя шес седь

вый рой тий ртый тый той мой

год

 

оптимальная политика эксплуатации оборудования, соответствующая функции Беллмана f₂(3):

а) зам., сохр., зам.; б) сохр., зам., сохр.;

в) зам., сохр.; г) сохр., зам.

18. Получена шкала оптимальной эксплуатации оборудования в течении 7 лет

 

С С С З С З С t (возраст)

0 1 2 3 4 5 6 7

Пер- вто- тре- четвер- пя - шес- седь

вый рой тий тый тый той мой

год

указанному промежутку эксплуатации оборудования соответствует функция Беллмана:

а) ; б) ; в) ; г)

 

19. При планировании удовлетворения потребности с минимальными затратами на перспективу методом динамического программирования функция Беллмана f_i(x) имеет смысл:

а) минимальные затраты на удовлетворение x единиц потребности по i- му варианту;

б) минимальные затраты максимального удовлетворения потребности;

в) минимальные затраты удовлетворения потребности в x единиц за счет расширения действующего предприятия и строительства i новых.

 

20. Удовлетворить потребность региона в 100 ед. продукта можно за счет двух действующих предприятий и трех новых, но тогда min затраты составят:

а) ;

б) ;

в) .

 

21. Смысл функции Беллмана f₄(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. Смысл функции Беллмана f₃(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 в некотором виде продукции. Для этого существуют действующие предприятия с мощностью N_i, но они не в состоянии полностью обеспечить всю потребность. Возникает вопрос о строительстве новых предприятий и расширении или реконструкции старых. Известны затраты на расширение старых предприятий (табл. 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. Выбор оптимальных маршрутов и инцидентных цепей

Построить граф коммуникаций из восьми вершин (пунктов). На ребрах графа указать время возможного перехода между пуктами t_ij (Табл.6.18). Методом динамического программирования найти оптимальные маршруты из любого i –го (i= ) пункта в восьмой конечный пункт и указать инцидентные цепи.

Таблица 6.18

Варианты заданий

№ вар.

t12

t13

t14

t25

t27

t34

t36

t38

t47

t57

t58

t68

t78