METODA PERT
Maciej Patan
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
METODA PERT
Maciej Patan
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
1
WPROWADZENIE
➣
PERT (ang. Program Evaluation and Review Technique)
➣
Metoda nale˙zy do sieci o strukturze logicznej zdeterminowanej
➣
Parametry opisuj ˛
ace poszczególne czynno´sci maj ˛
a charakter stochastyczny
➣
Zało˙zenia metody CPM (zbyt odwa˙zne):
•
najwcze´sniejszy mo˙zliwy termin rozpocz ˛ecia czynno´sci
•
najpó´zniejszy dopuszczalny termin rozpocz ˛ecia czynno´sci
•
parametry s ˛
a obliczane na podstawie znajomo´sci czasu trwania danej czynno´sci
➣
W metodzie PERT czas trwania ka˙zdej czynno´sci jest szacowany
➣
Obliczanie oczekiwanego czasu trwania czynno´sci dokonuje si ˛e na podstawie trzech
ocen czasu: optymistycznej, najbardziej prawdopodobnej i pesymistycznej
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
2
ZAŁO ˙
ZENIA
Niech
:
• t
c
- czas optymistyczny
• t
m
- czas najbardziej prawdopodobny
• t
p
- czas pesymistyczny
wtedy warto´s´c oczekiwana
t
0
t
0
=
t
c
+ 4t
m
+ t
p
6
jest to warto´s´c oczekiwana rozkładu beta
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
3
Realizacja metody PERT
1. Definiowanie wszystkich czynno´sci projektu
2. Ustalenie nast ˛epstwa czasowego czynno´sci
3. Oszacowanie czasu trwania ka˙zdej czynno´sci
4. Wyznaczenie ´scia˙zki krytycznej oraz kryteriów jako´sciowych i ilo´sciowych
5. Tworzenie harmonogramu
6. Przeszacowania i poprawki zgodne ze stanem rzeczywistym
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
4
Przykład. 1.
Dla wykonania przedsi ˛ewzi ˛ecia
P
opracowano dwa warianty
techniczne
A
i
B
. Nale˙zy na podstawie analizy sieciowej doko-
na´c wyboru wariantu gwarantuj ˛
acego wi ˛eksz ˛
a szans ˛e dotrzyma-
nia terminu dyrektywnego
t
d
= 48
dni. Charakterystyki czynno´sci
dla obu wariantów podano w poni˙zszych tabelach
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
5
Wariant
A
(i, j)
t
c
t
m
t
p
t
0
(1, 2)
13
14
15
14
(1, 3)
5
10
15
10
(1, 4)
7
10
19
11
(2, 3)
2
2
2
2
(2, 5)
10
10
10
10
(3, 6)
20
21
22
21
(3, 7)
4
16
16
14
(4, 7)
5
20
23
18
(5, 8)
5
8
11
8
(6, 8)
12
12
12
12
(7, 8)
18
18
30
20
Wariant
B
(i, j)
t
c
t
m
t
p
t
0
(1, 2)
17
20
20
19, 5
(1, 3)
14
14
14
14
(1, 4)
1
5
15
6
(2, 5)
2
10
12
9
(3, 6)
17
18
25
19
(3, 7)
15
15
15
15
(4, 7)
2
5
14
6
(5, 8)
18
20
28
21
(6, 8)
14
15
22
16
(7, 8)
18
21
24
21
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
6
Sie´c czynno´sci dla wariantu
A
1
0
0
2
14
14
3
16
16
4
11
12
5
24
42
6
37
38
7
30
30
8
50
50
14(0)
10(6)
11(1)
10(18)
2(0)
21(1)
14(0)
18(1)
8(18)
12(1)
20(0)
•
´scie˙zka krytyczna:
1 − 2 − 3 − 7 − 8
•
szacowany czas trwania przedsi ˛ewzi ˛ecia: 50 dni
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
7
Sie´c czynno´sci dla wariantu
B
1
0
0
2
19.5
20
3
14
14
4
6
23
5
28.5
29
6
33
34
7
29
29
8
50
50
19.5(0.5)
14(0)
6(17)
9(0.5)
19(1)
15(0)
6(17)
21(0.5)
16(1)
21(0)
•
´scie˙zka krytyczna:
1 − 3 − 7 − 8
•
szacowany czas trwania przedsi ˛ewzi ˛ecia: 50 dni
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
8
Wnioski
•
Dla obu wariantów oczekiwany czas trwania czynno´sci wynosi 50 dni, a w
zało˙zeniu termin dyrektywny wynosi
t
d
= 48
dni
•
Parametry opisuj ˛
ace przedsi ˛ewzi ˛ecie maj ˛
a charakter probabilistyczny i czas
trwania czynno´sci mie´sci si ˛e w granicach
[t
p
, t
c
]
•
Problem
:
Jak okre´sli´c, który z wariantów ma wi ˛eksze szanse dotrzy-
mania terminu dyrektywnego?
•
Rozwi ˛
azanie
:
Wprowadzamy poj ˛ecie
wariancji
– okre´slenie niepewno´sci zwi ˛
azanej z dan ˛
a
czynno´sci ˛
a
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
9
•
Interpretacja wariancji
Im wi ˛eksza jest rozpi ˛eto´s´c ocen mi ˛edzy czasem optymistycznym i
pesymistycznym, tym wi ˛eksza jest niepewno´s´c zwi ˛
azana z dan ˛
a czynno´sci ˛
a
•
Definicja wariancji
σ
2
=
t
p
− t
c
6
2
Im wi ˛eksza warto´s´c wariancji, tym wi ˛eksza niepewno´s´c z czasem trwania
danej czynno´sci
Przykład 2.
Obliczy´c niepewno´sci wykonania przedsi ˛ewzi ˛ecia
P
z przykładu 1
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
10
Wariant
A
(i, j)
t
c
t
m
t
p
t
0
σ
2
∗
(1, 2)
13
14
15
14
1
9
1
9
(1, 3)
5
10
15
10
25
9
(1, 4)
7
10
19
11
4
∗
(2, 3)
2
2
2
2
00
(2, 5)
10
10
10
10
0
(3, 6)
20
21
22
21
1
9
∗
(3, 7)
4
16
16
14
44
(4, 7)
5
20
23
18
9
(5, 8)
5
8
11
8
1
(6, 8)
12
12
12
12
0
∗
(7, 8)
18
18
30
20
44
´scie˙zka krytyczna:
1 − 2 − 3 − 7 − 8
wariancja całkowita:
σ
2
=
1
9
+ 0 + 4 + 4 = 8
1
9
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
11
Wariant
B
(i, j)
t
c
t
m
t
p
t
0
σ
2
(1, 2)
17
20
20
19, 5
1
4
∗
(1, 3)
14
14
14
14
00
(1, 4)
1
5
15
6
49
9
(2, 5)
2
10
12
9
25
9
(3, 6)
17
18
25
19
49
36
∗
(3, 7)
15
15
15
15
00
(4, 7)
2
5
14
6
4
(5, 8)
18
20
28
21
25
9
(6, 8)
14
15
22
16
16
9
∗
(7, 8)
18
21
24
21
11
´scie˙zka krytyczna:
1 − 3 − 7 − 8
wariancja całkowita:
σ
2
= 0 + 0 + 1 = 1
Nale˙zy wybra´c wariant
A
, bo stopie ´n niepewno´sci jest wi ˛ekszy i jest szansa na
dotrzymanie terminu dyrektywnego
t
d
= 48
dni
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
12
•
Wybieraj ˛
ac wariant
A
przedsi ˛ewzi ˛ecie mo˙ze zosta´c zrealizowane w
przedziale
41
8
9
− 58
1
9
dnia
•
Wybieraj ˛
ac wariant
B
przedsi ˛ewzi ˛ecie mo˙ze zosta´c zrealizowane w
przedziale
49 − 51
dnia
•
Nasuwaj ˛
a si ˛e kolejne pytania
Jakie jest prawdopodobie ´nstwo realizacji przedsi ˛ewzi ˛ecia do
48
dni?
Jakie jest prawdopodobie ´nstwo realizacji przedsi ˛ewzi ˛ecia do
50
dni?
Jakiemu przedziałowi czasu realizacji przedsi ˛ewzi ˛ecia odpowiada dane
prawdopodobie ´nstwo np.
0, 95
?
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
13
ROZWI ˛
AZANIE
Dystrybuanta rozkładu normalnego jest bardzo pomocna przy okre´slaniu praw-
dopodobie ´nstwa realizacji przedsi ˛ewzi ˛ecia
Definicja dystrybuanty rozkładu normalnego
Φ(x) =
1
√
2π
Z
x
−∞
e
−
x2
2
dx
Interpretacja geometryczna
x
x
F( )
x
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
14
•
Obszar zakre´slony - prawdopodobie ´nstwo zako ´nczenia przedsi ˛ewzi ˛ecia w
terminie do
t
d
P (t
d
¬ t
r
) = Φ(x)
•
Obliczanie prawdopodobie ´nstwa z definicji – bardzo uci ˛
a˙zliwe i
czasochłonne
•
Praktyczne okre´slanie prawdopodobie ´nstwa – tablice rozkładu normalnego
Tablice zawieraj ˛
a warto´sci dystrybuanty dla liczb dodatnich
x 0
(prawa
połówka dystrybuanty)
Jak wi ˛ec policzy´c warto´s´c dystrybuanty dla liczb ujemnych
x < 0
?
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
15
Wiadomo, ˙ze
Φ(inf) =
1
√
2π
Z
∞
−∞
e
−
x2
2
dx = 1
i ˙ze wykres dystrybuanty jest symetryczny. Zatem
Φ(x) = 1 − Φ(−x)
•
W tabelach s ˛
a podawane dla dystrybuanty rozkładu normalnego
N (0, 1)
•
Dane nale˙zy przeskalowa´c tak, aby posiadały warto´s´c ´sredni ˛
a równ ˛
a zero i
odchylenie standardowe równe 1
X =
t
d
− t
r
σ
c
gdzie:
t
d
- czas dyrektywny
t
r
– czas modelowy uko ´nczenia przedsi ˛ewzi ˛ecia
σ
c
– odchylenie standardowe
σ
c
=
p
σ
2
c
X
– czas przeskalowany do
N (0, 1)
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
16
Przykład. 3
a) Prawdopodobie ´nstwo realizacji przedsi ˛ewzi ˛ecia do 48 dni dla wariantu
A
X =
48 − 50
q
8
1
9
= −0, 702
P (t
d
¬ t
r
) = 1 − Φ(x) = 1 − 0, 76 = 0, 24
(24%)
x
0.702
-0.702
F( )
x
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
17
b) Prawdopodobie ´nstwo realizacji przedsi ˛ewzi ˛ecia do 50 dni dla wariantu
A
X =
50 − 50
q
8
1
9
= 0
P (t
d
¬ t
r
) = Φ(x) = 0 = 0, 5
(50%)
x
0
F( )
x
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
18
c) Prawdopodobie ´nstwo realizacji przedsi ˛ewzi ˛ecia do 58 dni dla wariantu
A
X =
58 − 50
q
8
1
9
= 2, 807
P (t
d
¬ t
r
) = 0, 997
(99, 7%)
x
2.807
F( )
x
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
19
d) Obliczy´c przedział czasu realizacji przedsi ˛ewzi ˛ecia odpowiadaj ˛
acy
prawdopodobie ´nstwu 0,95
P (t
d
¬ t
r
) = 0, 95
odczytujemy z tablic warto´s´c
X
X = 1, 64
podstawiamy do wzoru
1, 64 =
t
d
− 50
p
8
1
9
przekształcamy
t
d
= 1, 65 ·
r
8
1
9
+ 50 = 54, 7
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
20
e) Obliczy´c prawdopodobie ´nstwo uko ´nczenia przedsi ˛ewzi ˛ecia do 48 dni dla wariantu
B
X =
48 − 50
√
1
= −2
P (t
d
¬ t
r
) = 1 − Φ(−x) = 1 − 0, 977 = 0, 023
(2, 3%)
Uwaga!
Faktycznie w przykładzie 2 ustalili´smy, ˙ze lepszy oka˙ze si ˛e wariant
A
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
21
Obliczy´c prawdopodobie ´nstwo uko ´nczenia przedsi ˛ewzi ˛ecia do 58 dni dla wariantu
B
X =
58 − 50
√
1
= 8
P (t
d
¬ t
r
) ≈ 1
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne
Programowanie sieciowe. Metoda PERT
22
Obliczy´c przedział czasu realizacji przedsi ˛ewzi ˛ecia odpowiadaj ˛
acy prawdopodobie ´nstwu
0,95
P (t
d
¬ t
r
) = 0, 95
odczytujemy z tablic warto´s´c
X
X = 1, 65
podstawiamy do wzoru
1, 65 =
t
d
− 50
√
1
przekształcamy
t
d
= 1, 65 + 50 = 51, 65
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski