Podstawowe pojęcia Metoda CPM Metoda PERT
Analiza złożonych przedsięwzięć
wieloczynnościowych
Adam Kucharski
[e-mail]
Katedra Badań Operacyjnych
Wydział Ekonomiczno-Socjologiczny
pok. T413, 635 51 84
Podstawowe pojęcia Metoda CPM Metoda PERT
Przedsięwzięcie wieloczynnościowe
" Każde złożone przedsięwzięcie zostaje przedstawione za
pomocą skończonej liczby wzajemnie ze sobą powiązanych
pojedynczych czynności.
Podstawowe pojęcia Metoda CPM Metoda PERT
Przedsięwzięcie wieloczynnościowe
" Każde złożone przedsięwzięcie zostaje przedstawione za
pomocą skończonej liczby wzajemnie ze sobą powiązanych
pojedynczych czynności.
" Przedsięwzięcie zawiera się w skończonym przedziale czasu i
posiada wyróżniony początek i koniec.
Podstawowe pojęcia Metoda CPM Metoda PERT
Sposób przedstawiania
Analizy przedsięwzięć wieloczynnościowych dokonuje się
wykorzystując pojęcia z teorii grafów.
Symbol Programowanie sieciowe Teoria grafów
- Czynność A
uk
" Zdarzenie Wierzchołek
Podstawowe pojęcia Metoda CPM Metoda PERT
Czynność a zdarzenie
Czynność jest procesem trwającym w czasie, ale pociąga za sobą
również koszty związane z realizacją.
Podstawowe pojęcia Metoda CPM Metoda PERT
Czynność a zdarzenie
Czynność jest procesem trwającym w czasie, ale pociąga za sobą
również koszty związane z realizacją.
Zdarzenie określa rozpoczęcie lub zakończenie jednej lub wielu
czynności. Mówimy, że zdarzenie zaszło, jeśli zakończone zostały
wszystkie czynności, dla których jest ono zdarzeniem końcowym.
Podstawowe pojęcia Metoda CPM Metoda PERT
Czynność a zdarzenie
Czynność jest procesem trwającym w czasie, ale pociąga za sobą
również koszty związane z realizacją.
Zdarzenie określa rozpoczęcie lub zakończenie jednej lub wielu
czynności. Mówimy, że zdarzenie zaszło, jeśli zakończone zostały
wszystkie czynności, dla których jest ono zdarzeniem końcowym.
W programowaniu sieciowym często występują tzw. czynności
pozorne (oznaczane linią przerywaną), które nie wymagają
nakładów ani środków. Wprowadza się je w sytuacji, kiedy kilka
czynności wykonywanych równolegle poprzedza jedną czynność.
Podstawowe pojęcia Metoda CPM Metoda PERT
Rodzaje powiązań między czynnościami
1. Szeregowe  dana czynność (grupa czynności) może być
wykonana dopiero po zakończeniu pewnej czynności (grupy
czynności) poprzedzającej.
Podstawowe pojęcia Metoda CPM Metoda PERT
Rodzaje powiązań między czynnościami
1. Szeregowe  dana czynność (grupa czynności) może być
wykonana dopiero po zakończeniu pewnej czynności (grupy
czynności) poprzedzającej.
2. Równoległe  czynności wykonywane są niezależnie od siebie
w tym samym czasie.
Podstawowe pojęcia Metoda CPM Metoda PERT
Rodzaje powiązań między czynnościami
1. Szeregowe  dana czynność (grupa czynności) może być
wykonana dopiero po zakończeniu pewnej czynności (grupy
czynności) poprzedzającej.
2. Równoległe  czynności wykonywane są niezależnie od siebie
w tym samym czasie.
3. Przykład:
2
1 4 5
3
Podstawowe pojęcia Metoda CPM Metoda PERT
Cele analizy:
1. Zestawienie czynności oraz ich wzajemnych powiązań i
ustalenie programu działania.
Podstawowe pojęcia Metoda CPM Metoda PERT
Cele analizy:
1. Zestawienie czynności oraz ich wzajemnych powiązań i
ustalenie programu działania.
2. Określenie terminów rozpoczęcia i zakończenia
poszczególnych czynności.
Podstawowe pojęcia Metoda CPM Metoda PERT
Cele analizy:
1. Zestawienie czynności oraz ich wzajemnych powiązań i
ustalenie programu działania.
2. Określenie terminów rozpoczęcia i zakończenia
poszczególnych czynności.
3. Analiza tolerancji czasu rozpoczynania i kończenia czynności.
Podstawowe pojęcia Metoda CPM Metoda PERT
Cele analizy:
1. Zestawienie czynności oraz ich wzajemnych powiązań i
ustalenie programu działania.
2. Określenie terminów rozpoczęcia i zakończenia
poszczególnych czynności.
3. Analiza tolerancji czasu rozpoczynania i kończenia czynności.
4. Określenie czynności krytycznych ( wąskich gardeł ).
Podstawowe pojęcia Metoda CPM Metoda PERT
Cele analizy:
1. Zestawienie czynności oraz ich wzajemnych powiązań i
ustalenie programu działania.
2. Określenie terminów rozpoczęcia i zakończenia
poszczególnych czynności.
3. Analiza tolerancji czasu rozpoczynania i kończenia czynności.
4. Określenie czynności krytycznych ( wąskich gardeł ).
5. Racjonalny rozdział ograniczonych środków.
Podstawowe pojęcia Metoda CPM Metoda PERT
Cele analizy:
1. Zestawienie czynności oraz ich wzajemnych powiązań i
ustalenie programu działania.
2. Określenie terminów rozpoczęcia i zakończenia
poszczególnych czynności.
3. Analiza tolerancji czasu rozpoczynania i kończenia czynności.
4. Określenie czynności krytycznych ( wąskich gardeł ).
5. Racjonalny rozdział ograniczonych środków.
6. Określenie prawdopodobieństwa dotrzymania terminu
końcowego całego przedsięwzięcia.
Podstawowe pojęcia Metoda CPM Metoda PERT
Cele analizy:
1. Zestawienie czynności oraz ich wzajemnych powiązań i
ustalenie programu działania.
2. Określenie terminów rozpoczęcia i zakończenia
poszczególnych czynności.
3. Analiza tolerancji czasu rozpoczynania i kończenia czynności.
4. Określenie czynności krytycznych ( wąskich gardeł ).
5. Racjonalny rozdział ograniczonych środków.
6. Określenie prawdopodobieństwa dotrzymania terminu
końcowego całego przedsięwzięcia.
7. Ocena alternatywnych planów realizacji przedsięwzięcia.
Podstawowe pojęcia Metoda CPM Metoda PERT
Cele analizy:
1. Zestawienie czynności oraz ich wzajemnych powiązań i
ustalenie programu działania.
2. Określenie terminów rozpoczęcia i zakończenia
poszczególnych czynności.
3. Analiza tolerancji czasu rozpoczynania i kończenia czynności.
4. Określenie czynności krytycznych ( wąskich gardeł ).
5. Racjonalny rozdział ograniczonych środków.
6. Określenie prawdopodobieństwa dotrzymania terminu
końcowego całego przedsięwzięcia.
7. Ocena alternatywnych planów realizacji przedsięwzięcia.
8. Bieżąca kontrola realizacji przedsięwzięcia.
Podstawowe pojęcia Metoda CPM Metoda PERT
Analiza deterministyczna
W metodzie CPM (Critical Path Method) zakłada się, że czasy
trwania poszczególnych czynności są dokładnie znane
(deterministyczne). Oznaczmy:
n  liczba zdarzeń w sieci;
(i,j)  czynność o zdarzeniu początkowym i oraz końcowym j;
tij - czas trwania czynności (i,j);
TD  termin dyrektywny zakończenia przedsięwzięcia.
Podstawowe pojęcia Metoda CPM Metoda PERT
Terminy zdarzeń
j
i
tij
tj0 tj1
ti0 ti1
ti0  najwcześniejszy możliwy termin zajścia zdarzenia i;
ti1  najpóz
niejszy możliwy termin zajścia zdarzenia i;
tj0  najwcześniejszy możliwy termin zajścia zdarzenia j;
tj1  najpóz
niejszy możliwy termin zajścia zdarzenia j;
Podstawowe pojęcia Metoda CPM Metoda PERT
Wybrane charakterystyki wyznaczane dla czynności
NWPij = ti0  najwcześniejszy możliwy termin rozpoczęcia
czynności (i,j);
NPKij = ti1  najpóz
niejszy dopuszczalny termin zakończenia
czynności (i,j);
NPPij = NPKij - tij  najpóz
niejszy dopuszczalny termin
rozpoczęcia czynności (i,j);
NWKij = NWPij + tij  najwcześniejszy dopuszczalny termin
zakończenia czynności (i,j);
ZCij = NPKij - NWPij - tij  zapas całkowity dla czynności (i,j).
Rezerwa czasu, która może być zużyta na wykonanie danej
czynności bez wpływu na termin końcowy.
Podstawowe pojęcia Metoda CPM Metoda PERT
Etapy analizy
1. Wyznaczanie najwcześniejszego terminu dla zdarzenia i (ti0):
0
dla pierwszego zdarzenia t1 = 0
dla pozostałych:

