Диссертация (1149954), страница 12
Текст из файла (страница 12)
àññìàòðèâàåì âñåO(k n pm )âîçìîæíûõ ñîñòîÿíèé ñèñòåìû.2. Äëÿ êàæäîãî ñîñòîÿíèÿ âûáèðàåì îäíî èçO(k n pm )óïðàâëåíèé, ðåøàÿ îïòèìèçàöèîí-íóþ çàäà÷ó ìåòîäîì ïåðåáîðà.Èòîãî, ñëîæíîñòü ðåøåíèÿ çàäà÷è ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ ðàâíàO(T (k n pm )2 ) = O(T k 2n p2m ).À ñëîæíîñòü ðåøåíèÿ ïîëíûì ïåðåáîðîì ñîñòàâëÿëà áûO((k n pm )T ) = O(k T n pT m ),÷òî ãîðàçäî áîëüøå, ÷åì ïðè ïðèìåíåíèè ìåòîäà äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ.Àëãîðèòì ëåãêî îáîáùàåòñÿ íà ñëó÷àé, êîãäà çàäàíî ìíîæåñòâî âñåõ äîïóñòèìûõ íà÷àëüíûõ ïîòîêîâF0è ìíîæåñòâî âñåõ äîïóñòèìûõ êîíå÷íûõ ïîòîêîâFT íàïðèìåð, â òîì ñëó-÷àå, êîãäà çàäàíî óñëîâèå ïðèáûòèÿ âñåõ (èëè çàäàííîãî ÷èñëà) åäèíèö ïîòîêà â êîíå÷íóþâåðøèíó.  ýòîì ñëó÷àå ïðîñòî íóæíî íà íà÷àëüíîì,òîêîâf (T ),óäîâëåòâîðÿþùåå óñëîâèþóíêöèè Áåëëìàíàg1 (f (0))ïîf (T ) ∈ FT ,T -ì øàãå ðàññìàòðèâàòü ìíîæåñòâî ïî-à íà êîíå÷íîì, 1-ì øàãå âçÿòü ìàêñèìóìf (0) ∈ F0 .àññìîòðèì ãðà ñîîòâåòñòâóþùåé óïðàâëÿåìîé äèíàìè÷åñêîé ñèñòåìû. Ïðè îáðàùåíèèîðèåíòàöèè âñåõ åãî äóã ãðà îñòàíåòñÿ ãðàîì, à çíà÷åíèÿ óíêöèè ñòîèìîñòè íà âñåõ ïóòÿõ îñòàíóòñÿ òàêèìè æå).
Ñëåäîâàòåëüíî, ìîæíî ðàçâåðíóòü àëãîðèòì â ïðîòèâîïîëîæíîìíàïðàâëåíèè, äâèãàÿñü íå îò êîíå÷íîãî ìíîæåñòâàFTíàçàä, à îò íà÷àëüíîãî ìíîæåñòâàâïåðåä. Ïðè ýòîì ìû ïîëó÷àåì âñå îïòèìàëüíûå ïîòîêè, íà÷èíàþùèåñÿ âF0 .F053ëàâà 2Äèíàìè÷åñêèå íåñòðàòåãè÷åñêèåìíîãîêðèòåðèàëüíûå çàäà÷è íà ñåòÿõÊàê èçâåñòíî, â íàóêå âîçìîæíû ìîäåëè äâóõ òèïîâ: äåñêðèïòèâíûå (îïèñàòåëüíûå) è íîðìàòèâíûå (îïòèìèçàöèîííûå). Ýêîíîìèêà íàóêà, â êîòîðîé ïðåîáëàäàþò îïòèìèçàöèîííûåìîäåëè â îñîáåííîñòè, â ìèêðîýêîíîìèêå.
Îïòèìèçàöèîííàÿ ìîäåëü ïðåäïîëàãàåò çàäàíèåêðèòåðèåâ îïòèìàëüíîñòè. Áóäåì ñ÷èòàòü, ÷òî êðèòåðèè îïòèìàëüíîñòèìåðÿþòñÿ ýëåìåíòàìè èç óïîðÿäî÷åííûõ ìíîæåñòâ:fi (x) ∈ Y ,xãäåf1 (x), . . . , fn (x)èç- ñîñòîÿíèå ñèñòåìû,ìåíÿþùååñÿ ñ òå÷åíèåì âðåìåíè.Äèíàìè÷åñêèå ñèñòåìû, êàê èçâåñòíî, äåëÿòñÿ íà ñëåäóþùèå êëàññû:1.Äåòåðìèíèðîâàííûå2.Ñòîõàñòè÷åñêèå áóäóùåå îäíîçíà÷íî çàâèñèò îò ïðîøëîãî; çàâèñèìîñòü áóäóùåãî îò ïðîøëîãî ïîä÷èíÿåòñÿ íåêîòîðîìó ðàñ-ïðåäåëåíèþ âåðîÿòíîñòåé;3.Ñèñòåìû ñ íåîïðåäåëåííîñòüþìåòðû(a) èìåþòñÿ íåêîòîðûå âíåøíèå íåîïðåäåëåííûå ïàðà-u1 , .
. . , un :Óïðàâëÿåìûå âñå íåîïðåäåëåííûå ïàðàìåòðûuiîïðåäåëÿþòñÿ óïðàâëåíèÿìèñóáúåêòîâ ñ èçâåñòíûìè öåëÿìè:i. Óïðàâëåíèå îäíîãî ñóáúåêòàuçàäà÷à óïðàâëåíèÿèëèîïòèìèçàöèîííàÿçàäà÷à.ii. Óïðàâëåíèå íåñêîëüêèõ ñóáúåêòîâçàöèîííàÿ çàäà÷à(b)Íåóïðàâëÿåìûåèëèu = (u1 , . . . , un )ìíîãîàãåíòíàÿ îïòèìè-ñòðàòåãè÷åñêàÿ èãðà. åñòü íåîïðåäåëåííûå ïàðàìåòðûun+1,êîòîðûå íå çàâèñÿò îòóïðàâëåíèé èëè çàâèñÿò îò óïðàâëåíèé ñ íåèçâåñòíûìè öåëÿìè; ãîâîðÿò, ÷òî ýòî54óïðàâëåíèÿïðèðîäû.Ìû äëÿ ïðîñòîòû ðàññìàòðèâàåì ñëó÷àé, êîãäà âñå âîçäåéñòâèÿ íà ñèñòåìó èñõîäÿò îòèçâåñòíûõ ñóáúåêòîâ (â îáùåì ñëó÷àå, èõ áîëüøå îäíîãî) è íåò ñòîõàñòè÷åñêèõ âîçäåéñòâèé.Ïîäîáíûå ñèñòåìû ìîäåëèðóþòñÿ ñòðàòåãè÷åñêèìè èãðàìè.
Åñëè êîëè÷åñòâî óïðàâëÿþùèõñóáúåêòîân = 1, ïîëó÷àåì çàäà÷ó ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè. Òàêèì îáðàçîì, ìíîãî-êðèòåðèàëüíûå ìîäåëè ÷àñòíûé ñëó÷àé èãðîâûõ ìîäåëåé.  äàííîé ãëàâå ðàññìàòðèâàþòñÿìíîãîêðèòåðèàëüíûå ìîäåëè, â ñëåäóþùåé ãëàâå èãðîâûå.àññìîòðåííûå çàäà÷è ýòî ñî÷åòàíèå òðåõ êëàññîâ îïòèìèçàöèîííûõ çàäà÷: äèíàìè÷åñêèõ, ìíîãîêðèòåðèàëüíûõ è ñåòåâûõ. Ñîîòâåòñòâåííî ýòè 3 êëàññà çàäà÷ ïîðîæäàþò òàêèåñî÷åòàíèÿ:1. Äèíàìè÷åñêèå ìíîãîêðèòåðèàëüíûå çàäà÷è. àññìîòðåíû çàäà÷è ñ îáîáùåííûì èíòåãðàëüíûì âûèãðûøåì, âêëþ÷àþùèå â ñåáÿ çàäà÷è ñ èíòåãðàëüíûì, òåðìèíàëüíûì âûèãðûøåì, çàäà÷è íà óêëîíåíèå è ìíîãèå äðóãèå.
Ïîñòðîåíû ýåêòèâíûå àëãîðèòìûíàõîæäåíèÿ âñåõ îïòèìóìîâ Ïàðåòî äëÿ êîíå÷íîãî ìíîæåñòâà àëüòåðíàòèâ.2. Ìíîãîêðèòåðèàëüíûå ñåòåâûå çàäà÷è äëÿ ñåòè ñ èêñèðîâàííîé ñòðóêòóðîé èõ ìîæíî èíòåðïðåòèðîâàòü êàê ìíîãîêðèòåðèàëüíóþ îïòèìèçàöèþ îáîáùåííûõ ïîòîêîâ âñåòÿõ. Ïîñòðîåíû àëãîðèòìû îïòèìèçàöèè äëÿ âàæíûõ ÷àñòíûõ ñëó÷àåâ.3. Äèíàìè÷åñêèå ñåòåâûå ìíîãîêðèòåðèàëüíûå çàäà÷è ìíîãîêðèòåðèàëüíàÿ îïòèìèçàöèÿ îáîáùåííûõ äèíàìè÷åñêèõ ïîòîêîâ â ñåòÿõ. Ïîñòðîåíû äâà àëãîðèòìà íàõîæäåíèÿîïòèìàëüíîãî ïîòîêà: ïóòåì ñâåäåíèÿ äèíàìè÷åñêîãî ïîòîêà ê ñòàòè÷åñêîìó è ìåòîäîìäèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ. Ïðèâåäåíû ïðèìåðû ýêîíîìè÷åñêèõ ñèñòåì, îïòèìèçàöèÿ êîòîðûõ ñâîäèòñÿ ê ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè äèíàìè÷åñêèõ ïîòîêîâ,íàéäåíû îïòèìàëüíûå ðåøåíèÿ.2.1Äèíàìè÷åñêèå ìíîãîêðèòåðèàëüíûå çàäà÷èÏðè îïòèìèçàöèè óïðàâëÿåìûõ äèíàìè÷åñêèõ ñèñòåì ñ äèñêðåòíûì âðåìåíåì âî ìíîãèõñëó÷àÿõ öåëåñîîáðàçíî ïðèìåíÿòü ðåêóððåíòíûå ñîîòíîøåíèÿ äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, ââåäåííûå Áåëëìàíîì [6℄.
Íî â çàäà÷àõ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè, êàê è âèãðîâûõ çàäà÷àõ, ýòè ñîîòíîøåíèÿ íå âñåãäà âûïîëíÿþòñÿ [51℄. Èõ, îáû÷íî, ñâÿçûâàþò ñïðèíöèïîì äèíàìè÷åñêîé óñòîé÷èâîñòè, ñîãëàñíî êîòîðîìó êîíå÷íûé ó÷àñòîê îïòèìàëüíîéòðàåêòîðèè òàêæå îïòèìàëåí, õîòÿ, êàê áóäåò ïîêàçàíî äàëüøå, â îáùåì ñëó÷àå ïðèìåíè-55ìîñòü ìåòîäà äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ ìîæåò íå ñëåäîâàòü èç äèíàìè÷åñêîé óñòîé÷èâîñòè, è îáðàòíîå ñëåäîâàíèå òàêæå ìîæåò áûòü íåâåðíî. ðàáîòå ðàññìîòðåíû êàê çàäà÷è ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ñ èíòåãðàëüíûìèêðèòåðèÿìè îïòèìàëüíîñòè (ñóììà çíà÷åíèé ïî âñåì òî÷êàì òðàåêòîðèè), òàê è ñ òåðìèíàëüíûìè (çíà÷åíèå â êîíå÷íîé òî÷êå òðàåêòîðèè). Ïðè ýòîì çíà÷åíèå êðèòåðèÿ ìîã áûòü êàê÷èñëîì, òàê è âåêòîðîì. Ïðåäïîëàãàåòñÿ, ÷òî êðèòåðèé îïòèìàëüíîñòè ïðèíèìàåò çíà÷åíèåèç ïðîèçâîëüíîé óïîðÿäî÷åííîé ïîëóãðóïïû.
 êà÷åñòâå ïðèíöèïà îïòèìàëüíîñòè ðàññìàòðèâàåòñÿ îïòèìàëüíîñòü ïî Ïàðåòî. Îñíîâíûå ðåçóëüòàòû ýòîãî ðàçäåëà äëÿ êðèòåðèåâ èçóïîðÿäî÷åííûõ ïîëóãðóïï îïóáëèêîâàíû â [46℄.2.1.1Ñåìåéñòâî äèíàìè÷åñêèõ ìíîãîêðèòåðèàëüíûõ çàäà÷ è êðèòåðèè îïòèìàëüíîñòèÏóñòü èìååòñÿ äèíàìè÷åñêàÿ ñèñòåìàìåíåìT = {1, . .
. , m}Dñ ïðîñòðàíñòâîì ñîñòîÿíèéè ìíîæåñòâàìè óïðàâëåíèéU(x, t),X,ñ äèñêðåòíûì âðå-çàäàííûõ äëÿ êàæäîãî ñîñòîÿ-íèÿ ñèñòåìû â êàæäûé ìîìåíò âðåìåíè. Âîçìîæíà ïîñòàíîâêà ìíîãîêðèòåðèàëüíûõ çàäà÷îïòèìèçàöèè êàê äëÿ îáû÷íûõ ÎÄÑ ñ äèñêðåòíûì âðåìåíåì, òàê è äëÿ óïðàâëÿåìûõ. Âïåðâîì ñëó÷àå ïðîèçâîäèòñÿ âûáîð îïòèìàëüíîé òðàåêòîðèè, âî âòîðîì ñëó÷àå îïòèìàëüíîãî ïîçèöèîííîãî (ïðîãðàììíî-àäàïòèâíîãî) óïðàâëåíèÿu(x, t),çàâèñÿùåãî îò âðåìåíè èñîñòîÿíèÿ ñèñòåìû [6℄.
Ïîçèöèîííîå óïðàâëåíèå, êàê ñêàçàíî â ðàçäåëå 1, òàêæå îïðåäåëÿåòåäèíñòâåííóþ òðàåêòîðèþ.àññìîòðèì çàäà÷ó âûáîðà òðàåêòîðèèùåéñÿ â çàäàííîé òî÷êåx1h èëè ïðîãðàììíîãî óïðàâëåíèÿ u ÎÄÑ, íà÷èíàþ-è óäîâëåòâîðÿþùåé íåêîòîðîìó íàáîðó êðèòåðèåâ îïòèìàëüíîñòèf1 , . . . , fn :max (f1 (h(1), h(2), . .
. , h(m)), . . . , fn (h(1), h(2), . . . , h(m))),h∈P (x1 )ãäåP (x) ìíîæåñòâî òðàåêòîðèé ñèñòåìû, íà÷èíàþùèõñÿ â òî÷êåx,ïðèíèìàþò çíà÷åíèÿ â íåêîòîðîì ëèíåéíî óïîðÿäî÷åííîì ìíîæåñòâåà êðèòåðèè(R, <).f1 , . . . , fnÄàëåå, ãîâî-ðÿ îá óïîðÿäî÷åííîì ìíîæåñòâå, âñåãäà áóäåì èìåòü â âèäó ëèíåéíûé ïîðÿäîê, åñëè ýòîíå îãîâàðèâàåòñÿ îñîáî. Òî åñòü çàäà÷à ñâîäèòñÿ ê âûáîðó èç ïðîèçâîëüíîãî óïîðÿäî÷åííîãî ìíîæåñòâà àëüòåðíàòèâ(R, ∗, <).(R, <) èëè, ÷òî ýêâèâàëåíòíî, èç óïîðÿäî÷åííîé ïîëóãðóïïûÄåéñòâèòåëüíî, ëþáîå óïîðÿäî÷åííîå ìíîæåñòâî ìîæíî ïðåäñòàâèòü êàê óïîðÿäî-÷åííóþ ïðàâîñèíãóëÿðíóþ ïîëóãðóïïó, â êîòîðîé îïåðàöèÿÂàæíåéøèå ÷àñòíûå ñëó÷àè êðèòåðèåâ îïòèìàëüíîñòè∗ çàäàåòñÿ ñîîòíîøåíèåì a∗b = b.f1 , .
. . , fn :561.Òåðìèíàëüíàÿ ïîëåçíîñòü (òåðìèíàëüíûé âûèãðûø ):fi (h(1), . . . , h(m)) = fi (h(m));2.Èíòåãðàëüíàÿ ïîëåçíîñòü (èíòåãðàëüíûé âûèãðûø ):fi (h(1), . . . , h(m)) = fi1 (h(1)) + fi2 (h(2)) + · · · + fim (h(m))ãäå3.(R, +, ·, <) óïîðÿäî÷åííîå ïîëå;Îáîáùåííàÿ èíòåãðàëüíàÿ ïîëåçíîñòü (îáîáùåííûé èíòåãðàëüíûé âûèãðûø ):f (h(1), . . . , h(m)) = fi1 (h(1)) ∗ · · · ∗ fim (h(m))ãäå(R, ∗, <) óïîðÿäî÷åííàÿ ïîëóãðóïïà âêëþ÷àåò â ñåáÿ äâà ïðåäûäóùèõ ñëó÷àÿ.Àëãåáðàè÷åñêèé ïîäõîä ê êðèòåðèÿì îïòèìàëüíîñòè ïîçâîëÿåò îáîáùèòü çàäà÷è îïòèìèçàöèè, â êîòîðûõ êðèòåðèè îïòèìàëüíîñòè ñóììà çíà÷åíèé ïî òðàåêòîðèè, ïðîèçâåäåíèåçíà÷åíèé, òåðìèíàëüíûé ðåçóëüòàò, íàèìåíüøåå óêëîíåíèå è ò.ï. Ïðè ýòîì âûèãðûø ìîæåòáûòü êàê ÷èñëîì, òàê è âåêòîðîì.Äèíàìè÷åñêàÿ óñòîé÷èâîñòü [51℄ îïðåäåëÿåòñÿ íå äëÿ îäíîé îïòèìèçàöèîííîé çàäà÷è, àäëÿ öåëîãî ñåìåéñòâà çàäà÷, çàäàííûõ â ðàçíûå ìîìåíòû âðåìåíè â ðàçíûõ íà÷àëüíûõ óñëîâèÿõ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
