Оптимальное распределение инвестиций
Эта задача решается с помощью динамического программирования.
Динамическое программирование – это вычислительный метод для решения задач управления определенной структуры. Данная задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.
Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fi(xi) прирост мощности или прибыли на j-м предприятии, если оно получит xi рублей капитальных вложений. Требуется найти такое распределение (x1,x2,...,xn) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли z=f1(x1)+f2(x2)+...+fn(xn), при ограничении по общей сумме капитальных вложений x1+x2+...+xn=b, причем будем считать, что все переменные xj принимают только целые неотрицательные значения xj=0, или 1, или 2, или 3, ...
Функции fj(xj) мы считаем заданными, заметив, что их определение – довольно трудоемкая экономическая задача.
Воспользуемся методом динамического программирования для решения этой задачи. Введем параметр состояния и определим функцию состояния. За параметр состояния ξ примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk(ξ) определим как максимальную прибыль на первых k предприятиях, если они вместе получают ξ рублей. Параметр ξ может изменяться от 0 до b. Если из ξ рублей k-ое предприятие получит xk рублей, то каково бы ни было это значение, остальные ξ-xk рублей естественно распределить между предприятиями от первого до (k-1)-го так, чтобы была получена максимальная прибыль Fk-1(ξ-xk). Тогда прибыль k предприятий будет равна fk(xk)+Fk-1(ξ-xk). Надо выбрать такое значение xk между 0 и ξ, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению:
Fk(ξ)=max{fk(xk)+Fk-1(ξ-xk)}
0≤xk≤ ξ
для k=2,3,4,...,n. Если же k=1, то F1(ξ)=f1(ξ). (при условии, что функция f1 возрастающая).
Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере m (сотен тыс. рублей) выражается функцией fi(m). Приходим к задаче:
f1(x1)+f2(x2)+f3(x3)+f4(x4)→max,
x1+x2+x3+x4≤7,
x1, x2, x3, x4≥0,
где xi – пока еще неизвестный размер инвестиций i-й фирме.
xj | ||||||||
f1(x1) | ||||||||
f2(x2) | ||||||||
f3(x3) | ||||||||
f4(x4) |
Прежде всего, заполняем таблицу №1. Значения f2(x2) складываем со значениями F1(ξ-x2)=f1(ξ-x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем и указываем соответствующее значение =100*z2.
Таблица №1
ξ-x2 | |||||||||
x2 | |||||||||
Красным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 2 предприятиям.
ξ | ||||||||
F2(ξ) | ||||||||
z2 |
Таблица №2
ξ-x3 | |||||||||
x3 | |||||||||
Красным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 3 предприятиям.
ξ | ||||||||
F3(ξ) | ||||||||
z3 |
Таблица №3
ξ-x4 | |||||||||
x4 | |||||||||
Красным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 4 предприятиям.
ξ | ||||||||
F4(ξ) | ||||||||
z4 |
Сведем результаты в 4 таблицы. Теперь F4(700)=280 показывает максимальный суммарный эффект по всем 4-м фирмам, а z4(700)=400 – размер инвестиций в 4-ю фирму для достижения этого максимального эффекта. После этого на долю первых 3-х фирм осталось (700-400) и для достижения максимального суммарного эффекта по первым 3-м фирмам в 3-ю надо вложить 100, во вторую 100 и первую 100. Красным отмечены оптимальные значения инвестиций по фирмам (zi) и значения эффектов от них (Fi(ξ)).