Диссертация (1149954), страница 13
Текст из файла (страница 13)
Äà è ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ [51℄ ðåøàåò íå îäíó çàäà÷ó, à ñåìåéñòâîçàäà÷. Äàäèì ñòðîãîå îïðåäåëåíèå:Îïðåäåëåíèå 17.íàÿ ïîçèöèÿñèñòåìåDx0 .Ïóñòü äàíà ÎÄÑÒîãäàDíà ìíîæåñòâå ñîñòîÿíèéXñ âðåìåíåìñåìåéñòâî äèíàìè÷åñêèõ îïòèìèçàöèîííûõ çàäà÷,Tè íà÷àëü-ñîîòâåòñòâóþùèõ ýòî íàáîð(X, T, x0 , {P(x,t) }(x,t)∈X×T , (f1 (x,t) , . . . , fn (x,t) )(x,t)∈X×T ),ãäåP(x,t) ìíîæåñòâî òðàåêòîðèé, âûõîäÿùèõ èçòèìàëüíîñòè, çàäàííûå íà(x, t),à(f1 (x,t) , . . . , fn (x,t) ) êðèòåðèè îï-P(x,t) .Òî åñòü ñåìåéñòâî äèíàìè÷åñêèõ îïòèìèçàöèîííûõ çàäà÷ (ÑÄÎÇ) îçíà÷àåò, ÷òî äëÿ êàæäîé ïîäñèñòåìû çàäàíà îïòèìèçàöèîííàÿ çàäà÷à íà ìíîæåñòâå òðàåêòîðèé.
×àñòî î ðåøåíèèäèíàìè÷åñêèõ çàäà÷ ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, ãîâîðÿò, ÷òî ðåøàåòñÿ îäíàîïòèìèçàöèîííàÿ çàäà÷à äëÿ ðàçíûõ íà÷àëüíûõ ìîìåíòîâ âðåìåíè è íà÷àëüíûõ òî÷åê. Íî,57ñòðîãî ãîâîðÿ, ðåøàåòñÿ íå îäíà çàäà÷à, à ñåìåéñòâî çàäà÷, çàäàííûõ äëÿ êàæäîé ïîäñèñòåìû. È, ðàçóìååòñÿ, ïîñêîëüêó ñåìåéñòâî çàäà÷ ìîæåò áûòü çàäàíî ïðîèçâîëüíûì îáðàçîì,îòíþäü íå êàæäîå ñåìåéñòâî çàäà÷ (äàæå ñ îäíèì êðèòåðèåì îïòèìàëüíîñòè) ìîæíî ðåøèòüìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ.Îïðåäåëåíèå18.ÏóñòüçàäàíàÎÄÑDñfi (x1 , x2 , .
. . , xm ) = fi1 (x1 ) ∗ fi2 (x2 ) ∗ · · · ∗ fim (xm ).îáîáùåííûìÒîãäàèíòåãðàëüíûìâûèãðûøåìåñòåñòâåííîå ñåìåéñòâî çàäà÷ýòî ÑÄÎÇ ñ êðèòåðèÿìè, îïðåäåëÿåìûìè òàê:fi (x,t) (x, xt+1 , . . . , xm ) = fit (x) ∗ fit+1 (xt+1 ) ∗ · · · ∗ fim (xm ).Òàêèì îáðàçîì, ìû îðìàëèçîâàëè ðàññóæäåíèÿ î òîì, ÷òî âûèãðûø âûïëà÷èâàåòñÿ âðàçíûå ìîìåíòû âðåìåíè [51℄. Îïðåäåëåíèå ñåìåéñòâà çàäà÷ ïîçâîëÿåò ïîíÿòü, ÷òî è êîãäàâûïëà÷èâàåòñÿ òî÷íåå, êàê ìåíÿþòñÿ öåëè ñèñòåìû â çàâèñèìîñòè îò òåêóùåãî ìîìåíòàâðåìåíè.Çàìå÷àíèå2.1.1. Åñëè â îñíîâíîé çàäà÷å çàäàíà òåðìèíàëüíàÿ ïîëåçíîñòüäîé çàäà÷å ñåìåéñòâà òàêæå çàäàíà òåðìèíàëüíàÿ ïîëåçíîñòüfi (xm ).fi (xm ),òî â êàæ-Ïðè ýòîì çàäà÷à äëÿïîäñèñòåìû ýòî ïîäçàäà÷à çàäà÷è äëÿ èñõîäíîé ñèñòåìû, ïîñêîëüêó â íåé ðàññìàòðèâàåòñÿïîäìíîæåñòâî òðàåêòîðèé à èìåííî, òå òðàåêòîðèè, êîòîðûå ïðîõîäÿò ÷åðåç òî÷êó(x, t) è òå æå êðèòåðèè îïòèìàëüíîñòè.2.1.2Ñâîéñòâà îïòèìàëüíûõ ðåøåíèéÏðèíöèïû îïòèìàëüíîñòè â çàäà÷àõ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè èññëåäîâàëèñü â ðàçíûõ ðàáîòàõ [12, 19, 43℄ ñ òî÷êè çðåíèÿ íàõîæäåíèÿ ñàìèõ ïðèíöèïîâ.
 äàííîé ðàáîòå âîïðîñî ïîñòðîåíèè ïðèíöèïîâ îïòèìàëüíîñòè â ïðèìåíåíèè ê ëîãèñòè÷åñêèì ñèñòåìàì íå ðàññìàòðèâàåòñÿ. Ýòè ïðèíöèïû ìîãóò áûòü ñàìûìè ðàçíîîáðàçíûìè è çàâèñåòü îò ñïåöèèêèðàññìàòðèâàåìîé çàäà÷è. Íî â çàäà÷å íåñòðàòåãè÷åñêîé ìíîãîêðèòåðèàëüíîé îïòèìèçàöèèåñòåñòâåííî ïðåäïîëàãàòü, ÷òî ëþáîå îïòèìàëüíîå ðåøåíèå ÿâëÿåòñÿ Ïàðåòî-îïòèìàëüíûì[43℄. Ïîýòîìó, íàéäÿ âñå îïòèìóìû Ïàðåòî, ìîæíî çàòåì ïåðåáðàòü èõ è âûáðàòü èç íèõ òå,êîòîðûå óäîâëåòâîðÿþò äðóãèì ïðèíöèïàì îïòèìàëüíîñòè. Èñõîäÿ èç ýòîãî, äàëåå ïîñòðîåíû àëãîðèòìû íàõîæäåíèÿ âñåõ îïòèìóìîâ Ïàðåòî.Îáîçíà÷èìðèåâf.Parf (X) ìíîæåñòâî îïòèìóìîâ Ïàðåòî íà ìíîæåñòâåXïî âåêòîðó êðèòå-Îïòèìóìû Ïàðåòî óäîâëåòâîðÿþò ðÿäó âàæíûõ óñëîâèé.Òåîðåìà 6. Åñëè X îáîáùåííîå ìíîãîãðàííîå ìíîæåñòâî, à âñå êðèòåðèè (f1 , .
. . , fn ) 58íåïðåðûâíûå êóñî÷íî-ëèíåéíûå, òî îïòèìóìû Ïàðåòî óäîâëåòâîðÿþò ñëåäóþùèì óñëîâèÿì:1. Ñóùåñòâîâàíèå: ìíîæåñòâî îïòèìàëüíûõ ðåøåíèé íåïóñòî, ò.å., Parf (X) 6= ∅.2. Íåçàâèñèìîñòü îò ìíîæåñòâà àëüòåðíàòèâ: âûáîð îïòèìàëüíîãî ðåøåíèÿ çàâèñèò òîëüêî îò êðèòåðèåâ îïòèìàëüíîñòè, íî íå îò êàêèõ-ëèáî èíûõ ñâîéñòâ àëüòåðíàòèâ.
Òî åñòü ýòî íåñòðàòåãè÷åñêàÿ çàäà÷à îïòèìèçàöèè, â êîòîðîé çàäàíû âñåâîçìîæíûå êðèòåðèè îïòèìàëüíîñòè, è ê íèì áîëüøå íå÷åãî äîáàâèòü. Ôîðìàëüíî,åñëè x ∈ Parf (X), y ∈ Y , f (X) = f (Y ) è f (x) = f (y), òî y ∈ Parf (Y ). Î÷åâèäíî, âýòîì ñëó÷àå Parf (Y ) = f −1 (f (Parf (X))).3. Íåçàâèñèìîñòü îò ñïîñîáà èçìåðåíèÿ: îïòèìóìû Ïàðåòî íå çàâèñÿò îò ëþáûõñòðîãî âîçðàñòàþùèõ ïðåîáðàçîâàíèé êðèòåðèåâ fi∗ (x) = gi (fi (x)), ãäå gi ñòðîãîâîçðàñòàþùèå óíêöèè:Parf (X) = Parf ∗ (X).Òî åñòü ýòîò ïðèíöèï îïòèìàëüíîñòè ìîæíî ïðèìåíÿòü äëÿ êðèòåðèåâ, ïðèíèìàþùèõ çíà÷åíèÿ èç ëþáûõ ïîðÿäêîâûõ øêàë.4.
Íåçàâèñèìîñòü îò ïîñòîðîííèõ àëüòåðíàòèâ (ðàöèîíàëüíîñòü): åñëè x∗ îïòèìàëüíî äëÿ ìíîæåñòâà X è x∗ ∈ X ′ ⊆ X , òî x∗ îïòèìàëüíî è äëÿ ìíîæåñòâà X ′ .5. Òðàíçèòèâíîñòü: åñëè ìíîæåñòâî àëüòåðíàòèâ X ðàçáèòî íà ïîäìíîæåñòâà (êîòîðûå, âîîáùå ãîâîðÿ, ìîãóò ïåðåñåêàòüñÿ):X = X1 ∪ X2 ∪ · · · ∪ Xnòî ðåøåíèå çàäà÷è ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ñîñòàâëÿåòñÿ èç ðåøåíèé ïîäçàäà÷:Parf (X) = Parf (Parf (X1 ) ∪ Parf (X2 ) ∪ · · · ∪ Parf (Xn )).Ýòî óñèëåíèå óñëîâèÿ ðàöèîíàëüíîñòè, îçíà÷àþùåå, ÷òî ìîæíî ðàçáèòü ðåøåíèåñëîæíîé çàäà÷è íà ÷àñòè, âûáèðàÿ îïòèìàëüíîå ðåøåíèå èç îïòèìàëüíûõ ðåøåíèéïîäçàäà÷.Çàìå÷àíèå2.1.2.
Óñëîâèå åäèíñòâåííîñòè ðåøåíèÿ (äàæå â ñìûñëå åäèíñòâåííîñòè íàáîðà(f1 (x), . . . , fn (x)))íå ðàññìàòðèâàåòñÿ. Âî-ïåðâûõ, äëÿ âûïîëíåíèÿ ýòîãî óñëîâèÿ íóæåí ðÿäñïåöèè÷åñêèõ îãðàíè÷åíèé íà êðèòåðèè, íàïðèìåð, èõ ñòðîãàÿ âîãíóòîñòü [33℄. Âî-âòîðûõ,59ïðè óïðàâëåíèè ðåàëüíîé ýêîíîìè÷åñêîé ñèñòåìîé íàëè÷èå íåñêîëüêèõ îïòèìàëüíûõ ðåøåíèé íå ÿâëÿåòñÿ ïðåïÿòñòâèåì äëÿ ïðèíÿòèÿ óïðàâëåí÷åñêîãî ðåøåíèÿ äëÿ ýòîãî äîñòàòî÷íî ïðîäåëàòü ïðîèçâîëüíóþ ñòîõàñòè÷åñêóþ ïðîöåäóðó, âðîäå áðîñàíèÿ ìîíåòû.Ïðåæäå, ÷åì äîêàçàòü òåîðåìó, äîêàæåì ëåììó î ïðèíöèïàõ îïòèìàëüíîñòè, ïîðîæäåííûõ îòíîøåíèåì ïîðÿäêà.Ëåììà 6.1. Ïóñòü ≺ îòíîøåíèå ïðåäïîðÿäêà íà Rn .
Ïóñòü ïðèíöèï îïòèìàëüíîñòèçàäàåòñÿ êàê íåäîìèíèðóåìîñòü ïî ýòîìó îòíîøåíèþ íà ìíîæåñòâå êðèòåðèåâ:Self (X) = {x | ∀y ∈ X f (x) 6≺ f (y)}.Òîãäà ýòîò ïðèíöèï óäîâëåòâîðÿåò óñëîâèþ íåçàâèñèìîñòè îò ìíîæåñòâà àëüòåðíàòèâè óñëîâèþ íåçàâèñèìîñòè îò ïîñòîðîííèõ àëüòåðíàòèâ. Åñëè æå âûïîëíåíî óñèëåííîåóñëîâèå ñóùåñòâîâàíèÿ: äëÿ ëþáîãî x ∈ X â âåðõíåì êîíóñåC> (x) = {y ∈ X midx y}ñóùåñòâóþò îïòèìàëüíûå ýëåìåíòû òîãäà îí óäîâëåòâîðÿåò è ïðèíöèïó òðàíçèòèâíîñòè.Äîêàçàòåëüñòâî.Íåçàâèñèìîñòü îò ìíîæåñòâà àëüòåðíàòèâ î÷åâèäíà èç îïðåäåëåíèÿ.Íåçàâèñèìîñòü îò ïîñòîðîííèõ àëüòåðíàòèâ î÷åâèäíà: åñëè ýëåìåíò íåäîìèíèðóåì â áîëüøåì ìíîæåñòâå, òî îí íåäîìèíèðóåì è â ìåíüøåì.Äîêàæåì òðàíçèòèâíîñòü.
ÏóñòüSel′f (X) = Self (Self (X1 ) ∪ Self (X2 ) ∪ · · · ∪ Self (Xn )).Äîêàæåì, ÷òî åñëèf (Xi ).ìèíèðóåìûõ âìíîæåñòâóXi ,x ∈ Self (X),òîx ∈ Sel′f (X).Self (Xi ) ìíîæåñòâî àëüòåðíàòèâ, íåäî-Ëþáàÿ àëüòåðíàòèâà, íåäîìèíèðóåìàÿ âà çíà÷èò, ïî ðàöèîíàëüíîñòè, ïðèíàäëåæèò èòàêèå àëüòåðíàòèâû ñîäåðæàòñÿ â îáúåäèíåíèèX,ïðèíàäëåæèò íåêîòîðîìóSelf (Xi ).Self (X1 ) ∪ Self (X2 ) ∪ · · · ∪ Self (Xn ). Îïÿòü æå,ïî íåçàâèñèìîñòè îò ïîñòîðîííèõ àëüòåðíàòèâ, âñå îíè ñîäåðæàòñÿ âÏóñòü òåïåðüïîëîæèì, ÷òîxx ∈ Sel′f (X).Ïóñòüx ∈ Xi ,ýòîìòî åñòüäîìèíèðóåìî íåêèì ýëåìåíòîìñóùåñòâóåò òàêîé íåäîìèíèðóåìûé ýëåìåíòz ∈ Self (Xj ),à çíà÷èò, íå ìîæåò áûòüíåäîìèíèðóåìî, òî åñòüx ∈ Self (X).Ñëåäîâàòåëüíî, âñåy.z ∈ Xj ,x ∈ Self (Xi ).Sel′f (X).Îò ïðîòèâíîãî: ïðåä-Ïî óñèëåííîìó óñëîâèþ ñóùåñòâîâàíèÿ,÷òîy z.x ∈ Sel′f (X)Ñëåäîâàòåëüíî,x ≺ z,íî ïðè ïðîòèâîðå÷èå.
Ñëåäîâàòåëüíî,x60Çàìå÷àíèåïóñòü2.1.3. Óñèëåííîå óñëîâèå ñóùåñòâîâàíèÿ èìååò çíà÷åíèå. àññìîòðèì ïðèìåð:X = R,çàäàí îäèí êðèòåðèéàññìîòðèì ðàçáèåíèåf (x) = xè≺ îáû÷íîå îòíîøåíèå ïîðÿäêà íàR = X1 ∪ X2 = (inf ty; 0] ∪ (0; ∞). Òîãäà Self (X) = ∅,àX = R.Self (Self (X1 ) ∪Self (X2 )) = Self ({0} ∪ ∅) = {0}.Ïåðåéäåì òåïåðü ê äîêàçàòåëüñòâó òåîðåìû:Äîêàçàòåëüñòâî.1. Ñóùåñòâîâàíèå.
Äîñòàòî÷íî äîêàçàòü, ÷òî ñóùåñòâóåò ëåêñèêîãðà-è÷åñêèé îïòèìóì ïî âåêòîðó êðèòåðèåâ(f1 (x), . . . , fn (x)).Ìàêñèìóì ÍÊË-óíêöèèíà îãðàíè÷åííîì îáîáùåííîì ìíîãîãðàííèêîì ìíîæåñòâå âñåãäà ñóùåñòâóåò. Ïóñòüy1 = maxx∈X f1 (x).Ïðîîáðàç òî÷êèy1 : X1∗ = f1−1 (y1 ),î÷åâèäíî, ÿâëÿåòñÿ îãðàíè÷åí-íûì îáîáùåííûì ìíîãîãðàííûì ìíîæåñòâîì (êàê ïåðåñå÷åíèå îãðàíè÷åííîãî îáîáùåííîãî ìíîãîãðàííîãî ìíîæåñòâà è ïðîîáðàçà ÍÊË-óíêöèè äëÿ òî÷êè, êîòîðûé òîæåÿâëÿåòñÿ îáîáùåííûì ìíîãîãðàííûì ìíîæåñòâîì). Ñëåäîâàòåëüíî, ñóùåñòâóåò ìàêñèìóìy2 = maxx∈X1∗ f2 (x).Àíàëîãè÷íî äåéñòâóÿ äàëüøå, ïîëó÷àåì âåñü ëåêñèêîãðàè÷å-ñêèé ìàêñèìóì(y1 , . . . , yn ),íîì ìíîæåñòâåXn∗ .êîòîðûé äîñòèãàåòñÿ íà íåïóñòîì îáîáùåííîì ìíîãîãðàí-Äëÿ îïòèìóìà ïî Ïàðåòî ñóùåñòâîâàíèå ñëåäóåò èç òîãî, ÷òî ëåêñèêîãðàè÷åñêèé îïòèìóì îïòèìàëåí ïî Ïàðåòî è ñóùåñòâóåò.2.
Íåçàâèñèìîñòü îò ìíîæåñòâà àëüòåðíàòèâ ñëåäóåò èç ëåììû.3. Íåçàâèñèìîñòü îò ñïîñîáà èçìåðåíèÿ î÷åâèäíî.4. Íåçàâèñèìîñòü îò ïîñòîðîííèõ àëüòåðíàòèâ ñëåäóåò èç ëåììû.5. Òðàíçèòèâíîñòü. Îïðåäåëèì ñîîòâåòñòâóþùåå îòíîøåíèåâëåòâîðÿåò íàÏóñòü≺X≺è äîêàæåì, ÷òî îíî óäî-óñèëåííîìó óñëîâèþ ñóùåñòâîâàíèÿ. åñòåñòâåííîå îòíîøåíèå ïîðÿäêà íàìåíòû ýòî íåäîìèíèðóåìûå ýëåìåíòû ïî≺.Rn .Òîãäà îïòèìàëüíûå ïî Ïàðåòî ýëå-Äëÿ ïðîèçâîëüíîãîy = (y1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
