420 421

420 Programowanie dynamiczne

	A(5, 0) + gf (5)		0 +9		9
	m i)+s?(4)		2,5+7,8		10,3
gf(5) = max <	/2(5, 2) + g?(3)	> = max <	4,1+6,5	►=max <	10,6
	/2(5, 3)+rf(2)		5,5+4,5		10
	f2(5, 4) + *f(l)		6,5+ 2,8		9,3
	/a(5, 5) + gf (0)		7,5 + 0		7,5

oraz xf(5) = 2,

	/a(6, 0) + *f(6)		0 +10,2'		10,2
	/2(6, l) + g?(5)		2,5 + 9		11,5
	/2(6, 2)+*f(4)		4,1+7,8		11,9
max •	/2(6, 3)+g*(3)	i - max <	5,5 + 6,5	> = max'	12
	M6, 4)+g$(2)		6,5+ 4,5		11
	/2(6, 5) + gf (1)		7,5+ 2,8		10,3
	/2(6, 6)+gf (0)		8,0 + 0		8

oraz xf(6) = 3.

Etap 1

W pierwszym etapie pytamy, jakie środki należy przydzielić na realizację pierwszego projektu, aby łączny zysk z realizacji wszystkich projektów był maksymalny, zakładając, że w trakcie trwania całego projektu będziemy postępowali w sposób optymalny. Obliczamy wartość:

gf(y,) = max {/,(.y„ *,) + £? Oh -*■): Jc_leX,Cy_l)},

czyli maksymalny zysk z realizacji wszystkich trzech rozpatrywanych projektów, jeżeli na ich realizację możemy przydzielić środki w wysokości _y,. Dla interesującej nas wartości y, = 6 otrzymujemy:

	/i (6, 0) + gf (6)		0 +12		12 '
	/i(6, l) + g?(5)		1,5+10,6		12,1
	/,(6, 2) + gf (4)		2,5 + 9		11,5
max i	/,(6, 3) + gf(3)	> = max <	4 +7	> = max <	11
	/,(6, 4) + gJ(2)		5 +5,3		10,3
	/,(6, 5) + g*(l)		6,2+ 2,8		9
	/,(6, 6) + g?(0)		7,3 + 0		7,3

oraz (6)= 1.

Tak więc optymalny sposób podziału posiadanego funduszu przynosi nam łączny zysk z realizacji wszystkich projektów w wysokości 12,1 jednostek. Konstruujemy optymalny ciąg stanów i decyzji:

y f = 6,    =jc?(6)= 1,

y$=y*—xf = 6 — 1 =5,    xf =x$(5) =2,

yf=y*-xf = 5—2=3,    xf =xf(3) = 3,

yf = y f-xf = 3-3 = 0.

Na realizację projektu 1 należy przydzielić 1 jednostkę funduszu, na realizację projektu 11 — 2 jednostki, a na realizację projektu III — 3 jednostki.

Korzystając z wcześniejszych obliczeń, można również odpowiedzieć na pytanie, w jaki sposób zmieni się optymalny podział funduszu, jeżeli z jakichś względów zmniejszy się on do wysokości 5, 4, 3, 2 lub 1 jednostki. Aby to rozstrzygnąć, wystarczy obliczyć wartości funkcji g*(yi) dla yf = 5, 4, 3, 2, 1 oraz odpowiadające im wartości j: *(>’¥), a następnie wielkości funduszu przydzielane poszczególnym projektom. Wyniki obliczeń zestawiono w tablicy 9.2.

Tablica 9.2

Wielkość funduszu y*		Optymalny ciąg decyzji
		r* 1	r* ^A 2	X*
1	2,8	0	0	1
2	5,3	0	i	1
3	7,0	0	i	2
4	9,0	0	i	3
5	10,6	0	2	3
6	12,1	1	2	3

9.3.3. Dwukryterialne zagadnienie alokacji

Zadania dynamiczne można również rozpatrywać w ujęciu wielokryterialnym. Jeżeli interesuje nas znalezienie zbioru realizacji niezdorninowanych w przestrzeni kryterialnej i zbioru realizacji sprawnych w przestrzeni decyzyjnej, możemy do tego celu wykorzystać wektorową wersję zasady optyrnalności Bellmana. Pokażemy tę możliwość na przykładzie dwukryterialnego zadania rozdziału środków.

Przykład 9.4

Dany jest pewien system, złożony z trzech modułów. Dysponujemy zasobem środka w ilości 6 jednostek, które należy rozdzielić między poszczególne moduły. Przewidywane zależności pomiędzy ilościami środka przydzielonymi poszczególnym modułom a korzyściami oraz niezawodnością modułów przedstawiono w tablicy 9.3. Całkowita korzyść z działania systemu (o suma zysków dla poszczególnych modułów, natomiast niezawodność działania systemu to iloczyn niezawod-