W7.PDF

(158 KB) Pobierz
Microsoft Word - 8course-07d.doc
Sie zdarze cd .
Przeprowadzenie skomplikowanego procesu wymaga analizy harmonogramu
operacji składaj cych si na dany proces. Analiz sieci zdarze mo na przeprowadzi w
oparciu o takie metody jak np. PERT 1 (Program Evaluation and Review Technique) czy
te CPM (Critical Path method). Analiza pozwala ustawi takie sekwencje operacji aby
kolejno (lub równoczesno ) wykonywania operacji zapewniała z jednej strony
poprawn prac z punktu widzenia u ywanej technologii oraz umo liwiała np.
minimalizowanie czasu trwania procesu.
Elementy metody CPM widzieli my omawiaj c nasz „kulinarn ” sie zdarze . Długo
drogi krytycznej (drogi o maksymalnej wadze) dla danej sieci zdarze odpowiada
minimalnemu czasowi jaki jest potrzebny na wykonanie wszystkich operacji i zako czenia
procesu. Istnieje wiele algorytmów znajdowania maksymalnej drogi dla skierowanych
grafów acyklicznych. Zapoznamy si z jednym z nich, algorytmem LPA.
Algorytm LPA (ang. Longest Path Algorythm ).
Niech D b dzie sieci zdarze ze ródłem s i uj ciem f . Ponadto, niech
w
(
i
,
j
)
>
0
b dzie wag kraw dzi od wierzchołka v i do wierzchołka v j . Aby znale drog
o maksymalnej wadze wykonaj:
1. (Drzewo spinaj ce)
Niech T : dowolne drzewo spinaj ce zakorzenione w s .
2. (Inicjalizuj spowolnienia) Dla ka dej kraw dzi v i v j nie nale cej do T połó
1
s
(
i
,
j
)
=
-
. Parametr
s
( j
,
)
nazywamy „spowolnieniem”.
Ujemna warto s(i,j) sygnalizuje, e mo emy zwi kszy
wag jakiej drogi.
3. (Powi kszanie wagi)
Wykonuj kroki 4 – 6 gdy co najmniej jeden
s
(
i
,
j
)
<
0
.
4. (Wagi dróg w T)
Oblicz t(i), gdzie t(i) jest wag drogi od s do v i wzdłu
drzewa T. Dla ka dego wierzchołka połó t(i) jako etykiet .
1 Metoda PERT u ywa opisu probabilistycznego do analizy procesów kolejkowania. Metoda ta była
stworzona na potrzeby militarne (ameryka ski program rakietowy POLARIS).
37
i
3247208.008.png
5. (Nowe spowolnienia)
Dla ka dej kraw dzi v i v j nie nale cej do T połó
)
s
(
i
,
j
)
=
t
(
j
)
-
t
(
i
)
-
w
(
i
,
j
.
6. (Nowe drzewo ?)
Je li dla pewnych i,j
s
(
i
,
j
)
<
0
, to kraw d w drzewie T
prowadz c do wierzchołka zast p kraw dzi v i v j . Koniec
Drzewo T z etykietami t(i).
7. Koniec Algorytmu:
Drzewo T z etykietami t(i).
Przykład (zastosowania LPA).
Rozwa my sie zdarze z poni szego Rysunku.
v 2
2
v 4
2
5
v 1
4
1
2
v 6
3
3
2
4
v 3
2
v 5
0
9
We my nast puj ce drzewo spinaj ce T (krok 1):
Po przypisaniu wszystkim kraw dziom spowolnie –1
wykonamy pewn liczb iteracji (kroki 4 - 6).
W druj c po wybranym drzewie spinaj cym obliczamy warto ci parametrów t(i) dla
wszystkich wierzchołków oraz etykietujemy wierzchołki warto ciami t(i).
3
6
Dla kraw dzi nie nale cych do drzewa T (linie przerywane) obliczymy spowolnienia
s
(
i
,
j
)
=
t
(
j
)
-
t
(
i
)
-
w
(
i
,
j
)
. Mamy:
s
(
2
=
t
(
2
-
t
(
-
w
(
2
=
2
-
3
-
4
=
-
5
<
0
s
(
4
=
4
-
3
-
1
=
0
s
(
=
6
-
3
-
2
=
1
s
(
6
=
9
-
6
-
3
=
0
.
(Uwaga: kolejno wypisywania indeksów wierzchołków jest zgodna ze zwrotem
kraw dzi, tzn. i jest indeksem wierzchołka pocz tkowego a j wierzchołka ko cowego)
38
3247208.009.png 3247208.010.png
Opó nienie
s
(
2
=
-
5
jest ujemne wi c
prowadz c do wierzchołka v 2 kraw d v 1 v 2
zast pujemy kraw dzi v 3 v 2 . Opó nienia dla
pozostałych kraw dzi nie s ujemne wi c nie
0
usuwamy tych kraw dzi. Aktualne drzewo
spinaj ce ma posta :
Co najmniej jedno opó nienie
s
( j
i
,
)
było
7
9
ujemne wiec wykonujemy kolejn iteracj .
Obliczamy parametry t(i) i przypisujemy je
wierzchołkom:
0
14
3
11
Nast pnie obliczamy spowolnienia
s
( j
i
,
)
. Mamy:
s
(
2
=
t
(
2
-
t
(
-
w
(
2
=
7
-
0
-
2
=
5
s
(
4
=
9
-
3
-
1
=
5
s
(
=
11
-
3
-
2
=
1
s
(
6
=
14
-
11
-
3
=
0
.
W tej iteracji nie otrzymali my ju adnego ujemnego opó nienia co oznacza, e droga
wyznaczona przez drzewo spinaj ce otrzymane w poprzedniej iteracji jest drog o
maksymalnej wadze równej 14.
Sieci transportuj ce (przesyłowe).
Grafy skierowane s u ytecznym narz dziem do modelowania układów
transportowych (np. sieci drogowych, sieci telefonicznych, ruroci gów). Wa ne s
odpowiedzi na takie przykładowe pytania:
· jak g sty mo e by ruch samochodowy na sieci dróg o danej przepustowo ci (ilo aut
przeje d aj cych na godzin ) by nie prowadził do powstawania korków drogowych,
· jak wiele rozmów telefonicznych mo ne by realizowane równocze nie aby czas
oczekiwania na kolejne poł czenie nie przekraczał dopuszczalnej warto ci,
· w jakich ilo ciach i z jak pr dko ci mog by przesyłane płyny w sieci ruroci gów
aby przepływ był laminarny a przesyłana ilo płynu maksymalna.
Ogl daj c graf z Rysunku 22a wyobra amy sobie, e jaki materiał jest przesyłany od
ródła s wzdłu skierowanych kraw dzi do uj cia f .
39
3247208.011.png
pojemno
b
6
e
b
6 ,6
e
6
7
6,6
7,6
s
f
s
f
6
7
6,2
7,2
c
2
d
c
2, 2
d
Rysunek 22a
Rysunek 22b
strumie
Kraw dzie na Rysunku 22a s oznaczone pojemno ciami ł cz (kraw dzi). Na Rysunku
22b indeksy kraw dzi s postaci b
a , (pojemno , strumie ). Np. przez kraw d sc mo na
maksymalnie przetransportowa 6 jednostek (pojemno ) ale aktualnie s przesyłane 2
jednostki (strumie ).
Podamy 2 definicje u ywane w opisie sieci transportuj cych.
DEFINICJA 1 .
Sieci transportuj c nazywamy acykliczny i spójny graf skierowany z nieujemnymi
wagami kraw dzi , z jednym ródłem i jednym uj ciem.
· Wag kraw dzi xy od wierzchołka x do wierzchołka y oznaczamy c(x,y) i nazywamy
pojemno ci kraw dzi (ang. capacity ).
· Strumie (ang. flux ) f jest funkcj , która przyjmuje nieujemne warto ci na ka dej
kraw dzi, tj:
1.
0 f
£
£
c
(
x
,
y
)
dla
"
x
,
y
Î
grafu
G
.
2. Dla ka dego wierzchołka (za wyj tkiem ródła i uj cia) mamy:
à Ã
Î
f
x
,
y
)
=
f
(
y
,
v
)
: tzn. suma strumieni wpadaj cych do wierzchołka y równa jest
x
G
v
Î
G
sumie strumieni wypływaj cych z tego wierzchołka.
Podstawowe pytanie stawiane w analizie sieci transportuj cych: jak dla danych
pojemno ciach kraw dzi rozdzieli strumienie w kraw dziach aby całkowita ilo
materiału przesyłanego od ródła do uj cia była maksymalna .
40
(
3247208.001.png
DEFINICJA 2 .
Dana jest sie transportuj ca G. Niech P b dzie takim zbiorem wierzchołków, e zwiera
ródło s ale nie zawiera uj cia f , tzn.
s Î oraz
P
f Î , gdzie P jest dopełnieniem P .
P
· Ci ciem (ang. cut )
( P
P
,
)
nazywamy zbiór kraw dzi xy takich, e
x Î i
P
y Î .
P
· Pojemno ci ci cia nazywamy sum :
Î
c
(
P
,
P
)
=
c
(
x
,
y
)
.
x
P
,
y
P
· Warto ci strumienia w sieci G nazywamy sum :
Î
f
G
=
f
s )
,
x
.
x
G
· Strumie maksymalny to ten, który osi ga maksymaln warto na sieci G.
· Kraw d xy jest nasycona gdy
f
(
x
,
y
)
=
c
(
x
,
y
)
, w przeciwnym wypadku kraw d xy
jest nienasycona.
Przykład .
Rozwa my sie przedstawion na grafie obok. Kraw dzie sb , bd oraz ce s
nasycone bo np.
f
(
b
,
d
)
=
6
=
c
(
b
,
d
)
.
Zaznaczone ci cie
( P
P
,
)
jest zbudowane na
ci cie
zbiorach:
P
=
{
s
,
b
,
c
},
P
=
{
d
,
e
,
f
}
. Ci cie
b
6,6
e
to zawiera kraw dzie bd oraz ce, czyli
(
P
,
P
)
=
{
bd
,
ce
}
. Pojemno tego ci cia
6,6
7,6
s
f
wynosi
c
(
P
,
P
)
=
2
+
6
i jest równa
przepływaj cemu aktualnie strumieniowi.
Wszystkie (w tym przypadku dwie) kraw dzie
6,2
7,2
c
2,2
d
nale ce do ci cia s nasycone.
Strumie
f
G
=
f
(
s
,
b
)
+
f
(
s
,
c
)
=
c
(
s
,
b
)
+
c
(
s
,
c
)
=
6
+
2
=
8
=
c
(
P
,
P
)
jest maksymalny.
41
3247208.002.png 3247208.003.png 3247208.004.png 3247208.005.png 3247208.006.png 3247208.007.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin