424 425

424 Programowanie dynamiczne

Znajdujemy zbiory:

G?(y₃) = 'max' {F₃(y₃, x₃): x₃e X₃(y₃)),

gdzie symbolem 'max' oznaczamy zbiór wektorów niezdorninowanych rozpatrywanego zbioru. Zbiór G*(y₃) zawiera więc niezdominowane wektory ocen dla trzeciego modułu. Pierwsza składowa każdego wektora z tego zbioru określa korzyść, jaką można uzyskać z działania tego modułu, natomiast druga składowa — jego niezawodność, jeżeli na działanie tego modułu można przydzielić y, jednostek środka.

Obliczamy kolejno:

x?(0)={0],

jc?(2)={2], jef (3) = {3}, •*?(4)={4), jcf(5)= {5}, Jtf(6)={6}.

Gf(0) = /'\(0, 0) = {[0; 0,9]},

Gf(l) = F₃(l, 1)= {[2,8; 0,961], G’t(2) = F₃(2, 2) ={[4,5; 0,984|}, Gf(3) = F₃(3, 3)={L6,5; 0,9936]}, G*(4) = F₃(4, 4) = {[7,8; 0,9974]}, G?(5) = F,(5, 5) = {[9,0; 0,999]}, G* (6) = F,(6, 6) ={[10,2; 0,9994]},

Przypuśćmy, że na początku drugiego etapu mamy do dyspozycji y₂ jednostek środka, y₂e Y₂. Pytamy się, ile środka należy przydzielić dla drugiego modułu, zakładając, że do końca procesu będziemy postępowali w taki sposób, aby znaleziony ciąg decyzji był sprawny. W tym celu obliczamy:

Ctf(y₂) = 'm&x' { F₂(y₂, x₂)°Gf(y₂-x₂): x₂e X₂(y₂)).

Zbiór Gf (y₂) zawiera niezdominowane wektory ocen dla drugiego i trzeciego modułu. Pierwsza składowa każdego wektora z. tego zbioru określa korzyść, jaką można uzyskać z działania tych modułów, natomiast druga składowa — ich niezawodność, jeżeli na działanie modułu drugiego można przydzielić y₂ jednostek środka.

Dla kolejnych stanów dopuszczalnych obliczamy:

Gf(0) = 'max' {[0; 0,9]o[0; 0,9|) ={|0; 0,81]} oraz (0)= {0},

G* (l) = 'max'

j[0; 0,9] o [2,8; 0,96]1 {[2,5; 0,94] o [0; 0,9]J

=' max'

f [2,8; 0,864] 1 {[2,5; 0,846] (

= [2,8; 0,864]

oraz jc?(1)= {0},

	[0; 0,9] o [4,5; 0,984]		(4,5; 0,8856]
Gf(2) = 'max'-	[2,5; 0,94] o [2,8; 0,961 [4,1; 0,964] o [0; 0,9]	• = 'max'-	[5,3; 0,9024] [4,1; 0,8676]

= [5,3; 0,9024]

oraz x$(2) = {I},

Gf (3) = 'max'<

10; 0,9] o [6,5; 0,99361 [2,5; 0,941 o [4,5; 0,984j | 14,1; 0,964| o [2,8; 0,961 [5,5; 0,9784] o [0; 0.9]

= niax

[6,5; 0,8942]1 [?; 0,925]    [_J [7; 0,925]

[6,9; 0,9254] 15,5; 0,8805|

[6,9; 0,9254]

oraz xf(3)=[l, 2],

G?(4) = 'max’<

[0; 0,9] o 17,8; 0,9974]		[7,8; 0,8977]
[2,5; 0,94] o 16,5; 0,9936]		|9; 0,9340]
[4,1; 0,964] o 14,5; 0,984]	> = 'max'‘	[8,6; 0,94861
[5,5; 0,97841 o [2,8; 0,96]		18,3; 0,9393]
[6,5; 0,98701 o [0; 0,9]		[6,5; 0,8883]

[9; 0,9340] [8,6; 0,9486]

oraz xj(4)= (1, 2),

GJ(5) = 'max'<

[0; 0,9] o [9,0; 0,9991		[9; 0,899]
[2,5; 0,94] o [7,8; 0,9974]		[10,3; 0,9376|
[4,1; 0,964] o [6,5; 0,9936|	> =' max' <	[10,6; 0,9578]
[5,5; 0,97841 o [4,5; 0,9841		[10; 0,9627]
[6,5; 0,9870] o 12,8; 0,961		[9,3; 0,9475]
[7,5; 0,9922] o [0; 0,9]		17,5; 0,89301

[10,6; 0,957811 [10; 0,9627] J

oraz xf(5) = (2, 3],

[0; 0,9] o 110,2; 0,99941 [2,5; 0,94| o [9,0; 0,9991 [4,1; 0,9641 o [7,8; 0,9974]

[10,2; 0,8995]' [11.5; 0,9391] [11.9; 0,9615]

Gf (6) = 'max'< [5,5; 0,9784] o [6,5; 0.9936|| = 'maxW [12; 0,9721]

16,5; 0,9870] o [4,5; 0,9841 [7,5; 0,99221 o [2,8; 0,961 18,0; 0,9953] o [0; 0,91 = [12; 0,9721)

[U; 0,9712] [10,3; 0,9525| 18; 0,8958)

> =

oraz x*(6) = 3.

Na początku pierwszego etapu proces znajduje się w stanie y, = 6. Znajdujemy; Gf(y,) = 'max' [F,(y„ z,)oGf(y,-x_l): x,e X,(y,)), czyli;