tj0 = max ti0 + tij j = 2, 3, . . . , n
i:iPodstawowe pojęcia Metoda CPM Metoda PERT
Etapy analizy
1. Wyznaczanie najwcześniejszego terminu dla zdarzenia i (ti0):
0
dla pierwszego zdarzenia t1 = 0
dla pozostałych:

tj0 = max ti0 + tij j = 2, 3, . . . , n
i:i2. Wyznaczanie najpóz
niejszego terminu dla zdarzenia i (ti1):
1
dla ostatniego zdarzenia najczęściej tn = TD
dla pozostałych:

ti1 = min tj1 - tij j = n - 1, n - 2, . . . , 1
i:iPodstawowe pojęcia Metoda CPM Metoda PERT
Etapy analizy
1. Wyznaczanie najwcześniejszego terminu dla zdarzenia i (ti0):
0
dla pierwszego zdarzenia t1 = 0
dla pozostałych:

tj0 = max ti0 + tij j = 2, 3, . . . , n
i:i2. Wyznaczanie najpóz
niejszego terminu dla zdarzenia i (ti1):
1
dla ostatniego zdarzenia najczęściej tn = TD
dla pozostałych:

ti1 = min tj1 - tij j = n - 1, n - 2, . . . , 1
i:i3. Wyznaczanie luzów czasowych: Li = ti1 - ti0
Podstawowe pojęcia Metoda CPM Metoda PERT
Etapy analizy
1. Wyznaczanie najwcześniejszego terminu dla zdarzenia i (ti0):
0
dla pierwszego zdarzenia t1 = 0
dla pozostałych:

