414 415

414 Programowanie dynamiczne

więc, że korzystniej jest przekazać cały zasób środka na realizację projektu II, stąd:

(.V3> = 3yi a-f (>■,) = ().

Przechodzimy do etapu drugiego. Przypuśćmy, że na początku tego etapu dysponujemy ilością środka y₂. Określamy funkcję:

gf(y₂) = max [f₂(y₂, ^) + g?(0,4jc₂ + 0,3y₂):x₂e X₂(y₂)) =

= max {2xl + 3 (y₂ -x₂)² + 3 (0,4.v₂ + 0,3y₂)²: x₂ e X₂(y₂)) ■

Wykresem funkcji h₂(x₂)-2x₂ + 3(y₂— jc₂)² + 3(0,4x₂ + 0,3y₂)² jest ponownie parabola o ramionach skierowanych do góry. Porównując ze sobą wartości funkcji h₂(x₂) na końcach przedziału [0, y₂], stwierdzamy, że tym razem korzystniej jest przekazać cały zasób środka na realizację projektu I. Mamy:

g*(.V₂) = 3,47y₂, x$(y₂) = y₂.

Chcąc wyznaczyć optymalny podział środka y, w pierwszym etapie, definiujemy funkcję:

gf0’i) = max {/,(y,, *,) + gf (0,4*,+0,3y,) e X,(y,)} =

= max {2x? + 3(y, — jc,)² + 3,47(0,4X|-t-0,3y_t)²: x, eX|(yi)}.

Parabola /j,(x_l) = 2x:? + 3(y|-x₁)² + 3,47(0,4x,+0,3y,)² ma i tym razem ramiona skierowane do góry. Porównując wartości funkcji /?, na końcach przedziału [0, y,], stwierdzamy, że w pierwszym etapie najkorzystniej jest przydzielić cały posiadany zasób środka na realizację projektu I.

Ponieważ początkowa wartość środka jest równa y, = 100, otrzymujemy:

yf = 100,    xf =*f(100) = 100,

yf = 70,    xf =xf(70) = 70,

y f =49,    *f=**(49) = 0,

yj= 14.7.

W pierwszym i drugim etapie należy przydzielić cały posiadany aktualnie zasób środka (w ilościach, odpowiednio, 100 i 70 jednostek) na realizację projektu I, natomiast w okresie trzecim pozostałą ilość (49 jednostek) — na realizację projektu II. Okazuje się, że po zakończeniu trzeciego etapu pozostanie jeszcze 14,7 jednostek środków. Dochód osiągnięty przy takim podziale wynosi 37 003.

Rozwiązanie zadania otrzymaliśmy w postaci analitycznej. Pozwala ono na wskazanie optymalnego rozdziału środków dla dowolnej wartości początkowej y,. Jeżeli na przykład ilość środka na początku pierwszego etapu uległa zmniejszeniu do 80 jednostek, otrzymujemy:

yf = 80,    *f =*f(80) = 80,

yf = 56,    jef =*?(56) = 56,

yf = 39,2,    xf =xf (39,2) = 0,

yf = 11,76.

Mając na początku pierwszego okresu do dyspozycji 80 jednostek środka, należy w pierwszym i drugim etapie przydzielić cały zasób środka (w ilościach równych, odpowiednio, 80 i 56 jednostek) na realizację projektu 1, natomiast w etapie trzecim — pozostałą ilość środka, czyli 39,2 jednostki, na realizację projektu 11. Okazuje się, że po zakończeniu trzeciego etapu pozostanie jeszcze 11,76 jednostek środka. Dochód osiągnięty przy takim rozdziale wynosi 23 681,92.

9.3.2. Zagadnienie alokacji

Metodę programowania dynamicznego stosowaliśmy dotychczas dla procesów dynamicznych, przebiegających w czasie. W wielu przypadkach można zadanie statyczne przedstawić jako proces dynamiczny, przyjmując podział na etapy w umowny sposób. Możliwość taką omówimy w tym podrozdziale.

Przykład 9.3²

Dany jest fundusz wynoszący 6 jednostek (np. min zł), który należy podzielić między trzy projekty. Przewidywane wielkości zysku z realizacji tych projektów przedstawione są w tablicy 9.1.

Tablica 9.1

Wielkość przydzielonej kwoty	Zysk z projektu
	I	II	III
0	0	0	0
1	1,5	2,5	2,8
2	2,5	4,1	4,5
3	4,0	5,5	6.5
4	5,0	6,5	7.8
5	6,2	7,5	9.0
6	7,3	8	10,2

Należy rozdzielić fundusz między projekty w laki sposób, by zmaksymalizować łączną wartość zysku.

Przystępując do rozwiązania sformułowanego powyżej problemu metodą programowania dynamicznego, przyjmiemy umownie, że jest to trzyetapowy proces decyzyjny. W etapie o numerze t określamy, jaką część funduszu przy-

⁵ Zadanie opisane w tym przyktadze można rozwiq/.ać przy użyciu programu DYNAM2.EXE.