Составители:
Рубрика:
45
êîòîðîãî ìîãóò áûòü íà÷àòû îïåðàöèè, èìåþùèå v
i
â êà÷åñòâå íà÷àëü-
íîé âåðøèíû.
Ïðè ðàñ÷åòàõ êàæäîé âåðøèíå óäîáíî ïîñòàâèòü â ñîîòâåòñòâèå ÷èñ-
ëî (âðåìÿ) ñëåäóþùèì îáðàçîì:
Ò(v
1
)=0, T(v
i
)=max{t(µ)} (i≠1),
ãäå t(µ) îçíà÷àåò äëèíó ïóòè è ìàêñèìóì îïðåäåëÿåòñÿ ïî âñåì ïóòÿì èç
v
1
â v
i
.
Äëèíîé ïóòè µ íàçûâàåòñÿ ñóììà äëèí äóã, âõîäÿùèõ â µ:
() ()
u
LLu
∈µ
µ=
∑
.
Äëèííåéøèé ïî âðåìåíè ïóòü îò íà÷àëüíîãî ñîáûòèÿ v
1
äî êîíå÷-
íîãî ñîáûòèÿ v
n
íàçûâàåòñÿ êðèòè÷åñêèì ïóòåì, êîòîðûé ìîæåò áûòü
íå åäèíñòâåííûì, íàïðèìåð äëÿ ãðàôà íà ðèñ. 3.1 åñòü äâà êðèòè÷åñêèõ
ïóòè (ïî âåðøèíàì ãðàôà):
1 124568 1
(, , , , , ), ( )13,
vvv vvv L
µ= µ =
212468 2
(,,,,),()13.
vvv vv L
µ= µ =
Äëèíà êðèòè÷åñêîãî ïóòè ñîîòâåòñòâóåò êðàò÷àéøåìó âðåìåíè, çà
êîòîðîå ìîãóò áûòü âûïîëíåíû âñå îïåðàöèè ïðîåêòà, à çíà÷èò, è âåñü
ïðîåêò â öåëîì.
Çàìåòèì, ÷òî ïî ñâîåé ïðèðîäå ãðàô, ïðåäñòàâëÿþùèé ïðîöåññ âû-
ïîëíåíèÿ îïåðàöèé, ÿâëÿåòñÿ àöèêëè÷åñêèì. Íàëè÷èå öèêëà ñîçäàëî áû
íåâîçìîæíóþ ñèòóàöèþ, êîãäà íè îäíà èç îïåðàöèé öèêëà íå ìîãëà áû
íà÷àòüñÿ ïåðâîé, ïîñêîëüêó ëþáàÿ èç íèõ çàâèñèò îò äðóãîé îïåðàöèè.
Ðèñ. 3.1. Ãðàô âûïîëíåíèÿ îïåðàöèé ïðîåêòà
v
(0)
v
(3) v
#
(8)
v
$
(10)
v
&
(13)
v
%
(8)
v
!
(4)
v
"
(5)
4
5
2
3
2
3
2
423
3
4
1
Страницы
- « первая
- ‹ предыдущая
- …
- 43
- 44
- 45
- 46
- 47
- …
- следующая ›
- последняя »
