Ekonomicko-matematické
metody č. 11
Prof. RNDr. Jaroslav Ramík, CSc.
přednáší
doc. RNDr. David Bartl, Ph.D.
Časová analýza projektů
• Projekt: soubor činností prostorově a časově
omezených, technologicky a organizačně
souvisejících
• Realizace projektu: realizace všech činností
tvořících projekt.
• Pro každou činnost musíme stanovit údaje, které ji
charakterizují, např. dobu trvání, požadavky na
zajištění a její návaznost v rámci celého projektu
 pořadí činností v projektu není náhodné.
Konstrukce síťového grafu projektu
• matematickým modelem projektu je síť - hranově
či uzlově ohodnocený orientovaný graf, kde
jednotlivé hrany představují činnosti
• každá činnost je vyjádřena orientovanou hranou
mezi dvěma uzly, které představují začátek a
konec dané činnosti
• ve shodě s obvyklou terminologií z praxe síťové
analýzy používáme místo síť název síťový graf
• ohodnocení hran:
– časové ohodnocení činností
– zdrojové ohodnocení činností
– nákladové (finanční) ohodnocení činností
Časová analýza projektu
• dva přístupy:
– deterministický: metoda kritické cesty - CPM
(Critical Path Method)
– stochastický: metoda PERT
(Program Evaluation and Review Technique)
CPM
• 4 fáze výpočtu:
• I. fáze: Výpočet nejdříve možných začátků a
konců činností.
• II. fáze: Výpočet nejpozději přípustných
začátků a konců prováděných činností.
• III. fáze: Výpočet celkových časových rezerv.
• IV. fáze: Interpretace získaných výsledků.
CPM
označení:
• (i,j) činnost s počátkem v uzlu i a koncem
v uzlu j,
• yij doba trvání činnosti (i,j),
• ti
(0) termín nejdříve možného zahájení
činností vycházejících z uzlu i,
• ti
(0) + yij termín nejdříve možného ukončení činnosti
(i,j),
• tj
(1) termín nejpozději přípustného
ukončení činností končících v uzlu j,
• tj
(1) - yij termín nejpozději přípustného
zahájení činnosti (i,j),
• Tp plánovaná délka trvání celého
projektu.
CPM
I. fáze – Postup “od začátku do konce”výpočet
nejdříve možných termínů začátků
a konců činností:
t1
(0) = 0 i = 1,2,…,n.
II. fáze – Postup “od konce k začátku”výpočet
nejpozději přípustných začátků a
konců prováděných činností:
tn
(1) = Tp j = n,…,2,1.
 ijij ytt  )0()0(
max
 ijji ytt  )1()1(
min
CPM
• III. fáze – Celkové časové rezervy (CR)
činností jsou časy, které je možno čerpat, aniž se
prodlouží trvání celého projektu.
CRij = tj
(1) – ti
(0) – yij.
– Činnosti s nulovou celkovou rezervou se nazývají
kritické činnosti a tvoří kritickou cestu mezi
vstupem a výstupem sítě. Kritické činnosti rozhodují
o délce trvání celého projektu.
– Tp > tn
(0)  projekt je možno realizovat v plánovaném
čase a projekt má časovou rezervu.
– Tp < tn
(0)  projekt není možno realizovat
v plánovaném čase bez zkrácení doby trvání
některých činností.
CPM - příklad
Činnost Předcházející činnost Doba trvání
A ------ 5
B ----- 10
C ----- 6
D A 6
E A 1
F C 2
G C 5
H E, B, F 8
I E, B, F 7
J D, H 9
K D, H 7
L G, I, J 12
CPM- příklad
JB
A
D
E
C
G
F
I
H
K
L1
2
3
4
5
6
7
CPM - příklad
(i,j) yij ti
(0)
ti
(0)
+ yij tj
(1)
- yij tj
(1)
CRij
(1,2) 5
(1,3) 6
(1,4) 10
(2,4) 1
(2,5) 6
(3,4) 2
(3,6) 5
(4,5) 8
(4,6) 7
(5,6) 9
(5,7) 7
(6,7) 12
0
0
0
5
6
10
5
5
6
11
6
6
8
11
10
10
18
17
18
18
27
25
27 39 39
39
27
32
27
27
27
18
20
22
18
18
10
12
10
10
10
8
9
0
82
94 4
2
0
4
7
2
16
0
10
0
14
0
CPM - příklad
3
6 8
1
0 0
2
5 9
4
10 10
5
18 18
6
27 27
7
39 39
5
6
10
1
6
8
5
12
7
2
7
9
4
0
0
0
0
4
7
10
14
2 2
16
CPM - příklad
Činnost 1-5 6-10 11-15 16-20 21-25 26-30 31-35 36-40
B
H
J
L
A
C
D
E
F
G
I
K
PERT
• časová analýza projektu - stochastický
přístup
• doba trvání (každé) činnosti je náhodná
veličina s tzv. β-rozdělením
pravděpodobnosti na intervalu .
• Symbolem označíme střední hodnotu a
symbolem m označíme modus (tj.
nejpravděpodobnější hodnotu)
ba,
y
hustota β-rozdělení
0
0,01
0,02
0,03
0,04
0,05
0,06
0,07
a m b
a bm y
PERT
• Levý krajní bod intervalu a nazveme optimistický
odhad trvání činnosti (nejkratší doba trvání
činnosti), pravý krajní bod intervalu b označíme
jako pesimistický odhad trvání činnosti (nejdelší
doba trvání činnosti), modus m budeme nazývat
modální odhad trvání činnosti
(nejpravděpodobnější doba trvání činnosti).
PERT
• Pro každou činnost můžeme vypočítat její střední
hodnotu doby trvání a směrodatnou odchylku.
 střední hodnotu doby trvání činnosti (i,j):
 směrodatná odchylka sij doby trvání činnosti (i,j):
 Při výpočtu kritické cesty metodou PERT namísto pevně
zadaných hodnot délek trvání jednotlivých činností yij
použijeme střední hodnoty dob trvání činností a
 dále postupujeme stejně jako u metody CPM!!!
6
4 ijijij
ij
bma
y


6
ijij
ij
ab
s


PERT
• Výsledkem výpočtů jsou jednotlivé hrany tvořící kritickou
cestu. Namísto délky projektu vypočítáme pouze střední
hodnotu doby trvání celého projektu a směrodatnou
odchylku doby trvání celého projektu.
• Střední hodnota trvání projektu
• Směrodatná odchylka doby trvání projektu

..
,
ckrit
jiyT

..
2
,)(
ckrit
jisTs
PERT
• S jakou pravděpodobností bude projekt dokončen
v plánovaném termínu Tp ?
– trvání projektu T lze přibližně odhadnout pomocí
normálního rozdělení pravděpodobnosti se střední
hodnotou směrodatnou odchylkou s(T)
–
kde F je distribuční funkce N(0,1)
( v Excelu funkce NORM.S.DIST)
T
  






 

)(Ts
TT
FTTP
p
p
PERT - Příklad
Je dán projekt, který má následující síťový graf.
Optimistické, pesimistické a modální odhady trvání
činností jsou uvedeny v následující tabulce. Činnost E
je fiktivní. Najděte kritickou cestu, vypočítejte střední
hodnotu doby trvání projektu a směrodatnou
odchylku doby trvání projektu. Určete
pravděpodobnost toho, že celý projekt bude
realizován v čase, který nepřekročí plánovaný termín
ukončení projektu Tp = 42 dní. S jakou
pravděpodobností bude projekt ukončen za 35 dní?
PERT – Příklad.
B
A
D
E
C
G
F
I
H
K
L1
2
3
4
5
6
7
J
PERT – Příklad..
(i,j) a ij m ij b ij ijy s2
ij
(1,2) 3 5 7
(1,3) 4 5 12
(1,4) 8 9 16
(2,4) 0 0 0
(2,5) 5 6 7
(3,4) 1 2 3
(3,6) 3 4 11
(4,5) 6 8 10
(4,6) 6 7 8
(5,6) 7 8 15
(5,7) 6 7 8
(6,7) 11 12 13
5
6
10
0
6
2
5
8
7
9
7
12
16/36
64/36
64/36
0
4/36
4/36
64/36
16/36
4/36
64/36
4/36
4/36
PERT – Příklad…
(i,j) a ij m ij b ij ijy s2
ij ti
(0)
ti
(1)
tj
(0)
tj
(1)
(1,2) 3 5 7 5 16/36 0 5 5 10
(1,3) 4 5 12 6 64/36 0 6 2 8
(1,4) 8 9 16 10 64/36 0 10 0 10
(2,4) 0 0 0 0 0 5 5 10 10
(2,5) 5 6 7 6 4/36 5 11 12 18
(3,4) 1 2 3 2 4/36 6 8 8 10
(3,6) 3 4 11 5 64/36 6 11 22 27
(4,5) 6 8 10 8 16/36 10 18 10 18
(4,6) 6 7 8 7 4/36 10 17 20 27
(5,6) 7 8 15 9 64/36 18 27 18 27
(5,7) 6 7 8 7 4/36 18 25 32 39
(6,7) 11 12 13 12 4/36 27 39 27 39
PERT – Příklad….
• kritickou cestu tvoří hrany
(1,4), (4,5), (5,6) a (6,7)
• do výpočtu střední hodnoty doby trvání
projektu, rozptylu a směrodatné odchylky
doby trvání projektu zahrnujeme jen
hodnoty příslušné těmto hranám
PERT – Příklad…..
• Střední hodnota trvání projektu:
• Rozptyl doby trvání celého projektu:
• Směrodatná odchylka doby trvání projektu:
39129810
.
,  krit
jiyT
36
148
36
4641664
)(
.
2
,
2


 krit
jisTs
03,2
36
148
)(
.
2
,  krit
jisTs
PERT – Příklad……
• S jakou pravděpodobností bude projekt
ukončen za dobu kratší než 42 dnů a s jakou
pravděpodobností za dobu kratší než 35
dnů? ( )
93056,0=)1;48,1(..=
=)48,1(=)
03,2
39-42
(=)
)(
-
(=42≤
DISTSNORM
FF
Ts
TT
FTP
p
( )
02442,0=)1;97,1(..=
=)97,1(=)
03,2
39-35
(=)
)(
-
(=35≤
DISTSNORM
FF
Ts
TT
FTP
p
PERT – Příklad…….
• V tabulce hodnot distribuční funkce N(0,1)
nalezneme hodnoty (v Excelu fce: NORM.S.DIST):
F(1,48) = 0,43056 , F(1,97) = 0,47558.
• Hledané hodnoty pravděpodobnosti tedy jsou:
    93056,043056,05,048,15,042  FTP
    02442,047558,05,097,15,035  FTP
P( T ≤ 42) = 93 %
P( T ≤ 35) = 2 %