Prob_siec.pdf
(
3200 KB
)
Pobierz
Microsoft PowerPoint - problemy sieciowe.ppt
Zarządzanie transportem
Problemy sieciowe
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29
E-mail: piotr.sawicki@put.poznan.pl
URL: http://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: http://www.put.poznan.pl/~piotrs
Plan prezentacji
Istota problemów sieciowych
•
definicje podstawowych pojęć
•
typowe problemy sieciowe
Problem najkrótszej drogi
•
sformułowanie problemu
•
metody/algorytmy rozwiązania problemu
Problem minimalnie rozgałęzionego drzewa
•
sformułowanie problemu
•
metody/algorytmy rozwiązania problemu
Problem maksymalnego przepływu
•
sformułowanie problemu
•
metody/algorytmy rozwiązania problemu
Podsumowanie
Piotr Sawicki / Zarządzanie transportem
2
68
Piotr Sawicki
Wprowadzenie
Istota problemów sieciowych
sieć
(
graf
)
Æ
połączenie wielu
punktów o różnej lokalizacji
•
w
ę
ę
ze
ze
ł
ł
Æ
punkt sieci
(
wierzchołek grafu
) o
określonych parametrach
– lokalizacja
– przepustowość
– popyt / podaż
–inne
•
gałąź
gałąź
(
łuk
)
Æ
odcinek łączący
dwa sąsiednie węzły; odcinek o
określonych własnościach
– przepustowość
–długość
– max. prędkość
– koszt przemieszczenia po łuku
Piotr Sawicki / Zarządzanie transportem
3
68
Wprowadzenie
Istota problemów sieciowych
skierowana
Æ
gałąź (
łuk
) o
zdefiniowanym kierunku przepływu
–przepływ jednokierunkowy
–przepływ dwukierunkowy
•
gałąź
nieskierowana
Æ
gałąź
(łuk) o niezdefiniowanym kierunku
przepływu
•
sie
skierowana
Æ
układ węzłów
połączonych wyłącznie gałęziami
(łukami) skierowanymi
•
droga
droga
Æ
sekwencja gałęzi (łuków)
pomiędzy węzłem początkowym i
końcowym
– droga skierowana
– droga nieskierowana
Piotr Sawicki / Zarządzanie transportem
4
68
Definicje podstawowych pojęć
•
sieć
Definicje podstawowych pojęć
•
gałąź
gałąź
skierowana
gałąź
nieskierowana
sie
ć
ć
skierowana
Wprowadzenie
Istota problemów sieciowych
Definicje podstawowych pojęć
•
rodzaje dróg
–
droga otwarta
droga zamknięta
Æ
droga,
której węzeł początkowy i
końcowy jest tym samym
węzłem (
droga obiegowa
)
•
rodzaje punktów
–
punkt początkowy
punkt początkowy
Æ
punkt
nadania towaru
–
punkt ko
cowy
Æ
punkt
dostawy towaru
–
punkt po
redni
Æ
punkt
przez który przechodzi droga
z punktu początkowego do
końcowego
Piotr Sawicki / Zarządzanie transportem
5
68
Wprowadzenie
Istota problemów sieciowych
Problem 1
Æ
W jaki sposób przejechać z określonego punktu poczatkowego
do punktu końcowego drogi, aby
•
długość drogi była minimalna?
•
czas przejazdu był minimalny?
•
koszt przejazdu był minimalny?
Problem 1
Æ
problem
najkrótszej drogi (ścieżki)
Piotr Sawicki / Zarządzanie transportem
6
68
droga otwarta
Æ
droga,
której węzeł początkowy i
końcowy są różnymi węzłami
–
droga zamknięta
punkt ko
ń
ń
cowy
punkt po
ś
ś
redni
Wprowadzenie
Istota problemów sieciowych
Problem najkrótszej drogi
Æ
przykłady
zastosowań
•
przejazd pogotowia i straży pożarnej do odległego
miejsca wypadku
Æ
jaka droga jest najszybsza?
•
przewóz międzymagazynowy towarów o krótkim
terminie przydatności (FMCG)
Æ
jak droga jest
najszybsza?
•
awaryjna (pilna) dostawa węgla do elektrociepłowni
Æ
jaka droga jest najszybsza?
•
…
Piotr Sawicki / Zarządzanie transportem
7
68
Wprowadzenie
Istota problemów sieciowych
Problem 2
Æ
Jak zorganizować przepływ towaru, aby wykorzystać dostępną
przepustowość wszystkich połączeń komunikacyjnych?
Problem 2
Æ
problem
maksymalnego przepływu
h
h
h
h
h
h
h
h
Poziom obciążenia gałęzi = 50%
h
Poziom obciążenia gałęzi = 80%
Piotr Sawicki / Zarządzanie transportem
8
68
Wprowadzenie
Istota problemów sieciowych
Problem maksymalnego przepływu
Æ
przykłady
zastosowań
•
sterowanie ruchem miejskim
Æ
jak zaprogramować
sterowniki sygnalizacji świetlnej w celu
równomiernego rozłożenia ruchu miejskiego?
•
wyznaczenie trasy przewozu towarów przy znanym
obciążeniu poszczególnych łuków sieci
Æ
jak
dokonać przewozu dużego ładunku nawozów
sztucznych drogą kolejową?
•
….
Piotr Sawicki / Zarządzanie transportem
9
68
Wprowadzenie
Istota problemów sieciowych
Problem 3
Æ
Które gałęzie systemu transportowego łączą wszystkie jej
węzły w taki sposób aby całkowita długość połączeń była minimalna?
Problem 3
Æ
problem
minimalnie rozgałęzionego
drzewa
Piotr Sawicki / Zarządzanie transportem
10
68
Plik z chomika:
Danuszka
Inne pliki z tego folderu:
wymagania.pdf
(1070 KB)
asystent1.zip
(1978 KB)
Test6.exe
(9643 KB)
Test3.exe
(3 KB)
Test2.exe
(5136 KB)
Inne foldery tego chomika:
Psychologia
Zgłoś jeśli
naruszono regulamin