Metody síťové analýzy Řeší problematiku složitých systémů, zejména pak vazby mezi jejich jednotlivými prvky. Vychází z teorie grafů. Základní metody síťové analýzy: CPM (Critical Path Method) – deterministický model. PERT (Program Evaluation and Review Technique) – stochastický model.
Základní pojmy Uzel – vyjadřuje začátek nebo konec činnosti. Hrana – grafické znázornění činnosti. Může být: orientovaná
i
neorientovaná
i
tij
j j
Činnost – vlastní provádění konkrétní pracovní operace. Fiktivní činnost – činnost, která nespotřebovává čas ani zdroje.
1
Základní pojmy Projekt – soubor činností se vzájemnými časovými a logickými vazbami. Síťový graf – grafické znázornění projektu, je modelem projektu. Uzlově definovaný graf – činnosti jsou reprezentovány pomocí uzlů a hrany představují vazby mezi těmito činnostmi. Hranově definovaný graf – činnosti jsou reprezentovány pomocí orientovaných hran a uzly udávají ukončení předchozích a začátky následujících činností.
Uzlově definovaný graf
3 12
9 1 5
5
2 6
7
9
13
14
4 10
13
2
Hranově definovaný graf
15 6
9
4
28 13
10
11
Základní pojmy Konečný graf – obsahuje konečný počet uzlů. Částečně definovaný graf – obsahuje alespoň jednu orientovanou hranu. Úplně definovaný graf – graf, jehož všechny hrany jsou orientované. Acyklický graf – neobsahuje žádnou smyčku. Cesta – posloupnost všech na sebe navazujících činností, od počátečního až ke koncovému uzlu grafu. Kritická cesta – cesta s nejdelším trváním, určuje dobu trvání projektu.
3
Cyklus v grafu
Acyklický graf
4
Základní pojmy Souvislý graf – graf, kde mezi každýma dvěma různými uzly existuje cesta. Úplný graf – graf, ve kterém existuje hrana mezi každou dvojicí uzlů – je nutně souvislý. Podgraf – je tvořen některými nebo i všemi uzly původního grafu a některými z hran pův. grafu. Kostra grafu – podgraf, který obsahuje všechny uzly původního grafu a neobsahuje cyklus. Hamiltonovská cesta – cesta, která obsahuje všechny uzly grafu, ale nemusí obsahovat všechny hrany.
Souvislý graf Neorientovaně souvislý graf
Úplný graf
5
Graf, jeho podgraf a kostra Graf
Příklad podgrafu
Kostra grafu
Hamiltonovská cesta 2
3
1
4
8
5
7
6
6
Typické úlohy teorie grafů určení minimální (maximální) kostry grafu, nalezení nejkratší cesty, určení maximálního toku (propustnosti) v síti, úloha obchodního cestujícího – Hamiltonovská cesta o minimální celkové délce. úloha čínského pošťáka – nalezení trasy obsahující všechny hrany grafu, nalezení optimálního umístění depa – obslužného střediska pro ostatní uzly, analýza a řízení projektů.
Optimální spojení míst Jedná se o úlohu nalezení minimální kostry grafu. Popis algoritmu: 1. V celém grafu se vyberou dvě hrany s nejnižším ohodnocením. 2. V dalších krocích se vždy vybere další hrana s minimálním ohodnocením tak, aby netvořila cyklus s již dříve vybranými hranami. 3. Krok 2 se opakuje až do vybrání celkového počtu (n – 1) hran, které budou tvořit hledanou minimální kostru grafu.
7
Příklad 1 Problém prof. Borůvky Byla postavena malá elektrárna, která může zásobovat elektrickým proudem pět okolních obcí. Elektrické vedení lze postavit pro každou dvojici těchto obcí a je známá jeho délka v kilometrech (viz graf). Požadavkem je, aby elektřina byla zavedena do všech těchto obcí a současně, aby elektrické vedení bylo co nejkratší, a tím i nejlevnější na stavbu, údržbu a ztráty elektrického proudu. BORŮVKA, O. O jistém problému minimálním. Moravská přírodovědecká společnost v Brně, 1926
Příklad 1 Vzdálenosti mezi obcemi 2
5
3
14
4
10
7
20
1
6
4
17 19 11
5
8
Příklad 2 - zadání Firma má záměr vybudovat kabelové rozvody pro televizi a další služby mezi sídlišti ve středně velkém městě. Rozložení sídlišť a jejich vzájemné vzdálenosti jsou uvedeny na mapce. Stanovte optimální trasování rozvodů tak, aby délka výsledné sítě byla minimální. 4
2
5
5 6
3
1
9
6 5
6
3 8
12 7
2
4
7
Příklad 3 – zadání (maximální kostra grafu) Pracovníci elektrárny omylem vešli do pracovny profesora Mefista. Ten se nechá oslovovat jako prof. Borůvka, vyslechne pozorně delegaci s tím, že problém vyřeší. Ve své prohnanosti má však v úmyslu vyřešit úlohu zcela opačně. Ponechat sice ve výsledku co nejmenší počet použitých spojení, ale nalézt takový výsledek, kde je celkové vedení ze všech možných nejdelší.
9
Příklad 3 Vzdálenosti mezi obcemi 2
5
3
14
4
10
7
20
1
6
4
17 19 11
5
Nalezení nejkratší cesty Jedná se o úlohu nalezení minimální vzdálenosti mezi dvojicí míst. Uzly jsou např. křižovatky, železniční stanice apod. Popis algoritmu: 1. Hodnota ve výchozím uzlu se rovná nule – u1 = 0. 2. Délka cesty je dána součtem dosavadní délky (obsažené v hodnotě ui) a délky uvažovaného úseku hij (hrany) s tím, že nás zajímá minimum výsledku: uj = min(ui + hij)
j = 2, 3, …, n
3. Krok 2 se opakuje, dokud není vypočtena hodnota un či hodnoty uj pro všechny uzly.
10
Příklad 4 - zadání 8 3
8
4 7
1 Dodavatel
3
5
5
7
1
1
6
5
1
2 4
2
5
6
2
3
11
1
10
3
4 8
5
12 Odběratel
9
Příklad 5 - zadání Nalezněte nejkratší cestu po železniční síti z Liberce do Nymburku. SP
38
LB
21
38 18
TU
LI
59
12
ČL
21
JI
18
45
BA 9
18
DB
21
16 23
KO
MB 29 30
NY
11
Nalezení Hamiltonovské cesty 1. Konstrukci HC začneme ve zvoleném uzlu u0 tak, že k němu vybereme takovou s ním sousedící hranu, jejíž ohodnocení je minimální. 2. K uzlu, ve kterém se aktuálně nacházíme, vybereme dále do HC takovou s ním sousedící hranu, jejíž ohodnocení je minimální a jejíž koncový uzel není do HC ještě vybrán. Existuje-li více takových hran, vybereme libovolnou z nich. 3. Postup dle kroku 2 opakujeme tak dlouho, dokud lze vybrat alespoň jednu další hranu požadované vlastnosti. Není-li již možno krok 2 opakovat, vybereme hranu, která spojuje naposled vybraný uzel s uzlem u0.
Příklad 6 - zadání Navrhněte takovou trasu vozidla pro obsluhu všech uzlů, která bude minimalizovat vykonanou dopravní práci. Obsluha začne a skončí v uzlu 0 a předpokládáme, že ložná kapacita vozidla je dostatečně velká, takže rozvážené zboží můžeme naložit pouze jednou v uzlu 0.
12
Příklad 6 – graf sítě
8
1
6
7
2
3
9 4
0
5
3
5
6
6
3
5
1
6
5
2
8
2
3
4
5
7
3
Příklad 7 - zadání Navrhněte takovou trasu manipulačního vlaku, jehož počáteční a konečnou stanicí je Nymburk, která bude minimalizovat vykonanou dopravní práci. SP 38
LB
21
38 18
TU
LI
59
12
ČL
21
JI
18
45
BA 9
18
16
DB 23
KO
21
MB 29 30
NY
13
Řešení pomocí programu STORM 2.0 – zadání úlohy
http://www.mti.tul.cz/cs/oa-mater
Řešení pomocí programu STORM 2.0 – výstup
14
