Решить задачу методом динамического программирования (по вариантам)

S0 = 600 усл. ед. (начальное состояние системы)
хk – средства, выделенные к-му предприятию (управление на к-ом шаге);
Sк – количество денежных средств, которые необходимо распределить между оставшимися к предприятиями (состояние системы после к-го шага);
n = 5 (число этапов или шагов);
- оптимальная прибыль, полученная от к-го, (к+1)-го, n – го предприятий, если между ними распределили средства Sk-1
Математическая модель задачи:
1) ограничения на выделяемы средства
,
2) уравнения состояния
Sk = Sk-1 – xk , 0 ≤ Sk-1 ≤ 600
3) целевая функция
Z =
Уравнения Беллмана
к = 5, 5 этап
к = 4, 4 этап
к = 3, 3 этап
к = 2, 2 этап
к = 1, 1 этап
Заполним таблицу.
Этап 5:F5(c5)=g5(x5)
С5 X5=0 X5=100
X5=200 X5=300
X5=400 X5=500
X5=600
F5(C5) X5*
0 0 - - - - - - 0 0
100 - 49 - - - - - 49 100
200 - - 55 - - - - 55 200
300 - - - 58 - - - 58 300
400 - - - - 59 - - 59 400
500 - - - - - 60 - 60 500
600 - - - - - - 61 61 600
Этап 4:F4(c4)=g4(x4)+F5(c4-x4)
С4
X4=0 X4=100 X4=200 X4=300 X4=400 X4=500 X4=600 F4(C4) X4*
0 0+0=0 - - - - - - 0 0
100 0+49=49 71+0=71 - - - - - 71 100
200 0+55=55 71+49=120 77+0=77 - - - - 120 100
300 0+58=58 71+55=126 77+49=126 82+0=82 - - - 126 200
400 0+59=59 71+58=129 77+55=132 82+49=131 84+0=84 - - 132 200
500 0+60=60 71+59=130 77+58=135 82+55=137 84+49=133 86+0=86 - 137 300
600 0+61=61 71+60=131 77+59=136 82+58=140 84+55=139 86+49=135 87+0=87 140 300
Этап 3:F3(c3)=g3(x3)+F4(c3-x3)
С3 X3=0 X3=100 X3=200 X3=300 X3=400 X3=500 X3=600 F3(C3) X3*
0 0+0=0 - - - - - - 0 0
100 0+71=71 65+0=65 - - - - - 71 0
200 0+120=120 65+71=136 73+0=73 - - - - 136 100
300 0+126=126 65+120=185 73+71=144 75+0=75 - - - 185 100
400 0+132=132 65+126=191 73+120=193 75+71=146 78+0=78 - - 193 200
500 0+137=137 65+132=197 73+126=199 75+120=195 78+71=149 80+0=80 - 199 200
600 0+140=140 65+137=202 73+132=205 57+126=182 78+120=198 80+71=151 82+0=82 205 200
Этап 2:F2(c2)=g2(x2)+F3(c2-x2)
С2
X2=0 X2=100 X2=200 X2=300 X2=400 X2=500 X2=600 F2(C2) X2*
0 0+0=0 - - - - - - 0 0
100 0+71=71 49+0=49 - - - - - 71 0
200 0+136=136 49+71=120 55+0=55 - - - - 136 0
300 0+185=185 49+136=185 55+71=126 58+0=58 - - - 185 0,100
400 0+193=193 49+185=234 55+136=191 58+71=129 59+0=59 - - 234 100
500 0+199=199 49+193=242 55+185=240 58+136=194 59+71=130 60+0=60 - 242 100
600 0+205=205 49+199=248 55+193=248 58+185=243 59+136=195 60+71=131 61+0=61 248 100
Этап 1:F1(c1)=g1(x1)+F2(c1-x1)
С1
X1=0 X1=100 X1=200 X1=300 X1=400 X1=500 X1=600 F1(C1) X1*
0 0+0=0 - - - - - - 0 0
100 0+71=71 51+0=51 - - - - - 71 0
200 0+136=136 51+71=122 59+0=59 - - - - 136 0
300 0+185=185 51+136=187 59+71=130 64+0=64 - - - 187 100
400 0+234=234 51+185=236 59+136=195 64+71=135 67+0=67 - - 236 100
500 0+242=242 51+234=285 59+185=244 64+136=200 67+71=138 70+0=70 - 285 100
600 0+248=248 51+242=293 59+234=293 64+185=249 67+136=103 70+71=141 71+0=71 293 100,200
1-му предприятию выделить 100 2-му предприятию выделить 100 3-му предприятию выделить 200 4-му предприятию выделить 100 5-му предприятию выделить 100 Что обеспечит максимальный доход, равный 293