tj0 = max ti0 + tij j = 2, 3, . . . , n
i:i2. Wyznaczanie najpóz
niejszego terminu dla zdarzenia i (ti1):
1
dla ostatniego zdarzenia najczęściej tn = TD
dla pozostałych:

ti1 = min tj1 - tij j = n - 1, n - 2, . . . , 1
i:i3. Wyznaczanie luzów czasowych: Li = ti1 - ti0
4. Wyznaczanie zapasów czasu dla czynności.
Podstawowe pojęcia Metoda CPM Metoda PERT
Tworzenie witryny internetowej
Czynność Opis czynności Czynności Czas trwania
bezp. poprz. [h]
A Wstępny projekt  1
B Opracowanie układu strony A 2
C Opracowanie elem. graf. B 5
D Opracowanie stron tematycznych B 8
E Projektowanie bazy danych B 2
F Tworzenie layoutu końcowego C 2
G Wprowadzenie danych do bazy E 3
H Uruchomienie i testowanie D, F, G 8
Podstawowe pojęcia Metoda CPM Metoda PERT
Sieć powiązań między czynnościami
4
C
F
A B D H
1 2 3 5 7
E
G
6
Podstawowe pojęcia Metoda CPM Metoda PERT
Harmonogram przedsięwzięcia
Czynność tij NWPij NPPij NWKij NPKij ZCij Czynność
krytyczna
A 1 0 0 1 1 0 TAK
B 2 1 1 3 3 0 TAK
C 5 3 4 8 9 1 nie
D 8 3 3 11 11 0 TAK
E 2 3 6 5 8 3 nie
F 2 8 9 10 11 1 nie
G 3 5 8 8 11 3 nie
H 8 11 11 19 19 0 TAK
TD=19 h
Podstawowe pojęcia Metoda CPM Metoda PERT
Ścieżka krytyczna
4
C
F
A B D H
1 2 3 5 7
E
G
6
Podstawowe pojęcia Metoda CPM Metoda PERT
Wykres Gantta
Program WinStorm
Podstawowe pojęcia Metoda CPM Metoda PERT
Analiza stochastyczna
W metodzie PERT (Program Evaluation and Review Technique)
zakłada się, że czasy trwania czynności są zmiennymi losowymi.
a
tij  optymistyczny czas trwania czynności (i,j);
b
tij  pesymistyczny czas trwania czynności (i,j);
m
tij  najbardziej prawdopodobny czas trwania czynności (i,j).
Podstawowe pojęcia Metoda CPM Metoda PERT
Analiza stochastyczna c.d.
Oczekiwany czas trwania czynności (i,j):
a m b
tij + 4tij + tij
mij =
6
Wariancja czasu trwania czynności (i,j):
2
b a
tij - tij
2
sij =
6
Podstawowe pojęcia Metoda CPM Metoda PERT
Cechy analizy w metodzie PERT:
1. analizę czasową sieci wykonuje się analogicznie jak w
metodzie CPM, wykorzystując wartości oczekiwane mij
zamiast ustalonych czasów trwania czynności (tij);
Podstawowe pojęcia Metoda CPM Metoda PERT
Cechy analizy w metodzie PERT:
1. analizę czasową sieci wykonuje się analogicznie jak w
metodzie CPM, wykorzystując wartości oczekiwane mij
zamiast ustalonych czasów trwania czynności (tij);
2. każdy termin i zapas jest zmienną losową;
Podstawowe pojęcia Metoda CPM Metoda PERT
Cechy analizy w metodzie PERT:
1. analizę czasową sieci wykonuje się analogicznie jak w
metodzie CPM, wykorzystując wartości oczekiwane mij
zamiast ustalonych czasów trwania czynności (tij);
2. każdy termin i zapas jest zmienną losową;
3. szansa dotrzymania terminu dyrektywnego (TD) na poziomie
0
terminu najwcześniejszego dla ostatniego zdarzenia (tn)
wynosi 50%.
Podstawowe pojęcia Metoda CPM Metoda PERT
Prawdopodobieństwo dotrzymania dowolnego TD
Termin realizacji przedsięwzięcia (tn) w metodzie PERT ma
rozkład asymptotycznie normalny z wartością oczekiwaną m(tn)
0
równą wartości oczekiwanej terminu najwcześniejszego (tn) oraz
wariancją s2(tn) równą sumie wariancji czasów trwania czynności
krytycznych.
Prawdopodobieństwo dotrzymania dowolnego TD wyznacza się na
podstawie tablic rozkładu normalnego standaryzowanego (N(0, 1)):

