Modely sieťovej
analýzy
Sieťová analýza
Sieťová analýza – súbor modelov a metód
založených na grafickom vyjadrení realizujúcich
časovú, resp. nákladovú analýzu.
Používa sa predovšetkým na prípravu a realizáciu
investičných projektov, vlastnej výstavby, resp.
prípravy a realizácie rozsiahlych akcií, ktoré v sebe
zahŕňajú na seba nadväzujúce činnosti.
Sieťová analýza – základné pojmy
Projekt – priestorovo a/alebo časovo vymedzený súbor organizačne, resp.
technologicky súvisiacich (nadväzujúcich) činností zameraných na
dosiahnutie určitého cieľa.
Činnosť – priestorovo a/alebo časovo vymedzený súbor prác zameraných na
realizáciu projektu.
Ohodnotenie činnosti – predstavujú rôzne ukazovatele, na báze ktorých
možno realizovať analýzu projektu.
Časová analýza projektu – ohodnotenie činností na báze trvania činností.
Nákladová analýza projektu – ohodnotenie činností na báze nákladov na
realizáciu činností.
Technologické väzby – technologická nadväznosť jednotlivých činností
navzájom.
Sieťové grafy
Sieťový graf – matematický model projektu.
Hranovo orientované sieťové grafy – hrany grafu
reprezentujú činnosti projektu a uzly reprezentujú udalosti.
Činnosti projektu sa vyjadrujú orientovanými hranami grafu
medzi uzlami grafu.
Uzlovo orientované sieťové grafy – uzly grafu
reprezentujú činnosti a hrany vyjadrujú väzby medzi
činnosťami. Činnosti projektu sa vyjadrujú uzlami v tvare
štvoruholníka, väzby orientovanými hranami.
Štruktúra sieťovéhu grafu
Štruktúra sieťového grafu – deterministická resp.
stochastická.
Pravdepodobnostné ohodnotenie – prezentuje podmienené
pravdepodobnosti realizácie jednotlivých činností, používa
sa keď nemožno presne určiť ohodnotenie činnosti, táto
hodnota je považovaná za náhodnú.
Metódy riešenia sieťových grafov
Sieťový graf
Štruktúra grafu
Ohodnotenie
Druh ohodnotenia
Metóda
Deterministické
CPM
Stochastické
PERT
Náklady
Deterministické
CPM/COST
Čas
Deterministické
Náklady
Deterministické
Pravdepodobnosť
Stochastické
Čas
Deterministické
Čas
Deterministická
Hranovo
definovaný
Stochastická
Uzlovo
definovaný
Deterministická
GERT
MPM
Kritická cesta
Kritická cesta – najdlhšia cesta v sieťovom grafe,
ktorá zodpovedá vetve s najdlhším trvaním
činností na nej ležiacich.
Hľadanie kritickej cesty sa používa predovšetkým
na určenie harmonogramu výstavby rôznych
projektov, na riadenie výrobných činností z
hľadiska ich časového rozvrhovania, na riešenie
úloh o maximálnej priepustnosti komunikačného
systému a iné.
Hľadanie kritickej cesty
Hľadanie kritickej cesty sa používa na určenie
harmonogramu na seba nadväzujúcich činností:
výstavba rôznych projektov,
riadenie výrobných činností z hľadiska ich
časového rozvrhovania,
riešenie úloh o maximálnej priepustnosti
komunikačného systému a iné.
Relácie medzi činnosťami
činnosti A (čer.) a B (mod.) prebiehajú paralelne, sú vzájomne nezávislé
činnosti A a B nemôžu prebiehať paralelne, sú vzájomne závislé
činnosť B môže začať len vtedy, ak bola činnosť A ukončená
činnosť B môže prebiehať, ak činnosť A už prebiehala určitú dobu
činnosť B môže prebiehať až po určitej dobe po ukončení činnosti A
fiktívna činnosť, činnosť C (zel.) môže začať po skončení A aj B
Hľadanie kritickej cesty pomocou
lineárneho programovania
min z( x ) = ∑∑ d ij x ij
i∈P j∈R
∑x =∑x
ij
i∈P
k∈R
jk
j = 2, 3,...., n
∑x
ij
=1
i =1
∑x
ij
=1
j= n
j∈R
i∈P
x ij ∈{ 0,1}
i ∈ P, j ∈ R
kde
d ij ≥ 0 pre i = 1, 2, ..., n − 1, j = 2, 3, ..., n
{
P = p ∈ {1, 2, ..., n}d pj ≠ 0, j = 1, 2, ..., n
}
R = { r ∈ {1, 2, ..., n}d ir ≠ 0, i = 1, 2, ..., n}
Hľadanie kritickej cesty pomocou
lineárneho programovania
min
tn
tj - ti ≥ dij i =1,2,...,n-1, j = 2,3,...,n
ti ≥ 0 i =1,2,...,n
na praktické výpočty je vhodné ti = 0.
Hľadanie kritickej cesty metódou
CPM (Critical Path Method)
existencia sieťového grafu, ktorý je acyklický,
hrany smerujú od uzlov s menšími indexami
do uzlov s väčšími indexami
deterministická metóda, presne určené
hodnoty trvania činností tij
určená nadväznosť jednotlivých činností
CPM – symbolika
T0 – čas začatia projektu,
T1 – vypočítaný čas ukončenia projektu,
tij – trvanie činnosti z uzla ui do uzla uj,
ZMi (ti0) – najskôr možný začiatok začatia činností vychádzajúcich z uzla ui,
KMj (tj0) – najskôr možný koniec činností končiacich v uzle uj,
ti0 + tij najskôr možný koniec činnosti (i, j),
ZPi (ti1) – najneskôr prípustný začiatok začatia činností vychádzajúcich z uzla
ui,
tj1 – tij najneskôr prípustný začiatok činnosti (i, j),
KPj (tj1) – najneskôr prípustný koniec činností končiacich v uzle uj,
RCij – kritická rezerva činnosti (i, j):
RCij = KPj – KMj = ZPi – ZMi = tj1 – ti0 – tij
CPM – výpočet
Výpočet prebieha v 2 etapách.
1. etapa – výpočet vpred (od začiatočného uzla ku koncovému)
Položíme ZMi (ti0) = 0
ti0 = 0
tj0 = ti0 + tij
Výpočet KMj (tj0) = ZMi + tij
Výpočet ZMj (najskôr možné konce činností pre už vypočítané KMj)
ZMj = max KMj
ti0 = max tj0
Výpočet T1 = max KMn
T1 = max tn0
2. etapa – výpočet vzad (od koncového uzla k začiatočnému)
Položíme KPj (tj1) = T1
tn1 = T1
Výpočet ZPi (tj1) = KPj – tij
ti1 = tj1 – tij
Výpočet KPi (najneskôr prípustné začiatky činností pre už vypočítané ZPi)
KPi = min ZPj
Výpočet RCij
ti1 = min ti1
RCij = KPj – KMj = ZPi – ZMi = tj1 – ti0 – tij
CPM – spôsoby riešenia
Grafické riešenie
najskôr možný koniec
činností, ktoré vchádzajú do
uzla uj
Tabuľkové riešenie
ui
KMj
(tj0)
KPj
(ti1)
najneskôr
prípustný
začiatok činností,
ktoré vychádzajú
z uzla ui
CPM – Príklad
Činnosť
Nech treba
vykonať
nasledujúce
činnosti:
A
Pred.
činnosť
-
Trvanie
tij
6
B
-
8
C
-
2
D
A
1
E
B,D
5
F
A
4
G
B,D
5
H
B,D
3
I
B,D
2
J
C,E
1
K
F,G
6
L
F,G,H
8
M
H
4
N
I,J,M
3
CPM – Príklad
Činnosť
F
A
D
B
C
G
H
E
I
K
Fi
L
M
N
J
A
Pred.
činnosť
-
Trvanie
tij
6
B
-
8
C
-
2
D
A
1
E
B,D
5
F
A
4
G
B,D
5
H
B,D
3
I
B,D
2
J
C,E
1
K
F,G
6
L
F,G,H
8
M
H
4
N
I,J,M
3
CPM – Príklad
F
A
D
B
C
G
H
E
I
K
Fi
L
M
N
J
CPM – Príklad
Riešenie
CPM
Nákladová analýza kritickej cesty
V princípe každá činnosť sa dá vykonať aj za kratší čas ako sú
určené normy
Nech tij je normálne trvanie činnosti spojené s normálnymi
nákladmi cij a Tij je minimálne trvanie činnosti spojené so
zvýšenými nákladmi Cij
Predpoklady:
nad normálne trvanie činnosti nie je možné racionálne
predlžovať čas trvania, lebo vplyvom konštantných nákladov
sa budú celkové náklady zvyšovať
minimálnu dobu trvania činnosti nie je možné skracovať z
technických dôvodov.
CPM
Nákladová analýza kritickej cesty
Graf vývoja nákladov v závislosti od dĺžky trvania činnosti
Cij − cij
aij = −
tij − Tij
náklady
Cij
Zvýšené náklady
aij
cij
Tij
Normálne náklady
tij
čas
CPM - Nákladová analýza kritickej
cesty Weberovým postupom
Výpočet kritickej cesty pri normálnom trvaní činností tij s
normálnymi nákladmi cij, pričom celkové náklady sú
CNN = ∑cij i = 1,2,...,n −1; j = 2,3,...,n
i, j
Pre všetky činnosti
Cij − cij
aij = −
i = 1,2,...,n −1; j = 2,3,...,n
sa vypočíta spád
tij − Tij
Možno skracovať len kritické činnosti, pre ktoré vyberáme
minimálnu hodnotu aij. Kritické činnosti možno skrátiť na čas
Tij so zvýšenými nákladmi Cij, pričom môžu vznikať nové
kritické cesty a teda treba vypočítať nové riešenie.
Redukcia sa realizuje, pokiaľ sa nevyčerpajú všetky možnosti
skrátenia.
Hľadanie kritickej cesty metódou PERT (Program
Evaluation and Review Technique)
spôsob výpočtu rovnaký ako CPM
stochastická metóda, určené hodnoty optimistického
odhadu trvania činnosti aij, pesimistického odhadu trvania
činnosti bij, najpravdepodobnejšieho odhadu trvania
činnosti mij
výpočet trvania činnosti
a + 4m + b
tij =
ij
ij
6
ij
Hľadanie kritickej cesty metódou PERT (Program
Evaluation and Review Technique)
aij + 4mij + bij
Výpočet trvania činnosti
d ij =
6
Beta rozdelenie – výhodné vlastnosti na modelovanie
a
zodpovedá premenlivosti prevádzkových podmienok
Vlastnosti:
Unimodálne – jeden vrchol, ktorý zodpovedá
najpravdepodobnejšej dobe trvania (modus) mij,
Konečné variačné rozpätie - časy trvania sa vyskytujú v intervale
medzi najkratšou (aij) a najdlhšou dobou trvania (bij),
Symetria – závisí na polohe vrcholu vo vnútri intervalu a podľa
toho možno vytvoriť hypotetickú krivku funkcie hustoty
pravdepodobnosti.
Hľadanie kritickej cesty metódou PERT (Program
Evaluation and Review Technique)
Beta rozdelenie
Hľadanie kritickej cesty metódou PERT (Program
Evaluation and Review Technique)
aij + 4mij + bij
Výpočet trvania činnosti
tij =
6
Smerodajná odchýlka činnosti
 bij − aij 
σ ij = 

6


2
Rozptyl činnosti
 bij − aij 
2
σ ij = 


Smerodajná odchýlka trvania projektu
σ (T ) =
Pravdepodobnosť ukončenia do plánovaného Tp
 Tp − T 
p(Tp ≤ T ) = Φ 

σ
(
T
)


6
2
σ
∑ ij
K

PERT – Príklad
Nech treba
vykonať
nasledujúce
činnosti:
D
E
A
Fi
C
I
H
K
G
B
J
F
Odhad dĺžky trvania činnosti v dňoch
Činnosť Predch. optimistický najpravdepodobnejší pesimistický
bij
aij
mij
A
4
6
10
B
2
2
2
C
10
18
20
D
A
2
6
10
E
A
6
8
12
F
B
2
4
6
G
A, C
8
11
13
H
A, C
8
11
14
I
E
5
5
5
L
J
G
7
9
11
K
G
10
20
25
L
F, J
5
9
10
PERT – Príklad
PERT – Príklad
Riešenie
PERT – Príklad
Riešenie
Výsledok: trvanie projektu T = 47
Smerodajná odchýlka trvania projektu
σ ( T ) = ∑ σ ij2 = 9,722 = 3,118
Plánované ukončenie Tp = 46
K
Pravdepodobnosť ukončenia do plánovaného Tp = 46
 Tp − T 
 46 − 47 
p( TP = 46 ) = Φ 
=
Φ

 3,188  = Φ [− 0 ,313676] = 0 ,62172
(
T
)
σ




p( TP = 46 ) = Φ [z ] = 1 − Φ [− z ] = 1 − 0 ,62172 = 0,37828
PERT – Príklad
Riešenie
Tabuľka hodnôt distribučnej funkcie normálneho rozdelenia:
z
0,00
0,10
0,20
0,30
0,40
0,50
0,60
z
0,30
0,31
0,32
0,33
0,34
0,35
0,36
0,37
0,38
0,39
0,40
Φ(z)
0,5000000
0,5398278
0,5792597
0,6179114
0,6554217
0,6914625
0,7257469
Φ(z)
0,6179114
0,6217195
0,6255158
0,6293000
0,6330717
0,6368307
0,6405764
0,6443088
0,6480273
0,6517317
0,6554217
z
0,70
0,80
0,90
1,00
1,10
1,20
1,30
Φ(z)
0,7580363
0,7881446
0,8159399
0,8413447
0,8643339
0,8849303
0,9031995
z
1,40
1,50
1,60
1,70
1,80
1,90
2,00
Φ(z)
0,9192433
0,9331928
0,9452007
0,9554345
0,9640697
0,9712834
0,9772499
z
2,10
2,20
2,30
2,40
2,50
2,60
2,70
Φ(z)
0,9821356
0,9860966
0,9892759
0,9918025
0,9937903
0,9953388
0,9965330
z
2,80
2,90
3,00
3,10
3,20
3,30
3,50
Φ(z)
0,9974449
0,9981342
0,9986501
0,9990324
0,9993129
0,9995166
0,9997674
Download

a ij