35466 img375 (3)

w miarę bc/.picc/.nie, ;i im.iu| bezpieczeństwa na danej linii l*vly sławki pobierane prze/ towarzystwo ulrczpicczeiiiowc. Rozwiązanie problemu wymagało podzielenia ealej liasy na etapy, a w każdym z etapów określenia miast etapowych oraz wszystkich możliwych połączeń pomiędzy nimi.

Łatwo można solne wyobrazić inne możliwości zastosowania tak sformułowanego zagadnienia do szerokiej klasy problemów poszukiwania najkrótszej lub najdłuższej drogi w sieci.

Oba wcześniej wymienione zagadnienia można rozwiązać stosując podejście charakterystyczne dla programowania dynamicznego. Polega ono na podziale zagadnienia pierwotnego na podproblemy lub etapy, a następnie na ich sekwencyjnym rozwiązywaniu, aż do znalezienia rozwiązania optymalnego. Stosuje się przy tym, niezależnie od algorytmu, zasadę optymalności Bellmana, w myśl której optymalne rozwiązanie zagadnień z zakresu programowania dynamicznego ma tę własność, że optymalne rozwiązanie dla /c-tego etapu jest jednocześnie rozwiązaniem optymalnym dla etapów k, k + l, ..., N. Tak więc optymalne rozwiązanie dla etapu pierwszego stanowi optymalne rozwiązanie dla całego problemu.

W związku z powyższą zasadą problem z zakresu programowania dynamicznego rozwiązuje się rozpoczynając od poszukiwania rozwiązania dla ostatniego etapu (7Vj, a następnie idąc wstecz poszukuje się rozwiązania dla etapu N— 1. Uzyskane w ten sposób rozwiązanie dla etapów N— 1 oraz fVjest optymalne bez względu na to, w jaki sposób osiągnięto etap N— 1. Powtarzając powyższy sposób etap po etapie, dochodzimy do rozwiązania optymalnego dla pierwszego etapu, a więc i dla całego problemu.

Powyższa zasada zostanie zilustrowana na przykładzie zagadnienia alokacji inwestycji oraz problemu dyliżansu.

Przykład 39. Przedsiębiorca Jerzy Płatek, posiadający kredyt inwes-lycyjny w wysokości 6 min zł oraz halę produkcyjną w Krakowie, postanowił zainstalować nowoczesne linie piekarnicze: francuską (F), szwedzką (S) oraz polską (P). Dobowe zdolności produkcyjne pieczywa (w tonach), w zależności od wysokości nakładów inwestycyjnych przeznaczonych na zainstalowanie linii produkcyjnej danego typu, przedstawiono w tabl. 181.

Tablica 181

Nakłady (w min zł)		0	1	2	3	4	5	6
Zdolności	F	0	6	12	12	12	15	20
produkcyjne	S	0	5	8	11	14	17	18
linii (w t)	P	0	4	15	15	15	15	16

Analiza rynku wykazała, że każda z linii produkcyjnych pozwala uzyskiwać jednakowe zyski w przeliczeniu na 1 t pieczywa. Jerzy Płatek musi więc w tym przypadku podjąć decyzję dotyczącą podziału kredytu pomiędzy poszczególne programy inwestycyjne tak, aby piekarnia osiągnęła maksymalną, dobową zdolność produkcyjną.

K o /. w i ą / u n i c. Powyższy problem, należący do kategorii programowaniu dynamicznego, można rozwiązać za pomocą procedury opisanej w kilku dupach.

Kkok 1. Załóżmy, że jedynym możliwym rozwiązaniem jest zakupienie polskiej linii produkcyjnej (P) i zadajmy sobie pytanie dotyczące uzyskanej w len sposób dobowej zdolności produkcyjnej w zależności od zainwestowanej kwoty. Wyniki podano w tabl. 182.

Tablica 182

Nakłady (w min zł)	0	1	2	3	4	5	6
Zdolności produkcyjne linii P (w t)	0	4	15	15	15	15	16

W tym przypadku jedynym sensownym rozwiązaniem jest zainwestowanie 6 min zł w polską linię produkcyjną w celu osiągnięcia zdolności produkcyjnej 16 t pieczywa na dobę. Rezultat ten zapiszemy następująco:

P(6)= 16,

co oznacza, że 6 min zł zainwestowane w polską linię produkcyjną zapewnia produkcję 16 t pieczywa na dobę.

Krok 2. Załóżmy, że dostępne są dwa typy linii produkcyjnych: P oraz S, i zadajmy sobie następujące pytanie: jak należy podzielić kredyt inwestycyjny pomiędzy te dwa programy, aby uzyskać maksymalną zdolność produkcyjną?

W tym przypadku możliwe jest siedem wariantów podziału 6 min zł kredytu, które dają następujące dobowe zdolności produkcyjne:

P(6) + S(0) = 16 + 0 = 16,

P(5) + S(l) = 15 + 5 = 20,

P(4) + S(2) = 15 + 8 = 23,

P(3) + S(3) = 15 + 11 = 26,

P(2) + S(4) = 15 + 14 = 29,

P(l) + S(5) = 4 + 17 = 21,

P(0) + S(6) = 0 + 18 = 18.

W powyższej sytuacji należy więc zainwestować 2 min zł w polską linię oraz 4 min zł w szwedzką linię, osiągając w ten sposób 29 t pieczywa na dobę.

Krok 3. Spróbujmy obecnie znaleźć optymalny podział kredytu pomiędzy linię P oraz S przy malejącej kwocie nakładów inwestycyjnych:

a) 5 min zł na linie P oraz S

P(5) + S(0) = 15 + 0 = 15,

P(4) + S(l)= 15 + 5 = 20,

P(3) + S(2) = 15 + 8 = 23,

207