400 401

400 Programowanie dynamiczne

Zachodzi związek: f(y„ *r) = ^(*/) + P/0'<+i)-

Dla ułatwienia dalszych rozważań zdefiniujemy pomocniczą funkcję X, która przyporządkowuje dowolnej liczbie rzeczywistej wartość 1, gdy jest to liczba dodatnia, oraz 0, gdy nie jest to liczba dodatnia. Formalna definicja funkcji X. jest następująca:

wwj¹’ g^dy^r>⁰-" '    [O, gdyr^O.

W rozpatrywanym modelu koszty uzupełnienia zapasu w danym etapie są sumą kosztów stałych k„ niezależnych od skali uzupełnienia zapasów i kosztów zmiennych, proporcjonalnych do wielkości zamówienia. Jeżeli w pewnym etapie nie składamy zamówienia, to nie ponosimy kosztów stałych. Tak więc koszty uzupełnienia zapasów można zapisać następująco:

^,(x_l) = k_lX,(x,) + r,x_r

Koszty magazynowania w danym etapie są proporcjonalne do ilości produktu zmagazynowanego na końcu tego etapu. Uwzględniając odpowiedni współczynnik proporcjonalności m„ otrzymujemy:

Pamiętając o postaci funkcji przejścia, możemy napisać:

Fr(y,-i) = »V (y, + x,-d,).

Korzystając z wyprowadzonych powyżej związków, widzimy, że do obliczenia wartości funkcji uzupełnienia zapasów i magazynowania w etapie t możemy posłużyć się zależnością:

f (y„ x,) = k,-X, (x,) + c, ■ x, + m,-(y,+x,- d,).

9.2.2. Stany i decyzje dopuszczalne

Wyznaczymy zbiory stanów i decyzji dopuszczalnych dla kolejnych etapów, rozpoczynając od pierwszego.

Etap 1

Na początku pierwszego etapu w magazynie znajduje się jedna jednostka produktu. Oznacza to, że zbiór stanów początkowych procesu jest jednoclemen-towy, stąd:

r, = m.

Dla ustalonego stanu początkowego procesu znajdujemy decyzje dopuszczalne, zakładając, że rozpatrywany produkt jest niepodzielny. Korzystamy przy tym z zależności:

Xj(l)= {jc_t: 0<1+ X\ — 3^4, 0^JC|<4}.

Ponieważ z drugiego warunku mamy jc, = {0, l, 2, 3, 4}, obliczamy kolejno:

czyli 0« X,(l), czyli 1 g Aj(l), czyli 2e X,(l), czyli 3 6 X, (1), czyli 4€ Ar,(l),

jc, =0, OsU+O-3^4, jc, = 1, 0<l + l-3<4, jc, = 2, 05$l+2-3<4, jc, =3, 0<l+3-3<4, X\ =4, 0 ^ 1 +4-3 <4, tak więc:

X,(l)={2, 3,4}.

Etap 2

Zajmiemy się wyznaczeniem stanów i decyzji dopuszczalnych dla drugiego etapu. Wykorzystamy funkcje przejścia, która ma postać:

y₂ = yi+^i-3.

Podstawiając do tej zależności kolejne decyzje dopuszczalne ze zbioru Ajly,), otrzymujemy dla kolejnych wartości x,:

jc,=2, y₂=l+2 —3 = 0, jc, = 3, y₂ = 1 +3 — 3= 1,

=4, y₂=l+4-3 = 2, czyli:

r₂={ o, 1,2}.

Zajmiemy się teraz wyznaczeniem zbiorów decyzji dopuszczalnych dla kolejnych stanów etapu drugiego.

Dla stanu y₂ = 0 otrzymujemy:

X₂(0)={jc₂: 0sS0+x₂-3<4, 0s$x₂«$4}.

Ponieważ z drugiego warunku mamy x₂= {0, 1, 2, 3, 4), dla kolejnych wartości x₂ sprawdzamy, czy spełniony jest warunek pierwszy:

x₂ = 0.    0^0 + 0-3<4,    czyli    0<s    X₂(l),

x₂=1,    0$t0+l-3<4,    czyli    1 e    X₂(1),

jc₂ = 2,    0 3E 0 + 2-3 <4,    czyli    2e    X₂(l),

x_:. = 3,    0^0 + 3-3^4,    czyli    3e    X₂(l),

x> = 4,    0 ^0+4-3 <4,    czyli    4€    X₂(l),

tak więc:

,Y₂(0)={3, 4).