кр динамическое программирование. кр_2_1_Аксенов. Задача (Динамическое программирование)

• Название: Задача (Динамическое программирование)
• Анкор: кр динамическое программирование
• Дата: 24.11.2022
• Размер: 17.47 Kb.
• Имя файла: кр_2_1_Аксенов.docx
• Тип: Задача; #811107

Аксенов Андрей Б-02
Вариант 1.
Задача 1. (Динамическое программирование)

Совет директоров фирмы изучает предложения по модернизации четырех предприятий. Для этих целей выделено 5 миллионов рублей. Для каждого из четырех предприятий разработано несколько альтернативных проектов. Каждый из проектов характеризуется суммарными затратами Сj и будущими доходами Rj , j=1, 2, 3, 4. На каждом предприятии можно реализовать только по одному проекту. Соответствующие данные приведены в таблице. Необходимо выбрать такие проекты для каждого предприятия, чтобы фирма получила максимальный годовой доход.

	Предприятие 1		Предприятие 2		Предприятие 3		Предприятие 4
	С1	R1	C2	R2	C3	R3	C4	R4
1	0	0	0	0	0	0	0	0
2	1	3	3	5	1	4	2	3
3	-	-	5	9	2	6	-	-

• 
  i - номер этапа, ставится в соответствие номеру предприятия, i = 1..4
  
• 
  u_i - стратегия (управление) на этапе i, выражает номер проекта С_i для предприятия i
  
• 
  x_i - состояние на этапе i, выражает суммарные затраты
  
• 
  f_i (x_i) - значение функции Беллмана, равное максимальному будущему доходу
  

Рекуррентное уравнение Беллмана для алгоритма прямой прогонки будет иметь вид:





Этап 1

x1	u1	f1(x1)	u1*
0	1	0	1
1	2	3	2

Этап 2

x2	u2	f2(x2)	(u1*, u2*)
0	1	0	1, 1
1	1	3	2, 1
3	2	5	1, 2
4	2	8	2, 2
5	3	9	1, 3

Этап 3

x3	u3	f3(x3)	(u1*, u2*, u3*)
0	1	0	1, 1, 1
1	2	4	1, 1, 2
2	2	7	2, 1, 2
3	3	9	2, 1, 3
4	2	9	1, 2, 2
5	2	12	2, 2, 2

Этап 4

x4	u4	f4(x4)	(u1*, u2*, u3*, u4*)
0	1	0	1, 1, 1, 1
1	1	4	1, 1, 2, 1
2	1	7	2, 1, 2, 1
3	1	9	2, 1, 3, 1
4	2	10	2, 1, 2, 2
5	1	12	2, 2, 2, 1

Оптимальным решением задачи является: модернизация предприятий 1, 2 и 3 проектом 2, предприятия 4 - проектом. Суммарный годовой доход 12 миллионов рублей.

Ответ: (2, 2, 2, 1)