6. Оптимальное распределение капиталовложений. Метод динамического программирования

Задача 6. В производственное объединение входят при предприятия. Прирост продукции каждого из них в зависимости от величины выделенных предприятию капиталовложений указан в приведенной ниже таблице.

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

Капиталовложения (в усл.ден.ед.) каждому предприятию могут быть выделены только в размерах кратных 20 (усл.ден.ед.), и общий объем капиталовложений составляет (усл.ден.ед.).

Решить задачу о распределении денежных ресурсов методом динамического программирования

Решение:

Составим математическую модель данной задачи оптимального распределения ресурсов. Для этого сначала введем переменные:

- количество денежных средств, выделяемых -му предприятию ;

- соответствующий прирост выпуска продукции -го предприятия .

Затем запишем выражение целевой функции, имеющей смысл суммарного прироста выпуска продукции всего производственного объединения:

(1)

Далее запишем ресурсное ограничение

. (2)

По смыслу задачи переменные должны быть неотрицательными:

, , . (3)

В результате получаем математическую формулировку задачи:

Найти такие значения переменных , , , которые удовлетворяют ограничениям (2), (3) и доставляют наибольшее значение целевой функции (1).

Решение поставленной задачи методом динамического программирования Беллмана содержит следующие основные этапы ([6]):

1) Вложение данной конкретной задачи в семейство подобных задач (инвариантное погружение задачи);

2) Составление уравнения Беллмана, исходя из принципа оптимальности Беллмана;

3) Решение уравнения Беллмана;

4) Выделение решения исходной задачи из найденной функции Беллмана.

Перейдем к реализации указанных этапов.

1) Вместо одной исходной задачи (1)-(3) с заданным значением суммарного ресурса и числом предприятий рассмотрим семейство подобных задач с изменяющимся значением суммарного ресурса и изменяющимся числом предприятий :

, (4)

, (5)

. (6)

Введем функцию 2-х переменных - функцию Беллмана

,

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

2) Принцип оптимальности многошагового процесса впервые был сформулирован Р. Беллманом и заключается в следующем: завершающая часть процесса должна быть оптимальной относительно текущего реализовавшегося состояния. Математическим выражением этого принципа для данной задачи является уравнения Беллмана ([6]):

, (8)

где , .

3) Уравнение Беллмана имеет очевидное краевое условие

(9)

Зная , из уравнения (8) последовательно находим:

,

где в силу краевого условия (9);

.

При этом на каждом шаге решается стандартная задача нахождения наибольшего значения функции одной переменной на отрезке .

Приведем табличную реализацию изложенного выше решения уравнения Беллмана.

4) Выделим решение исходной задачи из найденной выше функции Беллмана , организовав так называемую "попятную" процедуру.

Сначала найдем оптимальное значение переменной . Для этого в последнем соотношении для положим :

(10)

и найдем то значение на котором достигается максимум в правой части соотношения (10). По таблице 2 определяем , и это наибольшее значение достигается при .

После выделения единиц ресурса третьему предприятию на остальные два предприятия (второе и первое) следует распределить оставшийся ресурс .

Положим в предпоследнем соотношении для :

(11)

и найдем то значение , на котором достигается максимум в правой части соотношения (11). По таблице 1 определяем , и это наибольшее значение достигается при .

Оптимальное значение первой переменной найдем из условия

, (12)

т.е. .

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

, , (усл.ден.ед.)