Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
1
Zarządzanie systemami
transportu drogowego
Zarządzanie systemami
transportu drogowego
Problemy sieciowe
cz. 2.
Problem maksymalnego przepływu
Problem minimalnie rozgałęzionego
Problemy sieciowe
cz. 2.
Problem maksymalnego przepływu
Problem minimalnie rozgałęzionego
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 748, tel. 61 665 22 49
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotr.sawicki
Wydział Maszyn Roboczych i Transportu
pok. 748, tel. 61 665 22 49
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotr.sawicki
Problem minimalnie rozgałęzionego
drzewa
Problem minimalnie rozgałęzionego
drzewa
Problem maksymalnego przepływu
Modelowanie
Problem maksymalnego przepływu
•
polega na znalezieniu maksymalnego strumienia towaru (lub pojazdów) który może
„przejść” od węzła początkowego do końcowego w określonym czasie
•
całkowita wielkość przepływu ograniczona jest przepustowością poszczególnych
gałęzi
– godziny szczytu
– stan dróg (nawierzchni)
– pora roku
– czasowe ograniczenie prędkości
– inne
•
założenia dodatkowe
t
ść k żd j ł i j t
i
( ó
k
l
t ść)
33
26
Piotr Sawicki / Zarządzanie systemami transportu drogowego
– przepustowość każdej gałęzi jest ograniczona (górna, maksymalna wartość)
– przepustowość węzłów jest nieograniczona
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
2
Problem maksymalnego przepływu
Modelowanie i rozwiązywanie problemu
Modelowanie i rozwiązywanie problemu maksymalnego przepływu
algorytm maksymalnego
Metoda rozwiązania
Metoda rozwiązania
w postaci grafu
Modelowanie problemu
Modelowanie problemu
algorytm maksymalnego
przepływu (AMP), met.
Forda i Fulkersona
metoda ograniczeń
i rozgałęzień
w postaci grafu
skierowanego
w postaci grafu
skierowanego oraz
programowania
całkowitoliczbowego
33
27
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Problem maksymalnego przepływu
Modelowanie w postaci problemu sieciowego
Modelowanie problemu w postaci grafu skierowanego
•
zakładamy, że rozważaną sieć transportową można przedstawić w postaci graf
skierowanego
>
>
=
E
V
G
gdzie:
V – zbiór węzłów, v
ij
∈ V
E
>
– zbiór łuków skierowanych e
ij
o określonej przepustowości w czasie
ρ
ij
•
problem polega na znalezieniu maksymalnego przepływu towaru od węzła
początkowego do końcowego w analizowanym przedziale czasu
=
E
V
G
,
33
28
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
3
Problem maksymalnego przepływu
Modelowanie w postaci problemu sieciowego
Przepustowość gałęzi
•
mierzona jest w tonach ładunku w ciągu godziny
•
liczby określające przepustowość gałęzi wskazują pozostałą możliwą wartość
przepływu
C
8
Max. przepływ z C do B
(8 ton/godz.)
B
0
6
Przepływ z B do A jest
zabroniony
(0 ton/godz.)
Max. przepływ z B do C
(6 ton/godz.)
33
29
Piotr Sawicki / Zarządzanie systemami transportu drogowego
A
C
8
Max. przepływ z A do B
(8 ton/godz.)
B
0
Problem maksymalnego przepływu
Modelowanie w postaci problemu sieciowego
Analiza przepływu
•
konwencja zapisu Æ gałąź skierowana
Przepływ w kierunku BÆC
wynosi 8 ton/godz.
Przepływ w kierunku CÆB
jest zabroniony
•
sposób analizy i uwzględnienia realizacji przepływu w kierunku AÆC
Pytanie:
jaka jest maksymalna przepustowość drogi A Æ C?
C
0
6
8
B
6 – 6 = 0
0
6
14
C
8
0
B
33
30
Piotr Sawicki / Zarządzanie systemami transportu drogowego
•
obciążenie (przydział do) gałęzi relacji AÆC przepływem F=6
•
korekta pozostałej do wykorzystania przepustowości
A
8
Najmniejsza dostępna przepustowość
gałęzi na drodze AÆC (6 ton/godz.)
8 – 6 = 2
2
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
4
Problem maksymalnego przepływu
Modelowanie w postaci problemu sieciowego
Analiza przepływu
•
zapis realizacji przepływu w kierunku AÆC
A
C
2
6
0
14
B
33
31
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Problem maksymalnego przepływu
Rozwiązywanie problemu za pomocą AMP
Wstępna analiza
przepływów
•
maksymalna przepustowość
gałęzi wychodzących z
ł S Æ 130 / d
0
40
węzła S Æ 130 ton/godz.
(80 + 50 = 130)
•
maksymalna przepustowość
gałęzi wchodzących do
węzła R Æ 105 ton/godz.
(20 + 25 + 60 = 105)
•
WNIOSEK Æ maksymalne
obciążenie sieci
S
80
50
50
40
0
50
50
0
0
40
35
35
45
0
25
30
0
0
50
0 60
33
32
Piotr Sawicki / Zarządzanie systemami transportu drogowego
obciążenie sieci
transportowej może wynosić
105 ton/godz.
•
jakie jest rzeczywiste
obciążenie na
poszczególnych gałęziach?
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0
30
25 40
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
5
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania, met.
Forda-Fulkersona
•
KROK 1 Æ dokonaj
identyfikacji wszystkich
li
h d ó S d R
0
40
możliwych dróg z S do R,
dla których ρ
ij
> 0
– S-G-B-R
– S-G-Wa-B-R
– S-G-Wa-R
– S-G-P-Wa-B-R
– S-G-P-Wa-R
– S-G-P-Ł-Ka-Kr-R
S
80
50
50
40
0
50
50
0
0
40
35
35
45
0
25
30
0
0
50
0 60
33
33
Piotr Sawicki / Zarządzanie systemami transportu drogowego
S G P Ł Ka Kr R
– S-G-P-Wr-Ka-Kr-R
– S-P-Wa-R
– S-P-Ł-Ka-Kr-R
– S-P-Ł-Wa-R
– S-P-Wa-B-R
– S-P-Wr-Ka-Kr-R
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0
30
25 40
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 2 Æ dokonaj identyfikacji
najmniejszej przepustowości na
wybranych drogach w [ton/godz.]:
0
40
– S-G-B-R:
40
– S-G-Wa-B-R:
30
– S-G-Wa-R:
25
– S-G-P-Wa-B-R:
50
– S-G-P-Wa-R:
25
– S-G-P-Ł-Ka-Kr-R:
20
– S-G-P-Wr-Ka-Kr-R: 20
– S-P-Wa-R:
25
S
80
50
50
40
0
50
50
0
0
40
0
35
45
0
25
30
0
0
50
0 60
rozważana droga Æ
33
34
Piotr Sawicki / Zarządzanie systemami transportu drogowego
S P Wa R:
25
– S-P-Ł-Ka-Kr-R:
20
– S-P-Ł-Wa-R:
25
– S-P-Wa-B-R:
50
– S-P-Wr-Ka-Kr-R:
20
– S-P-Wr-Ka-Wa-R:
25
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0
30
25 40
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
6
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 3 Æ obciążenie przepływem
(
ρ=50
) wszystkich gałęzi drogi:
S-G-P-Wa-B-R
0
40
50
– redukcja przepustowości w
kierunku przepływu
– zaznaczenie realizacji przepływu
Uwaga:
przepustowość łuków
G-P
P-Wa
Wa-B
S
80
50
50
40
0
50
50
0
0
40
0
35
45
0
25
30
0
0
50
0 60
30
0
0
0
10
50
50
50
33
35
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Wa B
uległa wyczerpaniu
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0
30
25 40
90
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 3 cd
Æ
sieć transportowa po poprzedniej
alokacji przepływu
ρ=50
ton/godz.
Æ
d k
j li
kt l j
50
40
Æ
dokonaj analizy aktualnej
przepustowości dróg
– S-G-B-R:
40
– S-G-Wa-B-R:
30
– S-G-Wa-R:
25
– S-G-P-Wa-B-R:
50
– S-G-P-Wa-R:
25
– S-G-P-Ł-Ka-Kr-R:
20
S G P W K K R
20
S
30
50
50
40
50
0
0
50
0
40
0
35
45
0
25
30
0
0
0
50 10
redukcja
ρ(B-R) =10 Æ
10
33
36
Piotr Sawicki / Zarządzanie systemami transportu drogowego
– S-G-P-Wr-Ka-Kr-R: 20
– S-P-Wa-R:
25
– S-P-Ł-Ka-Kr-R:
20
– S-P-Ł-Wa-R:
25
– S-P-Wa-B-R:
50
– S-P-Wr-Ka-Kr-R:
20
– S-P-Wr-Ka-Wa-R:
25
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0
30
25 90
drogi zawierające
gałęzie: G-P-Wa-B
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
7
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 4 Æ dokonaj kolejnej
alokacji przepływu na drogach
– S-G-B-R:
10
50
40
– S-G-Wa-R:
25
– S-P-Ł-Ka-Kr-R:
20
– S-P-Ł-Wa-R:
25
– S-P-Wr-Ka-Kr-R:
20
– S-P-Wr-Ka-Wa-R:
25
S
30
50
50
40
50
0
0
50
0
40
0
35
45
0
25
30
0
0
0
50 10
rozważana droga Æ
33
37
Piotr Sawicki / Zarządzanie systemami transportu drogowego
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0
30
25 90
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 4 cd Æ alokacja
przepływu
ρ= 25
ton/godz. do
gałęzi drogi S-P-Ł-Wa-R
50
40
– redukcja przepustowości w
kierunku przepływu
– zaznaczenie realizacji
przepływu
Uwaga:
przepustowość łuku Wa-R
uległa wyczerpaniu
S
30
50
50
40
50
0
0
50
0
40
0
35
45
0
25
30
0
0
0
50 10
25
10
15
0
75
25
25
33
38
Piotr Sawicki / Zarządzanie systemami transportu drogowego
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0
30
25
90
50
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
8
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 4 cd
Æ
sieć transportowa po
poprzedniej alokacji
ρ=25
50
40
ton/godz
Æ
dokonaj analizy aktualnej
przepustowości dróg
– S-G-B-R:
10
– S-G-Wa-R:
25
– S-P-Ł-Ka-Kr-R:
20
– S-P-Ł-Wa-R:
25
S P W K K R
20
S
30
25
75
40
50
0
0
50
25
15
25
10
45
0
0
30
0
0
0
50 10
drogi zawierające
gałąź: Wa-R
10
33
39
Piotr Sawicki / Zarządzanie systemami transportu drogowego
– S-P-Wr-Ka-Kr-R:
20
– S-P-Wr-Ka-Wa-R:
25
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0
30
50
90
redukcja ρ(P-Ł)=10
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 5
Æ
wybór kolejnej drogi
– S-G-B-R:
10
50
40
– S-P-Ł-Ka-Kr-R:
10
– S-P-Wr-Ka-Kr-R:
20
S
30
25
75
40
50
0
0
50
25
15
25
10
45
0
0
30
0
0
0
50 10
rozważana droga Æ
33
40
Piotr Sawicki / Zarządzanie systemami transportu drogowego
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0
30
50
90
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
9
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 5 cd
Æ
alokacja przepływu
ρ = 20
ton/godz. do gałęzi drogi
S P W K K R
60
30
S-P-Wr-Ka-Kr-R
– redukcja przepustowości w
kierunku przepływu
– zaznaczenie przepływu towaru
Uwaga:
przepustowość łuku Ka-K uległa
wyczerpaniu
S
20
25
75
40
50
0
0
50
25
15
25
10
45
0
0
30
0
10
0
50 0
20
5
20
95
33
41
Piotr Sawicki / Zarządzanie systemami transportu drogowego
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0 30
50
100
20
20
0
10
70
20
30
20
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 5 cd
Æ
sieć transportowa po
poprzedniej alokacji
20 / d
d ł i d
i
60
30
20 ton/godz. do gałęzi drogi
S-P-Wr-Ka-Kr-R
Æ
dokonaj analizy aktualnej
przepustowości dróg
– S-G-B-R:
10
– S-P-Ł-Ka-Kr-R:
10
– S-P-Wr-Ka-Kr-R:
20
S
20
5
95
20
50
0
0
50
25
15
25
10
45
0
0
30
0
10
0
50 0
drogi zawierające
gałąź: Ka-Kr
rozważana droga Æ
33
42
Piotr Sawicki / Zarządzanie systemami transportu drogowego
R
S – punkt początkowy R – punkt końcowy
70
20
20
0 30 10
20
0 30
50
100
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
10
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 6
Æ
alokacja przepływu
10 ton/godz. do gałęzi drogi
S G B R
50
40
30
60
S-G-B-R
– redukcja przepustowości w
kierunku przepływu
– zaznaczenie przepływu towaru
30
5
95
20
50
0
0
50
25
15
25
10
45
0
25
30
0
0
0
50 10
S
20
0
10
33
43
Piotr Sawicki / Zarządzanie systemami transportu drogowego
R
S – punkt początkowy R – punkt końcowy
70
20
20
0 30 10
20
0
30
50 90
100
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Kroki postępowania …cd
•
KROK 6 cd
Æ
sieć transportowa po
poprzednich alokacjach
ł
60
30
przepływu
PYTANIE:
Æ
czy jest możliwe alokowanie
jakiegokolwiek przepływu do
gałęzi wchodzących w skład
dróg SÆR?
S
20
5
95
20
50
0
0
50
25
15
25
10
45
0
0
30
0
10
0
50 0
33
44
Piotr Sawicki / Zarządzanie systemami transportu drogowego
R
S – punkt początkowy R – punkt końcowy
50
20
20
0 30 10
20
0
30
50
100
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
11
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Analiza rezultatu
•
podsumowanie wszystkich
alokacji (4 iteracje) przepływów
– S-G-P-Wa-B-R:
50
60
30
– S-P-Ł-W-R:
25
– S-P-Wr-Ka-Kr-R:
20
– S-G-B-R:
10
S
20
5
95
20
50
0
0
50
25
15
25
10
45
0
0
30
0
10
0
50 0
20
33
45
Piotr Sawicki / Zarządzanie systemami transportu drogowego
R
S – punkt początkowy R – punkt końcowy
50
20
20
0 30 10
20
0
30
50
100
20
Problem maksymalnego przepływu
Rozwiązania problemu za pomocą AMP
Analiza rezultatu
•
sumaryczne przepływy w sieci
transportowej
– sieć transportowa obciążona
j t
ł
60
30
jest przepływem wynoszącym
105 ton/godz.
S 20
5
95
20
50
0
0
50
25
15
25
10
45
0
0
30
0
10
0
50 0
105
105
20
33
46
Piotr Sawicki / Zarządzanie systemami transportu drogowego
R
S – punkt początkowy R – punkt końcowy
50
20
20
0
30 10
20
0
30
50
100
105
105
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
12
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Algorytm maksymalnego przepływu
(1) znajdź wszystkie możliwe drogi w kierunku przepływu z punktu nadania do
odbioru, dla których minimalna przepustowość gałęzi jest większa od zera
(2) wybierz drogę, dla której minimalna przepustowość ρ osiąga największą wartość
spośród wszystkich dróg i przydziel przepływ ρ do wszystkich gałęzi na tej drodze
(i) zredukuj przepustowość każdej gałęzi tej drogi w kierunku przepływu, o
wartość ρ
(ii) zaznacz przepływ towaru w kierunku przeciwnym do przepływu
(3) wróć do kroku (1) i powtarzaj do chwili, kiedy przepustowość wszystkich dróg
określonych w kroku (1) zostanie wyczerpana
33
47
Piotr Sawicki / Zarządzanie systemami transportu drogowego
y
( )
y
p
(4) maksymalny przepływ jest sumą wszystkich przepływów ρ przydzielonych do
poszczególnych dróg, podczas iteracyjnie realizowanego kroku (2)
Problem maksymalnego przepływu
Rozwiązanie problemu za pomocą AMP
Dlaczego zaznaczany jest przepływ w kierunku przeciwnym?
1
1
1
1
1
0
2
1
1
0
A
B
1
1
1
1
1
1
a) sieć pierwotna
A
B
0
1
1
2
0
2
b) pierwsza droga
2
0
33
48
Piotr Sawicki / Zarządzanie systemami transportu drogowego
A
B
0
0
2
2
1
1
0
2
c) druga droga
A
B
1
1
1
1
d) ostatecznie …
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
13
Problem maksymalnego przepływu
Modelowanie w postaci zadania programowania liniowego
Sformułowanie problemu maksymalnego przepływu w postaci zadania
programowania liniowego
•
zakładamy, że rozważaną sieć transportową można przedstawić w postaci grafu
skierowanego
gdzie:
V – zbiór węzłów, v
ij
∈ V
E
>
– zbiór łuków skierowanych e
ij
o maksymalnej dostępnej przepustowości
w czasie x
ij
max
•
dla każdego łuku należy zdefiniować zmienną decyzyjną
x
ij
określającą przepływ
>
>
=
E
V
G
,
33
49
Piotr Sawicki / Zarządzanie systemami transportu drogowego
dla każdego łuku należy zdefiniować zmienną decyzyjną
x
ij
określającą przepływ
towarowy z punktu i do punktu j
Problem maksymalnego przepływu
Modelowanie w postaci zadania programowania liniowego
Model matematyczny problemu maksymalnego przepływu Æ zadanie
programowania liniowego
•
funkcja celu
∑
ri
x
Max
•
przy ograniczeniach (dla węzłów pośrednich)
∑
∈
=
E
i
r
e
ri
)
,
(
s
r
j
i
x
x
E
j
i
e
ji
E
j
i
e
ij
,
,
;
0
)
,
(
)
,
(
≠
∀
=
−
∑
∑
∈
=
∈
=
max
0
x
x
≤
≤
33
50
Piotr Sawicki / Zarządzanie systemami transportu drogowego
gdzie:
r – węzeł początkowy (nadania)
s – węzeł końcowy (odbioru)
0
ij
ij
x
x
≤
≤
2
j
x
ij
s
r
1
i
x
ri
x
r1
x
r2
x
2j
x
1s
x
js
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
14
Problem maksymalnego przepływu
Modelowanie w postaci zadania programowania liniowego
Konstrukcja modelu dla rozważanego przypadku
•
funkcja celu
Max (x
SG
+ x
SP
)
•
ograniczenia
0
40
G: x
GB
+ x
GWa
+ x
GP
– x
SG
= 0
B: x
BR
– x
GB
– x
WaB
= 0
P: x
PWa
+ x
PŁ
+ x
PWr
– x
SP
– x
GP
= 0
Wa: x
WaB
+ x
WaR
– x
GWa
– x
PWa
– x
ŁWa
– x
KaWa
= 0
Ł: x
ŁKa
+ x
ŁWa
– x
ŁP
= 0
Wr: x
WrKa
– x
PWr
= 0
S
80
50
50
40
0
50
50
0
0
40
0
35
45
0
25
30
0
0
50
0 60
33
51
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Ka: x
KaKr
+ x
KaWa
– x
WrKa
– x
ŁKa
= 0
Kr: x
KrR
– x
KaKr
= 0
0
≤ x
SG
≤ 80
(1)
…
0
≤ x
KrR
≤ 30
(17)
R
S – punkt początkowy R – punkt końcowy
50
40
0
20 10 30
0
0
30
25 40
Przykład
Przykład
Problem maksymalnego przepływu
Rozwiązania z zastosowaniem metody rozgałęzień i ograniczeń
Zapis modelu
matematycznego w
Solverze MS Excel
Maksymalna przepustowość gałęzi x
ij
max
Zmienne decyzyjne x
ij
33
52
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Ograniczenia dla węzłów
(kierunek przepływu)
Funkcja celu
Pozostała przepustowość x
ij
max
– x
ij
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
15
Problem maksymalnego przepływu
Rozwiązania z zastosowaniem metody rozgałęzień i ograniczeń
55
0
Analiza rozwiązania problemu
Æ
maksymalny przepływ
wynosi 105 ton/godz.
S 25
0
100
40
0
50
20
30
0
40
20
15
25
0
0
15
15
40
30
20 0
105
105
33
53
Piotr Sawicki / Zarządzanie systemami transportu drogowego
•
istnieje kilka rozwiązań
(rozłożeń) przepływu Æ
rozwiązania równoważne
R
S – punkt początkowy R – punkt końcowy
30
40
0
0
30 10
20
20
30
50
100
105
105
Problem minimalnie rozgałęzionego drzewa
Modelowanie i rozwiązanie
Problem minimalnie rozgałęzionego drzewa
•
polega na połączeniu wszystkich węzłów sieci transportowej gałęziami (łukami) w taki
sposób, że ich całkowita długość jest minimalna
•
charakterystyka sieci transportowej
– gałęzie scharakteryzowane są przez ich długość
– węzły nie posiadają żadnej charakterystyki ilościowej Æ jedynie znana jest ich lokalizacja
•
rozróżnienie węzła początkowego i końcowego nie jest istotne
33
54
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
16
Problem minimalnie rozgałęzionego drzewa
Modelowanie i rozwiązywanie problemu
Modelowanie i rozwiązywanie problemu minimalnie rozgałęzionego drzewa
algorytm minimalnie
Metoda rozwiązania
Metoda rozwiązania
w postaci grafu
Modelowanie problemu
Modelowanie problemu
algorytm minimalnie
rozgałęzionego drzewa
AMRD
metoda ograniczeń i
rozgałęzień
w postaci grafu
nieskierowanego
w postaci grafu
nieskierowanego oraz
programowania
całkowitoliczbowego
33
55
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Problem minimalnie rozgałęzionego drzewa
Modelowanie w postaci problemu sieciowego
Modelowanie problemu w postaci grafu nieskierowanego
•
zakładamy, że rozważaną sieć transportową można przedstawić w postaci grafu
nieskierowanego
E
V
G
,
=
gdzie:
V – zbiór węzłów, v
ij
∈ V
E – zbiór łuków nieskierowanych e
ij
∈ E o określonej długości
l
ij
E
V
G
,
33
56
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
17
Problem minimalnie rozgałęzionego drzewa
Rozwiązanie za pomocą AMRD
Kroki postępowania
•
KROK 1: wybierz dowolny
węzeł w sieci Æ węzeł W
•
KROK 2: znajdź węzeł
położony najbliżej węzła W
•
KROK 3: znajdź węzeł
położony najbliżej
połączonych węzłów
•
KROK 4: kontynuuj
poszukiwania węzłów
najbliższych do już
ł
h d
178
W
33
57
Piotr Sawicki / Zarządzanie systemami transportu drogowego
połączonych do czasu,
kiedy wszystkie węzły
zostaną połączone
165
Problem minimalnie rozgałęzionego drzewa
Rozwiązanie za pomocą AMRD
Kroki postępowania ..cd
•
KROK 5: określ długość
wykorzystanych węzłów
134
+ 188
+ 196
+ 75
+ 165
+ 199
+ 178
+ 234
178
W
33
58
Piotr Sawicki / Zarządzanie systemami transportu drogowego
+ 234
+ 296
=1665 km
165
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
18
Problem minimalnie rozgałęzionego drzewa
Rozwiązanie za pomocą AMRD
Algorytm minimalnie rozgałęzionego drzewa
(1) wybierz dowolny węzeł w rozważanej sieci transportowej
(2) znajdź kolejny najbliżej położony węzeł i połącz je
( )
j
j y
j
j p
y ę
p ą j
(3) znajdź kolejny węzeł położony najbliżej połączonych wcześniej węzłów
(4) krok (3) powtarzaj do chwili, gdy wszystkie węzły zostaną połączone
(5) określ długość gałęzi wykorzystanych do połączenia wszystkich węzłów; długość
ta jest minimalna
33
59
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Problem minimalnie rozgałęzionego drzewa
Rozwiązanie za pomocą AMRD
Zadanie Æ określ minimalną długość gałęzi łączących wszystkie węzły
rozpoczynając od węzła (Poznań)
•
wybór (długość) gałęzi tworzących
minimalnie rozgałęzione drzewo
i l
d b
i
178
W
nie zależy od wyboru pierwszego
punktu
178
W
33
60
Piotr Sawicki / Zarządzanie systemami transportu drogowego
165
165
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
19
Problem minimalnie rozgałęzionego drzewa
Modelowanie w postaci zadania programowania liniowego
Sformułowanie problemu minimalnie rozgałęzionego drzewa
w postaci
zadania programowania całowitoliczbowego
•
zakładamy, że rozważaną sieć transportową można przedstawić w postaci graf
nieskierowanego
G =
〈V, E〉
gdzie:
V – zbiór węzłów, v
ij
∈ V
E – zbiór łuków nieskierowanych e
ij
o określonej długości l
ij
przy czym l
ij
= l
ji
•
dla każdej gałęzi (łuku) należy zdefiniować zmienną decyzyjną
x
ij
określającą, czy
gałąź z węzła i do j (e
ij
) została przyłączona do „drzewa”, czy nie (
zmienna binarna
)
33
61
Piotr Sawicki / Zarządzanie systemami transportu drogowego
•
problem polega na znalezieniu (przyłączeniu do drzewa) takich gałęzi, które utworzą
połączenie wszystkich węzłów o minimalnej długości całkowitej
⎩
⎨
⎧
→
=
wypadku
przeciwnym
w
0
drzewa"
"
do
y
przyłączon
jest
łuk
jeżeli
1
j
i
x
ij
Problem minimalnie rozgałęzionego drzewa
Modelowanie w postaci zadania programowania liniowego
Model matematyczny problemu minimalnie rozgałęzionego drzewa Æ
zadanie programowania całkowitoliczbowego
•
funkcja celu
minimalizacja długości wykorzystanych gałęzi
(w – liczba wszystkich gałęzi)
w
•
przy ograniczeniach
1) każdy węzeł musi być przyłączony do „drzewa”
∑
∈
=
w
E
j
i
e
ij
ij
x
l
)
,
(
Min
∑
∑
∈
=
∈
=
≥
+
E
j
i
e
ji
E
j
i
e
ij
x
x
)
,
(
)
,
(
1
2
x
12
x
x
2n
x
23
33
62
Piotr Sawicki / Zarządzanie systemami transportu drogowego
2) drzewo musi zawierać n-1 gałęzi (n – liczba węzłów)
3) dla każdej trójki węzłów mogą występować tylko dwie gałęzie, dla czwórki – trzy gałęzie,….
4) zmienna decyzyjna x
ij
jest zmienną binarną x
ij
= 1
∪ 0
3
j
x
ij
n
1
i
x
1i
x
13
x
3j
x
jn
1
−
=
∑
∈
=
n
x
w
E
j
i
e
ij
)
,
(
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
20
Problem minimalnie rozgałęzionego drzewa
Modelowanie w postaci zadania programowania liniowego
Konstrukcja modelu matematycznego
•
funkcja celu
Min (l
SG
x
SG
+ l
SP
x
SP
+ l
PG
x
PG
+ l
GWa
x
GWa
+ l
GB
x
GB
+ l
WaB
x
WaB
+ l
PWa
x
PWa
+ l
PŁ
x
PŁ
+ l
ŁWa
x
ŁWa
+ l
PWr
x
PWr
+ l
ŁKa
x
ŁKa
+ l
WrKa
x
WrKa
+ l
KaKr
x
KaKr
+ l
KaWa
x
KaWa
+ l
KrR
x
KrR
+ l
WaR
x
WaR
+ l
BR
x
BR
)
i
i
•
ograniczenia
1) każdy węzeł musi być przyłączony do drzewa
S: x
SG
+ x
SP
≥ 1
G: x
SG
+ x
PG
+ x
GWa
+ x
GB
≥ 1
B: x
GB
+ x
WaB
+ x
BR
≥ 1
P: x
SP
+ x
PG
+ x
PWa
+ x
PŁ
+ x
PWr
≥ 1
Wa: x
GWa
+ x
WaB
+ x
PWa
+ x
ŁWa
+ x
WaR
+ x
KaWa
≥ 1
Ł
≥ 1
1
33
63
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Ł:
x
PŁ
+ x
ŁWa
+ x
ŁKa
≥ 1
Wr: x
PWr
+ x
WrKa
≥ 1
Ka: x
ŁKa
+ x
WrKa
+ x
KaKr
≥ 1
Kr: x
KaKr
+ x
KrR
≥ 1
R: x
KrR
+ x
WaR
+ x
BR
≥ 1
178
165
Problem minimalnie rozgałęzionego drzewa
Modelowanie w postaci zadania programowania liniowego
Konstrukcja modelu matematycznego ..cd
•
ograniczenia …cd
2) drzewo musi zawierać n-1 gałęzi
x
SG
+ x
SP
+ x
PG
+ x
GWa
+ x
GB
+ x
WaB
2
+ x
PWa
+ x
PŁ
+ x
ŁWa
+ x
PWr
+ x
ŁKa
+ x
WrKa
+ x
KaKr
+ x
KaWa
+ x
KrR
+ x
WaR
+ x
BR
= 9
3)
eliminacja zamkniętych dróg
x
SG
+ x
SP
+ x
PG
≤ 2
x
PG
+ x
GWa
+ x
PWa
≤ 2
x
GB
+ x
WaB
+ x
GWa
≤ 2
1
1
2
3
4
5
6
33
64
Piotr Sawicki / Zarządzanie systemami transportu drogowego
….
x
PWr
+ x
WrKa
+ x
ŁKa
+ x
PŁ
≤ 3
x
KaKr
+ x
KrR
+ x
KaWa
+ x
WaR
≤ 3
178
165
7
8
9
10
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
21
Problem minimalnie rozgałęzionego drzewa
Modelowanie w postaci zadania programowania liniowego
Konstrukcja modelu matematycznego ..cd
•
ograniczenia
4) zmienna x
ij
jest zmienna binarną
x
SG
; x
SP
; x
PG
; x
GWa
; x
GB
; x
WaB
;
2
x
PWa
; x
PŁ
; x
ŁWa
; x
PWr
; x
ŁKa
;
x
WrKa
; x
KaKr
; x
KaWa
; x
KrR
;
x
WaR
; x
BR
= 1
∪ 0
Problem zostanie rozwiązany za
pomocą metody rozgałęzień
i ograniczeń w Solverze MS Excel
1
1
2
3
4
5
6
33
65
Piotr Sawicki / Zarządzanie systemami transportu drogowego
178
165
7
8
9
10
Przykład
Przykład
Problem minimalnie rozgałęzionego drzewa
Rozwiązywanie z zastosowaniem metody ograniczeń i rozgałęzień
Zapis modelu matematycznego w Solverze MS Excel
Tab1: Zdefiniowanie komórek, którymi
może posługiwać się Solver
33
66
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Tablica przydziału (wyboru) gałęzi
spośród zdefiniowanych komórek (Tab1)
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
22
Problem minimalnie rozgałęzionego drzewa
Rozwiązywanie z zastosowaniem metody ograniczeń i rozgałęzień
Zapis modelu matematycznego w Solverze MS Excel
Funkcja celu
33
67
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Ograniczenia
Problem minimalnie rozgałęzionego drzewa
Rozwiązywanie z zastosowaniem metody ograniczeń i rozgałęzień
Zapis modelu matematycznego w Solverze MS Excel
33
68
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
23
Problem minimalnie rozgałęzionego drzewa
Rozwiązywanie z zastosowaniem metody ograniczeń i rozgałęzień
Zapis modelu matematycznego w Solverze MS Excel
33
69
Piotr Sawicki / Zarządzanie systemami transportu drogowego
Problem minimalnie rozgałęzionego drzewa
Rozwiązywanie z zastosowaniem metody ograniczeń i rozgałęzień
Analiza rozwiązania
Całkowita długość wszystkich
gałęzi wynosi 1665 km
1
W
33
70
Piotr Sawicki / Zarządzanie systemami transportu drogowego
178
165
Zarządzanie Systamami Transportu
Drogowego
dr inż. Piotr Sawicki / WMRiT / PP
24
Podsumowanie
Porównanie rozważanych problemów sieciowych
Najkrótsza droga
przez sieć
Maksymalny przepływ
w sieci
Minimalnie rozgałęzione
drzewo
Rozważane
połączenia
droga z węzła początkowego
do końcowego
droga z węzła
początkowego do
droga z dowolnego węzła w
sieci do pozostałych węzłów
połączenia
do końcowego
początkowego do
końcowego
sieci do pozostałych węzłów
Reprezentacja w
postaci grafu
graf graf
graf
Parametry gałęzi długość w określonym
kierunku
przepustowość w
określonym kierunku
długość
Modelowanie
problemu
(i) graf nieskierowany
(ii) graf skierowany i
i
(i) graf skierowany
(ii) graf skierowany i
i
(i) graf nieskierowany
(ii) graf nieskierowany i
i
33
71
Piotr Sawicki / Zarządzanie systemami transportu drogowego
programowanie
całkowitoliczbowe
programowanie
całkowitoliczbowe
programowanie
całkowitoliczbowe
Sposób
rozwiązywania
(i) algorytm najbliższego
sąsiedztwa (ANS)
(ii) metoda ograniczeń
i rozgałęzień
(i) algorytm maksymalnego
przepływu (AMP) - met.
Forda-Fulkersona
(ii) metoda ograniczeń
i rozgałęzień
(i) algorytm minimalnie
rozgałęzionego drzewa
(AMRD)
(ii) metoda ograniczeń
i rozgałęzień
Zarządzanie systemami
transportu drogowego
Zarządzanie systemami
transportu drogowego
Problemy sieciowe
Problemy sieciowe
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs
Wyszukiwarka
Podobne podstrony:
Probl siec cz1
Zakażenia grzybicze skóry cz2
Probl inter i kard 06'03
parafunkcje cz2
15 Sieć Następnej Generacjiid 16074 ppt
podziały złamań cz2 1sd
Sieć działań(diagram strzałkowy) v 2
8(45) Diagramy klas cz2
Wykład12 Sieć z protokołem X 25 i Frame Relay
charakterystyka dochodow samorzadu terytorialnego (cz2
Wykład10a Sieć z protokołem X 25 i Frame Relay
Style kierowania cz2
Wykład5 sieć zintegrowana ISDN, BISDN
Wykład I Grafika inżynierska cz2
MDA ID zadprzedkol(3) cz2 13 14
Kartoteka Lodowa kraina WS3 po cz2
zwiazki nieorg 1 cz2
więcej podobnych podstron