Женщина / пример динамическое программирование

Задача скачана с сайта http://www.MatBuro.ru ©МатБюро - Решение задач по высшей математике

Тема: Динамическое программирование

ЗАДАНИЕ. Для двух		предприятий выделено a единиц средств.				Как распределить все
средства в течение 4			лет, чтобы доход был наибольшим, если известно, что доход от x
единиц средств, вложенных в первое предприятие,					равен f1 (x),	а доход от y единиц
средств, вложенных во второе предприятие, равен					f2 (y). Остаток средств к концу года
составляет g1 (x) для первого предприятия и g2 (y) для второго предприятия. Задачу
решить методом динамического программирования.
	a		f1	g1	f2		g2
	1000		3x	0,1x	2y		0,5y

РЕШЕНИЕ. Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.

Обозначим ak = xk + yk - средства, которые распределяются на k –ом шаге как сумма средств по предприятиям.

Суммарный доход от обоих предприятий на k –ом шаге:

zk = f1 (xk ) + f 2 (ak − xk ) = 3xk + 2(ak − xk ) = 2ak + xk

Остаток средств от обоих предприятий на k –ом шаге:

ak +1 = g1 (xk ) + g2 (ak − xk ) = 0,1xk +0,5(ak − xk ) = 0,5ak −0,4xk

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

Рекуррентные соотношения Беллмана для этих функций

z4 (a4 ) = max {2ak + xk }

0≤x4 ≤a4

zk (ak ) = max {2ak + xk + zk +1 (0,5ak −0,4xk )}

0≤xk ≤ak

Проведем оптимизацию, начиная с четвертого шага:

4-й шаг.

Оптимальный доход равен: z4 (a4 ) = max {2ak + xk }= 3a4 , т.к. линейная

0≤x4 ≤a4

возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при x4 = a4 .

3-й шаг.

1

		Задача скачана с сайта http://www.MatBuro.ru
	©МатБюро - Решение задач по высшей математике
z3 (a3 ) = max {2a3	+ x3	+3(0,5a3 −0,4x3 )}= max {3,5a3 −0,2x3 )}= 3,5a3 ,	т.к.	линейная
0≤x3 ≤a3		0≤x3 ≤a3

убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x3 = 0 .

2-й шаг.

z2 (a2 ) = max {2a2	+ x2	+3,5(0,5a2	−0,4x2 )}= max {3,75a2 −0,4x2 )}= 3,75a2 , т.к. линейная
0≤x2 ≤a2			0≤x2 ≤a2

убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е.

при x2		= 0 .
		1-й шаг.
z (a ) = max			{2a	+ x	+3,75(0,5a	−0,4x )}= max			{3,875a	−0,5x )}= 3,875a т.к. линейная
1	1	0≤x1 ≤a1	1	1	1	1	0≤x1	≤a1	1	1	1

убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x1 = 0 .

Результаты оптимизации:
z	(a	) = 3,875a	;	x = 0
1	1	1		1
z2 (a2 ) = 3,75a2 ;				x2 = 0
z3 (a3 ) = 3,5a3 ;				x3 = 0

z4 (a4 ) = 3a4 ; x4 = a4

Определим количественное распределение средств по годам:

Т.к. a	= a =1000,		x =	0 , получаем a		2	= 0,5a	−0,4x = 500 . Далее аналогично:
1			1				1	1
x2 =0 , a3		= 0,5a2	−0,4x2		= 250
x3 = 0 , a4		= 0,5a3 −0,4x3			=125
x4 = a4	=125

Представим распределение средств в виде таблицы:

предприятие			год
	1	2		3	4
1	0	0		0	125
2	1000	500		250	0

При таком распределении средств за 4 года будет получен доход, равный

zmax = z1 (a1 ) = 3,875 1000 = 3875

2