Àëãîðèòì ðåàëèçàöèè ñåòåâîé ñòîõàñòè÷åñêîé ìîäåëè ðåñóðñíîãî ìåãàïðîåêòà Í.È. Ïëÿñêèíà 1 Èíñòèòóò ýêîíîìèêè è îðãàíèçàöèè ïðîìûøëåííîãî ïðîèçâîäñòâà ÑÎ ÐÀÍ, 2 Íîâîñèáèðñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò, Íîâîñèáèðñê, Ðîññèÿ. pliaskina@hotmail.com Àííîòàöèÿ  ñòàòüå ïðåäëîæåí àëãîðèòì ñòàòèñòè÷åñêîãî ðîçûãðûøà ïî- ñòðîåíèÿ ðàñïèñàíèÿ ñåòåâîé ñòîõàñòè÷åñêîé ìîäåëè ðåñóðñíîãî ìåãàïðîåê- òà. Âûáèðàåòñÿ ðåàëèçàöèÿ ìîäåëè ñ ìàêñèìàëüíîé ïðèáûëüþ íà åäèíèöó âëîæåííûõ èíâåñòèöèé ïðè çàäàííûõ äèðåêòèâíûõ ñðîêàõ è îãðàíè÷åííî- ñòè ðåñóðñîâ. Êëþ÷åâûå ñëîâà: ñåòåâàÿ ñòîõàñòè÷åñêàÿ ìîäåëü, àëãîðèòì ñòàòèñòè÷å- ñêîãî ðîçûãðûøà, ìåãàïðîåêò, çàäà÷à îïòèìèçàöèè, ïîñòðîåíèå ðàñïèñàíèÿ Óñòîé÷èâîå îáåñïå÷åíèå ýêîíîìèêè ñòðàíû òîïëèâíî-ýíåðãåòè÷åñêèìè ðåñóð- ñàìè ïðè âîçðàñòàþùåì ñïðîñå è âûñîêîé èíåðöèîííîñòè ìèíåðàëüíî-ñûðüåâîãî êîìïëåêñà îáóñëîâëèâàåò ïîâûøåíèå çíà÷èìîñòè ìåãàïðîåêòîâ îñâîåíèÿ ðåñóðñîâ íîâûõ ðåãèîíîâ. Ìåãàïðîåêò ÿâëÿåòñÿ äîëãîñðî÷íûì êàïèòàëîåìêèì ïðîåêòîì ñ ìíîæåñòâîì ó÷àñòíèêîâ è âûñîêèìè ðèñêàìè ðåàëèçàöèè èõ èíâåñòèöèîííûõ ïðî- åêòîâ. Äëÿ óïðàâëåíèÿ èíâåñòèöèîííîé ïðîãðàììîé ìåãàïðîåêòà ïðåäëàãàåòñÿ èñ- ïîëüçîâàòü ñåòåâûå ñòîõàñòè÷åñêèå ìîäåëè. 1 Ôîðìàëüíîå îïèñàíèå ñòîõàñòè÷åñêîé ñåòåâîé ìîäåëè ìåãàïðîåêòà Ìîäåëè äàííîãî òèïà ïîçâîëÿþò ó÷èòûâàòü àëüòåðíàòèâíûå òåõíîëîãèè âûïîëíå- íèÿ ðàáîò ñ îïðåäåëåííîé âåðîÿòíîñòüþ èõ ðåàëèçàöèè. Ñòîõàñòè÷åñêàÿ ñåòåâàÿ ìîäåëü ìåãàïðîåêòà ïðåäíàçíà÷åíà äëÿ îöåíêè âëèÿíèÿ íåîïðåäåííîñòè âûïîë- íåíèÿ ðàáîò íà ñðîêè, ìàñøòàáû è ýôôåêòèâíîñòü åãî ðåàëèçàöèè. Çàäà÷à ðå- àëèçàöèè èíâåñòèöèîííîé ïðîãðàììû ìåãàïðîåêòà ïðåäñòàâëåíà êàê çàäà÷à îï- òèìèçàöèè ðåñóðñíî-êàëåíäàðíîãî ïëàíèðîâàíèÿ ïðè àëüòåðíàòèâíûõ âàðèàíòàõ âûïîëíåíèÿ ðàáîò ñ ðàçëè÷íûìè âåðîÿòíîñòÿìè. Ïðåäëîæåí àëãîðèòì ñòàòèñòè- ÷åñêîãî ðîçûãðûøà ïîñòðîåíèÿ ðàñïèñàíèÿ âûïîëíåíèÿ ìåãàïðîåêòà. Âûáèðàåòñÿ ðåàëèçàöèÿ ìîäåëè ñ ìàêñèìàëüíîé ïðèáûëüþ íà åäèíèöó âëîæåííûõ èíâåñòèöèé ïðè çàäàííûõ äèðåêòèâíûõ ñðîêàõ è îãðàíè÷åííîñòè ðåñóðñîâ. Ïðåäïîëàãàåòñÿ, Copyright ⃝ c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org Àëãîðèòì ðåàëèçàöèè ñåòåâîé ñòîõàñòè÷åñêîé ìîäåëè 639 ÷òî òåõíîëîãè÷åñêàÿ ïîñëåäîâàòåëüíîñòü âûïîëíåíèÿ ðàáîò ïðîåêòà çàäàíà â âèäå îðèåíòèðîâàííîãî ãðàôà G = (X, U ), áåç êîíòóðîâ è ïåòåëü, ãäå X  ìíîæåñòâî âåðøèí, ñîîòâåòñòâóþùèõ ñîáûòèÿì ñåòåâîé ìîäåëè; U ⊂ X × X  ìíîæåñòâî äóã, ñîîòâåòñòâóþùèõ ðàáîòàì. Ïóñòü U+−  ìíîæåñòâî ðàáîò, èñõîäÿùèõ èç âåð- øèíû X , Ux+ - ìíîæåñòâî ðàáîò, âõîäÿùèõ â âåðøèíó x ∈ X . Ïðè ïîñòðîåíèè ñòî- õàñòè÷åñêîé ñåòåâîé ìîäåëè èñïîëüçóþòñÿ âîñåìü òèïîâ ñîáûòèé, îïèñûâàþùèõ ïðàêòè÷åñêè âñå ñèòóàöèè, âñòðå÷àþùèåñÿ ïðè ìîäåëèðîâàíèè ñëîæíûõ ïðîåêòîâ [1]. Ïðåäïîëàãàåòñÿ, ÷òî çàäàíû ñëåäóþùèå âåëè÷èíû: N  ÷èñëî ðàáîò ñåòåâîé ìîäåëè; M  ÷èñëî âåðøèí (ñîáûòèé); W  ñïèñîê ðàáîò ñåòåâîé ìîäåëè ñ ýëå- ìåíòàìè (xv , yv , τv ), îïèñûâàþùèìè ñîîòâåòñòâåííî, íà÷àëüíîå, êîíå÷íîå ñîáûòèå è äëèòåëüíîñòü ðàáîòû v, v = 1, . . . , N ; Tmax  ïåññèìèñòè÷åñêàÿ îöåíêà äëèòåëü- íîñòè ïðîåêòà; pu  âåðîÿòíîñòü ðåàëèçàöèè ðàáîòû u ∈ U , 0 ≤ pu ≤ 1; P C  ñïèñîê ðåøàþùèõ ñîáûòèé, êîòîðûé âêëþ÷àåò â ñåáÿ èíôîðìàöèþ î êàæäîì àëü- òåðíàòèâíîì ñîáûòèè ñåòè â ñëåäóþùåì ïîðÿäêå: øèôð ðåøàþùåãî ñîáûòèÿ x, òèï ñîáûòèÿ x, øèôðû êîíå÷íûõ ñîáûòèé ðàáîò èç ìíîæåñòâà Ux− è âåðîÿòíîñòè ðåàëèçàöèè ðàáîò, âûõîäÿùèõ èç x; ôîðìèðóåòñÿ ìàññèâ Tp äëÿ âû÷èñëåíèÿ íàè- áîëåå ðàííèõ âðåìåí âåðøèí (ñîáûòèé) ñåòåâîé ìîäåëè; ìíîæåñòâî UM+ âêëþ÷àåò â ñåáÿ ôèêòèâíûå ðàáîòû íóëåâîé äëèòåëüíîñòè, ñîåäèíÿþùèå êîíöåâûå ñîáûòèÿ èñõîäíîé ñåòåâîé ìîäåëè ñ âåðøèíîé M ; K  çàäàííîå ÷èñëî ðåàëèçàöèé ñòîõà- ñòè÷åñêîé ñåòåâîé ìîäåëè. 2 Àëãîðèòì ñòàòèñòè÷åñêîãî ðîçûãðûøà Àëãîðèòì ñòàòèñòè÷åñêîãî ðîçûãðûøà îòäåëüíîé ðåàëèçàöèè ñåòåâîé ñòîõàñòè÷å- ñêîé ñåòåâîé ìîäåëè ñîñòîèò â ïîñëåäîâàòåëüíîì ðàññìîòðåíèè ãðóïïèðîâîê ðàáîò Ux− è âû÷èñëåíèè âðåìåííûõ õàðàêòåðèñòèê ñîáûòèé.  ðåçóëüòàòå ðîçûãðûøà ÷àñòü ðàáîò îêàçûâàåòñÿ ðåàëèçîâàííîé, îñòàëüíûå ðàáîòû èñêëþ÷àþòñÿ èç ñïèñ- êà. Ðîçûãðûø êàæäîé ðàáîòû (x, y) ∈ Ux− îïðåäåëÿåòñÿ êîíêðåòíûì îïèñàíèåì ëîãè÷åñêèõ âîçìîæíîñòåé íà÷àëüíîãî ñîáûòèÿ x è êîíå÷íîãî ñîáûòèÿ y ýòîé ðà- áîòû. Èñêëþ÷åíèå ðàáîòû (x, y) èç òåêóùåé ðåàëèçàöèè ïðîèçâîäèòñÿ ñîãëàñíî ïðàâèëó A, à âêëþ÷åíèå åå â êîíêðåòíóþ ðåàëèçàöèþ - ñîãëàñíî ïðàâèëó B [1]. Ñ öåëüþ óìåíüøåíèÿ âû÷èñëèòåëüíûõ çàòðàò èñïîëüçóåòñÿ âåòâëåíèå àëãîðèòìà â çàâèñèìîñòè îò ÷èñëà N . Ïðè N < M0 /2 èñïîëüçóåòñÿ ïðèâåäåíèå âåðîÿòíîñòåé ê îáùåìó çíàìåíàòåëþ; ïðè M0 /2 < N < M0  ìåòîä Óîëêåðà; ïðè N > M0  áèíàðíûé ïîèñê, çàòðàòû êîòîðîãî èìåþò ïîðÿäîê log2 N . Çäåñü M0  ðàçìåð ìàêñèìàëüíîãî ìàññèâà äëÿ çàäàííîãî êîìïüþòåðà è âûáðàííîãî ÿçûêà ïðîãðàì- ìèðîâàíèÿ. Äëÿ îäíîé ðåàëèçàöèè àëãîðèòì òðåáóåò âûïîëíåíèÿ îïåðàöèé â êî- ëè÷åñòâå O(nM ) ïðè N < M0 è O(nM log2 N ) ïðè N ≥ M0 . Íåîáõîäèìàÿ ïàìÿòü ëèíåéíî çàâèñèò îò ÷èñëà ðàáîò n, ÷èñëà ñîáûòèé è Tmax . Äëÿ àíàëèçà ðåçóëüòàòîâ òåêóùåé ðåàëèçàöèè èñïîëüçóåòñÿ ñ÷åò÷èê K+ óñïåø- íûõ ðåàëèçàöèé, ãèñòîãðàììà q ðàñïðåäåëåíèÿ âåëè÷èíû Tkp , ñ÷åò÷èêè ðåàëèçî- âàííîñòè rv è êðèòè÷íîñòè kv ðàáîòû v. Êàæäîé ðåàëèçàöèè ξ, 1 ≤ ξ ≤ K ñòî- õàñòè÷åñêîé ñåòåâîé ìîäåëè cîîòâåòñòâóåò çíà÷åíèå ñëó÷àéíîé âåëè÷èíû âðåìå- íè çàâåðøåíèÿ ïðîåêòà Tkpξ . Ðåàëèçàöèÿ ÿâëÿåòñÿ óäà÷íîé ïðè âûïîëíåíèè óñëî- âèÿ Tkpξ ≤ Tmax .  ýòîì ñëó÷àå óâåëè÷èâàåì íà åäèíèöó êîëè÷åñòâî óñïåøíûõ 640 Í.È. Ïëÿñêèíà ðåàëèçàöèé ñ÷åò÷èêà K+ èξ êîððåêòèðóåì ãèñòîãðàììó ðàñïðåäåëåíèÿ âåëè÷èíû Tkp : qτ = qτ + 1, ãäå T = [Tkp ]. Íà ñëåäóþùåì ýòàïå îñóùåñòâëÿåì ïîñëåäîâàòåëü- íûé ïðîñìîòð ñïèñêà ðàáîò ñåòåâîé ìîäåëè. Åñëè ðàáîòà ñ íîìåðîì v âîøëà â äàí- íóþ ðåàëèçàöèþ, òî óâåëè÷èâàåì íà åäèíèöó ñ÷åò÷èê ðåàëèçîâàííîñòè rv . Ïðîâå- ðÿåì ïðèíàäëåæíîñòü êàæäîé ðåàëèçîâàííîé ðàáîòû êàêîìó-ëèáî êðèòè÷åñêîìó ïóòè.  ñëó÷àå óñïåøíîñòè èñõîäà óâåëè÷èâàåì íà åäèíèöó ñ÷åò÷èê êðèòè÷íîñòè kv ðàññìàòðèâàåìîé ðàáîòû è îòìå÷àåì ôàêò ïðèíàäëåæíîñòè êðèòè÷åñêîìó ïó- òè. Ïîñëå ðîçûãðûøà çàäàííîãî ÷èñëà K ðåàëèçàöèé ïðîèçâîäèòñÿ îêîí÷àòåëüíàÿ îáðàáîòêà ïîëó÷åííûõ ðåçóëüòàòîâ, âêëþ÷àþùàÿ ñëåäóþùèå îïåðàöèè: 1. Âû÷èñëåíèå ýìïèðè÷åñêîé ôóíêöèè ðàñïðåäåëåíèÿ âðåìåíè âûïîëíåíèÿ ïðî- åêòà [2]. − + pT − = qT − ; pT = pT −1 + qT , T = Tkp + 1, . . . , Tkp . kp kp  ðåçóëüòàòå âåëè÷èíà pT äàåò−îöåíêó âåðîÿòíîñòè îñóùåñòâëåíèÿ ïðîåêòà â ïðåäåëàõ ïëàíîâîãî ïåðèîäà [Tkp , T ]. 2. Âû÷èñëåíèå êîýôôèöèåíòîâ ðåàëèçîâàííîñòè è êðèòè÷íîñòè ðàáîò rv = rv /K+, v = 1, . . . , N ; kv = kv /K+, v = 1, . . . , N. 3. Îöåíêà âåðîÿòíîñòè íåóäà÷íîãî èñõîäà ñåòåâîãî ïðîåêòà âåëè÷èíîé Pn = 1 − K + /K (äëÿ ñîáûòèé c Tkp > Tmax ). 4. Îöåíêà âåðîÿòíîñòè âîçìîæíûõ èñõîäîâ ñòîõàñòè÷åñêîé ñåòåâîé ìîäåëè ïî çíà÷åíèÿì rv äëÿ ôèêòèâíûõ ðàáîò èç ìíîæåñòâà UM+ , âõîäÿùèõ â ñîáûòèå ñ íîìåðîì M .  ðåçóëüòàòå ïðèìåíåíèÿ àëãîðèòìà ïîëó÷àåì ñåìåéñòâî äåòåðìèíèðîâàííûõ ñå- òåâûõ ìîäåëåé.  êàæäîé êîíêðåòíîé ðåàëèçàöèè äåòåðìèíèðîâàííîé ñåòåâîé ìî- äåëè ðåøàåòñÿ çàäà÷à îòûñêàíèÿ äîïóñòèìîãî ðàñïèñàíèÿ η∗ ìèíèìàëüíîé äëè- òåëüíîñòè, ïðè êîòîðîì öåëåâàÿ ôóíêöèÿ T (η) = max ∈ V (tu + τu ) → min u η Ïðè ýòîì âûïîëíÿþòñÿ óñëîâèÿ: 1. ñîáëþäàåòñÿ òåõíîëîãèÿ âûïîëíåíèÿ ðàáîò tu + τu ≤ tv äëÿ ëþáîé ïàðû ðàáîò u, v ∈ U òàêîé, ÷òî yu = xv ; 2. âûïîëíÿþòñÿ äèðåêòèâíûå ñðîêè tu + τu ≤ Tdir (x) äëÿ âñåõ ðàáîò u ∈ U ñ yu = x, ãäå x ∈ X dir ; 3. ñóììàðíàÿ èíòåíñèâíîñòü â ëþáîé ìîìåíò âðåìåíè t = t, . . . , T è äëÿ ëþáîãî òèïà ðåñóðñîâ (k = 1, . . . , m) ïîòðåáëÿåìûõ ðåñóðñîâ íå ïðåâûøàåò êîëè÷åñòâà Σu∈U k(t) ruk ≤ R¯tk ðåñóðñîâ, èìåþùèõñÿ â ìîìåíò t, ãäå Rtk -çàïàñ ðåñóðñîâ k -ãî òèïà â t-ì ïðîìåæóòêå ïëàíèðóåìîãî âðåìåíè. Ïðåäëîæåííûé àëãîðèòì ðåàëèçîâàí íà ÏÊ ñ ïîìîùüþ ÿçûêà ïðîãðàììèðîâàíèÿ Ñ++ íà ðåàëüíîé ýêîíîìè÷åñêîé èíôîðìàöèè ìåãàïðîåêòà ÂÑÍÃÊ. Ïðîèçâåäåíî 20 ðåàëèçàöèé ñòîõàñòè÷åñêîé ñåòåâîé ìîäåëè. Âû÷èñëåíà ôóíêöèÿ ðàñïðåäåëåíèÿ Àëãîðèòì ðåàëèçàöèè ñåòåâîé ñòîõàñòè÷åñêîé ìîäåëè 641 âðåìåíè âûïîëíåíèÿ ïðîåêòà, ïîñòðîåíà ãèñòîãðàììà ðàñïðåäåëåíèÿ Tkp è èíòå- ãðàëüíàÿ ôóíêöèÿ ðàñïðåäåëåíèÿ. Ïåññèìèñòè÷åñêàÿ îöåíêà äëèòåëüíîñòè ïðîåê- òà Tmax ðàâíà 44 ãîäàì, Tkp äëÿ ýôôåêòèâíîé ðåàëèçàöèè ñîñòàâëÿåò 42, 5 ãîäà. Äëÿ ðåàëèçàöèè ïðîãðàììû ìåãàïðîåêòà íåîáõîäèìî èíâåñòèðîâàòü 144, 1 ìëðä. äîëë. êàïèòàëüíûõ âëîæåíèé. Óäåëüíàÿ ïðèáûëü ñîñòàâëÿåò 768,8 äîëë./ò íåôòè. Ñïèñîê ëèòåðàòóðû 1. Ãèìàäè Ý.Õ., Ãîí÷àðîâ Å.Í., Çàëþáîâñêèé Â.Â., Ïëÿñêèíà Í.È., Õàðèòîíîâà Â.Í.: Î ïðîãðàììíî-ìàòåìàòè÷åñêîì îáåñïå÷åíèè äëÿ çàäà÷è ðåñóðñíî-êàëåíäàðíîãî ïëà- íèðîâàíèÿ Âîñòî÷íî-Ñèáèðñêîãî íåôòåãàçîâîãî êîìïëåêñà. Âåñòíèê Íîâîñèáèðñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà. Ñåðèÿ: Ìàòåìàòèêà, ìåõàíèêà, èíôîðìàòèêà. Ò. 10, âûï. 4. - Ñ. 5267 (2010) 2. Ãèìàäè Ý.Õ., Ãëåáîâ Í.È.: Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû ïðèíÿòèÿ ðåøåíèé. Ó÷åáíîå ïîñîáèå. Íîâîñèáèðñê: ÍÃÓ, (2008) Algorithm Realization of a Stochastic Network Resource Mega-Project Management Model Nina I. Plyaskina 1 Institute of Economics and Industrial Engineering of SB RAS 2 Novosibirsk State Univer-sity, Novosibirsk, Russia, pliaskina@hotmail.com Abstract. An algorithm random drawing of construction schedule network stochastic model resource megaproject. Selects the implementation of the model with the maxi-mum profit per unit of investments at specified deadlines and lim- ited resources. Keywords: stochastic network model, a statistical algorithm lottery, mega- project, the optimization problem, the construction schedule. Copyright ⃝ c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org