Programowanie dynamiczne
Programowanie dynamiczne jest jednÄ… z
technik matematycznych, którą można
zastosować do rozwiązywania takich
problemów jak:
·ð zagadnienie dyliżansu,
·ð zagadnienie finansowania inwestycji,
·ð optymalizacja zapasów, alokacja
zasobów,
·ð wymiana majÄ…tku trwaÅ‚ego itd.
Zagadnienie dyliżansu - poszukiwanie
optymalnej drogi w sieci
Podział całej trasy na etapy, a następnie
sekwencyjne rozwiązywanie, aż do znalezienia
rozwiÄ…zania optymalnego. Stosuje siÄ™ tu tzw.
zasadę optymalności Bellmana, w myśl
której "Polityka optymalna ma tę własność,
że niezależnie od początkowego stanu i
początkowej decyzji pozostałe decyzje muszą
stanowić politykę optymalną ze względu na
stan wynikajÄ…cy z pierwszej decyzji."
1
Oznacza to, iż optymalne rozwiązanie
zagadnienia z zakresu programowania
dynamicznego, ma tę własność, że optymalne
rozwiÄ…zanie dla k-tego etapu jest
równocześnie rozwiązaniem optymalnym dla
etapów k+1, k+2, & N. Tak więc optymalne
rozwiÄ…zanie dla etapu pierwszego stanowi
optymalne rozwiązanie dla całego problemu.
Problem rozwiÄ…zuje siÄ™ rozpoczynajÄ…c
od poszukiwania rozwiÄ…zania dla ostatniego
etapu N, a następnie cofając się poszukuje się
rozwiÄ…zania dla etapu N-1. Uzyskane w ten
sposób rozwiązanie dla etapów N-1 oraz N
jest optymalne bez względu na to, w jaki
sposób osiągnięto etap N-1. Powtarzając w
powyższy sposób etap po etapie dochodzimy
do rozwiÄ…zania optymalnego dla pierwszego
etapu, a więc i dla całego problemu.
Przykład:
Kowalscy jadÄ… samochodem na urlop nad
morze. Cała trasa została podzielona na kilka
etapów. Odległości między poszczególnymi
miastami, przez które można przejechać jadąc
2
od miejsca zamieszkania 1 do miejsca pobytu
nad morzem 7 są przedstawione poniżej.
Znalez
ć najkrótszą trasę przejazdu z miejsca 1
do 7.
Krok I:
Załóżmy, że Kowalscy dotarli do etapu III. W
tej sytuacji odległość od celu wynosi:
od miasta 5: d5,7 = 70 km
od miasta 6: d6,7 = 50 km
w zależności od tego, w którym z miast w
etapie III zatrzymano siÄ™.
3
Krok II:
Cofamy się o jeden etap. Odległość miast w
etapie II od celu (miasta 7) wynosi:
d2,5 + d5,7 = d2,5,7
120 + 70 = 190 km
od miasta 2:
d2,6 + d6,7 = d2,6,7
120 + 50 = 170 km
d3,5 + d5,7 = d3,5,7
100 + 70 = 170 km
od miasta 3:
d3,6 + d6,7 = d3,6,7
90 + 50 = 140 km
d4,5 + d5,7 = d4,5,7
70 + 70 = 140 km
od miasta 4:
d4,5 + d6,7 = d4,6,7
130 + 50 = 180 km
4
Tak więc: z miasta 2 do 7 należy wybrać
drogÄ™ d2,6,7=170 km; z miasta 3 do 7 drogÄ™
d3,6,7=140 km; z miasta 4 do 7 drogÄ™
d4,5,7=140 km.
Krok III:
Cofamy się o jeden etap. Odległość miast w
etapie I od celu wynosi:
d1,2 + d2,6,7 = d1,2,6,7
50 + 170 = 220 km
d1,3 + d3,5,7 = d1,3,5,7
od miasta 1:
40 + 140 = 180 km
d1,4 + d4,5,7 = d1,4,5,7
30 + 140 = 170 km
Z miasta 1 do 7 należy wybrać drogę
d1,4,5,7=170 km.
5
Załóżmy, że pomyliśmy drogi i wyruszając
z miasta 1 zamiast do 4 pojechaliśmy do 3.
Jak należy zaplanować dalszą trasę?
d3,5 + d5,7 = d3,5,7
100 + 70 = 170 km
od miasta 3:
d3,6 + d6,7 = d3,6,7
90 + 50 = 140 km
6
Wybieramy drogÄ™ d3,6,7 liczÄ…cÄ… 140 km.
Zagadnienie finansowania inwestycji
Przykład:
Janusz Owsianko parajÄ…cy siÄ™ produkcjÄ…
płatków śniadaniowych, postanowił
zainwestować w nową linię technologiczną.
Zamierza w tym celu wziąć kredyt w
wysokości 5 mln zł. Miał do wyboru trzy linie
umownie nazwane A, B i C. Każda z tych linii
daje jednakowe zyski w przeliczeniu na 1 t
płatków. Miesięczne zdolności produkcyjne w
zależności od linii są następujące:
Zdolności Nakłady (w mln zł)
produkcyjne
0 1 2 3 4 5
(w setkach t)
A 0 1 2 2 3 5
B 0 4 4 5 5 6
C 0 4 5 5 7 9
Jak należy rozlokować nakłady, aby
zoptymalizować zdolności produkcyjne
zakładu?
7
Krok I:
Załóżmy, że jedynym rozwiązaniem jest
zakup linii produkcyjnej C; biorÄ…c pod uwagÄ™
miesięczną zdolność produkcyjną:
Zdolności Nakłady (w mln zł)
produkcyjne
0 1 2 3 4 5
(w setkach t)
C 0 4 5 5 7 9
należy całą kwotę kredytu, a zatem 5 mln zł
przeznaczyć na zakup tej linii, co da zdolność
produkcyjnÄ… na poziomie 9 setek ton.
Krok II:
Załóżmy teraz, że dostępne są dwie linie
produkcyjne C i B i całą kwotę dzielimy
między te linie:
(1) Dzielimy 5 mln:
C(5) + B(0) = 9 + 0 = 9
C(4) + B(1) = 7 + 4 = 11 MAX
C(3) + B(2) = 6 + 4 = 10
C(2) + B(3) = 5 + 5 = 10
C(1) + B(4) = 4 + 5 = 9
C(0) + B(5) = 0 + 6 = 6
8
(2) Dzielimy 4 mln:
C(4) + B(0) = 7 + 0 = 7
C(3) + B(1) = 5 + 4 = 9 MAX
C(2) + B(2) = 5 + 4 = 9 MAX
C(1) + B(3) = 4 + 5 = 9 MAX
C(0) + B(4) = 0 + 5 = 6
(3) Dzielimy 3 mln:
C(3) + B(0) = 5 + 0 = 5
C(2) + B(1) = 5 + 4 = 9 MAX
C(1) + B(2) = 4 + 4 = 8
C(0) + B(3) = 0 + 5 = 5
(4) Dzielimy 2 mln:
C(2) + B(0) = 5 + 0 = 5
C(1) + B(1) = 4 + 4 = 8 MAX
C(0) + B(2) = 0 + 4 = 4
(5) Dzielimy 1 mln:
C(1) + B(0) = 4 + 0 = 4 MAX
C(0) + B(1) = 0 + 4 = 4 MAX
9
Krok III:
Rozpatrzymy wszystkie możliwe kombinacje
podziału kwoty kredytu 5 mln na linie C+B
dołączając teraz nakłady na linię A:
Linia 0 1 2 3 4 5
C+B 0 4 8 9 9 11
A 0 1 2 2 3 5
Istnieje 6 wariantów podziału kwoty 5 mln
kredytu pomiędzy linie C+B oraz A, które dają
następujący podział zdolności produkcyjnych:
(C+B)(0) + A(5) = 0 + 5 = 5
(C+B)(1) + A(4) = 4 + 3 = 7
(C+B)(2) + A(3) = 8 + 2 = 10
(C+B)(3) + A(2) = 9 + 2 = 11 MAX
(C+B)(4) + A(1) = 9 + 1 = 10
(C+B)(5) + A(0) = 11 + 0 = 11 MAX
Janusz Owsianko powinien zainwestować:
·ð 3 mln w linie C i B oraz 2 mln w liniÄ™ A;
kwotÄ™ 3 mln przeznaczonÄ… na linie C i B
10
dzielimy: 2 mln na C i 1 mln na B, co
wynika z kroku II (3), czyli ostatecznie:
2 mln w C i 1 mln w B, 2 mln w liniÄ™ A,
·ð bÄ…dz
: całą kwotę 5 mln w linie C i B, a
konkretnie 4 mln w C i 1 mln w B, co
wynika kroku II (1).
W obydwu wariantach dostanie maksymalne
zdolności wytwórcze na poziomie 11 setek t
płatków śniadaniowych w skali miesiąca.
RozwiÄ…zanie w EXCEL: Dynamiczne.xlsx,
arkusz: Janusz Owsianko
Zastosowanie winqsb:
File
New Problem
11
Solve and
Analyse
Solve the
Problem
Solve
12
Solve and Display Steps
Przez pomyłkę
pojechaliśmy do
miasta 3:
Results
Perform What
if Analysis
po naciśnięciu
OK:
13
Zadania do rozwiÄ…zania:
Zad. 1. Kowalscy bardzo nie chcieli wracać do
domu z wczasów, a że pogoda była piękna
postanowili pojechać z miasta 7 do 1 najdłuższą
trasÄ…. Jaka to trasa i ile liczy km?
Rozwiązanie: Trasa: 7-5-2-1; odległość 240 km.
Zad. 2. Inwestor rozpoczynajÄ…cy pewne zadanie
inwestycyjne, realizowane za pomocÄ… czterech
programów inwestycyjnych, które umownie nazwiemy
I, II, III i IV musi podjąć decyzję bazując wyłącznie na
kosztach jednostkowych (w tys. zł) wiążących się z
każdym z programów. Koszty te przedstawia poniższe
zestawienie.
Koszty Nakłady (w mln)
jednostkowe
0 1 2 3 4
(w tys. zł)
I 100 85 75 60 50
II 100 70 62 52 40
III 100 90 80 70 60
IV 100 90 80 80 45
Jakie należy ponieść nakłady inwestycyjne na
poszczególne programy kierując się kryterium
minimalizacji kosztów jednostkowych?
Rozwiązanie: 4 mln zł na inwestycję IV; minimalny
koszt jednostkowy 45 tys. zł.
14