Hubert Skrzypulec Zabrze 05.12.2008r.
ZiIP 3.2
POLITECHNIKA ŚL
SKA W GLIWICACH
WYDZIAA
ORGANIZACJI I ZARZ
DZANIA
Katedra Informatyki i Ekonometrii
BADANIA OPERACYJNE
Projekt nr 5
Programowanie sieciowe
Metoda CPM
Treść zadania
W domu państwa Kowalskich zepsuł się telewizor. Jako, że jest on jeszcze na gwarancji
telewizor został zaniesiony do autoryzowanego serwisu. W trakcie sprawdzania i
eliminowania usterek serwisant musi wykonać szereg zabiegów, które muszą być
przeprowadzane w określonej kolejności. Spis czynności, wraz z uwzględnieniem kolejności
oraz czasu ich trwania przedstawia tabela 1. Na jej podstawie należy ustalić czas realizacji
naprawy, narysować diagram sieciowy, wyznaczyć ścieżkę krytyczną oraz narysować wykres
Gantta.
Tabela 1
Symbol Opis czynności Czynności Czas trwania w
poprzedzające minutach
A Przeniesienie telewizora na stanowisko naprawcze - 4
B Demontaż telewizora A 5
C Sprawdzenie zużycia kineskopu B 10
D Sprawdzenie zużycia dekodera koloru B 14
E Sprawdzenie zużycia detektora B 8
F Sprawdzenie zużycia układu sterowania B 6
G Naprawa i konserwacja kineskopu C 8
H Naprawa i konserwacja dekodera koloru D 10
I Naprawa i konserwacja detektora E 12
J Naprawa i konserwacja układu sterowania F 9
K Montaż telewizora G, H, I, J 7
L Oczekiwanie na transport K 2
M Przeniesienie do magazynu L 3
Na podstawie przedstawionych w tabeli czynności tworzę diagram sieciowy.
4
G
C
D H
5
K L M
A B
E
1 2 3 8 9 10 11
I
6
F
J
7
Strona 2 z 6
Tabela 2 przedstawia czasy trwania poszczególnych czynności
Tabela 2
Czynności tij
1  2 4
2  3 5
3  4 10
3  5 14
3  6 8
3  7 6
4  8 8
5  8 10
6  8 12
7  8 9
8  9 7
9  10 2
10  11 3
Zadanie rozwiązuję metodą CPM (Critical Path Method)  ścieżki krytycznej. Ścieżka
krytyczna jest to droga, której czas przejścia jest najdłuższy. Czynności i zdarzenia leżące na
niej mają zerowe zapasy czasu.
Oznaczenia
i tij j
wi pi wj pj
 czas trwania czynności z i do j
 najwcześniejszy możliwy moment rozpoczęcia czynności tij
 najpóz
niejszy dopuszczalny moment rozpoczęcia czynności tij
 najwcześniejszy możliwy moment zakończenia czynności tij
 najpóz
niejszy dopuszczalny moment zakończenia czynności tij
 całkowity zapas czasowy
 swobodny zapas czasowy
 warunkowy zapas czasowy
