1
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
."
2
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
3
od miejsca zamieszkania 1 do miejsca pobytu
nad morzem 7 są przedstawione poniżej.
Znaleźć 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:
d
5,7
=
70
km
od miasta 6:
d
6,7
=
50
km
w zależności od tego, w którym z miast w
etapie III zatrzymano się.
4
Krok II:
Cofamy się o jeden etap.
Odległość miast w
etapie II od celu (miasta 7) wynosi:
od miasta 2:
d
2,5
+ d
5,7
= d
2,5,7
120 +
70
= 190 km
d
2,6
+ d
6,7
= d
2,6,7
120 +
50
=
170
km
od miasta 3:
d
3,5
+ d
5,7
= d
3,5,7
100 +
70
= 170 km
d
3,6
+ d
6,7
= d
3,6,7
90 +
50
=
140
km
od miasta 4:
d
4,5
+ d
5,7
= d
4,5,7
70 +
70
=
140
km
d
4,5
+ d
6,7
= d
4,6,7
130 +
50
= 180 km
5
Tak więc: z miasta 2 do 7 należy wybrać
drogę d
2,6,7
=170 km; z miasta 3 do 7 drogę
d
3,6,7
=140 km; z miasta 4 do 7 drogę
d
4,5,7
=140 km.
Krok III:
Cofamy się o jeden etap.
Odległość miast w
etapie I od celu wynosi:
od miasta 1:
d
1,2
+ d
2,6,7
= d
1,2,6,7
50 +
170
= 220 km
d
1,3
+ d
3,5,7
= d
1,3,5,7
40 +
140
= 180 km
d
1,4
+ d
4,5,7
= d
1,4,5,7
30 +
140
=
170
km
Z miasta 1 do 7 należy wybrać drogę
d
1,4,5,7
=170 km
.
6
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ę?
od miasta 3:
d
3,5
+ d
5,7
= d
3,5,7
100 +
70
= 170 km
d
3,6
+ d
6,7
= d
3,6,7
90 +
50
=
140
km
7
Wybieramy drogę
d
3,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
produkcyjne
(w setkach t)
Nakłady (w mln zł)
0
1
2
3
4
5
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?
8
Krok I:
Załóżmy, że jedynym rozwiązaniem jest
zakup linii produkcyjnej C; biorąc pod uwagę
miesięczną zdolność produkcyjną:
Zdolności
produkcyjne
(w setkach t)
Nakłady (w mln zł)
0
1
2
3
4
5
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
9
(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
10
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
11
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ądź: 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
12
Solve and
Analyse
Solve the
Problem
Solve
13
Solve and Display Steps
Przez pomyłkę
pojechaliśmy do
miasta 3:
Results
Perform What
if Analysis
po naciśnięciu
OK:
14
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
jednostkowe
(w tys. zł)
Nakłady (w mln)
0
1
2
3
4
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ł.