wyklad - programowanie dynamiczne.pdf

(477 KB) Pobierz
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 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
1
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
od miejsca zamieszkania
1
do miejsca pobytu
nad morzem
7
są przedstawione poniżej.
Znaleźć najkrótszą trasę przejazdu z miejsca
1
do
7.
2
Etap I
Etap II
Etap III
Etap IV
2
5
1
40
3
7
6
4
Krok I:
Załóżmy, że Kowalscy dotarli
do etapu III.
W
tej sytuacji odległość od celu wynosi:
od miasta 5:
od miasta 6:
d
5,7
=
70
km
d
6,7
=
50
km
w zależności od tego, w którym z miast w
etapie III zatrzymano się.
Krok II:
Cofamy się o jeden etap.
Odległość miast w
etapie II
od celu (miasta
7)
wynosi:
3
d
2,5
+ d
5,7
= d
2,5,7
120 +
70
= 190 km
od miasta 2:
d
2,6
+ d
6,7
= d
2,6,7
120 +
50
=
170
km
d
3,5
+ d
5,7
= d
3,5,7
100 +
70
= 170 km
od miasta 3:
d
3,6
+ d
6,7
= d
3,6,7
90 +
50
=
140
km
d
4,5
+ d
5,7
= d
4,5,7
70 +
70
=
140
km
od miasta 4:
d
4,5
+ d
6,7
= d
4,6,7
130 +
50
= 180 km
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.
4
Krok III:
Cofamy się o jeden etap.
Odległość miast w
etapie I
od celu wynosi:
d
1,2
+ d
2,6,7
= d
1,2,6,7
50 +
170
= 220 km
od miasta 1:
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.
Etap I
Etap II
Etap III
Etap IV
2
5
1
40
3
7
6
4
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin