0000096

Metodo CPM sprowadza się głównie do wyznaczania ścieżek krytycznych 1 planowanie realizacji czynności leżęcych no tych ścieżkach. Łatwo zauważyć z definicji, że zdarzenia lożęee na dowolnej ścieżce krytycznej naję zerowe wartości luzów czaeo -wych L(x).    _#

W sieci przedstawionej na rys.10.13 istnieje Jedna ścieżka krytyczna określona cięgien zdarzeń |l.2,3.5,7,8 ] .

w celu unożllwlenla odpowiedniej kontroli 1 operatywnego kierowania przebiegłaś realizacji przedsięwzięcia, w metodzie PERT określa się dla czynności następujęce wielkości, zwane zapasani :

1/ zopee całkowity

3/ zapai niezależny

2N(x,y) - MX {O. (t (y) - T(x) - T(x.y))}

Zapoo całkowity Jeet to rezerwa czaou dla czynności <x,y> . której wyczerpanie nie opóźni najpóźniejszego terminu zdarzenia y. a tym samym realizacji całego przedsięwzięcia. Zapas swobodny Jeet to rezerwa czaou dla czynności <x.y>. której zużycie nie opóźni najwcześniejszych terminów rozpoczęcia czynności po niej następujących przy założeniu, źe rozpoczęcie czynności <x,y> naotępl w terminie najwcześniejszym. Zapas niezależny ma podobną interpretację Jak swobodny z tym, że rozpoczęcie czynności <x.y> nastąpi w terminie najpóźniejszym. Dla czynności leżą -cych na ścieżkach krytycznych wszystkie te zaposy są zerowe.

Bardziej ezczogółowe informacje na temat metod analizy sie-ciowej można znaleźć, między innymi, w pracach [46], [12] , [20] ,

M.

Programy komputerowe w języku ALGOL 1204 dla metod CPM i PERT są zamieszczone w [26] .

10.5. Problom komiwojażera

Zodenle komiwojażera jest sformułowane naotępujęco: Oeot n ♦ 1 miast oraz macierz odległości między tymi miastami L*

■ l^łlj] (n+1 )»(n*l )* ^N1® ^każd® ^pl,ro ■^{lMt J#łt} Połączona drogą bezpośrednią - dana jest binarna macierz przejść

^P> [f>u|fn.l),(n.l>    *^d*‘* **13 ■ ¹ -t.dy 1 tylko «.dy. gdy

istnieje bezpośrednio droga z miasta ido miasta j. Mlaste po -numerowane są przez 1 ■ 0,1.....n.

Komiwojażer, wyjoźdżejąc z miasta nr O powinien odwiedzić każde miasto dokładnie jeden raz i powrócić do miasta nr O, tak aby sumaryczna ilość przejechanych przezeń kilometrów była minimalna. Zadanie komiwojażera polega zatem na wyznaczeniu najkrót -ezęj, cyklicznej drogi Hoailtona w sieci 5 ■ <G,(J, {l)> . Za -danie to może nie mleć rozwiązanie (gdy w grafie G nie me cyklicznej drogi Hamiltona).

Niekiedy zadanie komiwojażera Jest formułowane przy założeniu,

*o graf G Jaet pełnym grafem Berge'a bez pętli. Wtedy zedenie ■a zawsze rozwiązanie.

191