Оптимальное распределение инвестиций

Эта задача решается с помощью динамического программирования.

Динамическое программирование – это вычислительный метод для ре­шения задач управления определенной структуры. Данная задача с n пере­менными представляется как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной пере­менной.

Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через f_i(x_i) прирост мощности или прибыли на j-м предприятии, если оно получит x_i рублей капитальных вложений. Требуется найти такое распределение (x₁,x₂,...,x_n) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли z=f₁(x₁)+f₂(x₂)+...+f_n(x_n), при ограничении по общей сумме капитальных вложений x₁+x₂+...+x_n=b, причем будем считать, что все переменные x_j принимают только целые не­отрицательные значения x_j =0, или 1, или 2, или 3,...

Функции f_j(x_j) мы считаем заданными, заметив, что их определение – довольно трудоемкая экономическая задача.

Воспользуемся методом динамического программирования для реше­ния этой задачи. Введем параметр состояния и определим функцию состояния. За пара­метр состояния ξ примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния F_k(ξ) определим как максимальную прибыль на первых k предприятиях, если они вместе получают ξ рублей. Параметр ξ может изменяться от 0 до b. Если из ξ рублей k-ое предприятие получит x_k рублей, то каково бы ни было это значение, остальные ξ-x_k рублей естественно распределить между предприятиями от первого до (k-1)-го так, чтобы была получена максимальная прибыль F_k-1(ξ-x_k). Тогда прибыль k предприятий будет равна f_k(x_k)+F_k-1(ξ-x_k). Надо выбрать такое значение x_k между 0 и ξ, чтобы эта сумма была максимальной, и мы при­ходим к рекуррентному соотношению:

F_k(ξ)=max{f_k(x_k)+F_k-1(ξ-x_k)}

0≤x_k≤ ξ

для k=2,3,4,...,n. Если же k=1, то F₁(ξ)=f₁(ξ). (при условии, что функция f₁ возрастающая).

Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере m (сотен тыс. рублей) выражается функцией f_i(m). Приходим к задаче:

f₁(x₁)+f₂(x₂)+f₃(x₃)+f₄(x₄)→max,

x₁+x₂+x₃+x₄≤7,

x₁, x₂, x₃, x₄≥0,

где x_i – пока еще неизвестный размер инвестиций i-й фирме.

Прежде всего, заполняем таблицу №1. Значения f₂(x₂) складываем со значениями F₁(ξ-x₂)=f₁(ξ-x₂) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем и указываем соответствующее значение =100*z₂.

Таблица №1

	ξ-x2
x2

Красным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 2 предприятиям.

Таблица №2

	ξ-x3
x3

Красным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 3 предприятиям.

Таблица №3

	ξ-x4
x4

Красным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 4 предприятиям.

Сведем результаты в 4 таблицы. Теперь F₄(700)=280 показывает максимальный суммарный эффект по всем 4-м фирмам, а z₄(700)=400 – размер инвестиций в 4-ю фирму для достижения этого максимального эффекта. После этого на долю первых 3-х фирм осталось (700-400) и для достижения максимального суммарного эффекта по первым 3-м фирмам в 3-ю надо вложить 100, во вторую 100 и первую 100. Красным отмечены оптимальные значения инвестиций по фирмам (z_i) и значения эффектов от них (F_i(ξ)).