Имеются четыре предприятия и сведения о том, какой прирост продукции они дадут в конце

Имеются четыре предприятия и сведения о том, какой прирост продукции они дадут в конце года, если между ними распределить 100 тыс. у.е. средств. Значения прироста выпуска продукции на предприятиях в зависимости от выделенных средств Х представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции. Х g1(x) g2(x) g3(x) g4(x) 0 0 0 0 0 20 12 14 20 29 40 36 32 36 33 60 34 42 27 46 80 49 56 32 50 100 55 59 38 44

I этап. Условная оптимизация
Запишем уравнение Беллмана на k-ом шаге:
ZkSk=max0≤xk≤Skgkxk+Zk+1(Sk-xk)
1-й шаг. k=4. Предполагаем, что все средства 100 тыс. у.е. переданы на инвестирование четвертого предприятия.
Заполним таблицу 1, рассмотрев все возможные значения для x4={0;20;40;60;80;100}.
Таблица 1
S4  X4 Z4(S4)) X4*
0 20 40 60 80 100
0 0           0 0
20   29         29 20
40     33       33 40
60       46     46 60
80         50   50 80
100           44 44 100
В этом случае максимальная прибыль составит Z4(S4)=50, x4* – значение, при котором достигается максимум Z4(S4).
2-й шаг. k=3. Определяем оптимальную стратегию инвестирования в третье и четвертое предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид
Z3S3=max0≤x3≤S2g3x3+Z4(S3-x3)
На его основе рассчитываются данные таблицы 2.
Значения g3x3 берутся из исходной таблицы, значения Z4S3-x3=Z4(S4) берутся из таблицы 1.
x3* – значение, при котором достигается максимум Z3(S3).
Таблица 2
S3  X3 Z3(S3)) X3*
0 20 40 60 80 100
0 0+0=0           0 0
20 0+29=29 20+0=20         29 0
40 0+33=33 20+29=49 36+0=36       49 20
60 0+46=46 20+33=53 36+29=65 27+0=27     65 40
80 0+50=50 20+46=66 36+33=69 27+29=56 32+0=32   69 20
100 0+44=44 20+50=70 36+46=82 27+33=60 32+29=61 38+0=38 82 40
3-й шаг

. k=2. Определяем оптимальную стратегию инвестирования во второе, третье и четвертое предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид
Z2S2=max0≤x2≤S2g2x2+Z3(S2-x2)
На его основе рассчитываются данные таблицы 3.
Значения g2x2 берутся из исходной таблицы, значения Z3S2-x2=Z3(S3) берутся из таблицы 2.
x2* – значение, при котором достигается максимум Z2(S2).
Таблица 3
S2  X2 Z2(S2)) X2*
0 20 40 60 80 100
0 0+0           0 0
20 0+29=29 14+0=14         29 0
40 0+49=49 14+29=43 32+0=32       49 0
60 0+65=65 14+49=63 32+29=61 42+0=42     65 0
80 0+69=69 14+65=79 32+49=81 42+29=71 56+0=56   81 40
100 0+82=82 14+69=83 32+65=87 42+49=91 56+29=85 59+0=59 91 60
4-й шаг. k=1. Определяем оптимальную стратегию инвестирования в первое, второе, третье и четвертое предприятия