Диссертация (1149954), страница 15
Текст из файла (страница 15)
Ïóñòü ïðèíöèï îïòèìàëüíîñòè îï-òèìóì Ïàðåòî. Òîãäà äëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷ âûïîëíÿåòñÿ ïðèíöèï îïòèìàëüíîñòè Áåëëìàíà.Äîêàçàòåëüñòâî.ïîëóãðóïïÏðåæäå âñåãî, çàìåòèì, ÷òî ïðîèçâåäåíèå ëèíåéíî óïîðÿäî÷åííûõ ñëåâàR × ···× R ÷àñòè÷íî óïîðÿäî÷åííàÿ ñëåâà (ïîêîìïîíåíòíî) ïîëóãðóïïàRnñïîêîìïîíåíòíûìè îïåðàöèÿìè, ïðè÷åì ñòðîãîñòü ïîðÿäêà ñëåâà äëÿ ïðîèçâåäåíèÿ ñîõðàíÿåòñÿ.
Òàêèì îáðàçîì, ìû ñâîäèì çàäà÷ó íàõîæäåíèÿ îïòèìóìà Ïàðåòî ê çàäà÷å íàõîæäåíèÿ ìàêñèìàëüíûõ ýëåìåíòîâ â ñòðîãî ñëåâà óïîðÿäî÷åííîé ïîëóãðóïïå. Îñòàëîñü äîêàçàòüóòâåðæäåíèå äëÿ òàêîé ïîëóãðóïïû.àññìîòðèì ïðîèçâîëüíóþ îïòèìàëüíóþ òðàåêòîðèþíîñòü îçíà÷àåò, ÷òî âûðàæåíèåRn .f1 (x1 ) ∗ f2 (x2 ) ∗ · · · ∗ fm (xm )àññìîòðèì òåïåðü ëþáóþ åå ïîäòðàåêòîðèþäîñòèãàåòñÿ ìàêñèìóì öåëåâîé óíêöèè ïîäçàäà÷èëè áû ñóùåñòâîâàëà èíàÿ ïîäòðàåêòîðèÿ÷åíèåh = (x′1 , x′2 , . .
. x′m ).íåäîìèíèðóåìî â ïîëóãðóïïå(x′t , x′t+1 , . . . x′m )è äîêàæåì, ÷òî íà íåéft (xt ) ∗ · · · ∗ fm (xm ).(x′t , x′′t+1 , . . . x′′m ),Äåéñòâèòåëüíî, åñ-íà êîòîðîé äîñòèãàëîñü áû çíà-ft (x′t ) ∗ ft+1 (x′′t+1 ) ∗ · · · ∗ fm (x′′m ) > ft (x′t ) ∗ ft+1 (x′t+1 ) ∗ · · · ∗ fm (x′m ),ñëåâà ëåâî-óïîðÿäî÷åííîñòè, îçíà÷àëî áû, ÷òîf1 (x′1 ) ∗ · · · ∗ ft (x′t ) ∗ ft+1 (x′t+1 ) ∗ · · · ∗ fm (x′m ),Åå îïòèìàëü-ýòî, ïî ñòðîãîéf1 (x′1 ) ∗ · · · ∗ ft (x′t ) ∗ ft+1 (x′′t+1 ) ∗ · · · ∗ fm (x′′m ) >÷òî ïðîòèâîðå÷èò íåäîìèíèðóåìîñòè òðàåêòîðèè(x′1 , .
. . x′m ).Òåîðåìà 9øà).(î äèíàìè÷åñêîì ïðîãðàììèðîâàíèè äëÿ îáîáùåííîãî èíòåãðàëüíîãî âûèãðû-Ïóñòü f (x) = f1 (x1 ) ∗ · · · ∗ fm (xm ) îáîáùåííûé èíòåãðàëüíûé âûèãðûø è çàäàíîåñòåñòâåííîå ÑÄÎÇ. Ïóñòü R ëåâî-óïîðÿäî÷åííàÿ ïîëóãðóïïà, à ïðèíöèï îïòèìàëüíîñòè îïòèìóì Ïàðåòî. Òîãäà ðåêóððåíòíûå óïðàâëåíèÿ îïòèìàëüíû è ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâû.66Äîêàçàòåëüñòâî.Àíàëîãè÷íî äîêàçàòåëüñòâó òåîðåìû 8, ñâîäèì çàäà÷ó îïòèìèçàöèè ê çà-äà÷å íàõîæäåíèÿ íåäîìèíèðóåìûõ ýëåìåíòîâ â ëåâî-óïîðÿäî÷åííîé ïîëóãðóïïå. Äàëüøåóòâåðæäåíèå ñëåäóåò èç ðåêóððåíòíûõ ñîîòíîøåíèé äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ äëÿóïîðÿäî÷åííûõ ïîëóãðóïï [1℄.Äëÿ ïðîèçâîëüíûõ óïîðÿäî÷åííûõ ïîëóãðóïï áåç ñâîéñòâà ñòðîãîñòè ñëåâà äàæå äëÿ îäíîãî êðèòåðèÿ íå âûïîëíÿåòñÿ ïðèíöèï îïòèìàëüíîñòè Áåëëìàíà: ñóùåñòâóþò îïòèìàëüíûåòðàåêòîðèè, êîíå÷íûå ó÷àñòêè êîòîðûõ íåîïòèìàëüíû.Ïðèìåð 10.{1, 2, 3},àññìîòðèì àâòîíîìíóþ ÎÄÑ íà ìíîæåñòâåîïðåäåëÿåìóþ òàê:D(1) = 4, D(4) = {2, 3}.X = {1, 2, 3, 4}ñ âðåìåíåìÏóñòü íà÷àëüíàÿ âåðøèíàäóåò ìàêñèìèçèðîâàòü ìèíèìàëüíîå çíà÷åíèå íà òðàåêòîðèè:x1 = 1êîòîðûé îïðåäåëÿåò åñòåñòâåííîå ñåìåéñòâî óíêöèé âûèãðûøà äëÿ ïîäñèñòåì:Ñóùåñòâóåò âñåãî 2 òðàåêòîðèè îñíîâíîé ñèñòåìû:è íà îáåèõ äîñòèãàåòñÿ îäèíàêîâîå (à çíà÷èò, îïòèìàëüíîå) çíà÷åíèåìå, íà÷èíàþùåéñÿ â òî÷êå4,è ñëå-f (x1 , x2 , x3 ) = min(x1 , x2 , x3 ).Ýòî îáîáùåííûé èíòåãðàëüíûé âûèãðûø íà óïîðÿäî÷åííîé ïîëóãðóïïå (äèîèäå)min(x2 , x3 ), f (x3 ) = x3 .T =f (x2 , x3 ) =(1, 4, 2), (1, 4, 3)f = 1.îïòèìàëüíîé áóäåò òîëüêî îäíà ïîäòðàåêòîðèÿ(Z, min),Íî â ïîäñèñòå-(4, 3), âòîðàÿ(4, 2) íåîïòèìàëüíà.
Ñëåäîâàòåëüíî ïåðâàÿ òðàåêòîðèÿ ÿâëÿåòñÿ äèíàìè÷åñêè óñòîé÷èâîé,à âòîðàÿ íåò. Ïðèíöèï Áåëëìàíà íå âûïîëíÿåòñÿ.Îäíàêî è äëÿ ïðîèçâîëüíîé óïîðÿäî÷åííîé ïîëóãðóïïû âñåãäà ñóùåñòâóåò õîòÿ áû îäíàäèíàìè÷åñêè óñòîé÷èâàÿ òðàåêòîðèÿ, êîòîðóþ, êàê ñëåäóåò èç [1℄, ìîæíî íàéòè ðåêóððåíòíûìè ñîîòíîøåíèÿìè äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ (ÑÄÏ).
Òàêèì îáðàçîì, äëÿ èíòåãðàëüíîãî âûèãðûøà íà óïîðÿäî÷åííûõ ïîëóãðóïïàõ, åñëè ïîðÿäîê íå ñòðîãèé ñëåâà,âûïîëíÿþòñÿ ÑÄÏ, íî ìîæåò íå âûïîëíÿòüñÿ ïðèíöèï îïòèìàëüíîñòè Áåëëìàíà. Ñ äðóãîéñòîðîíû, äàæå åñëè âûïîëíÿåòñÿ ïðèíöèï îïòèìàëüíîñòè Áåëëìàíà, îòíþäü íå êàæäîå îïòèìàëüíîå ðåøåíèå óäîâëåòâîðÿåò ÑÄÏ.
Òàêèì îáðàçîì, ïðèíöèï îïòèìàëüíîñòè Áåëëìàíàè ÑÄÏ ýòî ñîâåðøåííî ðàçíûå ïîíÿòèÿ, õîòÿ ìåæäó íèìè è åñòü ñâÿçü (òàê æå, êàê îíàåñòü, íàïðèìåð, ìåæäó ñëîæåíèåì è óìíîæåíèåì).Ïðèìåð 11.Ïóñòü èìååòñÿ 3 êðèòåðèÿA, B, Còî. Ïóñòü çàäàíà àâòîíîìíàÿ ÎÄÑ íà ìíîæåñòâåîïðåäåëÿåìàÿ òàê:D(x) = {x − 1, x, x + 1}.è íóæíî íàéòè ïî íèì îïòèìóìû Ïàðå-X = {0, 1, 2, 3}ñ âðåìåíåìÏóñòü íà÷àëüíàÿ ïîçèöèÿäóåò ìàêñèìèçèðîâàòü ìàêñèìàëüíîå çíà÷åíèå êðèòåðèÿ íà òðàåêòîðèè:max(gi (x0 ), gi (x1 ), gi (x2 )) (òî åñòüT = {0, 1, 2},x0 = 0è ñëå-fi (x0 , x1 , x2 ) =âàæåí íàèëó÷øèé ðåçóëüòàò, äîñòèãíóòûé ñèñòåìîé çà âðå-ìÿ åå äåéñòâèÿ).
Çíà÷èò, ïðèíöèï îïòèìàëüíîñòè Áåëëìàíà íå âûïîëíÿåòñÿ, íî âñå æå îïòèìàëüíûå ýëåìåíòû ìîæíî íàéòè äèíàìè÷åñêèì ïðîãðàììèðîâàíèåì.67Ïóñòü êðèòåðèè òàêîâû:gA (x) = 1/|x − 1.5|, gB (x) = 1/|x − 0.1|, gC (x) = 1/|x − 4|.èñêàòü îïòèìóì ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ.  ìîìåíò âðåìåíèx = 0, 1, 2, 3Áóäåìt = 2 ïîçèöèèäîñòàâëÿþò, ñîîòâåòñòâåííî, çíà÷åíèÿ êðèòåðèåâ(gA , gB , gC )(0) = (2/3, 10, 1/4)(gA , gB , gC )(1) = (2, 10/9, 1/3)(gA , gB , gC )(2) = (2, 10/11, 1/2)(gA , gB , gC )(3) = (2/3, 10/21, 1).àññìîòðèì òåïåðü ìîìåíò âðåìåíèïîçèöèþx = 0,x = 1,ïîëó÷èâ âåêòîðïîëó÷èâ(2, 10/9, 1/2).(gA , gB , gC ) = (2, 10, 1/3).(gA , gB , gC ) = (2, 10, 1/3), ïîçèöèèëèáî â ïîçèöèþt = 1.
 ïîçèöèè x = 0 íàèáîëåå âûãîäíî ñäâèíóòüñÿ âx=2x = 2,ïîëó÷èâïîçèöèèx=1x = 1,ïîëó÷èâ ëèáî â ïîçèöèþïîëó÷èâ(gA , gB , gC ) =(gA , gB , gC ) = (2, 10/9, 1/2),(gA , gB , gC ) = (2, 10/11, 1).t = 0.àññìîòðèì, íàêîíåö, ìîìåíò âðåìåíèx = 1,x = 2,ëèáî â ïîçèöèþ ëèáî â ïîçèöèþx=1x = 3, ïîëó÷èâ (gA , gB , gC ) = (2, 10/11, 1). Íàêîíåö, â ïîçèöèè x = 3 íàèáîëååâûãîäíî ñäâèíóòüñÿ âíóòüñÿ â ïîçèöèèà îòòóäà âx = 2, ëèáî âåðíóòüñÿ ââx = 2,âx = 1,à îòòóäà ââx = 3,ïîëó÷èâà îòòóäà âïåðåìåñòèòüñÿ âx = 3,x = 0,(2, 10/9, 1).ïîëó÷èâ â èòîãå âñå òå æåà îòòóäà âx = 1,(gA , gB , gC ) = (2, 10, 1/2). ïîçèöèèx=2ïîëó÷èâ â èòîãåx = 3Âëèáî ëèáî ïåðåéòè(gA , gB , gC ) = (2, 10, 1/2),Íàêîíåö, â ïîçèöèèÈòàê, òðàåêòîðèè, îïòèìàëüíûå ïî Ïàðåòî íàèáîëåå âûãîäíî ñäâè-(gA , gB , gC ) = (2, 10, 1/3),ïîëó÷èâ â èòîãå(gA , gB , gC ) = (2, 10/11, 1).x = 2,x = 0ïîëó÷èâ íà ïîñëåäíåì øàãåïîëó÷èâ â èòîãåx = 0, ïîçèöèèëèáî íàèáîëåå âûãîäíî(gA , gB , gC ) = (2, 10/9, 1).(0, 1, 2), (1, 0, 1), (1, 0, 0), (1, 2, 3), (2, 1, 0), (2, 3, 2), (2, âñåãî 8 òðàåêòîðèé èç 26 âîçìîæíûõ.åêóððåíòíûå ñîîòíîøåíèÿ (2.1) ëåãêî îáîáùàþòñÿ íà ñëó÷àé, êîãäà çàäàíî ìíîæåñòâîâñåõ äîïóñòèìûõ íà÷àëüíûõ ñîñòîÿíèéÿíèé′Xm.X0′è ìíîæåñòâî âñåõ äîïóñòèìûõ êîíå÷íûõ ñîñòî- ýòîì ñëó÷àå ïðîñòî íóæíî íà íà÷àëüíîì,ñîñòîÿíèé(f1 , .
. . , fn )xm ,óäîâëåòâîðÿþùèõ óñëîâèþïî âñåì óïðàâëåíèÿì′xm ∈ Xm,u(x, 1) ∈ U(x, 1)m-ìøàãå ðàññìàòðèâàòü ìíîæåñòâîà íà êîíå÷íîì, 1-ì øàãå âçÿòü îïòèìóìäëÿ êàæäîãîx ∈ X0′ .Ïðè îáðàùåíèè îðèåíòàöèè âñåõ äóã ãðà óïðàâëÿåìîé äèíàìè÷åñêîé ñèñòåìû îñòàíåòñÿãðàîì, à çíà÷åíèÿ óíêöèè íà âñåõ åãî ïóòÿõ îñòàíóòñÿ òàêèìè æå (åñëè ïîëóãðóïïàíåêîììóòàòèâíà îòíîñèòåëüíî îïåðàöèèãðóïïó ñ îïåðàöèåé∗′ ,â êîòîðîé∗,Ròî âñåãäà ìîæíî ðàññìîòðåòü îòðàæåííóþ ïîëó-x∗′ y = y ∗ x).Ñëåäîâàòåëüíî, ìîæíî ðàçâåðíóòü àëãîðèòìäèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ â ïðîòèâîïîëîæíîì íàïðàâëåíèè, äâèãàÿñü íå îò êîíå÷íîãî ìíîæåñòâà′Xmíàçàä, à îò íà÷àëüíîãî ìíîæåñòâàX0′âïåðåä.
Ïðè ýòîì ìû ïîëó÷àåì âñå68îïòèìàëüíûå òðàåêòîðèè, íà÷èíàþùèåñÿ â2.2X0′ .Ìíîãîêðèòåðèàëüíûå çàäà÷è â ñåòÿõ äàííîì ðàçäåëå ðàññìàòðèâàþòñÿ ìíîãîêðèòåðèàëüíûå çàäà÷è íàõîæäåíèÿ îïòèìàëüíîãîïîòîêà â ñåòè [38℄. Ïîñòðîåíû ñëåäóþùèå àëãîðèòìû:1. Äëÿ äèñêðåòíûõ ïîòîêîâ ìîäèèöèðîâàííûé ìåòîä ðåøåòà äëÿ íàõîæäåíèÿ îïòèìóìà Ïàðåòî;2. Äëÿ ïîòîêîâ â ñåòè ñ âûïóêëûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè ìîäèèöèðîâàííûé ñèìïëåêñ-ìåòîä äëÿ íàõîæäåíèÿ îïòèìóìîâ Ïàðåòî;3. Äëÿ ïîòîêîâ â ñåòè ñ íåïðåðûâíûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè ìîäèèöèðîâàííûé ìåòîä êóñî÷íî-ëèíåéíîãî ïðîãðàììèðîâàíèÿ äëÿ íàõîæäåíèÿ îïòèìóìîâ Ïàðåòî;2.2.1Ïîñòàíîâêà çàäà÷è ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ïîòîêàâ ñåòè ñ óñèëåíèÿìèÑîðìóëèðóåì çàäà÷ó ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ïîòîêà â êîíå÷íîé ñåòè.ïîòîê â ñåòèÏóñòü çàäàíà ñåòüNñ íåñêîëüêèìè óíêöèÿìè ñòîèìîñòèF → R.
Çàäà÷à ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ïîòîêà â ñåòèòåðèàëüíîé îïòèìèçàöèè, â êîòîðîé ìíîæåñòâî àëüòåðíàòèââ ñåòèN,èîïðåäåëåíû â ðàçäåëå 1.2.Îïðåäåëåíèå 25.fÑåòüXNp1 , . . . pn : M × ýòî çàäà÷à ìíîãîêðè- ýòî ìíîæåñòâî ïîòîêîâà êðèòåðèè îïòèìàëüíîñòè ñòîèìîñòè ïîòîêîâ ñ ïðîòèâîïîëîæíûì çíàêîì−p1 (f ), . . . , −pn (f ).Óòâåðæäåíèå 2.2.1äà÷àõ).(î ñóùåñòâîâàíèè îïòèìàëüíûõ ïîòîêîâ â ìíîãîêðèòåðèàëüíûõ çà-Ïóñòü âñå ïðîïóñêíûå ñïîñîáíîñòè â ñåòè îãðàíè÷åíû, óñèëåíèÿ è ñòîèìîñòè íåïðåðûâíûå êóñî÷íî-ëèíåéíûå, è ìíîæåñòâî ïîòîêîâ íåïóñòî. Òîãäà ñóùåñòâóþò îïòèìóìû ïî Ïàðåòî.Äîêàçàòåëüñòâî.Ìíîæåñòâî ïîòîêîâ íåïóñòîå îãðàíè÷åííîå ìíîãîãðàííîå ìíîæåñòâî,ïîýòîìó ñóùåñòâîâàíèå îïòèìóìîâ ñëåäóåò èç òåîðåìà 6.Çàìå÷àíèå2.2.1.
Ïðîâåðêà íåïóñòîòû ìíîæåñòâà àëüòåðíàòèâ, êàê çàìå÷åíî â [52℄, ñâîäèòñÿê âñïîìîãàòåëüíîé çàäà÷å íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà.69Çàäà÷à íàõîæäåíèÿ ïîòîêîâ, îïòèìàëüíûõ ïî Ïàðåòî, íåîäíîêðàòíî ðàññìàòðèâàëàñü ðàíåå [29, 25, 21℄ äàæå äëÿ ïðîñòåéøèõ ïîòîêîâûõ çàäà÷ îíà íàìíîãî ñëîæíåå, ÷åì íàõîæäåíèå ìàêñèìóìà ñâåðòêè.  ðàáîòå äëÿ íåå ïîñòðîåí òîëüêî íå î÷åíü ýåêòèâíûé ïåðåáîðíûé àëãîðèòì.2.2.2Íàõîæäåíèå ëåêñèêîãðàè÷åñêè îïòèìàëüíîãî ïîòîêà â ñåòèñ óñèëåíèÿìè ñëó÷àå, åñëè êðèòåðèè îïòèìàëüíîñòè èçëèøêè ïîòîêà â ñòîêàõ, çàäà÷à ëåêñèêîãðàè÷åñêîé ìàêñèìèçàöèè ýòî çàäà÷à ìàêñèìèçàöèè âåêòîðà èçëèøêîâ â ñòîêàõ îòíîñèòåëüíîëåêñêèãðàè÷åñêîãî ïîðÿäêà. àññìîòðèì ñëåãêà ìîäèèöèðîâàííûé âåêòîð(min(r1 , c1 ), .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
