Návod na výpočty příkladů

í
Pelhřimov
Jindřichův Hradec
Jihlava
Telč
Třebíč
 
1
2
3
4
5
6
7
vi
0
22
19
46
49
78
84
j(hij)
2(22)
1(22)
1(19)
2(24)
3(30)
4(41)
5(35)
3(19)
4(24)
4(41)
3(41)
4(70)
5(29)
6(36)
 
 
5(30)
5(70)
6(29)
7(36)
 
 
 
 
6(41)
7(35)
 
 
b) určení maximálního toku
Hrana
Maximální průtok
Hrana
Maximální průtok
1 2
8
5 6
3
1 3
5
5 9
6
1 4
4
6 7
1
2 5
4
6 9
3
3 2
3
6 10
2
3 6
5
7 10
2
4 7
6
8 7
3
4 8
5
8 10
4
 
9 11
6
 
 
10 11
10
Data si přepíšeme do grafu, přičemž orientaci popisujeme šipkou a hodnotu průtoku dáváme k spojnicím.Dále pak spočítáme sumu průtoku na vstupu a výstupu, v našem případě na vstupu 8 + 5 + 4 = 17 a na výstupu 6 + 10 = 16 . Jelikož je na vstupu větší tok než na výstupu musíme zvolit nějaké menší číslo , nechali jsme sítí proudit 11 jednotek, které jsme rozepsali do tří větví směřujících z jedničky. Námi volený tok zapisujeme za čárku vedle kapacity hran jedná se o zelená čísla. Tento tok pak v jednotlivých větvích rozdělujeme podle pravidla ( součet toků do uzlu vstupujících se musí rovnat součtu toků z uzlu vystupujících.Najdeme nasycené cesty jsou to ty, které mají před čárkou i za čárkou stejné číslo (jsou vyznačeny silnější čárou).

Poté hledáme nenasycenou cestu od začátku ke konci. Pokud takovou cestu najdeme určíme minimální rozdíl mezi kapacitou a průtokem v dané cestě. Tu pak přidáme k průtoku a necháme znovu rozvést po síti podle podmínky o zachování toku a označíme nasycené cesty a zjišťujeme zda lze v síti najít nějakou nenasycenou cestu.
V našem případě jsme našli jednu nenasycenou cestu jedná se o cestu 1 – 4 – 8 – 10 - 11 a hmin ( 4 – 2; 5 – 1; 4 – 1;10 – 5 ) = 2
Jelikož jsme nenašli žádnou nenasycenou cestu je toto řešení. Maximální tok určíme na vstupu nebo výstupu , v našem případě 7 + 6 = 13
c) Určení maximálního toku pomocí modifikovaného FF algoritmu a minimální řez
Data sepíšeme do tabulky následujícím způsobem, v řádku označeném + vypisujeme zelená čísla uzlů z kterých vystupují cesty do daných uzlů v řádku i/j. V tabulce určíme diagonálu (silná čára) a nad diagonálu napíšeme čísla propustnosti hran (červená čísla ) v sloupci 0 napíšeme modré 0 do řádků kam vedou cesty.V našem případě řádky 1,2,3.
-
 
 
 
 
 
 
 
 
+
 
0
0,1
0,2
1
2,4
3,5
4,5,6
i/j
0
1
2
3
4
5
6
7
0
 
7
1
5
 
 
 
 
1
0
 
3
 
1
 
 
 
2
0
 
 
2
 
2
 
 
3
0
 
 
 
 
 
7
 
4
 
 
 
 
 
4
 
3
5
 
 
 
 
 
 
3
5
6
 
 
 
 
 
 
 
6
7
 
 
 
 
 
 
 
 
Zvolíme jednu cestu z grafu (jedno kterou) já volím cestu 7 – 6 – 3 – 0 v tabulce si šedivě vyznačíme průtoky. A hledáme minimální hodnotu v kterou pak nad diagonálou odečteme a pod diagonálou přičteme. Do řádku – napíšeme u zvolené cesty odkud kam vstupuje naše zvolená cesta ( červená čísla), v řádku plus změníme vstupující cesty, jediná změna, která se stala je modrá 0 což znamená, že do trojky už vstupuje pouze zelená 2. Zvolíme další cestu 7 – 6 – 3 – 2 – 0 . Vyznačíme šedivě.
-
3
 
 
6
 
 
7
 
