412 413

412 Programowanie dynamiczne

9. Konstruujemy optymalną realizację procesu. Korzystając z optymalnego stanu początkowego i strategii optymalnej, znajdujemy decyzję optymalną dla stanu yf, czyli jtf (yf), którą oznaczamy jako xf. Funkcja przejścia daje nam optymalny stan początkowy drugiego etapu:

y* = 0₂(yf, xf).

Kontynuując to postępowanie, otrzymujemy optymalny ciąg stanów

i decyzji. Możemy więc zapisać:
yf optymalny stan początkowy	xf =xf(yf)
yf = Q,(yf, xf)	x$=xf (yf)
yf = &T-t(y?-t, ^xf~i) yhi=&r(yh xf)	xf- = xf(yf)

Ciąg (yf, jef, y$, jcJ, ..., yf, xf, y-f₊,} tworzy optymalną realizację procesu. Jeżeli istnieje dokładnie jeden optymalny stan początkowy i dokładnie jedna strategia optymalna, to mamy wówczas dokładnie jedną optymalną realizację procesu. Jeżeli optymalnych stanów lub strategii jest więcej, możemy wyznaczyć wszystkie optymalne realizacje procesu, rozpatrując kolejne optymalne stany i strategie optymalne.

9.3. Przykłady wykorzystania

programowania dynamicznego

9.3.1. Zagadnienie rozdziału środka

Pokażemy teraz sposób wykorzystania metody programowania dynamicznego w przypadku, gdy zbiory stanów i decyzji nie są skończone. Nie istnieje więc wykorzystana uprzednio możliwość jawnego wypisania wszystkich stanów i decyzji.

Przykład 9.2

Rozdzielamy pewien środek na realizację dwóch projektów w odcinku czasu podzielonym na trzy okresy nazywane dalej etapami. Ilość a środka przydzielona na realizację projektu I, przynosi w ciągu jednego etapu dochód 2a² i zmniejsza się do ilości 0,7a. Ilość b środka, przydzielona na realizację projektu II, przynosi w ciągu jednego etapu dochód 3b² i zmniejsza się do ilości 0,3b. Początkowa ilość środka, jaką dysponujemy, wynosi 100 jednostek. Należy dokonać takiego rozdziału środka w poszczególnych etapach dla obydwu projektów, aby zmaksymalizować łączny dochód z realizacji projektów I i II.

Zadanie można przedstawić jako trzyetapowy proces decyzyjny. Stanem procesu na początku danego etapu jest ilość środka, jaka pozostała do dyspozycji na początku tego etapu (po uprzednim wykorzystaniu w etapach poprzednich). Decyzją x, jest ilość środków przydzielona na początku etapu t na realizację projektu I. Pozostałe środki w ilości y,—x, zostają przydzielone na realizację drugiego projektu.

Funkcja przejścia ma postać:

y,_t i = 0,7¹, + 0,3 (y, - x,) = Q,4x< + 0,3y,.

Wyznaczymy zbiory stanów dopuszczalnych dla poszczególnych stanów. Stan początkowy jest zadany — mamy do dyspozycji 100 jednostek środka, stąd >>, = = 100. Przydzielając w etapie pierwszym cały zasób środka na realizację projektu 1, na początku etapu drugiego będziemy dysponowali ilością y₂ = 70 jednostek. Przydzielając cały zasób środka na realizację projektu II, na początku etapu 2 będziemy dysponowali ilością 30 jednostek.

Łatwo się przekonać, że dla każdego podziału środków, w którym zarówno projektowi I, jak i projektowi II przydzielimy dodatnią ilość środka, na początku etapu 2 będziemy dysponowali ilością środka z przedziału (30, 70). Prowadząc dalej analogiczne rachunki, stwierdzimy, że ilość środka, jaką dysponujemy na początku trzeciego etapu, mieści się w przedziale [9, 49], a ilość środka, jaką dysponujemy na końcu procesu, w przedziale [2,7; 34,3].

Jeżeli na początku dowolnego etapu znajdziemy się w stanie y„ to możemy podjąć jedną z następujących decyzji:

1

przydzielić cały zasób środka na realizację projektu I (czyli x, = y,),

• przydzielić cały zasób środka na realizację projektu II (czyli jc, = 0),

•    dokonać takiego podziału środka między projekty, przy którym ilości środka przydzielone poszczególnym projektom są różne od zera (czyli x, e (0, y,)).

Zbiór decyzji dopuszczalnych przy zadanym stanie y, ma więc postać:

X,0’,) = [0,y,].

Dla stanu y,e Y, i decyzji x, e X,(y,) funkcja korzyści dla etapu t ma postać: f 0’p x,) = 2x², + 3 (y,-x,)⁷.

Zapiszemy równania optymalności. Przypuśćmy, że na początku trzeciego etapu dysponujemy ilością środka y₃. Określamy funkcję:

g?(y₃) = max [f₃(y₃, x₃):x₃e X,(y₃)} = max (2xy + 3(y₃—^r₃)²: t₃eXj(y,)).

Wykresem funkcji h₃(x₃) = 2x\ + 3 (y₃ -x_})² jest parabola skierowana ramionami do góry.

Oznacza to, że funkcja h₃(x_}) może osiągać maksimum tylko na końcach przedziału [0, y₃]. Podstawiając wartość x₃=y₃, otrzymujemy h₃(y₃) = 2y\. Przydzielając cały zasób środka na realizację projektu II, mamy h_i(0) = 3yj. Widać