Strona 3 z 6
Zależności
Rozwiązanie
Wyrysowuję siatkę czynności, oszacowuję zapasy czasowe, czas trwania naprawy wraz z
wyznaczeniem ścieżki krytycznej.
4
19 25
6
10 8
5
14
23 23
10
0
1 2 3
4 5 7 3
8 9 2 10 11
0 4 4 9 9
0
40 40 42 42 45 45
33 33
8
12
0 0
0
0 0 0
0
6
17 21
4
6 9
7
15 24
9
Czas wykonania naprawy to 45 minut. Ścieżka krytyczna jest sekwencją czynności:
1 2 3 5 8 9 10 11
Dla takiej sekwencji czynności zapas czasowy wynosi 0. Zgodnie z praktyką
rozwiązywania zagadnień sieciowych jest to nasze rozwiązanie optymalne.
Przygotowuję dane do wyznaczenia wykresu Gantta. Wszystkie oznaczenia zostały
wyjaśnione na stronie trzeciej.
Strona 4 z 6
Tabela 3
Czynności
1  2 4 0 4 0 4 0 4 0 4 0 0 0
2  3 5 4 9 4 9 4 9 4 9 0 0 0
3  4 10 9 19 9 25 9 25 15 19 6 0 6
3  5 14 9 23 9 23 9 23 9 23 0 0 0
3  6 8 9 17 9 21 9 21 13 17 4 0 4
3  7 6 9 15 9 24 9 24 18 15 9 0 9
4  8 8 19 33 25 33 19 33 25 27 6 6 6
5  8 10 23 33 23 33 23 33 23 33 0 0 0
6  8 12 17 33 21 33 17 33 21 29 4 4 0
7  8 9 15 33 24 33 15 33 24 24 9 9 0
8  9 7 33 40 33 40 33 40 33 40 0 0 0
9  10 2 40 42 40 42 40 42 40 42 0 0 0
10  11 3 42 45 42 45 42 45 42 45 0 0 0
Rysunek 1 Wykres Gantta
Na wykresie uzyskaliśmy dokładnie taki sam rezultat jak w przypadku rozwiązania
metodą sieci czynności. Ścieżkę krytyczną tworzy sekwencja czynności: 1 2
3 5 8 9 10 11. Czas tego przedsięwzięcia wynosi 45 minut.
Strona 5 z 6
Tabela 4 Rozwiązanie tego zagadnienia za pomocą dodatku Solver w arkuszu kalkulacyjnym Microsoft Excel
Microsoft Excel 12.0 Raport wyników
Komórka celu (Min)
Komórka Nazwa Wartość początkowa Wartość końcowa
$B$12 f celu 0 45
Komórki decyzyjne
Komórka Nazwa Wartość początkowa Wartość końcowa
$B$1 t1 0 0
$B$2 t2 0 4
$B$3 t3 0 9
$B$4 t4 0 25
$B$5 t5 0 23
$B$6 t6 0 21
$B$7 t7 0 15
$B$8 t8 0 33
$B$9 t9 0 40
$B$10 t10 0 42
$B$11 t11 0 45
Warunki ograniczające
Komórka Nazwa Wartość komórki formuła Status Luz
$B$14 t2-t1 4 $B$14>=4 Wiążące 0
$B$15 t3-t2 5 $B$15>=5 Wiążące 0
$B$16 t4-t3 16 $B$16>=10 Niewiążące 6
$B$17 t5-t3 14 $B$17>=14 Wiążące 0
$B$18 t6-t3 12 $B$18>=8 Niewiążące 4
$B$19 t7-t3 6 $B$19>=6 Wiążące 0
$B$20 t8-t4 8 $B$20>=8 Wiążące 0
$B$21 t8-t5 10 $B$21>=10 Wiążące 0
$B$22 t8-t6 12 $B$22>=12 Wiążące 0
$B$23 t8-t7 18 $B$23>=9 Niewiążące 9
$B$24 t9-t8 7 $B$24>=7 Wiążące 0
$B$25 t10-t9 2 $B$25>=2 Wiążące 0
$B$26 t11-t10 3 $B$26>=3 Wiążące 0
$B$1 t1 0 $B$1>=0 Wiążące 0
$B$2 t2 4 $B$2>=0 Niewiążące 4
$B$3 t3 9 $B$3>=0 Niewiążące 9
$B$4 t4 25 $B$4>=0 Niewiążące 25
$B$5 t5 23 $B$5>=0 Niewiążące 23
$B$6 t6 21 $B$6>=0 Niewiążące 21
$B$7 t7 15 $B$7>=0 Niewiążące 15
$B$8 t8 33 $B$8>=0 Niewiążące 33
$B$9 t9 40 $B$9>=0 Niewiążące 40
$B$10 t10 42 $B$10>=0 Niewiążące 42
$B$11 t11 45 $B$11>=0 Niewiążące 45
Strona 6 z 6