+
 
0
0,1
2
1
2,4
3,5
4,5,6
i/j
0
1
2
3
4
5
6
7
0
 
7
1
 0
 
 
 
 
1
0
 
3
 
1
 
 
 
2
0
 
 
2
 
2
 
 
3
5
 
 
 
 
 
2
 
4
 
 
 
 
 
4
 
3
5
 
 
 
 
 
 
3
5
6
 
 
 
5
 
 
 
1
7
 
 
 
 
 
 
5
 
3) takto pokračujeme až do doby dokud můžeme nějakou cestu vybrat. Maximální průtok najdeme na místě, kde jsme pod diagonálou napsali 0
-
3,2
 
3
6
 
 
7
 
+
 
0
1
2
1
2,4
3,5
4,5
i/j
0
1
2
3
4
5
6
7
0
 
7
 
 
 
 
 
 
1
0
 
3
 
1
 
 
 
2
1
 
 
1
 
2
 
 
3
5
 
1
 
 
 
1
 
4
 
 
 
 
 
4
 
3
5
 
 
 
 
 
 
3
5
6
 
 
 
6
 
 
 
 
7
 
 
 
 
 
 
6
 
Volím cestu 7 – 5 – 2 – 1 – 0
-
3,2,1
2
3,5
6
 
7
7
 
+
 
0
1
2
1
4
3,5
4,5
i/j
0
1
2
3
4
5
6
7
0
 
5
 
 
 
 
 
 
1
2
 
1
 
1
 
 
 
2
1
2
 
1
 
 
 
 
3
5
 
1
 
 
 
1
 
4
 
 
 
 
 
4
 
3
5
 
 
2
 
 
 
3
3
6
 
 
 
6
 
 
 
 
7
 
 
 
 
 
2
6
 
Volím cestu 7 – 4 – 1 – 0
-
3,2,1
2,4
3,5
6
7
7
7
 
+
 
0
1
2
 
4
3,5
4,5
i/j
0
1
2
3
4
5
6
7
0
 
4
 
 
 
 
 
 
1
3
 
1
 
 
 
 
 
2
1
2
 
1
 
 
 
 
3
5
 
1
 
 
 
1
 
4
 
1
 
 
 
4
 
2
5
 
 
2
 
 
 
3
3
6
 
 
 
6
 
 
 
 
7
 
 
 
 
1
2
6
 
Volím cestu 7 – 5 – 6 - 3 – 2 – 1 – 0
-
3,2,1
2,4
3,5
6
7
7
7,5
 
+
 
0
 
 
 
4
5
4,5
i/j
0
1
2
3
4
5
6
7
0
 
3
 
 
 
 
 
 
1
4
 
 
 
 
 
 
 
2
1
3
 
 
 
 
 
 
3
5
 
2
 
 
 
 
 
4
 
1
 
 
 
4
 
2
5
 
 
2
 
 
 
2
2
6
 
 
 
7
 
1
 
 
7
 
 
 
 
1
3
6
 
Maximální tok je 4 + 1 + 5 = 10
Určení minimálního řezu. V tabulce jsou v řádcích označených + a i/j vidět nenasycené cesty (červená čísla v tabulce ) Ostatní cesty jsou nasycené v obrázku jsou označeny silnější čárou. Minimální řez určíme tak, že u vstupu oddělíme přerušovanou čarou nenasycené cesty od nasycených v našem případě ( 0 , 1 ) zbytek (0,2),(0,3),(1,2),(1,4)
Síťová analýza

Minimální doba ukončení projektu
 
Následující
Doba
Činnost
činnost
trvání
a
c
10
b
c
5
c
d, e
2
d
f
6
e
 
12
f
 
4
Nakreslíme graf přičemž dodržujeme následující činnosti , pokud jdou do jednoho uzlu dvě činnosti a jedna musí čekat na druhou rychlejší činnost označujeme čárkovanou čarou. Viz příklad.
2) Spočteme minimální dobu skončení projektu. Vyházíme z počátečního bodu a počítáme nejdelší čas, to sčítáme až do koncového bodu v našem případě 24 = ( 10 + 2 + 12 ). Toto nazýváme kritickou cestou v našem případě a – c – e
Model CPM
Číslo
Charakteristika operace
Operace, které
Doba realizace
operace
 
