Задача № 358

Для двух предприятий выделено 1400 единиц денежных средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от х единиц, вложенных в первое предприятие равен , а доход от у единиц, вложенных в первое предприятие равен . Остаток средств к концу года составляет - для первого предприятия, - для второго предприятия. Решить задачу методом динамического программирования.

Решение

Процесс распределения средств разобъем на 4 этапа – по соответствующим годам.

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

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

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

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

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

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

4-й шаг.

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

3-й шаг.

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

2-й шаг.

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

1-й шаг.

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

Результаты оптимизации:

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

Т.к. , получаем

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

предприятие	год
	1	2	3	4
1	1400	700	0	0
2	0	0	350	105

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