Распределение Q средств между N предприятиями.

Пусть х _n – средства, выделенные n-му предприятию; они приносят в конце года прибыль с_n(х _n).

Будем считать, что х _n принимает только целые значения, прибыль с_n(х _n) не зависит от вложения средств в другие предприятия и суммарная прибыль равна сумме прибылей, полученных от каждого предприятия. Тогда модель имеет вид:

Найти целочисленные неотрицательные переменные х _n (n=1,2,…,N), удовлетворяющие ограничению:

∑_n х _n = Q, (2.8.2)

и обращающие в максимум функцию

С=∑_n с_n(х _n). (2.8.3)

Здесь процесс распределения средств можно рассматривать как многошаговый, номер шага совпадает с номером предприятия; состояние будет определяться величиной s_n – количество средств, подлежащих распределению на n-м шаге (с конца).

Обозначим f_n(s_n) – условную оптимальную прибыль, полученную от последних n предприятий при распределении между ними s_n средств и вычисляемую в соответствие с динамическим рекуррентным соотношением:

f_n(s_n)=mах_"х(с_n(х _n) + f_n-1(s_n-1)), n=1,2,…,N. (2.8.4)

Пример 2.8.2. Пусть N = 4, Q =5, значения с_n(х _n) заданы в табл. 2.8.1.

Таблица 2.8.1.

х	с4(х)	с3(х)	с2(х)	с1(х)

Как и в предыдущем примере начинаем анализ с последнего предприятия. Индекс «1» соответствует последнему предприятию, а индекс «4» –первому. Для n=1 прибыль проставлена в последней колонке.

Для n=2

f₂(0)=mах[с₂(0)+f₁(0)]=0 при x ₂(0)=0,

f₂(1)=mах[с₂(1)+f₁(0),с₂(0)+f₁(1)]=mах[3+0,0+4]=4 при x ₂(1)=0,

f₂(2)=mах[с₂(2)+f₁(0),c₂(1)+f₁(1),с₂(0)+f₁(2)]=

=mах[4+0,3+4,0+6]=7 при x ₂(2)= 1,

f₂(3)=mах[с₂(3)+f₁(0),с₂(2)+f₁(1),с₂(1)+f₁(2),с₂(0)+f₁(3)]=

=mах[7+0,4+4,3+6,0+8]=9 при x ₂(3)=1,

f₂(4)=mах[с₂(4)+f₁(0),с₂(3)+f₁(1),с₂(2)+f₁(2),с₂(1)+f₁(3),с₂(0)+f₁(4)]=

=mах[11+0,7+4,4+6,3+8,0+13]=13 при х ₂(4)=0,

f₂(5)=mах[с₂(5)+f₁(0),с₂(4)+f₁(1),с₂(3)+f₁(2),с₂(2)+f₁(3),с₂(1)+f₁(4),с₂(0)+f₁(5)]

=mах[18+0,11+4,7+6,4+8,3+13,0+16]=18 при x₂(5)=5.

Для n=3

f₃(0)=mах[с₃(0)+f₂(0)]=0 при x₃(0)=0,

f₃(1)=mах[с₃(1)+f₂(0),с₃(0)+f₂(1)]=mах[6+0,0+4,]=6 при x ₃(1)=1,

f₃(2)=mах[с₃(2)+f₂(0),c₃(1)+f₂(1),с₃(0)+f₂(2)]=

=mах[9+0,6+4,0+7]=10 при x ₃(2)=1,

f₃(3)=mах[с₃(3)+f₂(0),с₃(2)+f₂(1),с₃(1)+f₂(2),с₃(0)+f₂(3)]=

=mах[11+0,9+4,6+7,0+9]=13 при x ₃(3)=1 или 2,

f₃(4)=mах[с₃(4)+f₂(0),с₃(3)+f₂(1),с₃(2)+f₂(2),с₃(1)+f₂(3),с₃(0)+f₂(4)]=

=mах[13+0,11+4,9+7,6+9,0+13]=16 при х ₃(4)=2,

f₃(5)=mах[с₃(5)+f₂(0),с₃(4)+f₂(1),с₃(3)+f₂(2),с₃(2)+f₂(3),с₃(1)+f₂(4),с₃(0)+f₂(5)]

=mах[15+0,13+4,11+7,9+9,6+13,0+18]=19 при x ₃(5)=1.

И, наконец, для n=4

f₄(0)=mах[с₄(0)+f₃(0)]=0 при x ₄(0)=0,

f₄(1)=mах[с₄(1)+f₃(0),с₄(0)+f₃(1)]=mах[8+0,0+6,]=8 при x ₄(1)=1,

f₄(2)=mах[с₄(2)+f₃(0),c₄(1)+f₃(1),с₄(0)+f₃(2)]=

=mах10+0,8+6,0+10]=14 при x ₄(2)=1,

f₄(3)=mах[с₄(3)+f₃(0),с₄(2)+f₃(1),с₄(1)+f₃(2),с₄(0)+f₃(3)]=

=mах[11+0,10+6,8+10,0+13]=18 при x ₄(3)=1,

f₄(4)=mах[с₄(4)+f₃(0),с₄(3)+f₃(1),с₄(2)+f₃(2),с₄(1)+f₃(3),с₄(0)+f₃(4)]=

=mах[12+0,11+6,10+10,8+13,0+16]=21 при х ₄(4)=1,

f₄(5)=mах[с₄(5)+f₃(0),с₄(4)+f₃(1),с₄(3)+f₃(2),с₄(2)+f₃(3),с₄(1)+f₃(4),с₄(0)+f₃(5)]

=mах[18+0,12+6,11+10,10+13,8+16,0+19]=24 при x ₄(5)=1.

Теперь соберем оптимальное решение (при последовательном рассмотрении всех состояний оптимальные переходы подчеркивались):

Для первого предприятия, когда s₄=5, видим, что x ₄(5)=1, значит, первое предприятие получает 1 и остается s₃=s₄– x ₄(5)=5–1=4. Находим лучшее размещение средств для второго предприятия (на третьем с конца шаге) при s₃=4. Это х ₃(4)=2, остается s₂=s₃– x ₃(4)=4–2=2. На втором (с конца) шаге x ₂(2)=1 и на последнее предприятие (первый с конца шаг) остается s₁= s₂ – x ₂(2)=2–1=1 и x₁(1)=1.

Максимум суммарной прибыли равен 24 у.е.