předcházejí
v měsících
1.
Základové práce
6.,13.,12.
5
2.
Montáž ocelové konstrukce
1.,7.
2
3.
Obezdění obvodových a vnitřních stěn
2.
6
4.
Dokončení střechy
3.
2
5.
Instalace technologického zařízení
4.,8.
6
6.
Dodávka stavebních hmot
10.
1
7.
Dodávka ocelové konstrukce
6.,12.,13.
0,5
8.
Dodávka technologického zařízení
7.
0,8
9.
Zaměření stavby
-
0,25
10.
Příprava staveniště
11.
2
11.
Zbuduvání přístupové cesty
9.
4
12.
Vybudování přívodů a odpadů vody
11.
3
13.
Napojení na rozvod elektrické energie
11.
6
(výstaba trafostanice)
 
 
14.
Zkušební provoz
5.
0,5
data z tabulky si překreslíme do grafu viz předchozí příklad
Spočítáme kritický čas z toho usuzujeme na operace rozhodující o nejdříve možném termínu ukončení stavby (kritická cesta ) v našem případě 1,2,3,4,5,9,11,13,14
Výpočet lhůtových ukazatelů projektu pomocí incidenční matice
1)Data z grafu přepíšeme do tabulky. Do prvního řádku v sloupci Ti0 napíšeme červenou 0
i/j
Ti0
0
1
2
3
4
5
0
0
 
10
15
 
 
 
1
10
 
 
10
20
 
 
2
20
 
 
 
5
10
 
3
30
 
 
 
 
10
26
4
40
 
 
 
 
 
