Page 211 - 4685
P. 211
Капіталовкладення (x), гр. од. Приріст випуску продукції і-го підприємства g i
(x), од./год
1 2 3 4
0 0 0 0 0
50 25 30 36 28
100 60 70 64 56
150 100 90 95 110
200 140 122 130 142
Потрібно скласти план розподілу обмежених капіталовкладень по цих
підприємствах (К= 200 грошових одиниць або гр. од.), що максимізує
загальний приріст випуску при заданій номенклатурі і структурі галузевого
плану виробництва продукції.
Рішення. Дане завдання може бути вирішене методом динамічного
програмування. Позначимо: g (х) – приріст випуску продукції на i-му
i
підприємстві при х одиниць капіталовкладень на реконструкцію або
розширення активної частини його основних фондів; F (К) – максимально
можливий приріст випуску продукції при розподілі суми К між чотирма
підприємствами.
Тоді, згідно основного функціонального рівняння Беллмана,
F (К) = max[g (x) + F (K- х)];
3
4
4
0 ≤х≤К
F (х)=max[g (х)] = g (х);
1
1
1
0 ≤х≤К
тобто максимальний приріст випуску продукції на першому підприємстві
при розподілі для нього х (0 ≤х≤К) одиниць капіталовкладень (лише для нього)
відповідатиме значенням графи 2 вихідних даних.
Реалізація завдання полягатиме в послідовному вирішенні рівнянь
Беллмана, що описують максимальний приріст випуску при розподілі К=200
між двома підприємствами, потім трьома і чотирма. В процесі обчислень х
змінюється від 0 до K з кроком ∆= 50.
F (50) = max [g (х) + F (50 - х)] =
1
2
2
0 ≤х ≤50
= max [g (0) + g (50); g2 (50) + g (0)= max [0 + 25; 30 + 0] = 30;
1
1
2
F (100) = max [ (x) + F (100 - x)] = max [(g (0) +g (100); g (50) +
2
g2
1
1
2
2
0 ≤ х ≤ 100
+ g (50); g (100) + g (0) = max [0 + 60; 30 + 25; 70 + 0] = 70;
1
1
2
F (150) = max [g (x) + F (150 - x)] = max [g (0) + g (150); g (50) +
2
2
1
2
1
2
0 ≤ х ≤150
+ g (100); g (100)+ g (50); g (150) + g (0)= max [0 + 100; 30 + 60; 70 +
2
2
1
1
1
25; 90 + 0] = 100;
F (200) = max [g (x) + F (200) - x)] = max [g (0) + g (200); g (100) +
2
2
1
2
1
2
0 ≤ х ≤150
+ g (100); g (150) + g (50); g (50) + g (150); g (200) + g (0) = max [0 +
1
2
2
1
2
1
1
140; 60 + 70; 25 + 90; 100 + 30; 122 + 0] = 140;
і так далі:
207