Диссертация (1149954), страница 16
Текст из файла (страница 16)
. . , min(rn , cn ))lex .â 1-ì ñòîêå äîñòèã çíà÷åíèÿÅãî ìîæíî èíòåðïðåòèðîâàòü òàê: âàæíåå âñåãî, ÷òîáû ïîòîêc1 . Åñëè ïîòîê äîñòèã ýòîãî çíà÷åíèÿ, íóæíî ðåøàòü ñëåäóþùóþçàäà÷ó äîñòèæåíèå âî 2-ì ñòîêå çíà÷åíèÿc2 ,ìàêñèìèçàöèÿ: íàéòè ìàêñèìàëüíûé ïîòîê ân-ìi = 1, . . . n − 1.h(r1 , . . . rn ) =àçóìååòñÿ, ìîæåò áûòü è âñåè.ò.ä. Âàæíûé ÷àñòíûé ñëó÷àé óñëîâíàÿñòîêå, åñëè ïîòîê â i-ì ñòîêå íå ìåíüøåci = +∞ci , òîãäà ýòî îáû÷íàÿ ëåêñèêîãðàè-÷åñêàÿ ìàêñèìèçàöèÿ.Äëÿ äèñêðåòíîãî ïîòîêà â [52℄ ïðåäëîæåí àëãîðèòì ïîñëåäîâàòåëüíîãî äèõîòîìè÷åñêîãî ïîèñêà ñëîæíîñòèO(n log p),ãäåp êîëè÷åñòâî âîçìîæíûõ ïîòîêîâ ÷åðåç äóãó. Äëÿïðîèçâîëüíîãî ïîòîêà (äèñêðåòíîãî èëè íåïðåðûâíîãî), ìû ìîæåì âîñïîëüçîâàòüñÿ ñëåäóþùèìàëãîðèòìîì íàõîæäåíèÿ ëåêñèêîãðàè÷åñêè ìàêñèìàëüíîãî ïîòîêà (ñâåäåíèå ê çàäà÷åóñëîâíîé ìàêñèìèçàöèè):1.
Èùåì ìàêñèìàëüíûé ïîòîê â 1-ì ñòîêå.2. Åñëè ìàêñèìóì ìåíüøåc1 , îñòàíàâëèâàåìñÿ. Åñëè íå ìåíüøå, ââîäèì äóãó îò 1-ãî ñòîêà,èäóùóþ ê äîïîëíèòåëüíîé âåðøèíå, áåç óñèëåíèé è ñ íèæíåé ïðîïóñêíîé ñïîñîáíîñòüþc1 .3. Èùåì ìàêñèìàëüíûé ïîòîê âî 2-ì ñòîêå. Ìíîæåñòâî äîïóñòèìûõ ïîòîêîâ, ñîãëàñíîïðåäûäóùåìó øàãó, íåïóñòî, òàê ÷òî ýòà çàäà÷à èìååò ðåøåíèå.4. Àíàëîãè÷íî ñðàâíèâàåì ïîëó÷èâøèéñÿ ïîòîê âî 2-ì ñòîêå ñÑëîæíîñòü àëãîðèòìà g(M, N)O(ng(M +n, N +n)), ãäå MèNc2 ,è ò.ä..êîëè÷åñòâî äóã è âåðøèí â ãðàå, ñëîæíîñòü àëãîðèòìà íàõîæäåíèÿ ìàêñèìàëüíîãî ïîòîêà.Åñëè æå ïðèíöèïû îïòèìàëüíîñòè ñòîèìîñòè ïîòîêîâ ñ ïðîòèâîïîëîæíûì çíàêîì, çàäà÷ó ëåêñèêîãðàè÷åñêîé îïòèìèçàöèè óæå íåëüçÿ ñâåñòè ê ïîñëåäîâàòåëüíîìó ðåøåíèþ70çàäà÷ îïòèìèçàöèè ïîòîêà: âåäü ïîñëå ïåðâîãî øàãà íà êàæäîì øàãå ïðèäåòñÿ ðàññìàòðèâàòü äîïîëíèòåëüíûå ëèíåéíûå îãðàíè÷åíèÿ íà ñòîèìîñòü ïîòîêà, âêëþ÷àþùèå â ñåáÿ âñåðåáðà ñåòè.
Íî, åñëè óñèëåíèÿ è ñòîèìîñòè âûïóêëûå êóñî÷íî-ëèíåéíûå, îíà ñâîäèòñÿ êðåøåíèþn ïîñëåäîâàòåëüíûõçàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ. Åñëè óñèëåíèÿ è ñòîèìî-ñòè íåïðåðûâíûå êóñî÷íî-ëèíåéíûå, îíà ñâîäèòñÿ ê ðåøåíèþnïîñëåäîâàòåëüíûõ çàäà÷êóñî÷íî-ëèíåéíîãî ïðîãðàììèðîâàíèÿ [21℄.2.2.3Àëãîðèòìû íàõîæäåíèÿ ïîòîêîâ â ñåòè ñ óñèëåíèÿìè, îïòèìàëüíûõ ïî ÏàðåòîÅñëè òðåáóåòñÿ íàéòè õîòÿ áû îäíî ðåøåíèå, îïòèìàëüíîå ïî Ïàðåòî, ìîæíî íàéòè ëåêñèêîãðàè÷åñêè ìàêñèìàëüíûé ïîòîê, êîòîðûé, êàê èçâåñòíî, îïòèìàëåí ïî Ïàðåòî [36℄. Çàäà÷àíàõîæäåíèÿ âñåõ ðåøåíèé, îïòèìàëüíûõ ïî Ïàðåòî, ãîðàçäî ñëîæíåå. äèñêðåòíîì ñëó÷àå áóäåì ïðåäïîëàãàòü, ÷òî ìû ìîæåì ýåêòèâíî ïåðå÷èñëèòü âñåxâîçìîæíûõ ïîòîêîâ (ðàçóìååòñÿ, ñëåäóåò ðàññìàòðèâàòü òîëüêî òå ïîòîêè, êîòîðûå ÿâëÿ-þòñÿ âîçìîæíûìè êàíäèäàòàìè íà Ïàðåòî-îïòèìàëüíîñòü).
Ïðîñòåéøèé ñïîñîá ýòî ñäåëàòüîïèñàí â ïðåäûäóùåì ðàçäåëå, â àëãîðèòìå ìàêñèìèçàöèè äèñêðåòíîãî ïîòîêà (â îáùåìñëó÷àå âîïðîñ îá ýåêòèâíîñòè ýòîãî ñïîñîáà îñòàåòñÿ îòêðûòûì). Ïîëó÷àåì ñëåäóþùèéàëãîðèòìèëüòðîâàííîãî ïåðåáîðà äëÿ íàõîæäåíèÿ âñåõ ïàðåòî-îïòèìàëüíûõ ïîòîêîâ:1. Ïåðåáèðàåì âñå ïîòîêè è çàïîìèíàåì äëÿ êàæäîãî ïîòîêàfåãî âåêòîð ñòîèìîñòåé2. Ââîäèì íà ïîòîêàõ ëåêñèêîãðàè÷åñêîå îòíîøåíèå ïîðÿäêàýòî çàéìåòO(nx log x)<c(f ).è ñîðòèðóåì ïî íåìó âðåìåíè. Ïðè ýòîì ëåêñèêîãðàè÷åñêîå îòíîøåíèå ïîðÿäêà ýòî ðàñøèðåíèå ÷àñòè÷íîãî ïîðÿäêà íà âåêòîðàõ êðèòåðèåâ.3. Ïðèìåíÿåì àíàëîã ðåøåòà Ýðàòîñåíà: ìàêñèìàëüíûé ýëåìåíò, î÷åâèäíî, îïòèìàëåíïî Ïàðåòî. Ñðàâíèâàåì åãî ñî âñåìè ìåíüøèìè è âû÷åðêèâàåì äîìèíèðóåìûå.4.
Èç îñòàâøèõñÿ ýëåìåíòîâ ìàêñèìàëüíûé îïòèìàëåí ïî Ïàðåòî. Äåëàåì ñ íèì òî æåñàìîå è ò. ä.Ñëîæíîñòü àëãîðèòìà O(n(K + log x)x),ãäåK êîëè÷åñòâî ïîòîêîâ, îïòèìàëüíûõïî Ïàðåòî. Ìîæíî íàéòè íå âñå ïîòîêè, îáðåçàâ ïîèñê íà íåêîòîðîì øàãå. Òî÷íî òàêèì æåàëãîðèòìîì ìîæíî íàéòè ìíîæåñòâî âñåõ ïîòîêîâ, ñëàáî îïòèìàëüíûõ ïî Ïàðåòî.Çàäà÷à íàõîæäåíèÿ ïàðåòî-îïòèìàëüíûõ ïîòîêîâ â ñåòè ñ âîãíóòûìè êóñî÷íî-ëèíåéíûìèóñèëåíèÿìè ýòî ïàðåòîâñêàÿ çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ ñèO(Mk + N)îãðàíè÷åíèÿìè, ãäåkO(Mk)ïåðåìåííûìè êîëè÷åñòâî êóñî÷êîâ â êàæäîé óíêöèè. Ïðè ýòîì71ìíîæåñòâî äîïóñòèìûõ ðåøåíèéX âûïóêëîå ìíîãîãðàííîå ìíîæåñòâî. Âñå êðèòåðèè ïðèýòîì ëèíåéíûå óíêöèè, à çíà÷èò, âñå ïàðåòîâñêèå ýëåìåíòû ìîæíî íàéòè, ìàêñèìèçèðîâàâ íåîòðèöàòåëüíûå ëèíåéíûå êîìáèíàöèè êðèòåðèåâ [43℄.
ÂåðøèíûìíîæåñòâàXîáðàçóþò íåîðèåíòèðîâàííûé ãðà(X 1 , X 2 ), â êîòîðîìX1è ðåáðàX2ïîäìíîæåñòâî ïàðåòî-îïòèìàëüíûõ âåðøèí îáðàçóåò ñâÿçíûé ïîäãðà.Îòñþäà ïîëó÷àåìàëãîðèòìíàõîæäåíèÿ âñåõ ïàðåòî-îïòèìàëüíûõ ïîòîêîâ:1. Íàõîäèì ëåêñèêîãðàè÷åñêè ìàêñèìàëüíûé ïîòîê çà âðåìÿO(ng(M, N)). Îí ÿâëÿåòñÿâåðøèíîé ìíîãîãðàííèêà äîïóñòèìûõ ðåøåíèé, à çíà÷èò, è ãðàà äîïóñòèìûõ ïîòîêîâ.àññìàòðèâàåì åãî êàê áàçîâóþ âåðøèíó â ñèìïëåêñ-ìåòîäå.2.
Ïðèâîäèì ÇËÏ ê êàíîíè÷åñêîìó âèäó ïîëó÷àåì çàäà÷ó ñèO(Mk + N)O(Mk + N)ïåðåìåííûìèîãðàíè÷åíèÿìè.3. Ìåòîäîì ïîèñêà â øèðèíó ïåðåáèðàåì âñå âåðøèíû ãðàà, ïîêà ñðåäè íèõ åñòü ïàðåòîîïòèìàëüíûå. Ïåðåõîä ê ñîñåäíåé âåðøèíå ýòî ïðîñòî ñìåíà áàçèñà â ñèìïëåêñòàáëèöå. Òî åñòü íà êàæäîì øàãå ïåðåáèðàåì âñå âîçìîæíûå ïåðåìåííûåðûå ìîæíî èñêëþ÷èòü èç áàçèñà è ïåðåìåííûåxj ,xi ,êîòî-êîòîðûå ìîæíî òóäà âêëþ÷èòü òàê,÷òîáû çíà÷åíèå êàêîãî-òî èç êîýèöèåíòîâ öåëåâîé óíêöèè óâåëè÷èëîñü. Êîëè÷åñòâî ðåáåð, ïðèìûêàþùèõ ê âåðøèíå O((Mk + N)2 )4. Íài-ìO((Mk + N)2 ).Êàæäàÿ ñìåíà áàçèñà çàéìåòâðåìåíè.øàãå âîçâðàùàåìñÿ ê âåðøèíàìè, íàéäåííûì íà(i − 1)-ìøàãå è ñðàâíèâàåìêàæäóþ èç íèõ ñ ñîñåäíèìè (âñå îíè óæå íàéäåíû), ÷òîáû ïðîâåðèòü, ÿâëÿåòñÿ ëèîíà ïàðåòî-îïòèìàëüíîé. Ïðîâåðêà çàíèìàåò âñåãîO(Mn(Mk + N)2 )âðåìåíè.
Åñëèÿâëÿåòñÿ, âêëþ÷àåì åå â îêîí÷àòåëüíûé ñïèñîê, åñëè íåò âñå âåðøèíû, êîòîðûåÿâëÿþòñÿ ñîñåäíèìè òîëüêî ñ íåé, âêëþ÷àåì â äîïîëíèòåëüíûé ñïèñîê ñîñåäåé.5. Ïîñëå òîãî, êàê âñå áàçèñíûå (ò.å. îáðàçóþùèå âåðøèíû ìíîãîãðàííèêà) ïàðåòîîïòèìàëüíûå ïîòîêè íàéäåíû, íàéäåì âñå îñòàëüíûå ïîòîêè. Îíè ñîäåðæàòñÿ â ãðàíÿõìíîãîãðàííèêà, ÿâëÿþùèõñÿ âûïóêëûìè êîìáèíàöèÿìè ïàðåòî-îïòèìàëüíûõ âåðøèí.Äåéñòâèòåëüíî, ëþáàÿ âûïóêëàÿ êîìáèíàöèÿ ïàðåòî-îïòèìàëüíûõ âåðøèí, î÷åâèäíî,ïàðåòî-îïòèìàëüíà, à åñëè â âûïóêëîé êîìáèíàöèèîäíà íåîïòèìàëüíàÿ âåðøèíàλ1 x1 + · · ·+ λl xlñîäåðæèòñÿ õîòÿ áûxi , òî ìîæíî óìåíüøèòü λi äî íóëÿ, óéäÿ èç âíóòðåííîñòèãðàíè è ïåðåéäÿ ê äîìèíèðóþùåé òî÷êå.Íî âñå ãðàíè ìíîãîãðàííèêà çàäàíû â ÿâíîì âèäå îãðàíè÷åíèÿìè ÇËÏ èõO(Mk +N)øòóê. Îñòàåòñÿ ïåðåáðàòü èõ è ïðîâåðèòü êàæäóþ èç íèõ, êàêèå ïàðåòî-îïòèìàëüíûå72âåðøèíû è êàêèå èç èõ ñîñåäåé îíà â ñåáÿ âêëþ÷àåò.
Åñëè, êðîìå ïàðåòî-îïòèìàëüíûõâåðøèí, ãðàíü âêëþ÷àåò â ñåáÿ è êàêèõ-òî èõ ñîñåäåé (èëè âêëþ÷àåò ìåíååMkïàðåòî-îïòèìàëüíûõ âåðøèí), çíà÷èò, îíà íå ïîäõîäèò. Ýòà ïðîâåðêà çàíèìàåò ïîðÿäêàO(Mk(Mk + N)3 + KMk(Mk + N))âðåìåíè.Ïîñêîëüêó êîëè÷åñòâî ïåðåáèðàåìûõ ðåáåð ïîðÿäêàO(K(Mk + N)2 )ãäåK êîëè÷åñòâîáàçèñíûõ (ò.å.
îáðàçóþùèõ âåðøèíû ìíîãîãðàííèêà) ïàðåòî-îïòèìàëüíûõ ïîòîêîâ, ïîëó÷àåìñëîæíîñòü àëãîðèòìàO(ng(Mk, N) + K(Mk + N)4 ). ñåòè ñ íåïðåðûâíûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìèàëãîðèòìíàõîæäåíèÿ ïàðåòî-îïòèìàëüíûõ ïîòîêîâ àíàëîãè÷íûé íî òîëüêî íà êàæäîé øàãå ïîëó÷àåì çàäà÷ó êóñî÷íîëèíåéíîãî ïðîãðàììèðîâàíèÿ, êîòîðàÿ ñâîäèòñÿ ê íàáîðó çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ [21℄.Âî âñåõ ïåðå÷èñëåííûõ ñëó÷àÿõ ìíîæåñòâî ýåêòèâíûõ ïîòîêîâ ìîæåò îêàçàòüñÿ î÷åíüáîëüøèì íàïðèìåð, â ò.í.ìíîæåñòâîì ïîòîêîâXïîëíûõ ìíîãîêðèòåðèàëüíûõ çàäà÷àõîíî ñîâïàäàåò ñî âñåì[29℄, ó êîòîðîãî, âîîáùå ãîâîðÿ, äàæå ìíîæåñòâî âåðøèí ýêñïîíåí-öèàëüíî âåëèêî [62℄.
Íî äëÿ íåêîòîðûõ 2-êðèòåðèàëüíûõ çàäà÷ êîëè÷åñòâî îïòèìàëüíûõïîòîêîâ ïîëèíîìèàëüíî ïîMèNè ñóùåñòâóþò ýåêòèâíûå àëãîðèòìû èõ íàõîæäåíèÿ:1. Ïàðåòî-îïòèìàëüíûå ðåøåíèÿ 2-êðèòåðèàëüíîé çàäà÷è î íàçíà÷åíèÿõ ñnâåðøèíàìè(÷àñòíûé ñëó÷àé çàäà÷è î ìàêñèìàëüíîì äèñêðåòíîì ïîòîêå) ìîæíî íàéòè çà âðåìÿO(n5)[25℄.2. Ñóùåñòâóþò ïîëèíîìèàëüíûå àëãîðèòìû ðåøåíèÿ îáùåé 2-êðèòåðèàëüíîé ïîòîêîâîéçàäà÷è â ñåòè áåç óñèëåíèé [29℄.Ê ñîæàëåíèþ, ýòè ÷àñòíûå ñëó÷àè ïîêà íå ñêëàäûâàþòñÿ â îáùóþ êàðòèíó.2.3Ìíîãîêðèòåðèàëüíàÿ îïòèìèçàöèÿ äèíàìè÷åñêèõ ïîòîêîâ â ñåòÿõ2.3.1Äâà àëãîðèòìà ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè äèíàìè÷åñêèõ ïîòîêîâ ðàçäåëå 1.3.1 ìû óæå äàëè ñòðîãîå îïðåäåëåíèå äèíàìè÷åñêîãî ïîòîêà, à â ðàçäåëå 2.1.2 îáùåå îïðåäåëåíèå çàäà÷è ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè è èñïîëüçóåìîå ñåìåéñòâîïðèíöèïîâ îïòèìàëüíîñòè.73Îïðåäåëåíèå 26.Ïóñòü äàíà äèíàìè÷åñêàÿ ñåòüNñ íåñêîëüêèìè óíêöèÿìè ñòîèìîñòèpt1 , .
. . , ptn : M × F → R. Çàäà÷à ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè äèíàìè÷åñêîãî ïîòîêà ýòî çàäà÷à ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè, â êîòîðîé ìíîæåñòâî àëüòåðíàòèâýòî ìíîæåñòâî äèíàìè÷åñêèõ ïîòîêîâïîòîêîâfâ ñåòèN,Xà êðèòåðèè îïòèìàëüíîñòè ñòîèìîñòèp1 (f ), . . . , pn (f ).×àñòíûé ñëó÷àé ýòîé çàäà÷è çàäà÷à ìíîãîêðèòåðèàëüíîé ìàêñèìèçàöèè äèíàìè÷åñêîãîïîòîêà â ñåòè ñ íåñêîëüêèìè ñòîêàìès1 , . .
. , sn .Çàäà÷à ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè äèíàìè÷åñêîãî ïîòîêà ðåøàåòñÿ òàê æå, êàê èîïòèìèçàöèîííàÿ çàäà÷à ñ îäíèì êðèòåðèåì.  ÷àñòíîñòè, âûïîëíÿåòñÿ òåîðåìà:Òåîðåìà 10(ñâåäåíèå äèíàìè÷åñêîé ìíîãîêðèòåðèàëüíîé çàäà÷è ê ñòàòè÷åñêîé).Ïóñòü âäèíàìè÷åñêîé ñåòè N ïðîïóñêíûå ñïîñîáíîñòè îãðàíè÷åíû, ñóùåñòâóþò äîïóñòèìûå ïîòîêè, óíêöèè glt (x1 , . . .
, x|e−1 (l)| ), pt (x) íåïðåðûâíûå êóñî÷íî-ëèíåéíûå è äàíà çàäà÷à ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè äèíàìè÷åñêîãî ïîòîêà.Òîãäà ñóùåñòâóåò Ïàðåòî-îïòèìàëüíûé äèíàìè÷åñêèé ïñåâäîïîòîê f ′ , êîòîðîìó ñîîòâåòñòâóåò Ïàðåòî-îïòèìàëüíûé ñòàòè÷åñêèé ïñåâäîïîòîê f â ñåòè, ðàçâåðíóòîé âîâðåìåíè NT . Ïðè ýòîì ñòàòè÷åñêèé è äèíàìè÷åñêèé ïîòîê ñîîòâåòñòâóþò äðóã äðóãó ïîîðìóëàì(1.12).Äîêàçàòåëüñòâî.Ñîãëàñíî óòâåðæäåíèþ 2.2.1, îïòèìàëüíûå ïîòîêè â ñåòè, ðàçâåðíóòîé âîâðåìåíè, ñóùåñòâóþò, òî åñòü äëÿ òàêèõ ñåòåé âûïîëíÿåòñÿ óñëîâèå ñóùåñòâîâàíèÿ.Ñîãëàñíî óòâåðæäåíèþ 1.3.2, ìíîæåñòâî çíà÷åíèé ïîòîêà â äèíàìè÷åñêîé ñåòè âçàèìíîîäíîçíà÷íî ñîîòâåòñòâóåò çíà÷åíèþ ïîòîêà â ñåòè, ðàçâåðíóòîé âî âðåìåíè, è çíà÷åíèÿ âñåõêðèòåðèåâ îïòèìàëüíîñòè ïðè ýòîì ðàâíû.
Ïî óñëîâèþ íåçàâèñèìîñòè îò ìíîæåñòâà àëüòåðíàòèâ, ýòî îçíà÷àåò, ÷òî ìíîæåñòâî îïòèìàëüíûõ ïîòîêîâ â äèíàìè÷åñêîé ñåòè ðàâíî ìíîæåñòâó îïòèìàëüíûõ ïîòîêîâ â ñåòè, ðàçâåðíóòîé âî âðåìåíè. À ïî óñëîâèþ ñóùåñòâîâàíèÿ,ýòî ìíîæåñòâî íåïóñòî.Òàêèì îáðàçîì, ïîëó÷àåìàëãîðèòìûðåøåíèÿ ñëåäóþùèõ êëàññîâ çàäà÷ ìíîãîêðèòå-ðèàëüíîé îïòèìèçàöèè äèíàìè÷åñêèõ ïîòîêîâ ïóòåì ñâåäåíèÿ äèíàìè÷åñêîé ñåòè ê ñåòè,ðàçâåðíóòîé âî âðåìåíè:1. Äëÿ äèñêðåòíûõ ïîòîêîâ ìîäèèöèðîâàííûé ìåòîä ðåøåòà äëÿ íàõîæäåíèÿ îïòèìóìîâ Ïàðåòî;2. Äëÿ âåùåñòâåííûõ ïîòîêîâ â ñåòè ñ âûïóêëûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè:74(a) ïîñëåäîâàòåëüíûé ñèìïëåêñ-ìåòîä äëÿ ëåêñèêîãðàè÷åñêîé ìèíèìèçàöèè ñòîèìîñòåé, ò.å.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