6
5
56
 
 
 
 
 
 
2)dopočítáváme kritický čas tak, že do řádku 1 v sloupci Ti0 napíšeme modré číslo jako součet červené 0 + zelené 10, v řádku 2 hledáme maximum s čísel ( 0 + 15 , 10 + 10 ) = 20 v dalším kroku max( 10 + 20 , 20 + 5 ) = 30 Takto pokračujeme až do konce a v řádku 5 najdeme kritickou dobu
Spočteme časové rezervy. Graf si předěláme podle tohoto postupu zároveň zapisujeme data do tabulky. Červená čísla jsou zadána jde o propustnost hran.Vstup označíme nulami. Zelená čísla pak spočítáme jako součet čísel v kruhu levých čísel dole + červených čísel, začneme hranou 0 – 1 , 0 + 10 = 10 , zelené číslo pak přepisujeme do levé části kruhu, pokud do uzlu vstupují dvě větve bereme maximální číslo jako u uzlu 2 max (15, 20) toto je pak hodnota kterou zapisujeme Ti0 a TJ0 do tabulky, přičemž indexem i označujeme vstupní uzel ( modrá čísla v tabulce) a indexem J výstupní uzel ( hnědá čísla v tabulce). Fialová čísla spočteme jako rozdíl mezi koncovým uzlem a červeným číslem musíme jít proti šipce , pokud najdeme uzel z kterého vystupují dvě šipky bereme minimální hodnotu. Uzel 4 56 – 6 = 50, uzel 3 min (56 – 26 = 30,50 – 10 = 40 ). Toto číslo zapisujeme do pravé části kruhu toto je pak hodnota kterou zapisujeme Ti1 a TJ1 do tabulky, přičemž indexem i označujeme vstupní uzel ( růžová čísla v tabulce) a indexem J výstupní uzel ( tyrkysová čísla v tabulce).
hrana
tij
Ti0
TJ0
Ti1
TJ1
Rc
Rv
Rn
Rz
0,1
10
0
10
0
10
0
0
0
0
0,2
15
0
20
0
25
10
5
5
10
1,2
10
10
20
10
25
5
0
0
5
1,3
20
10
30
10
30
0
0
0
0
2,3
5
20
30
25
30
5
5
0
0
2,4
10
20
40
25
50
20
10
5
15
3,4
10
30
40
30
50
10
0
0
10
3,5
26
30
56
30
56
0
0
0
0
4,5
6
40
56
50
56
10
10
0
0
Spočteme Rc tak, že se rovná rozdílu TJ1 a Ti0 a tij. Tzn Rc = 10 - 0 - 10 - = 0
Spočteme RV tak, že se rovná rozdílu TJ0 a Ti0 a tij. Tzn Rv = 10 - 0 - 10 - = 0
Spočteme Rn tak, že se rovná rozdílu TJ0 a Ti1 a tij. Tzn Rn = 10 - 0 - 10 - = 0
Spočteme Rz tak, že se rovná rozdílu TJ1 a Ti1 a tij. Tzn Rz = 10 - 0 - 10 - = 0
metoda PERT
V tabulce je uvedena očekávaná hodnota doby trvání jednotlivých operací te a odhad rozptylu doby trvání (2te. Plánovaný termín realizace projektu je 20 dní.
Operace
te
((((
0,1
2
3,8
0,2
2
3,2
1,2
4
1
1,3
6
2,4
2,3
1
2
2,4
1
0,6
3,4
5
3
4,5
8
4
Napíšeme si tabulku přičemž červená a modrá čísla opíšeme ze zadané tabulky. Zelené číslo je předpokládaná doba realizace, počáteční a koncový uzel jsme položili roven 0 . Parametr Ti0 počítáme stejně jako u incidenční matice. Řádek
1 vyjde 2 + 0 = 2 řádek 2 max ( 2 + 0 , 4 + 2 ) = 6 atd. stejně postupujeme pro σ2To akorát používáme modrá čísla.Parametr T1j spočteme jako rozdíl zeleného čísla a červeného čísla pozor postupujeme po řádcích ne sloupcích a vybíráme min.Parametr σ2T1 spočítáme obdobně ale sčítáme modrá čísla a děláme max.
Ti0
σ2To
i/j
0
1
2
3
4
5
0
0
0
 
2
2
 
 
 
 
3,8
3,2
 
 
 
2
3,8
1
 
 
4
6
 
 
 
 
1
2,4
 
 
6
3,2
2
 
 
 
1
1
 
 
 
 
2
0,6
 
8
6,2
3
 
 
 
 
5
 
 
 
 
 
3
 
13
9,2
4
 
 
 
 
 
8
 
 
 
 
 
4
21
13,2
5
 
 
 
 
 
 
 
 
 
 
 
 
T1j
-1
1
6
7
12
20
σ2T1
13,2
9,4
9
7
4
0
2) Výsledkem jsou hodnoty
T0 = (0; 2; 6; 8; 13; 21(
T1 = (-1; 1; 6; 7; 12; 20(
(2T0 = (0; 3,8; 3,2; 6,2; 9,2; 13,2(
(2T1 = (13,2; 9,4; 9; 7; 4; 0(
3)Určete pravděpodobnost dodržení plánovaného termínu ukončení projektu
Ts=20 – předpokládaný čas dokončení
05čas který nám vyšel pro 5
((T05rozptyl pro 5
u= (Ts-05)/√((T05=(20-21)/ √13,2
u=-0,275
pravděpodobnost P(-0,275) je podle tabulky normálního rozdělení 0,40, což odpovídá 40
30
36
35
29
70
41
24
41
19
22
7
Třeb.
6
Telč
5
Jihl.
4
Hrad.
3
Pelh.
2
Ves.
1
Táb.
3,3
6,6
10,5
2,2
2,2
1,1
3,1
6,3
5,1
3,0
4,1
5,5
4,4
3,0
5,5
6,1
4,2
5,5
8,4
11
10
9
8
7
6
5
4
3
2
1
3,3
6,6
10,7
2,2
2,2
1,1
3,1
6,3
5,3
3,0
4,3
5,5
4,4
3,0
5,5
6,1
4,4
5,5
8,4
11
10
9
8
7
6
5
4
3
2
1
7
6
5
4
3
2
1
0
4
6
12
2
5
10
f
e
d
c
b
a
14
(0,5)
5
(6)
4
(2)
3
(6)
8
(0,8)
6
(1)
1
(5)
7
(0,5)
2
(2)
10
(2)
12
(3)
11
(4)
13
(6)
9
(0,25)
6
26
10
10
5
20
10
10
15
5
3
4
1
0
2
10
15
15
20
30
15
10
20
10
10
0
50
40
10
40
25
10
40
25
5
25
10
56
26
30
46
6
4
40 50
5
56 56
3
30 30
1
10 10
2
20 25
0
0 0
5
4
3
2
1
0