Распределение 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) Здесь процесс распределения средств можно рассматривать как многошаговый, номер шага совпадает с номером предприятия; состояние будет определяться величиной sn – количество средств, подлежащих распределению на n-м шаге (с конца). Обозначим fn(sn) – условную оптимальную прибыль, полученную от последних n предприятий при распределении между ними sn средств и вычисляемую в соответствие с динамическим рекуррентным соотношением: fn(sn)=mах"х(сn(х n) + fn-1(sn-1)), n=1,2,…,N. (2.8.4) Пример 2.8.2. Пусть N = 4, Q =5, значения сn(х n) заданы в табл. 2.8.1. Таблица 2.8.1.
Как и в предыдущем примере начинаем анализ с последнего предприятия. Индекс «1» соответствует последнему предприятию, а индекс «4» –первому. Для n=1 прибыль проставлена в последней колонке. Для n=2 f2(0)=mах[с2(0)+f1(0)]=0 при x 2(0)=0, f2(1)=mах[с2(1)+f1(0),с2(0)+f1(1)]=mах[3+0,0+4]=4 при x 2(1)=0, f2(2)=mах[с2(2)+f1(0),c2(1)+f1(1),с2(0)+f1(2)]= =mах[4+0,3+4,0+6]=7 при x 2(2)= 1, f2(3)=mах[с2(3)+f1(0),с2(2)+f1(1),с2(1)+f1(2),с2(0)+f1(3)]= =mах[7+0,4+4,3+6,0+8]=9 при x 2(3)=1, f2(4)=mах[с2(4)+f1(0),с2(3)+f1(1),с2(2)+f1(2),с2(1)+f1(3),с2(0)+f1(4)]= =mах[11+0,7+4,4+6,3+8,0+13]=13 при х 2(4)=0, f2(5)=mах[с2(5)+f1(0),с2(4)+f1(1),с2(3)+f1(2),с2(2)+f1(3),с2(1)+f1(4),с2(0)+f1(5)] =mах[18+0,11+4,7+6,4+8,3+13,0+16]=18 при x2(5)=5. Для n=3 f3(0)=mах[с3(0)+f2(0)]=0 при x3(0)=0, f3(1)=mах[с3(1)+f2(0),с3(0)+f2(1)]=mах[6+0,0+4,]=6 при x 3(1)=1, f3(2)=mах[с3(2)+f2(0),c3(1)+f2(1),с3(0)+f2(2)]= =mах[9+0,6+4,0+7]=10 при x 3(2)=1, f3(3)=mах[с3(3)+f2(0),с3(2)+f2(1),с3(1)+f2(2),с3(0)+f2(3)]= =mах[11+0,9+4,6+7,0+9]=13 при x 3(3)=1 или 2, f3(4)=mах[с3(4)+f2(0),с3(3)+f2(1),с3(2)+f2(2),с3(1)+f2(3),с3(0)+f2(4)]= =mах[13+0,11+4,9+7,6+9,0+13]=16 при х 3(4)=2, f3(5)=mах[с3(5)+f2(0),с3(4)+f2(1),с3(3)+f2(2),с3(2)+f2(3),с3(1)+f2(4),с3(0)+f2(5)] =mах[15+0,13+4,11+7,9+9,6+13,0+18]=19 при x 3(5)=1. И, наконец, для n=4 f4(0)=mах[с4(0)+f3(0)]=0 при x 4(0)=0, f4(1)=mах[с4(1)+f3(0),с4(0)+f3(1)]=mах[8+0,0+6,]=8 при x 4(1)=1, f4(2)=mах[с4(2)+f3(0),c4(1)+f3(1),с4(0)+f3(2)]= =mах10+0,8+6,0+10]=14 при x 4(2)=1, f4(3)=mах[с4(3)+f3(0),с4(2)+f3(1),с4(1)+f3(2),с4(0)+f3(3)]= =mах[11+0,10+6,8+10,0+13]=18 при x 4(3)=1, f4(4)=mах[с4(4)+f3(0),с4(3)+f3(1),с4(2)+f3(2),с4(1)+f3(3),с4(0)+f3(4)]= =mах[12+0,11+6,10+10,8+13,0+16]=21 при х 4(4)=1, f4(5)=mах[с4(5)+f3(0),с4(4)+f3(1),с4(3)+f3(2),с4(2)+f3(3),с4(1)+f3(4),с4(0)+f3(5)] =mах[18+0,12+6,11+10,10+13,8+16,0+19]=24 при x 4(5)=1. Теперь соберем оптимальное решение (при последовательном рассмотрении всех состояний оптимальные переходы подчеркивались): Для первого предприятия, когда s4=5, видим, что x 4(5)=1, значит, первое предприятие получает 1 и остается s3=s4– x 4(5)=5–1=4. Находим лучшее размещение средств для второго предприятия (на третьем с конца шаге) при s3=4. Это х 3(4)=2, остается s2=s3– x 3(4)=4–2=2. На втором (с конца) шаге x 2(2)=1 и на последнее предприятие (первый с конца шаг) остается s1= s2 – x 2(2)=2–1=1 и x1(1)=1. Максимум суммарной прибыли равен 24 у.е.
|
