Математические методы в экономике. Копылов Г.Н - 30 стр.

     Ýòîò øàã ïîâòîðÿåòñÿ ïîêà ýòî âîçìîæíî.
     Åñëè â ðåçóëüòàòå âñå âåðøèíû ïîëó÷àò íîìåðà, òî â ãðàôå
íåò îðèåíòèðîâàííûõ öèêëîâ. Åñëè æå íå âñå âåðøèíû ïîëó÷èëè
íîìåðà, òî ñðåäè îñòàâøèõñÿ âåðøèí åñòü öèêë. Ýòî îçíà÷àåò,
÷òî òðåáîâàíèÿ ïðîòèâîðå÷èâû. Íàø êîìïëåêñ ðàáîò âûïîëíèòü
íåâîçìîæíî.
     Ïîäâåäåì èòîãè. Â ýòîì ïàðàãðàôå áûëà ðàññìîòðåíà ñëåäó-
þùàÿ çàäà÷à.
     Èçâåñòåí ïåðå÷åíü ðàáîò, âðåìÿ, íåîáõîäèìîå äëÿ âûïîëíåíèÿ
êàæäîé ðàáîòû, à òàêæå îòíîøåíèå ïðåäøåñòâîâàíèÿ ìåæäó ðà-
áîòàìè.
     Íàñ èíòåðåñóþò îòâåòû íà ñëåäóþùèå âîïðîñû:
     Ìîæíî ëè âûïîëíèòü äàííûé êîìïëåêñ ðàáîò?
     Çà êàêîå ìèíèìàëüíîå âðåìÿ ìîæíî âûïîëíèòü âñå ðàáîòû?
     Åñòü ëè ðåçåðâû ñðîêîâ âûïîëíåíèÿ îòäåëüíûõ ðàáîò?
     Êàêèå ðàáîòû ñàìûå âàæíûå? ( Ñðûâ ñðîêîâ âûïîëíåíèÿ êà-
êèõ ðàáîò ïðèâåäåò ê ñðûâó ñðîêîâ ñäà÷è âñåãî êîìïëåêñà?).
     Äëÿ îòâåòîâ íà ýòè âîïðîñû áûëè ðàññìîòðåíû áûñòðûå
(ïîëèíîìèíàëüíûå) àëãîðèòìû. Ýòî îçíà÷àåò, ÷òî â ïðàêòè÷åñ-
êîé ñèòóàöèè ñ ïðèìåíåíèåì ÝÂÌ ìîæíî ðåøèòü çàäà÷ó ïðàê-
òè÷åñêè ëþáîé ðàçìåðíîñòè.
     Îòìåòèì äâà ìîìåíòà, êîòîðûå ìîãóò ïðèâåñòè ê áîëåå ñëîæ-
íûì çàäà÷àì è ñóùåñòâåííî çàòðóäíèòü ïîèñê îïòèìàëüíîãî ðå-
øåíèÿ:
     1.  ðÿäå çàäà÷ ìîãóò âîçíèêíóòü äðóãèå îãðàíè÷åíèÿ íà ïî-
ðÿäîê âûïîëíåíèÿ ðàáîò. Íàïðèìåð, «ðàáîòû À è Â ìîãóò âûïîë-
íÿòüñÿ â ëþáîì ïîðÿäêå, íî íå îäíîâðåìåííî».
     2. Ìû ñ÷èòàëè, ÷òî ñðîêè âûïîëíåíèÿ êàæäîé ðàáîòû ôèê-
ñèðîâàíû.  ðåàëüíûõ çàäà÷àõ îíè ìîãóò áûòü ñëó÷àéíûìè âåëè-
÷èíàìè, à òàêæå çàâèñåòü îò ðàñïðåäåëåíèÿ íåêîòîðîãî ðåñóðñà
(íàïðèìåð, äåíåã èëè êîëè÷åñòâà ðàáîòíèêîâ).
     Ïðè ó÷åòå ýòèõ ôàêòîðîâ ìîãóò ïîëó÷èòüñÿ çàäà÷è, äëÿ êî-
òîðûõ íå èçâåñòíû áûñòðûå è òî÷íûå àëãîðèòìû ðåøåíèÿ.

          Çàäà÷è äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿ
     Çàäàí êîìïëåêñ èç 20 ðàáîò, ðàñïîëîæåííûõ â âèäå ïðÿìî-
óãîëüíèêà 4×5. Êàæäóþ ðàáîòó ìîæíî íà÷èíàòü âûïîëíÿòü ïîñëå
îêîí÷àíèÿ åå ñîñåäà ñëåâà è ñîñåäà ñâåðõó. Íàéòè: 1) ìèíèìàëü-


                              30