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

Как пример для решения используется следующая задача оптимального распределения ресурсов. Инвестиции общим объемом 600 млн. руб. необходимо распределить для вложения в 4 проекта, прибыль которых в результате различных вариантов вложений представлена в таблице 1.1. Шаг .

Таблица 1.1

Динамическое программирование или, что равносильно, динамическое планирование - это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой Кузнецов А. В. Высшая математика: Математическое программирование. - Минск: Вышэйшая школа, 2001 - С. 237. Так многие экономические процессы могут быть естественным образом разделены на шаги, на некий промежуток времени (год, месяц, декада и т.д.). Однако метод ДП применим не только к задачам, в которых фигурируют временные отрезки, напротив часто он используется для решения задач, в которых шаг вводится искусственно. Собственно, «динамика» подобных задач заключается в методе решения.

Существует несколько видов задач ДП, и задача оптимального распределения инвестиций (ресурсов) является одной из них. Смысл ее заключается в том, что планируется реализация группы из проектов . Каждый проект может принести свою определенную прибыль при определенном количестве инвестиций в этот проект. Инвестиции в каждый проект измеряются в одних и тех же единицах, причем инвестиции в любой из проектов не зависят от того, какое количество инвестиций было вложено в остальные проекты. На деятельность в рамках этой группы проектов выделены какие-то средства , которые должны быть распределены между ними таким образом, чтобы прибыль, полученная в конечном итоге, была максимальна, то есть распределить средства оптимально. Получаем задачу определения объема инвестиций в каждый проект.

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

Поэтому процесс решения разбивается на шаги и исследуется методом ДП. В основу алгоритма метода положен принцип оптимальности Р. Беллмана: оптимальная стратегия обладает таким свойством, что каковы бы ни были начальное состояние и начальное решение, последующие должны быть оптимальными относительно состояния, полученного в результате первоначального решения Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика: Математическое программирование. - Минск: Вышэйшая школа, 2001 - С. 244; так же используется т.н. принцип погружения, согласно которому задача ДП не меняется от изменения количества шагов .

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

ЦФ в подобной задаче будет иметь вид:

Задача ОРИ появляется в силу наличия ограниченного ресурса :

Для решения задачи (1.1) - (1.2) применяется аппарат функциональных уравнений Р. Беллмана. Она погружается в семейство подобных задач распределения. Вместо решения одной задачи с заданным объемом инвестиций и фиксированным числом проектов рассматриваются их семейства, в которых объем ресурса меняется от 0 до , а число проектов - от 1 до . Таким образом статическая, по сути, задача ОРИ становится задачей ДП.

Вводится последовательность функций , где - максимальная прибыль в случае, если все инвестиции вкладываются в первый проект, - максимальная прибыль в случае распределения инвестиций по двум проектам и т.д. - максимальная прибыль, получаемая от распределения инвестиции между проектами. Из всего этого можно заключить, что .

В двух случаях элемент последовательности имеют простой вид:

, , .

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

Исходя из (1.3) можно построить рекуррентное соотношение, связывающее и для произвольных .

Решением исходной задачи получается при , т.е. из соотношения:

При получении решения задачи, т.е. при нахождении ход решения разворачивается в обратную сторону - определяется , затем . Затем из соответствующего выражения находится и т.д. Теперь находятся уже не условно-оптимальные, а оптимальные значения ЦФ на каждом этапе и оптимальные инвестиции в один проект, два и более.

Вычислительный алгоритм решения задачи ОРИ методом ДП состоит в следующем. Т.к. при решении функциональных уравнений Р. Беллмана невозможно протабулировать все значения ЦФ для каждого проекта, то промежуток разбивается на определенное количество интервалов, допустим, с шагом и считается, что функции и определены лишь в точках , причем . Значение для , отличных от (), можно получить интерполяцией. Множества значений записываются в таблицу. На последнем этапе достигается максимальное значение ЦФ и оптимальный объем инвестиций, вкладываемый в -ный проект, т.е. . Затем, как упомянуто выше процесс решения идет в обратном направлении. Найденное дает возможность найти , а следовательно, из формулы 1.4 и затем из него . Процесс решения оканчивается с нахождением .

Принцип построения решения представлен на блок-схеме ниже.

2.Программная реализация