TD - m(tn)
P (tn < TD) = Ć
s(tn)
P (tn < TD) 0,3  harmonogram ryzykanta;
P (tn < TD) 0,6  harmonogram asekuranta;
Podstawowe pojęcia Metoda CPM Metoda PERT
Tworzenie witryny internetowej
(przypadek stochastyczny)
Czynności
a m b
Czynność bezp. tij tij tij
poprz.
A  1 2 3
B A 1 2 6
C B 2 5 14
D B 8 9 10
E B 1 3 5
F C 3 4 5
G E 2 4 6
H D, F, G 5 8 11
Podstawowe pojęcia Metoda CPM Metoda PERT
Harmonogram przedsięwzięcia
2
Czynność mij sij NWPij NPPij NWKij NPKij ZCij Czynność
krytyczna
A 2,0 0,11 0,0 0,0 2,0 2,0 0 TAK
B 2,5 0,69 2,0 2,0 4,5 4,5 0 TAK
C 6,0 4,00 4,5 4,5 10,5 10,5 0 TAK
D 9,0 0,11 4,5 5,5 13,5 14,5 1 nie
E 3,0 0,44 4,5 7,5 7,5 10,5 3 nie
F 4,0 0,11 10,5 10,5 14,5 14,5 0 TAK
G 4,0 0,44 7,5 10,5 11,5 14,5 3 nie
H 8,0 1,00 14,5 14,5 22,5 22,5 0 TAK
m(t7) = 22,5
s2(t7) = 0,11 + 0,69 + 4 + 0,11 + 1 = 5,91
s(t7) = 2,43
Podstawowe pojęcia Metoda CPM Metoda PERT
Ścieżka krytyczna
4
C
F
A B D H
1 2 3 5 7
E
G
6
Podstawowe pojęcia Metoda CPM Metoda PERT
Wykres Gantta
Program WinStorm
Podstawowe pojęcia Metoda CPM Metoda PERT
Prawdopodobieństwo dotrzymania dowolnego TD

TD - m(t7) TD - 22,5
P (t7 < TD) = Ć = Ć
s(t7) 2,43
Podstawowe pojęcia Metoda CPM Metoda PERT
Prawdopodobieństwo dotrzymania dowolnego TD

TD - m(t7) TD - 22,5
P (t7 < TD) = Ć = Ć
s(t7) 2,43
Harmonogram ryzykanta:

21 - 22,5
P (t7 < 21) = Ć = 0,27
2,43
Podstawowe pojęcia Metoda CPM Metoda PERT
Prawdopodobieństwo dotrzymania dowolnego TD

TD - m(t7) TD - 22,5
P (t7 < TD) = Ć = Ć
s(t7) 2,43
Harmonogram ryzykanta:

21 - 22,5
P (t7 < 21) = Ć = 0,27
2,43
Harmonogram asekuranta:

23,5 - 22,5
P (t7 < 23,5) = Ć = 0,66
2,43