404 405

404 Programowanie dynamiczne

Dla stanu y₃ = 3 mamy odpowiednio:

x₃ = 0, 3 + 0 - 3 = 0, x₃ = 1, 3 + 1 — 3 5* 0, x₃ = 2, 3 + 2 — 3 5* 0, *₃ = 3, 3 + 3 — 3?t0, jc₃ = 4, 3 + 4-35*0,

czyli Oe X₃(3), czyli I e xj(3), czyli 2g X₃(3), czyli 3 ć X₃(3), czyli 4<E X₃(3),

a stąd:

X,(2)={0).

Zestawiając obecnie otrzymane zbiory stanów i decyzji, otrzymujemy:

y.=m

Y₂={ 0, 1,2} y₃={0, 1,2,3}

X,(l)={2, 3,4} X,(0)=(3,4} X₂(l)=(2, 3, 4} X-,(2) = {1, 2, 3, 4} X,(0)={3)

X₃(l)= {2}

X₃(2)={1}

*_a(3)= {0}

n={0}.

Rozpatrywany proces możemy zilustrować graficznie, przyjmując, że sta nom procesu odpowiadają wierzchołki grafu, a decyzjom — łuki. Liczby w nawiasach to wartości zmiennych decyzyjnych. Odpowiedni graf został przedstawiony na rys. 9.1.

Rysunek 9.1

9.2.3. Wartości funkcji kosztów etapowych

Stwierdziliśmy już uprzednio, że koszty uzupełnienia zapasów będziemy obliczać ze wzoru:

f (y,. x,) = k, X,(x,) + c, x, + m, <y,+x,~ cl,).

Dla poszczególnych stanów i odpowiadających im decyzji obliczamy kolejno:

f(fl, 3) = 1 • 8 + 2 • 3 + 3 ■ (0 + 3-3) = 14,

/(O, 4)=1 -8 + 2- 4 + 3-(0 + 4 —3)=19,

/,(1, 2)= 1-8 + 2-2 + 3-(1+2-3) = 12,

/(l, 3)= 1-8 + 2-3 + 3-(1 + 3-3)= 17,

/,(!, 4)= 1-8+2-4 + 3-(1 +4-3) = 22,

f(2, 1)= 1-8 + 2-1+3 -(2+ 1-3) = 10,

/(2, 2)= 1-8 + 2-2 + 3 (2 + 2-3)= 15, f( 2. 3) = 1 -8 + 2-3 +3-(2+ 3 —3) = 20,

/,(2, 4)=1 - 8 + 2- 4 + 3-(2 + 4-3) = 25,

/,(3, 0)= 1-8 + 2 0+3-(3 + 0-3) = 0.

Obliczone wartości nanosimy na graf procesu tak, jak to zostało przedstawione na rys. 9.2.

Rysunek 9.2