Programowanie
Programowanie
dynamiczne
dynamiczne
Opracowano na podstawie:
Opracowano na podstawie:
1.
1.
„
„
Badania operacyjne w przykładach i
Badania operacyjne w przykładach i
zadaniach” pod red. Karola Kukuły
zadaniach” pod red. Karola Kukuły
Wyd. Naukowe PWN
Wyd. Naukowe PWN
2.
2.
„
„
Matematyczne techniki zarządzania”
Matematyczne techniki zarządzania”
pod red. Zbigniewa Łuckiego Wyd.
pod red. Zbigniewa Łuckiego Wyd.
AGH
AGH
3.
3.
Badania operacyjne mgr inż. Piotr
Badania operacyjne mgr inż. Piotr
Betlej
Betlej
Programowanie
Programowanie
dynamiczne
dynamiczne
•
jest jedną z technik matematycznych
jest jedną z technik matematycznych
poszukiwania rozwiązań
poszukiwania rozwiązań
optymalnych
optymalnych
•
określa sposób podejścia do
określa sposób podejścia do
rozwiązywania problemu niż jako
rozwiązywania problemu niż jako
pojedynczy uniwersalny algorytm.
pojedynczy uniwersalny algorytm.
rozwiązanie
rozwiązanie
•
polega na podziale zagadnienia pierwotnego na
polega na podziale zagadnienia pierwotnego na
podproblemy lub etapy, a następnie na ich sekwencyjnym
podproblemy lub etapy, a następnie na ich sekwencyjnym
rozwiązywaniu, aż do znalezienia rozwiązania
rozwiązywaniu, aż do znalezienia rozwiązania
optymalnego.
optymalnego.
•
Stosuje się przy tym, niezależnie od algorytmu,
Stosuje się przy tym, niezależnie od algorytmu,
zasadę
zasadę
optymalności Bellmana
optymalności Bellmana
, w myśl której optymalne
, w myśl której optymalne
rozwiązanie zagadnień z zakresu programowania
rozwiązanie zagadnień z zakresu programowania
dynamicznego ma tę własność, że optymalne rozwiązanie
dynamicznego ma tę własność, że optymalne rozwiązanie
dla
dla
k
k
-tego etapu jest jednocześnie rozwiązaniem
-tego etapu jest jednocześnie rozwiązaniem
optymalnym dla etapów k + 1, k + 2, ..., N. Tak więc
optymalnym dla etapów k + 1, k + 2, ..., N. Tak więc
optymalne rozwiązanie dla etapu pierwszego stanowi
optymalne rozwiązanie dla etapu pierwszego stanowi
optymalne rozwiązanie dla całego problemu.
optymalne rozwiązanie dla całego problemu.
•
W związku z powyższą zasadą problem z zakresu
W związku z powyższą zasadą problem z zakresu
programowania dynamicznego rozwiązuje się
programowania dynamicznego rozwiązuje się
rozpoczynając od poszukiwania rozwiązania dla ostatniego
rozpoczynając od poszukiwania rozwiązania dla ostatniego
etapu (N), a następnie cofając się poszukuje się
etapu (N), a następnie cofając się poszukuje się
rozwiązania dla etapu N-1 Uzyskane w ten sposób
rozwiązania dla etapu N-1 Uzyskane w ten sposób
rozwiązanie dla etapów N-1 oraz N jest optymalne bez
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.
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
Powtarzając w powyższy sposób etap po etapie dochodzimy
do rozwiązania optymalnego dla pierwszego etapu, a więc i
do rozwiązania optymalnego dla pierwszego etapu, a więc i
dla całego problemu.
dla całego problemu.
Zadania programowania
Zadania programowania
dynamicznego
dynamicznego
•
zagadnienie dyliżansu
zagadnienie dyliżansu
,
,
•
zagadnienie finansowania
zagadnienie finansowania
inwestycji
inwestycji
,
,
•
optymalizacja zapasów
optymalizacja zapasów
,
,
•
alokacja zasobów
alokacja zasobów
, czy
, czy
wymiana
wymiana
majątku trwałego
majątku trwałego
.
.
Zagadnienie finansowania
Zagadnienie finansowania
przedsięwzięcia
przedsięwzięcia
inwestycyjnego
inwestycyjnego
•
Zagadnienie finansowania przedsięwzięcia inwestycyjnego
Zagadnienie finansowania przedsięwzięcia inwestycyjnego
można scharakteryzować jako problem alokacji określonego
można scharakteryzować jako problem alokacji określonego
zasobu środków (w tym przypadku wyrażonego w jednostkach
zasobu środków (w tym przypadku wyrażonego w jednostkach
pieniężnych) pomiędzy poszczególne zadania (programy
pieniężnych) pomiędzy poszczególne zadania (programy
inwestycyjne), tak aby osiągnąć maksymalny efekt.
inwestycyjne), tak aby osiągnąć maksymalny efekt.
•
Przyjmuje się przy tym następujące założenia:
Przyjmuje się przy tym następujące założenia:
•
Efekt zastosowania każdego z programów inwestycyjnych nie
Efekt zastosowania każdego z programów inwestycyjnych nie
zależy od tego, czy zostały zastosowane równocześnie inne
zależy od tego, czy zostały zastosowane równocześnie inne
programy inwestycyjne.
programy inwestycyjne.
•
Zwrot nakładów inwestycyjnych jest mierzony w tych samych
Zwrot nakładów inwestycyjnych jest mierzony w tych samych
jednostkach.
jednostkach.
•
Nakłady inwestycyjne są liczbami całkowitymi.
Nakłady inwestycyjne są liczbami całkowitymi.
•
Funkcje określające związki między nakładami inwestycyjnymi
Funkcje określające związki między nakładami inwestycyjnymi
a wysokością zwrotu z nakładów są niemalejące.
a wysokością zwrotu z nakładów są niemalejące.
Przykład zagadnienia
Przykład zagadnienia
alokacji inwestycji
alokacji inwestycji
•
Przedsiębiorca Jan Rogala, posiadający kredyt inwestycyjny w wysokości
Przedsiębiorca Jan Rogala, posiadający kredyt inwestycyjny w wysokości
6 min złotych oraz halę produkcyjną w Rzeszowie, postanowił
6 min złotych oraz halę produkcyjną w Rzeszowie, postanowił
zainstalować nowoczesne linie piekarnicze:
zainstalować nowoczesne linie piekarnicze:
•
francuską (F),
francuską (F),
•
szwedzką (S)
szwedzką (S)
•
oraz polską (P).
oraz polską (P).
•
Dobowe zdolności produkcyjne pieczywa (w tonach) w zależności od
Dobowe zdolności produkcyjne pieczywa (w tonach) w zależności od
wysokości nakładów inwestycyjnych przeznaczonych na zainstalowanie
wysokości nakładów inwestycyjnych przeznaczonych na zainstalowanie
linii produkcyjnej danego typu, przedstawiono w poniższej tabeli:
linii produkcyjnej danego typu, przedstawiono w poniższej tabeli:
Analiza rynku wykazała, że każda z linii produkcyjnych, pozwala uzyskiwać
Analiza rynku wykazała, że każda z linii produkcyjnych, pozwala uzyskiwać
jednakowe zyski w przeliczeniu na 1 t pieczywa.
jednakowe zyski w przeliczeniu na 1 t pieczywa.
Jan Rogala musi więc w tym przypadku podjąć decyzję dotyczącą podziału
Jan Rogala musi więc w tym przypadku podjąć decyzję dotyczącą podziału
kredytu pomiędzy poszczególne programy inwestycyjne, tak aby
kredytu pomiędzy poszczególne programy inwestycyjne, tak aby
piekarnia osiągnęła maksymalną, dobową zdolność produkcyjną.
piekarnia osiągnęła maksymalną, dobową zdolność produkcyjną.
Rozwiązanie
Rozwiązanie
•
Powyższy problem, należący do
Powyższy problem, należący do
kategorii programowania
kategorii programowania
dynamicznego, można rozwiązać za
dynamicznego, można rozwiązać za
pomocą procedury opisanej w kilku
pomocą procedury opisanej w kilku
etapach.
etapach.
KROK 1.
KROK 1.
•
Załóżmy, że jedynym możliwym rozwiązaniem jest
Załóżmy, że jedynym możliwym rozwiązaniem jest
zakupienie polskiej linii produkcyjnej i zadajmy sobie
zakupienie polskiej linii produkcyjnej i zadajmy sobie
pytanie dotyczące uzyskanej w ten sposób dobowej
pytanie dotyczące uzyskanej w ten sposób dobowej
zdolności produkcyjnej w zależności od zainwestowanej
zdolności produkcyjnej w zależności od zainwestowanej
kwoty.
kwoty.
•
W tym przypadku, jedynym sensownym rozwiązaniem
W tym przypadku, jedynym sensownym rozwiązaniem
jest zainwestowanie 6 min zł w polską linię produkcyjną
jest zainwestowanie 6 min zł w polską linię produkcyjną
w celu osiągnięcia zdolności produkcyjnej 16 t pieczywa
w celu osiągnięcia zdolności produkcyjnej 16 t pieczywa
na dobę. Rezultat ten zapiszemy następująco:
na dobę. Rezultat ten zapiszemy następująco:
P(6) = 16,
P(6) = 16,
co oznacza, że 6 mln zł zainwestowane w polską linię
co oznacza, że 6 mln zł zainwestowane w polską linię
produkcyjną zapewnia produkcję 16 t pieczywa na dobę.
produkcyjną zapewnia produkcję 16 t pieczywa na dobę.
KROK 2.
KROK 2.
•
Załóżmy, że dostępne są dwa typy
Załóżmy, że dostępne są dwa typy
linii produkcyjnych P oraz S i
linii produkcyjnych P oraz S i
zadajmy sobie następujące pytanie:
zadajmy sobie następujące pytanie:
jak należy podzielić kredyt
jak należy podzielić kredyt
inwestycyjny pomiędzy te dwa
inwestycyjny pomiędzy te dwa
programy, aby uzyskać maksymalną
programy, aby uzyskać maksymalną
dobową zdolność produkcyjną?
dobową zdolność produkcyjną?
•
W tym przypadku możliwe jest siedem wariantów
W tym przypadku możliwe jest siedem wariantów
podziału 6 min kredytu, które dają następujące
podziału 6 min kredytu, które dają następujące
dobowe zdolności produkcyjne:
dobowe zdolności produkcyjne:
P(6) + S(0)= 16 + 0= 16,
P(6) + S(0)= 16 + 0= 16,
P(5) + S(l)= 15 + 5 = 20,
P(5) + S(l)= 15 + 5 = 20,
P(4) + S(2)= 15 + 8 = 23,
P(4) + S(2)= 15 + 8 = 23,
P(3) + S(3)= 15 + 11 =26,
P(3) + S(3)= 15 + 11 =26,
P(2) + S(4)= 15 + 14 = 29,
P(2) + S(4)= 15 + 14 = 29,
P(1) + S(5)= 4+17 = 21,
P(1) + S(5)= 4+17 = 21,
P(0) + S(6) = 0+18 = 18.
P(0) + S(6) = 0+18 = 18.
W powyższej sytuacji należy więc zainwestować 2
W powyższej sytuacji należy więc zainwestować 2
mln w polską linię oraz 4 mln w szwedzką linię,
mln w polską linię oraz 4 mln w szwedzką linię,
osiągając w ten sposób 29 t pieczywa na dobę, tzn.
osiągając w ten sposób 29 t pieczywa na dobę, tzn.
P(2) + S(4) = 29.
P(2) + S(4) = 29.
KROK 3.
KROK 3.
•
Spróbujmy obecnie znaleźć optymalny podział
Spróbujmy obecnie znaleźć optymalny podział
kredytu pomiędzy linię P oraz S przy malejącej
kredytu pomiędzy linię P oraz S przy malejącej
kwocie nakładów inwestycyjnych:
kwocie nakładów inwestycyjnych:
a)
a)
5 mln na linie P oraz S
5 mln na linie P oraz S
P(5) + S(O) = 15 + 0 = 15,
P(5) + S(O) = 15 + 0 = 15,
P(4) + S(1) = 15 + 5 = 20,
P(4) + S(1) = 15 + 5 = 20,
P(3) + S(2) = 15 + 8 = 23,
P(3) + S(2) = 15 + 8 = 23,
P(2) + S(3) = 15 + 11 = 26,
P(2) + S(3) = 15 + 11 = 26,
P(1) + S(4) = 4 + 14 = 18,
P(1) + S(4) = 4 + 14 = 18,
P(0) + S(5) = 0 + 17 = 17.
P(0) + S(5) = 0 + 17 = 17.
W przypadku dysponowania kwotą 5 mln zł na
W przypadku dysponowania kwotą 5 mln zł na
linię P oraz S należy zainwestować 2 mln w linię
linię P oraz S należy zainwestować 2 mln w linię
P oraz 3 mln w linię S, osiągając 26 t pieczywa
P oraz 3 mln w linię S, osiągając 26 t pieczywa
dobę. Rezultat zapiszemy w następujący sposób:
dobę. Rezultat zapiszemy w następujący sposób:
P(2) + S(3) = 26.
P(2) + S(3) = 26.
b) 4 mln zł na linie P oraz S
b) 4 mln zł na linie P oraz S
P(4) + S(0) = 15 + 0 = 15,
P(4) + S(0) = 15 + 0 = 15,
P(3) + S(1) = 15 + 5 = 20,
P(3) + S(1) = 15 + 5 = 20,
P(2) + S(2) = 15 + 8 = 23,
P(2) + S(2) = 15 + 8 = 23,
P(1) + S(3) = 4 + 11 = 15,
P(1) + S(3) = 4 + 11 = 15,
P(0) + S(4) = 0 + 14 = 14.
P(0) + S(4) = 0 + 14 = 14.
W przypadku dysponowania kwotą 4 mln zł
W przypadku dysponowania kwotą 4 mln zł
należy zainwestować po 2 mln zł w linię P
należy zainwestować po 2 mln zł w linię P
oraz S:
oraz S:
P(2) + S(2) = 23.
P(2) + S(2) = 23.
c) 3 mln zł na linie P oraz S:
c) 3 mln zł na linie P oraz S:
P(3) + S(0) = 15 + 0 = 15.
P(3) + S(0) = 15 + 0 = 15.
P(2) + S(1)= 15 + 5 = 20,
P(2) + S(1)= 15 + 5 = 20,
P(1) + S(2) = 4 + 8 = 12,
P(1) + S(2) = 4 + 8 = 12,
P(0) + S(3) = 0 + 11 = 11.
P(0) + S(3) = 0 + 11 = 11.
W tym przypadku należy zainwestować
W tym przypadku należy zainwestować
2 mln w linię P oraz 1 mln w linię S:
2 mln w linię P oraz 1 mln w linię S:
P(2) + S(1) = 20.
P(2) + S(1) = 20.
d) 2 mln zł na linie P oraz S
d) 2 mln zł na linie P oraz S
P(2) + S(0) = 15 + 0 = 15,
P(2) + S(0) = 15 + 0 = 15,
P(1) + S(1) = 4 + 5 = 9,
P(1) + S(1) = 4 + 5 = 9,
P(0) + S(2) = 0 + 8 = 8.
P(0) + S(2) = 0 + 8 = 8.
W tym przypadku należy
W tym przypadku należy
zainwestować 2 min zł w linię polską
zainwestować 2 min zł w linię polską
(P):
(P):
P(2) + S(0)= 15.
P(2) + S(0)= 15.
e) 1 mln zł na linie P oraz S
e) 1 mln zł na linie P oraz S
P(1) + S(0) = 4 + 0 = 4,
P(1) + S(0) = 4 + 0 = 4,
P(0) + S(1) = 0 + 5 = 5.
P(0) + S(1) = 0 + 5 = 5.
W tym przypadku należy zainwestować
W tym przypadku należy zainwestować
1 mln zł w linię szwedzką (S):
1 mln zł w linię szwedzką (S):
P(0) + S(1) = 5.
P(0) + S(1) = 5.
A zatem, w kroku 3 określiliśmy
A zatem, w kroku 3 określiliśmy
optymalne kombinacje nakładów na
optymalne kombinacje nakładów na
linie P oraz S.
linie P oraz S.
KROK 4.
KROK 4.
Konsekwentnie, w kroku 4 wystarczy rozpatrzyć
Konsekwentnie, w kroku 4 wystarczy rozpatrzyć
wszystkie kombinacje podziału 6 mln zł kredytu
wszystkie kombinacje podziału 6 mln zł kredytu
pomiędzy linię F oraz linie P + S. Zdolności
pomiędzy linię F oraz linie P + S. Zdolności
produkcyjne w zależności od nakładów
produkcyjne w zależności od nakładów
kredytowych przedstawiono w poniższej tabeli:
kredytowych przedstawiono w poniższej tabeli:
Jak łatwo zauważyć możliwych jest siedem wariantów
Jak łatwo zauważyć możliwych jest siedem wariantów
podziału 6 mln kredytu pomiędzy linie F oraz linie
podziału 6 mln kredytu pomiędzy linie F oraz linie
P + S, dających następujące zdolności produkcyjne:
P + S, dających następujące zdolności produkcyjne:
F(6) + (P + S)(0) = 20 + 0 = 20,
F(6) + (P + S)(0) = 20 + 0 = 20,
F(5) + (P + S)(1) = 15+5 = 20,
F(5) + (P + S)(1) = 15+5 = 20,
F(4) + (P + S)(2) = 12 + 15 = 27,
F(4) + (P + S)(2) = 12 + 15 = 27,
F(3) + (P + S)(3) = 12 + 20 = 32,
F(3) + (P + S)(3) = 12 + 20 = 32,
F(2) + (P + S)(4) = 12 + 23 = 35,
F(2) + (P + S)(4) = 12 + 23 = 35,
F(1) + (P + S)(5)= 6 + 26 = 32,
F(1) + (P + S)(5)= 6 + 26 = 32,
F(0) + (P + S)(6) = 0 + 29 = 29.
F(0) + (P + S)(6) = 0 + 29 = 29.
Tak więc maksymalną zdolność produkcyjną
Tak więc maksymalną zdolność produkcyjną
piekarni można uzyskać inwestując 2 min w linię
piekarni można uzyskać inwestując 2 min w linię
francuską (F) oraz 4 mln zł w linię P i S.
francuską (F) oraz 4 mln zł w linię P i S.
Aby uzyskać rozwiązanie ostateczne,
Aby uzyskać rozwiązanie ostateczne,
wystarczy odszukać w kroku 3 optymalny
wystarczy odszukać w kroku 3 optymalny
sposób podziału tych 4 mln zł pomiędzy
sposób podziału tych 4 mln zł pomiędzy
linię P oraz S (krok 3b).
linię P oraz S (krok 3b).
W rezultacie otrzymujemy rozwiązanie: 2
W rezultacie otrzymujemy rozwiązanie: 2
mln zł na linię F, 2 mln zł na linię P oraz 2
mln zł na linię F, 2 mln zł na linię P oraz 2
mln ma linię S, co zapewnia 35 t pieczywa
mln ma linię S, co zapewnia 35 t pieczywa
na dobę.
na dobę.
Zagadnienie dyliżansu
Zagadnienie dyliżansu
•
Nazwa zagadnienia pochodzi od pewnego kupca
Nazwa zagadnienia pochodzi od pewnego kupca
amerykańskiego, który transportował towary ze
amerykańskiego, który transportował towary ze
Wschodniego Wybrzeża USA na Wybrzeże
Wschodniego Wybrzeża USA na Wybrzeże
Zachodnie, używając w tym celu różnych
Zachodnie, używając w tym celu różnych
połączeń realizowanych za pomocą dyliżansu.
połączeń realizowanych za pomocą dyliżansu.
•
Oczywiście chodziło o dobór takich połączeń, aby
Oczywiście chodziło o dobór takich połączeń, aby
transport odbywał się w miarę bezpiecznie, a
transport odbywał się w miarę bezpiecznie, a
miarą bezpieczeństwa na danej linii były stawki
miarą bezpieczeństwa na danej linii były stawki
pobierane przez towarzystwo ubezpieczeniowe.
pobierane przez towarzystwo ubezpieczeniowe.
•
Rozwiązanie problemu wymagało podzielenia
Rozwiązanie problemu wymagało podzielenia
całej trasy na etapy, a w każdym z etapów
całej trasy na etapy, a w każdym z etapów
określenia miast etapowych oraz wszystkich
określenia miast etapowych oraz wszystkich
możliwych połączeń pomiędzy nimi.
możliwych połączeń pomiędzy nimi.
Przykład problemu
Przykład problemu
dyliżansu
dyliżansu
Firma transportowa EuroTrans, ustalając nowe
Firma transportowa EuroTrans, ustalając nowe
trasy przejazdu swych ciężarówek z Polski do
trasy przejazdu swych ciężarówek z Polski do
Hiszpanii, podzieliła całą trasę na pięć etapów.
Hiszpanii, podzieliła całą trasę na pięć etapów.
W każdym z etapów wyznaczono po kilka miast,
W każdym z etapów wyznaczono po kilka miast,
przez które przejeżdżać będą ciężarówki.
przez które przejeżdżać będą ciężarówki.
Problem polega na znalezieniu najkrótszej drogi
Problem polega na znalezieniu najkrótszej drogi
przejazdu pomiędzy Polską a Hiszpanią.
przejazdu pomiędzy Polską a Hiszpanią.
Odległości drogowe pomiędzy miastami (w
Odległości drogowe pomiędzy miastami (w
km) zaznaczono na poniższym rysunku:
km) zaznaczono na poniższym rysunku:
KROK 1.
KROK 1.
Załóżmy, że ciężarówki dotarły do
Załóżmy, że ciężarówki dotarły do
etapu 4.
etapu 4.
W tej sytuacji odległość od celu
W tej sytuacji odległość od celu
wynosi:
wynosi:
d
d
7,9
7,9
= 120 km lub d
= 120 km lub d
8,9
8,9
= 130
= 130
km,
km,
w zależności od tego, w którym z
w zależności od tego, w którym z
miast w etapie 4 zatrzymano się na
miast w etapie 4 zatrzymano się na
postój.
postój.
KROK 2.
KROK 2.
Cofnijmy się o jeden etap.
Cofnijmy się o jeden etap.
Odległość miast od celu w etapie 3 wynosi:
Odległość miast od celu w etapie 3 wynosi:
d
d
4,7
4,7
+ d
+ d
7,9
7,9
= 200 + 120 = 320,
= 200 + 120 = 320,
d
d
4,8
4,8
+ d
+ d
8,9
8,9
= 250 + 130 = 380.
= 250 + 130 = 380.
Tak więc z miasta 4 do 9 należy wybrać drogę o długości
Tak więc z miasta 4 do 9 należy wybrać drogę o długości
d
d
4,7,9
4,7,9
= 320. Podobnie:
= 320. Podobnie:
d
d
5,7
5,7
+ d
+ d
7,9
7,9
= 200 + 120 = 320,
= 200 + 120 = 320,
d
d
5,8
5,8
+ d
+ d
8,9
8,9
= 180 + 130 = 310,
= 180 + 130 = 310,
a więc z miasta 5 do 9 należy wybrać drogę o długości d
a więc z miasta 5 do 9 należy wybrać drogę o długości d
5,8,9
5,8,9
= 310.
= 310.
Następnie:
Następnie:
d
d
6,7
6,7
+ d
+ d
7,9
7,9
= 150 + 120 = 270,
= 150 + 120 = 270,
d
d
6,8
6,8
+ d
+ d
8,9
8,9
= 110 + 130 = 240,
= 110 + 130 = 240,
a więc z miasta 6 do 9 należy wybrać drogę o długości
a więc z miasta 6 do 9 należy wybrać drogę o długości
d
d
6,8,9
6,8,9
=
=
240
240
.
.
KROK 3.
KROK 3.
Powtórzmy całe postępowanie biorąc za punkt wyjścia
Powtórzmy całe postępowanie biorąc za punkt wyjścia
etap 2:
etap 2:
d
d
2,4
2,4
+ d
+ d
4,9
4,9
= 150 + 320 = 470,
= 150 + 320 = 470,
d
d
2,5
2,5
+ d
+ d
5,9
5,9
= 80 + 310 = 390,
= 80 + 310 = 390,
d
d
2,6
2,6
+ d
+ d
6,9
6,9
= 120 + 240 = 360,
= 120 + 240 = 360,
a więc z miasta 2 do 9 należy wybrać drogę:
a więc z miasta 2 do 9 należy wybrać drogę:
2-6-8-9
2-6-8-9
o długości 360 km.
o długości 360 km.
Podobnie
Podobnie
d
d
3,4
3,4
+ d
+ d
4,9
4,9
= 150 + 320 = 470,
= 150 + 320 = 470,
d
d
3,5
3,5
+ d
+ d
4,9
4,9
= 130 + 310 = 440,
= 130 + 310 = 440,
d
d
3,6
3,6
+ d
+ d
4,9
4,9
= 190 + 240 = 430,
= 190 + 240 = 430,
a więc z miasta 3 do 9 należy wybrać drogę:
a więc z miasta 3 do 9 należy wybrać drogę:
3-6-8-9
3-6-8-9
o długości 430 km.
o długości 430 km.
KROK 4.
KROK 4.
Dotarliśmy do punktu startowego, w
Dotarliśmy do punktu startowego, w
którym rozpatrujemy sposób dotarcia do
którym rozpatrujemy sposób dotarcia do
celu z miasta 1 przez miasta 2 lub 3:
celu z miasta 1 przez miasta 2 lub 3:
d
d
1,2
1,2
+ d
+ d
2,9
2,9
= 100 + 360 = 460,
= 100 + 360 = 460,
d
d
1,3
1,3
+ d
+ d
3,9
3,9
= 80 + 430 = 510,
= 80 + 430 = 510,
a więc z miasta 1 do 9 należy wybrać
a więc z miasta 1 do 9 należy wybrać
drogę:
drogę:
1-2-6-8-9
1-2-6-8-9
o długości 460 km.
o długości 460 km.
Document Outline