7.2. Задача оптимального распределения ресурсов
Допустим, что в нашем распоряжении имеется некоторое количество единиц какого-либо однородного ресурса. В качестве ресурса могут выступать деньги, человеческие технические ресурсы (например, материалы, оборудование) и т.д. в количестве w. Имеется Т объектов его распределения. Это могут быть объекты строительства, инвестиционные проекты, регионы и т. д. Пусть x - количество ресурса, выделяемое на
объект /. Известны функции эффективности при выделении ресурса в количестве X, на объект /-Дх,). Эффективность конкретного способа
распределения имеющегося ресурса оценивается как сумма эффективно-стей от вложения в каждый объект. В математическом виде задача записывается следующим образом:
Xj +Х2 + ... + Х7 = W,
X, 6 {О, 1,2,...}.
Согласно методу динамического программирования нам необходимо определить функции fd) как максимальную эффективность, которую можно получить, распределяя d единиц ресурса по объектам /, / + 1, Г. Как мы уже отмечали, fj{d) =0 для Bcex(i, 0<d<w. Последующие функции {t <Т) допускают задание через следующие рекуррентные соотношения
у; id) = max (X,) + {d - X,)}.(7.5)
Пусть x]{d) - значение х, на котором достигается значение максимума в соотношение (7.5). Сначала с помощью соотношения (7.5) находятся значения функции fj{x) и xj.(x) для всевозможньос значений аргумента (0<х< w). Далее аналогичным способом из соотношения (7.5) строятся функции /7 i(x) и X7 i(x)h так далее, заканчивая функциями /, (х) и Xi*(x). Значение max /Лх) и есть максимальная эффективность,
которая достигается при оптимальном способе распределения ресурсов между объектами. Само же оптимальное распределение X* =s(x*,xj,...,x*) получается как
b,-x,
(7.6)
Пример. Банк намерен предоставить 5 млн. руб. в качестве кредита для модернизации трех предприятий. Расчеты показывают, что вьщеле-
ние /-му предприятию (/ = 1, 2, 3) млн. руб. принесет /(/ млн. руб. прибыли (см. табл. 7.1). Как следует распределить всю сумму кредита по предприятиям, чтобы получить максимальную суммарную прибыль, если средства выделяются в размерах, кратных 1 млн. руб.?
Таблица 7.1
Решение.
Исходя из общего вида задачи (7.2) и учитывая, что w = 5, а Г = 3, данную задачу можно записать в виде:
max((Pi (xi) + <г?2 (Х2) + (р (х))
Xj + Х2 + Хз = 5, .
х,е{о, 1,2,3,4,5}, / = 1,2,3.
Вычислим функции /з(), f{d), fid). Как бьшо отмечено, f(cl) = О для всех значений ((i = О, 1, 2, 3, 4, 5).
**/**\
Вычислим значения функции f{d) и соответствующие значения xlid) исходя из соотношения
/з() = тах{(Хз) + /Дй?-х,)}
О < Хз < й?
или так как /4 (с?) = О, имеем
/з() = тахз(хз) Q<x<d
/з(0) = з(0) = 0, хз*(0) = 0,
/з(1) = тах{з(0),з(1)} = тах{0,2} = 2,
/з(2) = тах{«?з(0),«?з(1),«?з(2)} = тах{0,2,4} = 4, ХзЧ2) = 2,
/з(3) = тах{«?з(0),з(1),з(2),з(3)} = тах{0,2,4,5} = 5, з(3) = 3,
/з(4) = тах{«?з(0),з(1),з(2),з(3),«?з(4)} = тах{0,2,4,5,б} = 6,
Хз*(4) = 4,
/з(5) = тах{з(0),з(1),з(2),з(3),з(4),з(5)} = max (0,2,4,5,6,8} = 8,
Хз(5) = 5.
Далее вычислим значения функции /зС) и соответствующие значения XjCflf) исходя из соотношения
/2 {d) = max (2) + /3 - 2)} •
0<X2 <d