416 417

416 Programowanie dynamiczne

dzielamy na realizację projektu o numerze t (7=1, 2, 3). Stanem y, procesu na początku etapu t jest kwota, którą możemy dysponować w tym etapie, pozostała po odjęciu od wielkości całego funduszu kwot przydzielonych projektom o numerach 1,    f-1.

Decyzją x, dla etapu l jest wielkość funduszu, jaką chcemy przekazać na realizację projektu t. Wielkość funduszu, jaka pozostała do rozdziału na początku etapu /+l, jest różnicą między wielkością funduszu, jaką dysponowaliśmy na początku etapu t, oraz ilością środków przeznaczonych na realizację projektu o numerze t. Funkcja przejścia ma więc postać:

y,+ \=-y,-x,.

Funkcja korzyści dla etapu t określa wartość zysku otrzymanego w związku z realizacją projektu o numerze t.

Określimy zbiory stanów dopuszczalnych procesu na początku poszczególnych etapów. Stan początkowy jest zadany i wynosi 6, czyli y, = {6}. Na początku etapu 2 rozpatrywany przez nas proces może się znaleźć w stanie 0 (gdy na realizację projektu I przydzielono cały fundusz), w stanie 1 (gdy na realizację projektu I przydzielono 5 jednostek funduszu) lub też w jednym z pozostałych stanów, 2, 3, 4, 5 lub 6, które interpretujemy podobnie jak stany 0 i 1.

Na początku etapu 3 proces może się znaleźć w stanie 0 (jeżeli cały fundusz przydzielono na realizację projektu 1 i II), w stanie 1 (gdy pierwszemu i drugiemu projektowi przydzielono łącznie 5 jednostek) lub też w jednym z pozostałych stanów, 2, 3, 4, 5, 6. Ponieważ zamierzamy rozdzielić cały fundusz, stan końcowy procesu jest zadany i wynosi 0. Otrzymujemy więc następujące zbiory stanów:

(6),

y₂={0, 1, 2, 3, 4, 5. 6}, y,= {0, I, 2, 3, 4, 5, 6),

y₄={0).

Zajmiemy się teraz zbiorami decyzji dopuszczalnych dla kolejnych stanów dopuszczalnych. W etapie pierwszym, mając do dyspozycji 6 jednostek, możemy nie przydzielić żadnych środków na realizację projektu I bądź też przydzielić 1. 2, 3, 4, 5 lub 6 jednostek, stąd:

X,(6)={0, 1, 2, 3, 4, 5, 6).

Jeżeli na początku etapu 2 proces znajdzie się w stanie 0 (co oznacza, że wszystkie środki przydzielono na realizację projektu 1 (czyli na realizację pozostałych projektów nie ma już żadnych dodatkowych środków), to:

X₂(0)={()}.

Dysponując na początku etapu 2 funduszem w wysokości 1 jednostki, możemy nie przydzielić żadnych środków na realizację projektu II lub też przydzielić je w wysokości 1 jednostki, stąd:

x₂(1)={0, 1}.

Kontynuując powyższy tok rozumowania, uzyskamy pozostałe zbiory decyzji dopuszczalnych dla kolejnych stanów etapu 2. Zbiory te są następujące:

X₂(2) = {0, 1, 2),

X₂(3)={0, 1, 2, 3),

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

X₂(5)= {(), 1, 2. 3, 4, 5),

X₂(6)={0, 1, 2, 3, 4, 5, 6}.

Ponieważ mamy rozdysponować cały fundusz, a na początku etapu 3 pozostanie do dyspozycji pewna kwota, przekażemy ją w całości na realizację projektu III. Tak więc:

X,(0)={0),

X₃(l)={1},

Xj(2)= {2 j,

Xj(3)= (3),

Xj(4)= (4},

X₃(5)={5),

X₃(6)={6).

Widzimy, że przy konstrukcji zbiorów decyzji dopuszczalnych dla ustalonego stanu y„ musi być spełniony oczywisty warunek:

y, > x,.

Wartości funkcji f (y,. x) określają zysk z realizacji projektu o numerze t, jeżeli na początku etapu t dysponowaliśmy kwotą y, i przeznaczyliśmy na realizację projektu kwotę x,. Na podstawie wartości zapisanych w tablicy 9.1 możemy wypisać kolejne wartości tej funkcji. Łatwo zauważyć, że wartości te zależą od ilości środków przeznaczonych na realizację projektu i, natomiast nie zależą od ilości środków, jakie mamy do dyspozycji na początku tego etapu. Tak więc:

f\ (6, 0) = 0, /,(6, 1) = 1,5, /,(6, 2) = 2,5, /,(6, 3) = 4, /,(6, 4) = 5, f (6, 5) = 6,2, f\ (6, 6) = 7,3,

/2 0-2. 0) = 0, /₂(y₂, 1) = 2,5, f₂(y₂, 2) = 4,1. /₂(y₂, 3) = 5,5, /₂(y₂, 4) = 6,5, f2(y'2, 5) = 5,5, /iOh. 6) = 8,

/₃(0, 0) = 0,

/,(1, 1) = 2.8, /₃(2, 2) = 4,5, /₃(3, 3) = 6,5, /₃(4, 4) = 7,8, /₃(5, 5) = 9,

/₃ (6, 6) =10,2.