Составители:
Рубрика:
44
3. ÇÀÄÀ×È ÎÁ ÎÏÒÈÌÀËÜÍÛÕ ÐÀÑÑÒÎßÍÈßÕ
 ïðåäûäóùåé çàäà÷å ìû ñ÷èòàëè, ÷òî äëèíû âñåõ äóã ãðàôà G(V,U)
áûëè ðàâíû, íàïðèìåð L(u)=1. Ðàññìîòðèì òåïåðü ñëó÷àé, êîãäà êàæäîé
äóãå u ïîñòàâëåíî â ñîîòâåòñòâèå ÷èñëî L(u)>0, íàçûâàåìîå äëèíîé äóãè.
 çàâèñèìîñòè îò êîíêðåòíîãî ïðèëîæåíèÿ, ýòî ÷èñëî ìîæåò áûòü ìå-
ðîé ôèçè÷åñêîãî ðàññòîÿíèÿ, âðåìåíè, ñòîèìîñòè èëè äðóãîãî âàæíîãî
ïàðàìåòðà.
Ðàññìîòðèì îáùóþ ïîñòàíîâêó çàäà÷è îá îïòèìàëüíûõ ðàññòîÿíè-
ÿõ íà ïðèìåðå çàäà÷è ñåòåâîãî ïëàíèðîâàíèÿ è óïðàâëåíèÿ (ÑÏÓ) îïå-
ðàöèÿìè, íàçûâàåìûõ òàêæå çàäà÷àìè òèïà ÏÅÐÒ ( PERT).
Îðãðàô ÿâëÿåòñÿ åñòåñòâåííûì ñðåäñòâîì äëÿ îïèñàíèÿ è àíàëèçà
ñëîæíûõ ïðîåêòîâ, òðåáóþùèõ âûïîëíåíèÿ áîëüøîãî ÷èñëà âçàèìîñâÿ-
çàííûõ îïåðàöèé (ðàáîò). Ïðîåêòîì ìîæåò áûòü, íàïðèìåð, ïðîöåññ
ðàçðàáîòêè, ïîñòðîåíèÿ è ïðîâåðêè íåêîòîðîãî èçäåëèÿ, â òîì ÷èñëå è ñ
èñïîëüçîâàíèåì ÑÀÏÐ (ñèñòåìû àâòîìàòèçèðîâàííîãî ïðîåêòèðîâàíèÿ)
èëè ïðîöåññ ïðîåêòèðîâàíèÿ è ñòðîèòåëüñòâà çäàíèÿ, âêëþ÷àÿ ýòàïû
ïîëó÷åíèÿ è ïîäãîòîâêè ìåñòà ñòðîèòåëüñòâà.  îáùåì ñëó÷àå ïðåäïî-
ëîæèì, ÷òî ðàññìàòðèâàåòñÿ íåêîòîðûé ïðîåêò P è ìíîæåñòâî âñåõ îïå-
ðàöèé, ñâÿçàííûõ ñ âûïîëíåíèåì ïðîåêòà, ìîæíî ðàçäåëèòü íà îòäåëü-
íûå íåïåðåñåêàþùèåñÿ îïåðàöèè P{a
1
,a
2
, ... ,a
n
}.
Õîòÿ íåêîòîðûå îïåðàöèè ìîãóò áûòü íåçàâèñèìû äðóã îò äðóãà, â
îáùåì ñëó÷àå ìåæäó íèìè ñóùåñòâóåò çàâèñèìîñòü ïî âðåìåíè, íàïðè-
ìåð îïåðàöèÿ a
i
äîëæíà çàêîí÷èòüñÿ, ÷òîáû ìîãëà íà÷àòüñÿ îïåðàöèÿ a
j
.
Åñëè çàäàíû âñå òàêèå çàâèñèìîñòè, òî èõ óäîáíî ïðåäñòàâèòü â âèäå
îðãðàôà, êàê ïîêàçàíî íà ðèñ. 2.6. Êàæäàÿ äóãà ãðàôà ñîîòâåòñòâóåò
îäíîé îïåðàöèè, à êàæäàÿ âåðøèíà, íàçûâàåìàÿ ñîáûòèåì, ñîîòâåòñòâóåò
íåêîòîðîìó ìîìåíòó âðåìåíè.
Äëÿ âûïîëíåíèÿ îïåðàöèè à
i
âûäåëÿåòñÿ íåêîòîðîå âðåìÿ t(a
i
), ÷òî
îòðàæåíî ÷èñëàìè íà äóãàõ ãðàôà. Äëèíà (ò. å. ñóììà âðåìåííûõ èí-
òåðâàëîâ) ëþáîãî ïóòè èç v
1
â v
i
ñîîòâåòñòâóåò íèæíåé ãðàíèöå âðåìå-
íè, èçìåðÿåìîãî îò íà÷àëà ïðîåêòà äî íàñòóïëåíèÿ ñîáûòèÿ v
i
, ïîñëå
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
