Диссертация (1149954), страница 14
Текст из файла (страница 14)
, yn ) ∈f (X) âåðõíèé êîíóñ ýòî ïåðåñå÷åíèå îãðàíè÷åííîãî îáîáùåííîãî ìíîãîãðàííîãî ìíîæåñòâàf (X)ñ îáîáùåííûì ìíîãîãðàííûì ìíîæåñòâîì[y1 ; ∞) × · · · × [yn ; ∞),à ñëåäî-âàòåëüíî, ýòî îãðàíè÷åííîå îáîáùåííîå ìíîãîãðàííîå ìíîæåñòâî, äëÿ êîòîðîãî âûïîëíÿåòñÿ óñëîâèå ñóùåñòâîâàíèÿ.Òåïåðü òðàíçèòèâíîñòü Ïàðåòî-îïòèìàëüíîñòè ñëåäóåò èç ëåììû.612.1.3Ïðèíöèïû äèíàìè÷åñêîé óñòîé÷èâîñòè çàäà÷ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè è èõ âçàèìîñâÿçüÍàïîìíèì òåïåðü îñíîâíûå ïîíÿòèÿ, ñâÿçàííûå ñ äèíàìè÷åñêîé óñòîé÷èâîñòüþ, êîòîðûåèñïîëüçóþòñÿ â òåîðèè äèíàìè÷åñêèõ ìíîãîêðèòåðèàëüíûõ çàäà÷ è ïîçèöèîííûõ èãð [51,76, 77℄.Çàìå÷àíèå2.1.4. Äèíàìè÷åñêàÿ óñòîé÷èâîñòü, â îòëè÷èå îò óñòîé÷èâîñòè ïî Ëÿïóíîâó,àñèìïòîòè÷åñêîé óñòîé÷èâîñòè, è ò. ï.
íå òðåáóåò íèêàêîé òîïîëîãèè ýòî äèñêðåòíûé ïðèíöèï îòáîðà.Ñâîéñòâà äèíàìè÷åñêîé óñòîé÷èâîñòè èìåþò ìåñòî äëÿ ñåìåéñòâà îïòèìèçàöèîííûõ çàäà÷(P (x), (f1 , . . . , fn )) è èõ îïòèìàëüíûõ òðàåêòîðèé òî åñòü òàêèõ òðàåêòîðèé, íà êîòîðûõäîñòèãàåòñÿ îïòèìóì ïî êðèòåðèÿìÎïðåäåëåíèå 19.f1 , . . . , fn .Îïòèìàëüíàÿ òðàåêòîðèÿâ ÑÄÎÇ, åñëè ëþáàÿ åå ïîäòðàåêòîðèÿh íàçûâàåòñÿ (ñëàáî) äèíàìè÷åñêè óñòîé÷èâîé(h(t), h(t+1), h(t+2), . . .
, h(m)) ÿâëÿåòñÿ îïòèìàëüíîéâ çàäà÷å äëÿ ïîäñèñòåìû, îïðåäåëÿåìîé ïîçèöèåéÎïðåäåëåíèå 20.Áåëëìàíà(t, h(t)),Áóäåì ãîâîðèòü, ÷òî äëÿ ÑÄÎÇ âûïîëíÿåòñÿèëè ÷òî îíî ÿâëÿåòñÿïðèíöèï îïòèìàëüíîñòè(ñëàáî) äèíàìè÷åñêè óñòîé÷èâûì, åñëè âñå åãî îïòèìàëüíûåòðàåêòîðèè ÿâëÿþòñÿ äèíàìè÷åñêè óñòîé÷èâûìè.Èíà÷å ãîâîðÿ, ïðèíöèï Áåëëìàíà îçíà÷àåò, ÷òî åñëè òðàåêòîðèÿ ÿâëÿåòñÿ îïòèìàëüíîé,òî è ëþáàÿ åå êîíå÷íàÿ ïîäòðàåêòîðèÿ ÿâëÿåòñÿ îïòèìàëüíîé.Îïðåäåëåíèå 21.Îïòèìàëüíàÿ òðàåêòîðèÿh,íàçûâàåòñÿäèíàìè÷åñêè ñîâìåñòèìîéÑÄÎÇ, åñëè îíà äèíàìè÷åñêè óñòîé÷èâà è, êðîìå òîãî, äëÿ ëþáîãî ìîìåíòàåêòîðèèh′ = (h(t), h′ (t + 1), h′ (t + 2), .
. . h′ (m)), îïòèìàëüíîéh′′ = (h(1), h(2), . . . , h(t), h′ (t + 1), . . . , h′ (m))â ïîäçàäà÷åäëÿt äëÿ ëþáîé òðà-(h(t), t), òðàåêòîðèÿ(ñîñòàâëåííàÿ èç ñòàðîé òðàåêòîðèè, ê êîòîðîéïðèñîåäèíåí êîíå÷íûé ó÷àñòîê íîâîé) òàêæå îïòèìàëüíà.Èíà÷å ãîâîðÿ, åñëè òðàåêòîðèÿ îïòèìàëüíà, òî ìîæíî â ëþáîé ìîìåíò âðåìåíè åå ìîäèèöèðîâàòü, ïåðåéäÿ ê äðóãîé îïòèìàëüíîé ïîäòðàåêòîðèè ðåçóëüòèðóþùàÿ òðàåêòîðèÿáóäåò ïðîäîëæàòü îñòàâàòüñÿ îïòèìàëüíîé.
Çàìåòèì, êñòàòè, ÷òî äèíàìè÷åñêàÿ ñîâìåñòèìîñòü òðàåêòîðèè îòíþäü íå ãàðàíòèðóåò äèíàìè÷åñêóþ ñîâìåñòèìîñòü ïîäòðàåêòîðèé è,òåì áîëåå, ìîäèèöèðîâàííûõ òðàåêòîðèé. Ïîýòîìó î÷åíü âàæíî ñëåäóþùåå îïðåäåëåíèå:Îïðåäåëåíèå 22.ÑÄÎÇ íàçûâàåòñÿäèíàìè÷åñêè ñîâìåñòèìûìòðàåêòîðèè è ïîäòðàåêòîðèè äèíàìè÷åñêè ñîâìåñòèìû.[77℄, åñëè âñå îïòèìàëüíûå62Äëÿ òîãî, ÷òîáû îáîñíîâàòü ðåêóððåíòíûå ñîîòíîøåíèÿ äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, íóæíà íå äèíàìè÷åñêàÿ ñîâìåñòèìîñòü, à èíîé âèä äèíàìè÷åñêîé óñòîé÷èâîñòè[76, 58℄. Ïðè ýòîì îïòèìóì èùåòñÿ óæå íå ïî òðàåêòîðèÿì, à ïî ïîçèöèîííûì (ïðîãðàììíîàäàïòèâíûì) óïðàâëåíèÿìu.Íî â íåêîòîðîì ðîäå ìíîæåñòâà òðàåêòîðèé è ìíîæåñòâàïðîãðàììíî-àäàïòèâíûõ óïðàâëåíèé ýêâèâàëåíòíû:Óòâåðæäåíèå 2.1.1. Êàæäîìó ïðîãðàììíî-àäàïòèâíîìó óïðàâëåíèþ u(x, t) äëÿ êàæäîéíà÷àëüíîé òî÷êè è ìîìåíòà âðåìåíè (x0 , t0 ) ñîîòâåòñòâóåò åäèíñòâåííàÿ ñîâìåñòèìàÿñ íèì òðàåêòîðèÿ h(t), ò.å.
òàêàÿ, ÷òîh(t0 ) = x0 h(t + 1) = π(h(t), t, u(h(t), t))Äîêàçàòåëüñòâî.Î÷åâèäíî, ïî èíäóêöèè.Ìîæíî äîêàçàòü è îáðàòíîå óòâåðæäåíèÿ î ñóùåñòâîâàíèè äëÿ êàæäîé òðàåêòîðèè ñîâìåñòèìîãî ñ íåé ïðîãðàììíî-àäàïòèâíîãî óïðàâëåíèÿ.  ÷àñòíîñòè, ýòî óòâåðæäåíèå ñëåäóåòèç àêñèîìû âûáîðà. Îäíàêî, íå áóäåì ïðèâëåêàòü àêñèîìó âûáîðà, à èñïîëüçóåì áîëåå î÷åâèäíóþ è áîëåå ñëàáóþ àêñèîìó:Àêñèîìà 2.1.1(àêñèîìà âûáîðà äëÿ óïðàâëåíèé).Äëÿ êàæäîé ÎÄÑ i ñóùåñòâóåò õîòÿáû îäíî ïðîãðàììíî-àäàïòèâíîå óïðàâëåíèå u∗ (x, t) (áóäåì íàçûâàòü åãîóïðàâëåíèåì ïîóìîë÷àíèþ).Ïðè ìîäåëèðîâàíèè ðåàëüíûõ ñèñòåì ýòà àêñèîìà îçíà÷àåò, ÷òî ëèöî, ïðèíèìàþùåå ðåøåíèÿ, ìîæåò ïðèíÿòü ðåøåíèå âñåãäà (âàðèàíò áóðèäàíîâà îñëà èñêëþ÷àåòñÿ). õîòÿ îíîïðè ýòîì è íå îáÿçàíî áûòü îïòèìàëüíûì. Äëÿ êîíå÷íûõ ìíîæåñòââñåãäà âûïîëíÿåòñÿ, áëàãîäàðÿ íåïóñòîòå ìíîæåñòâX, Tàêñèîìà, ðàçóìååòñÿ,U(x, t).Óòâåðæäåíèå 2.1.2.
Åñëè âåðíà àêñèîìà âûáîðà äëÿ óïðàâëåíèé, òî äëÿ êàæäîé òðà-åêòîðèè ñóùåñòâóåò õîòÿ áû îäíî (âîçìîæíî, íå åäèíñòâåííîå) ñîâìåñòèìîå ñ íåéïðîãðàììíî-àäàïòèâíîå óïðàâëåíèå.Äîêàçàòåëüñòâî.Äîêàæåì àíàëîãè÷íî òîìó, êàê ýòî ñäåëàíî â óòâåðæäåíèè 2.2.4 èç [57℄.Ïóñòü äàíà òðàåêòîðèÿh.àññìîòðèì óïðàâëåíèå ïî óìîë÷àíèþïîçèöèé, ëåæàùèõ íà òðàåêòîðèèèçh(t)âh(t + 1)ñîâìåñòèìîå ñh.h(t),u∗ (x, t).Òåïåðü äëÿ âñåõçàìåíèì óïðàâëåíèÿ íà òàêèå, êîòîðûå äàþò ïåðåõîä ýòî âñåãäà âîçìîæíî ïî ñþðúåêòèâíîñòèπ.Ïîëó÷èì óïðàâëåíèåu(x, t),63Îïðåäåëåíèå 23.Íàçîâåì ïîçèöèîííîå (ïðîãðàììíî-àäàïòèâíîå) óïðàâëåíèåäèíàìè÷åñêè óñòîé÷èâûì (êîíñåêâåíöèàëüíûì)îïòèìàëüíûì â çàäà÷å äëÿ êàæäîé ïîäñèñòåìûÇàìå÷àíèåu ïîçèöèîííî[76, 58℄ â ÑÄÎÇ, åñëè îíî òàêæå ÿâëÿåòñÿD(x,t) .2.1.5. Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî îíî òàêæå ÿâëÿåòñÿ ïîçèöèîííî äèíàìè÷åñêèóñòîé÷èâûì â çàäà÷å äëÿ êàæäîé ïîäñèñòåìû.Ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâîå ïîçèöèîííîå óïðàâëåíèå, åñëè îíî ñóùåñòâóåò,î÷åíü óäîáíî.
Âåäü îíî ðåøàåò îäíèì ìàõîì ñðàçó âñå ñåìåéñòâî çàäà÷. Çàìåòèì îäíàêî,÷òî â íåòðèâèàëüíîì ÑÄÎÇ âñå ðåøåíèÿ íå ìîãóò áûòü ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâûìè (õîòÿ ìîæåò áûòü òàêîå, ÷òî âñå ðåøåíèÿ äèíàìè÷åñêè ñîâìåñòèìû). Âåäü äëÿ ëþáîãîîïòèìàëüíîãî ïîçèöèîííîãî óïðàâëåíèÿ ýêâèâàëåíòíîå óïðàâëåíèå òàêæå îïòèìàëüíî àýêâèâàëåíòíîå óïðàâëåíèå ìîæåò îïðåäåëÿòüñÿ âíå òðàåêòîðèè êàê óãîäíî.Äàäèì òåïåðü îïðåäåëåíèå ðåêóððåíòíûõ ñîîòíîøåíèé äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ:Îïðåäåëåíèå 24.Ïóñòü äàíî íåêîòîðîå ÑÄÎÇ íà ïðîñòðàíñòâåðåêóððåíòíàÿ ñòðàòåãèÿ (ðåêóððåíòíîå óïðàâëåíèå )Xñ âðåìåíåìT.
ýòî ïîçèöèîííîå óïðàâëåíèåÒîãäàu(x, t),óäîâëåòâîðÿþùåå ñëåäóþùèì ðåêóððåíòíûì ñîîòíîøåíèÿì:u(x, t) ∈ argu(x,t) Par(f1 (x,t) ,...,fn (x,t) ) ({h ∈ P (x, t) | ∀t′ > t h(t′ + 1) = π(h(t′ ), t′ , u(h(t′ ), t′ ))}(2.1)Òî åñòü ýòî óïðàâëåíèå, îïðåäåëÿåìîå ñëåäóþùèì îáðàçîì ïîñëåäîâàòåëüíî ñ êîíöà:åñëè, íà÷èíàÿ ñ ìîìåíòàt+1, óïðàâëåíèå ïîñ÷èòàíî, òî äëÿ ìîìåíòà t âûáèðàåì óïðàâëåíèå,êîòîðîå äàåò îïòèìàëüíóþ èç ïîëó÷àþùèõñÿ òðàåêòîðèé äëÿ ñîîòâåòñòâóþùåé ïîäñèñòåìû.Èíà÷å ãîâîðÿ, íà êàæäîì øàãå ìû ðåøàåì îäíîìåðíóþ ïîäçàäà÷ó èñõîäíîé ìíîãîìåðíîéçàäà÷è.
Íàïðèìåð äëÿ îáû÷íîé îïòèìèçàöèîííîé çàäà÷è íóæíî çàìåíèòüìàêñèìèçàöèèParfíà îïåðàòîðarg max.àçóìååòñÿ, ðåêóððåíòíîå óïðàâëåíèå ìîæåò áûòü íå åäèíñòâåííûì äàæå äëÿ îáû÷íîéîïòèìèçàöèîííîé çàäà÷è, ïîñêîëüêó ìàêñèìóì ìîæåò äîñòèãàòüñÿ íà íåñêîëüêèõ òðàåêòîðèÿõ.Òåîðåìà 7(î ñâÿçè ïðèíöèïîâ äèíàìè÷åñêîé óñòîé÷èâîñòè).1. Åñëè òðàåêòîðèÿ äèíà-ìè÷åñêè ñîâìåñòèìà, îíà äèíàìè÷åñêè óñòîé÷èâà.2. Åñëè ÑÄÎÇ äèíàìè÷åñêè ñîâìåñòèìî, îíî äèíàìè÷åñêè óñòîé÷èâî (ò.å., âûïîëíÿåòñÿïðèíöèï Áåëëìàíà).643. Åñëè ïîçèöèîííîå óïðàâëåíèå ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâî, îíî ïîðîæäàåò äèíàìè÷åñêè óñòîé÷èâûå (íî íå îáÿçàòåëüíî äèíàìè÷åñêè ñîâìåñòèìûå) òðàåêòîðèè.4. Åñëè óïðàâëåíèå äèíàìè÷åñêè óñòîé÷èâî è âûïîëíÿåòñÿ àêñèîìà íåçàâèñèìîñòè îòïîñòîðîííèõ àëüòåðíàòèâ, òî îíî ðåêóððåíòíî ïî âñåé òðàåêòîðèè.5.
Åñëè óïðàâëåíèå ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâî è âûïîëíÿåòñÿ àêñèîìà íåçàâèñèìîñòè îò ïîñòîðîííèõ àëüòåðíàòèâ, òî îíî ðåêóððåíòíî.Äîêàçàòåëüñòâî.1. Íåïîñðåäñòâåííî ñëåäóåò èç îïðåäåëåíèÿ 21.2. Íåïîñðåäñòâåííî ñëåäóåò èç îïðåäåëåíèÿ 22.3. Ñëåäóåò èç òîãî, ÷òî îïòèìàëüíîå óïðàâëåíèå ïîðîæäàåò îïòèìàëüíóþ òðàåêòîðèþ. Àïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâîå óïðàâëåíèå îïòèìàëüíî äëÿ âñåõ ïîäñèñòåì.4. Äåéñòâèòåëüíî, äèíàìè÷åñêè óñòîé÷èâîå óïðàâëåíèåx∗ (t)íà êàæäîì øàãåtòðàåêòî-ðèè äîñòàâëÿåò îïòèìóì äëÿ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèîííîé çàäà÷è èç ïîçèöèè(x∗ (t), t).
Ïðè ýòîì îíî ïðèíàäëåæèò îáëàñòè îïðåäåëåíèÿ îäíîìåðíîé ïîäçàäà÷è, à çíà÷èò, ñîãëàñíî íåçàâèñèìîñòè îò ïîñòîðîííèõ àëüòåðíàòèâ, äîñòàâëÿåò îïòèìóì è äëÿîäíîìåðíîé ïîäçàäà÷è.5. Ñëåäóåò èç ï.3,4.Çàìå÷àíèå2.1.6. Äàæå äëÿ îïòèìèçàöèîííîé çàäà÷è ñ îäíèì êðèòåðèåì ìîæíî ïðèâåñòèïðîñòåéøèå êîíòðïðèìåðû ÑÄÎÇ ñ ïðèíöèïîì îïòèìàëüíîñòè Áåëëìàíà, â êîòîðûõ ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâîå óïðàâëåíèå íå ïîðîæäàåò äèíàìè÷åñêè ñîâìåñòèìóþ òðàåêòîðèþ è íå âñå ðåêóððåíòíûå óïðàâëåíèÿ îïòèìàëüíû.Ïðèìåð 9.Àâòîíîìíàÿ ñèñòåìà ñX = {1, 2, 3, 4}, T = {1, 2}, D(1) = 2, D(2) = {3, 4},âûèãðûø äëÿ îñíîâíîé çàäà÷è îïðåäåëÿåòñÿ òàê:ïîäçàäà÷è òàê:f (2, 3) = f (2, 4) = 1.f (1, 2, 3) = 1, f (1, 2, 4) = 2, à âûèãðûø îñíîâíîé çàäà÷å îïòèìàëüíà òðàåêòîðèÿàäëÿ(1, 2, 4),àâ çàäà÷å äëÿ ïîäñèñòåìû îïòèìàëüíû îáå òðàåêòîðèè.
Ýòî çíà÷èò, ÷òî âûïîëíÿåòñÿ ïðèíöèï Áåëëìàíà. Óïðàâëåíèåòðàåêòîðèÿ(1, 2, 4)u(1) = 2, u(2) = 4ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâî. Îäíàêîíå ÿâëÿåòñÿ äèíàìè÷åñêè ñîâìåñòèìîé, ïîñêîëüêó, çàìåíèâ åå êîíå÷íûéó÷àñòîê íà òðàåêòîðèþ(2, 3),íåîïòèìàëüíóþ òðàåêòîðèþòàêæå îïòèìàëüíóþ â çàäà÷å äëÿ ïîäñèñòåìû, ïîëó÷èì óæå(1, 2, 3).Óïðàâëåíèåu(1) = 2, u(2) = 3ðåêóððåíòíî, íî îíî íåÿâëÿåòñÿ îïòèìàëüíûì, ïîñêîëüêó ïîðîæäàåò íåîïòèìàëüíóþ òðàåêòîðèþ ñåìåéñòâî çàäà÷ íå ÿâëÿåòñÿ åñòåñòâåííûì.(1, 2, 3). Ïðè÷èíà652.1.4Òåîðåìà î äèíàìè÷åñêîé óñòîé÷èâîñòè ìíîãîêðèòåðèàëüíûõçàäà÷ äëÿ êðèòåðèåâ îáîáùåííûõ èíòåãðàëüíûõ âûèãðûøåé [77℄ äîêàçàíî, ÷òî îïòèìóìû Ïàðåòî (êàê è ëþáûå ìàêñèìóìû ïî îòíîøåíèþ ÷àñòè÷íîãî ïîðÿäêà) äëÿ òåðìèíàëüíûõ ïîëåçíîñòåé äèíàìè÷åñêè ñîâìåñòèìû.
 [76℄ äîêàçàíî, ÷òîðåêóððåíòíûå óïðàâëåíèÿ ïî òåðìèíàëüíûì îïòèìóìàì Ïàðåòî îïòèìàëüíû è ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâû. Ïîñìîòðèì òåïåðü, âûïîëíÿþòñÿ ëè àíàëîãè÷íûå ñâîéñòâà äëÿèíòåãðàëüíûõ ïîëåçíîñòåé.Òåîðåìà 8(î äèíàìè÷åñêîé óñòîé÷èâîñòè îáîáùåííîãî èíòåãðàëüíîãî âûèãðûøà).ÏóñòüR ñòðîãî ñëåâà ëèíåéíî ëåâî-óïîðÿäî÷åííàÿ ïîëóãðóïïà è ëþáîé êðèòåðèé f (x) = f1 (x1 ) ∗· · · ∗ fm (xm ) îáîáùåííûé èíòåãðàëüíûé âûèãðûø.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
