ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ИНВЕСТИЦИЙ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

​OPTIMAL INVESTMENT ALLOCATION BY THE DYNAMIC PROGRAMMING METHOD

Zavodskaya Ekaterina Mikhailovna

Student, Department of Higher Mathematics, Ulyanovsk State Technical University,

Russia, Ulyanovsk

Kireev Sergey Vladimirovich

Scientific supervisor, PhD in Physics. - Mat. of Sciences, Associate Professor of the Department of Higher Mathematics, Ulyanovsk State Technical University,

Russia, Ulyanovsk

АННОТАЦИЯ

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

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

ABSTRACT

This article considers the problem of allocating a limited volume of investment funds among several enterprises in order to maximize total profit. The dynamic programming method, based on Bellman's optimality principle, is applied to solve it. The first part of the work presents the mathematical formulation of the problem, the derivation of recurrence relations, and a step-by-step calculation algorithm. The importance of the additivity property for applying this approach is substantiated.

The second part demonstrates a numerical example for three enterprises with tabulated profit functions. The computation process is performed in detail from the last step to the first, including filling in conditional optimization tables and finding the unconditional optimal plan. The results demonstrate the efficiency and high accuracy of the dynamic programming method in solving nonlinear discrete resource allocation problems.

Ключевые слова: динамическое программирование, принцип Беллмана, распределение инвестиций, оптимизация, рекуррентное уравнение.

Keywords: dynamic programming, Bellman principle, investment allocation, optimization, recurrence equation.

Задача оптимального распределения ограниченных ресурсов между несколькими альтернативными направлениями является классической в экономике и исследовании операций. При инвестировании средств в различные проекты или предприятия часто требуется выбрать такие объёмы вложений, чтобы суммарная прибыль была максимальной. Данная задача обладает свойством аддитивности и решается методом динамического программирования, позволяющего разбить сложную задачу на несколько простых подзадач. В настоящей работе рассматривается дискретный вариант задачи: инвестиции выделяются целыми единицами (например, миллионами рублей), а прибыль каждого предприятия задана таблично. Целью является построить оптимальный план распределения.

Математическая модель.

Пусть имеется n предприятий (в нашем случае n = 3). Инвестор располагает суммой S тыс. ден. ед. (в примере S = 6). Обозначим через - количество средств, вкладываемых в i-е предприятие (i = 1,2,3). Очевидно, что

Каждое предприятие при инвестировании x тыс. ден. ед. приносит прибыль (x), причём (0) = 0. Требуется максимизировать суммарную прибыль:

Для решения применим метод динамического программирования. Процесс распределения будем рассматривать как многошаговый: на каждом шаге i (начиная с первого предприятия) мы выбираем величину, после чего остаток средств переходит к следующему шагу.

Параметры модели.

Состояние системы s - количество средств, имеющихся в наличии перед шагом. Управление на i-м шаге - величина

Выигрыш на i-м шаге - (). Функция перехода - новое состояние s' = s -.

Рекуррентные соотношения Беллмана.

Обозначим через (s) максимальную прибыль, которую можно получить, распределяя средства s между предприятиями с номерами. Для последнего предприятия () вся оставшаяся сумма вкладывается в него:

Для , справедливо уравнение:

-оптимальное управление на шаге при состоянии .

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

Исходные данные для численного примера.

Общий объём инвестиций S = 6 тыс. ден. ед. Прибыли предприятий заданы в таблице 1 (значения условные, но демонстрируют нелинейную зависимость).

Таблица 1.

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

Решение методом динамического программирования.

Шаг 3. (последнее предприятие)

Для i = 3 имеем . Результаты представлены в таблице 2.

Таблица 2.

Оптимальные значения для шага 3.

Шаг 2.

Используем уравнение . Для каждого s от 0 до 6 перебираем возможные x и выбираем максимум. Результаты представлены в таблице 3.

Таблица 3.

Расчёт для шага 2.

Оптимальные управления на втором шаге (при наличии нескольких равных вариантов выбираем любой, например, наименьший x):

Шаг 1.

Начальное состояние s = 6. Используем уравнение  . Вычисления приведены в таблице 4.

Таблица 4.

Расчёт для первого шага при s = 6.

Максимальная сумма равна 23,0. Она достигается при и . Выберем (вложение в первое предприятие отсутствует). Тогда остаток . По таблице для второго шага при s=6 оптимальное управление . После этого остаток для третьего шага . На третьем шаге.

Таким образом, оптимальный план распределения:

Суммарная прибыль: тыс. ден. ед. Если бы мы выбрали на первом шаге, то получили бы: , что даёт прибыль  3,0 + 4,0 + 16,0 = 23,0  – получаем  тот же результат.

Проверка альтернативного оптимума.

При: остаток 5, , остаток 4,. Сумма: 3+4+16=23. Оба плана эквивалентны по прибыли. В реальных задачах можно выбрать любой из них.

Заключение

В статье для решения задачи оптимального распределения инвестиций был использован метод динамического программирования. На примере с числовыми данными показано, что рекуррентные соотношения Беллмана позволяют эффективно находить глобальный максимум суммарной прибыли, даже при нелинейных и дискретных зависимостях. Полученный оптимальный план обеспечивает максимальную прибыль в размере 23,0 тыс. ден. ед. Предложенный подход может быть использован на любое количество предприятий и любые объёмы инвестиций.

Список литературы:

1. Беллман Р., Дрейфус С. Динамическое программирование и современная теория управления. - М.: Наука, 1969. -118 с.
2. Вагнер Г. Основы исследования операций: в 3 т. - М.: Мир, 1973. - 504 с.
3. Карасева Р.Б. Оптимальное распределение инвестиций по объектам вложения методами динамического программирования // Научно-методический электронный журнал «Концепт». – 2016. - № 7 (июль). -0,3 п. л.
4. Коган Д.И. Динамическое программирование и дискретная многокритериальная оптимизация: учеб. пособие. - Н. Новгород: Изд-во Нижегор. гос. ун-та, 2005. - (Модели и методы конечномерной оптимизации; вып. 3).