Автореферат (1149953), страница 2
Текст из файла (страница 2)
 òàêîé ñèñòåìå äëÿ êàæäîãî íà÷àëüíîãî ñîñòîÿíèÿ x0 èêàæäîãî íà÷àëüíîãî ìîìåíòà âðåìåíè t0 ñóùåñòâóåò íåïóñòîé ïó÷îê P (x0 , t0 ) òðàåêòîðèé x(t).è óíêöèÿ ïåðåõîäàÑèñòåìû â äèñêðåòíîì ïðîñòðàíñòâå ìîäåëèðóþòñÿ ñåòÿìè.(L, M), ãäå L ïðîèçâîëüíîå ìíîæåñòâî, íàçûâàåìîåM ⊆ L × L ìíîæåñòâî ïàð âåðøèí, íàçûâàåìûõ äóãàìè.íàáîð (L, M, s, e), ãäå L, M ïðîèçâîëüíûå ìíîæåñòâà, àÎïðåäåëåíèå. ðà ýòî íàáîðìíîæåñòâîì âåðøèí, àÌóëüòèãðà ýòîs, e : M → L óíêöèè, ñîïîñòàâëÿþùèå êàæäîé äóãå ñîîòâåòñòâåííî íà÷àëüíóþ èêîíå÷íóþ âåðøèíó äóãè.((L, M), f, g) èëè ìóëüòèãðà ((L, M, s, e), f, g), äëÿ êîòîðîãî çàäàíû óíêöèè f : L → A (íàãðóæåííûå âåðøèíû ), g : M → B (íàãðóæåííûå äóãè ),ïðèíèìàþùèå çíà÷åíèÿ èç ïðîèçâîëüíûõ ìíîæåñòâ A, B .Ñåòü ýòî ãðàÑîñòîÿíèÿ âåðøèí ñåòè îïèñûâàþò ñîñòîÿíèÿ ðàçëè÷íûõ ýëåìåíòîâ ñèñòåìû, ðàñïðåäåëåííûõ â ïðîñòðàíñòâå. Ñîñòîÿíèÿ äóã îïèñûâàþò âçàèìîäåéñòâèÿ ìåæäó ýëå6ìåíòàìè ñèñòåìû.
 ñëó÷àå äèñêðåòíîãî âðåìåíè äóãàaâåðøèíût + 1.íèâ ìîìåíò âðåìåíèt(a, b)îçíà÷àåò, ÷òî ñîñòîÿíèåb â ìîìåíò âðåìåäóã u(i,j) (t) çàâèñÿò îòâëèÿåò íà ñîñòîÿíèå âåðøèíû äèíàìè÷åñêîì ñëó÷àå ñîñòîÿíèÿ âåðøèísi (t)èâðåìåíè, à ñîñòîÿíèÿ âåðøèí çàâèñÿò îò ñîñòîÿíèé âõîäÿùèõ äóã ñ çàïàçäûâàíèåì:Sj (t) = Sj ({u(i,j)(t − 1)}(i,j)∈M , t).Òðàåêòîðèÿ ñèñòåìû îïèñûâàåòñÿ ãðàîì, ðàçâåðíó-òûì âî âðåìåíè.Äëÿ ìîäåëèðîâàíèÿ ìèêðîýêîíîìè÷åñêèõ ñèñòåì íà ñðåäíåñðî÷íûõ èíòåðâàëàõ âðåìåíè óäîáíî ïðèìåíÿòü ëîãèñòè÷åñêèé ïîäõîä.
 ëîãèñòèêå ðàññìàòðèâàþòñÿ ïðîöåññû2-õ âèäîâ:•ëîêàëüíûå ïðîöåññû, ïðîèñõîäÿùèå â êîíêðåòíîì ìåñòå;•ïîòîêîâûå ïðîöåññû (ïîòîêè) äâèæåíèå îáúåêòîâ ìåæäó ëîêàëüíûìè ïðîöåññàìè:1. ìàòåðèàëüíûå ïîòîêè ïåðåìåùåíèå ìàòåðèàëüíûõ îáúåêòîâ, ó÷àñòâóþùèõ â ïðîèçâîäñòâå;2. èíàíñîâûå ïîòîêè ïåðåìåùåíèå äåíåã.Òîãäà ñîñòîÿíèå âåðøèíû ýòî èíòåíñèâíîñòü ëîêàëüíîãî ïðîöåññà â âåðøèíå, àñîñòîÿíèå äóãè ýòî ìîùíîñòü ïîòîêà. Ìíîæåñòâî ñîñòîÿíèé âåðøèíû è ìíîæåñòâî ñî-F (íàïðèìåð,m âàðüèðóåòñÿñòîÿíèé äóã ïðîèçâîëüíàÿ ÷àñòè÷íî ïðåäóïîðÿäî÷åííàÿ àáåëåâà ãðóïïàâåêòîðíîå ïðîñòðàíñòâîRn). Ïðåäïîëàãàåòñÿ, ÷òî ñîñòîÿíèåf (m)äóãècm (êîòîðàÿ ìîæåò áûòü è áåñêîíå÷íîé).
 îòñóòñòâèåâõîäíûõ âîçäåéñòâèé ñîñòîÿíèå si âåðøèíû i ìîæíî âàðüèðîâàòü â íåêîòîðûõ ïðåäåëàõîò 0 äî äîïóñòèìîãî èçëèøêà vi , à ïðè íàëè÷èè âõîäíûõ âîçäåéñòâèé ýòîò èçëèøåêîò 0 äî ïðîïóñêíîé ñïîñîáíîñòèäîáàâëÿåòñÿ ê ñîñòîÿíèþ âåðøèíû, ïîðîæäåííîìó èç ñîñòîÿíèé âõîäíûõ äóã ïðåîáðàçîâàíèåìg: Fk → F.àññìîòðåíûðàçìíîæèòåëè.íèéäóãèñåòèÄëÿýòîñâåðøèíàìèñóììàòîðàìíîæåñòâîñäâóõâèäîâ:ñóììàòîðû-ðàñïðåäåëèòåëèóñèëåíèåì-ðàñïðåäåëèòåëÿâåëè÷èí[gi ({f (m)}e(m)=i ); gi ({f (m)}e(m)=i ) + vi ][−∞; gi ({f (m)}e(m)=i ) + vi ] ìíîæåñòâîïîòîêàâíåéìíîæåñòâîMmìíîæåñòâî=ñîñòîÿíèéèñîñòîÿ-[0; c(m)], Siïîòîêîâ, Si==ñîñòîÿíèé ïñåâäîïîòîêîâ, à ìíîæåñòâî ñîñòîÿ-íèé äóã (óïðàâëåíèé) ýòî ìíîæåñòâî âåëè÷èí ïîòîêà, êîòîðûé ìîæåò âûéòè èç âåðøè-Ui =Q| f1 + · · · + fk ≤ si }. àçìíîæèòåëü ðàçìíîæàåòQ(òèðàæèðóåò) âõîäÿùèé ïîòîê: Ui =s(m)=i [0; c(m)] ∩ {(si , si , .
. . , si )}. ÔîðìàëèçîâàíàPçàäà÷à ìèíèìèçàöèè ñòîèìîñòè ïîòîêà: minm∈M pm (fm ). Äëÿ íåïðåðûâíûõ êóñî÷íîíû:s(m)=i [0; c(m)] ∩ {(f1 , . . . , fk )ëèíåéíûõ óñèëåíèé ýòà çàäà÷à ñâîäèòñÿ ê çàäà÷å êóñî÷íî-ëèíåéíîãî ïðîãðàììèðîâàíèÿ, äëÿ âîãíóòûõ êóñî÷íî-ëèíåéíûõ óñèëåíèé è ïñåâäîïîòîêîâ ê çàäà÷å ëèíåéíîãîïðîãðàììèðîâàíèÿ.7Áîëåå ïîäðîáíî ðàññìîòðåí ÷àñòíûé ñëó÷àé çàäà÷à íàõîæäåíèÿ ïîòîêà ìèíèìàëüíîé ñòîìîñòè â ñåòè ñ óñèëåíèÿìè â äóãàõ, îáîáùàþùàÿ çàäà÷ó íàõîæäåíèÿ ïîòîêà ìèíèìàëüíîé ñòîèìîñòè â ñåòè ñ ëèíåéíûìè óñèëåíèÿìè, êîòîðàÿ, â ñâîþ î÷åðåäü,îáîáùàåò êëàññè÷åñêèå çàäà÷è ìàêñèìèçàöèè ïîòîêà è ìèíèìèçàöèè ñòîèìîñòè ïîòîêà, ðàññìîòðåííûå åùå Ôîðäîì è Ôàëêåðñîíîì. Èçâåñòíû ïîëèíîìèàëüíûå àëãîðèòìûíàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà â ñåòè ñ ëèíåéíûìè óñèëåíèÿìè â ÷àñòíîñòè, àëãîðèòì àäçèêà è àëãîðèòì Òàðäîñ-Âåéíà.Äëÿ íåëèíåéíûõ óñèëåíèé â äóãàõ çàäà÷à îðìóëèðóåòñÿ òàê.
Ñåòü ñ óñèëåíèÿìèâ äóãàõ ýòî êîíå÷íûé îðèåíòèðîâàííûé ìóëüòèãðàäåëåíà îäíà âûäåëåííàÿ âåðøèíà′′s ∈ L,(L, M, s, e),äëÿ êîòîðîãî îïðå-íàçûâàåìàÿ ñòîêîì, à äëÿ êàæäîé âåðøèíû,v : L → R+ , è äëÿ êàæäîé äóãè íåîòðèöàòåëüíàÿ âåðõíÿÿ ïðîïóñêíàÿ ñïîñîáíîñòü c : M → R+ , íåîòðèöàòåëüíàÿ óíêöèÿíåîòðèöàòåëüíîãî àðãóìåíòà gm : R+ → R+ óíêöèÿ óñèëåíèÿ, è íåîòðèöàòåëüíàÿóíêöèÿ íåîòðèöàòåëüíîãî àðãóìåíòà pm : R+ → R+ óíêöèÿ ñòîèìîñòè. Ïîòîê âñåòè ýòî óíêöèÿ íà äóãàõ f : M → R, óäîâëåòâîðÿþùàÿ ñëåäóþùèì óñëîâèÿì:êðîìå ñòîêà, çàäàí äîïóñòèìûé äåèöèò1.2.f (m) ∈ [0; c(m)]PPV (x) = e(m)=x gm (f (m)) − s(m)=x f (m) ∈ [0; v(x)]s′′ .àññìîòðåíà çàäà÷à ìàêñèìèçàöèè (ïñåâäî)ïîòîêàçàöèè ñòîèìîñòèmaxf (−p · f )äëÿ âñåõ âåðøèí, êðîìå ñòîêàmaxf (−Vf (s′′ ))è çàäà÷à ìèíèìè-ïðè çàäàííîé âåëè÷èíå ïîòîêà. Ïåðâóþ çàäà÷ó ìîæíîñâåñòè êî âòîðîé.1.
ÅñëèÒåîðåìà (î äîñòèæåíèè ìàêñèìàëüíîãî çíà÷åíèÿ îïòèìàëüíûì ïîòîêîì).óñèëåíèå â äóãåmgm = max(g1m , . . . , gkm ),òî ñóùåñòâóåò îïòèìàëü-íûé ïñåâäîïîòîê, ñîâïàäàþùèé ñ îïòèìàëüíûì ïñåâäîïîòîêîì â îäíîé èçâñïîìîãàòåëüíûõ çàäà÷, â êîòîðûõ óñèëåíèå â äóãå2. Åñëè ñòîèìîñòü â äóãåmmpm = min(p1m , . . . , pkm ),çàìåíÿåòñÿ íàkgjm .òî ñóùåñòâóåò îïòèìàëü-íûé (ïñåâäî)ïîòîê, ñîâïàäàþùèé ñ îïòèìàëüíûì (ïñåâäî)ïîòîêîì â îäíîé èçâñïîìîãàòåëüíûõ çàäà÷, â êîòîðûõ ñòîèìîñòü â äóãåmçàìåíÿåòñÿ íàkpjm .Äëÿ íàáîðà ïàðàëëåëüíûõ äóã ìàêñèìàëüíûé ïîòîê ýòî ðåøåíèå çàäà÷èmax0≤xi ≤cix1 +···+xn ≤V(g1 (x1 ) + · · · + gn (xn )).(1)àññìîòðèì îïåðàöèþ àãðåãèðîâàíèÿ ñåòè ïî äóãàì, îïðåäåëÿåìóþ ñëåäóþùèì îáðà-m1 , .
. . , mk ìåæäó âåðøèíàìè a è b îáúåäèíÿþòñÿ â îäíó äóãó m, à èõ óñèëåíèÿ g1m , . . . , gkm ïðåîáðàçóþòñÿ â óñèëåíèå gm ïî ïðàâèëó: gm ýòî ðåøåíèå çàäà÷è (1).çîì: äóãè8Ýòî àãðåãèðîâàíèå ïî óñèëåíèÿì äóã. Àíàëîãè÷íî, ìîæíî îïðåäåëèòü àãðåãèðîâàíèå ïîñòîèìîñòÿì äóã, êîãäàpm ðåøåíèå çàäà÷è (1) ñ ìèíèìèçàöèåé ñòîèìîñòè.Òåîðåìà (î êîìïîçèöèè äóã).1. Ïóñòü âñå ñòîèìîñòè äëÿ ïàðàëëåëüíûõ äóã ðàâíûå ëèíåéíûå óíêöèè. Òîãäà êàæäîìó îïòèìàëüíîìó ïñåâäîïîòîêó â èñõîäíîé ñåòè ñîîòâåòñòâóåò îïòèìàëüíûé ïñåâäîïîòîê â àãðåãèðîâàííîé ïî óñèëåíèÿì äóã ñåòè, è íàîáîðîò.2.
Ïóñòü âñå óñèëåíèÿ äëÿ ïàðàëëåëüíûõ äóã ðàâíûå ëèíåéíûå óíêöèè. Òîãäàêàæäîìó îïòèìàëüíîìó ïñåâäîïîòîêó â èñõîäíîé ñåòè ñîîòâåòñòâóåò îïòèìàëüíûé ïñåâäîïîòîê â àãðåãèðîâàííîé ïî ñòîèìîñòè äóã ñåòè.Òåîðåìà î äîñòèæåíèè ìàêñèìóìà îïòèìàëüíûì ïîòîêîì è òåîðåìà î êîìïîçèöèèäóã ïîçâîëÿþò ñâåñòè, ñîîòâåòñòâåííî, óñèëåíèå â äóãå âèäàmax(f1 (x), . .
. , fn (x)) è óñè-maxx1 ···+xn =x (f1 (x1 ) + · · · + fn (xn )) ê íàáîðó óñèëåíèé â ïàðàëëåëüíûõf1 (x), . . . , fn (x). Èñõîäÿ èç ýòîãî, ïîñòðîåí ïîëóïåðåáîðíûé àëãîðèòì, ñâîäÿùèéëåíèå â äóãå âèäàäóãàõèñõîäíóþ çàäà÷ó ïóòåì ðàçìíîæåíèÿ äóã ê çàäà÷å â ñåòè ñ ëèíåéíûìè óñèëåíèÿìè.Çàäà÷à íàõîæäåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãî ïîòîêà ðàññìîòðåíà â îáùåì âèäå ñ ñóììàòîðàìè-óñèëèòåëÿìè è ðàçìíîæèòåëÿìè. Åå ÷àñòíûìè ñëó÷àÿìè îêàçûâàåòñÿçàäà÷à îïòèìèçàöèè ñåòè Ïåòðè, îïòèìèçàöèÿ â ëèíåéíûõ ïðîèçâîäñòâåííûõ ìîäåëÿõËåîíòüåâà è Íåéìàíà, çàäà÷à íàõîæäåíèÿ äèíàìè÷åñêîãî ïîòîêà íàèñêîðåéøåãî ïðèáûòèÿ.Òåîðåìà (ñâåäåíèå äèíàìè÷åñêîé çàäà÷è ê ñòàòè÷åñêîé).
Ïóñòü â äèíàìè÷åñêîé ñåòèäàíà çàäà÷à íàõîæäåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãî ïñåâäîïîòîêà íà êîíå÷íîì èíòåðâàëå âðåìåíè èëè ïîñòðîåíèÿ ïîòîêà íàèñêîðåéøåãî ïðèáûòèÿ. Òîãäà ñóùåñòâóåòf ′ , êîòîðîìó ñîîòâåòñòâóåò îïòèìàëüíûéðàçâåðíóòîé âî âðåìåíè NT .îïòèìàëüíûé äèíàìè÷åñêèé ïñåâäîïîòîêñòàòè÷åñêèé ïñåâäîïîòîêfâ ñåòè,Ñëîæíîñòü ñîîòâåòñòâóþùèõ àëãîðèòìîâ ðåøåíèÿ âûòåêàåò èç ñëîæíîñòè àëãîðèòìîâ äëÿ ñòàòè÷åñêèõ ïîòîêîâ è êîëè÷åñòâà âåðøèínTè äóãmTâ ãðàå, ðàçâåðíóòîìâî âðåìåíè.
Äëÿ äèñêðåòíîãî ïîòîêà áîëåå ýåêòèâíûì ìîæåò áûòü ðåøåíèå çàäà÷è ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ. Ïðè ðåøåíèè ìåòîäîì äèíàìè÷åñêîãîïðîãðàììèðîâàíèÿ ðàññìàòðèâàþòñÿ ñå÷åíèÿ ãðàà, ðàçâåðíóòîãî âî âðåìåíè, è äëÿêàæäîãî ìîìåíòà âðåìåíè ðåøàåòñÿ îïòèìèçàöèîííàÿ çàäà÷à ïðè êàæäîì èç âîçìîæíûõ ñîñòîÿíèé ñå÷åíèÿ. ãëàâå 2 ðàññìîòðåíû îïòèìóìû ïî Ïàðåòî â äèíàìè÷åñêèõ ñåòåâûõ ìíîãîêðèòå-ðèàëüíûõ çàäà÷àõ. Èññëåäóåòñÿ âîïðîñ î äèíàìè÷åñêîé óñòîé÷èâîñòè çàäà÷ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè è âîçìîæíîñòè ðåêóððåíòíîãî ðåøåíèÿ ýòèõ çàäà÷.
Âîçìîæíûðàçíûå âèäû äèíàìè÷åñêîé óñòîé÷èâîñòè. Âñå îíè îïðåäåëÿþòñÿ íå äëÿ îäíîé çàäà÷è,9à äëÿ ñåìåéñòâà äèíàìè÷åñêèõ îïòèìèçàöèîííûõ çàäà÷ (ÑÄÎÇ). Åñëè äàíà óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñèñòåìàDùàÿ åé äèíàìè÷åñêàÿ çàäà÷à ìíîãîêðèòåðèàëüíîé îïòèìèçàöèèx0 íà÷àëüíàÿ ïîçèöèÿ,(f1 , . . . , fn ) êðèòåðèè îïòèìàëüíîñòè íà ìíîæåñòâå òðà-åêòîðèé. Òîãäà ñåìåéñòâî çàäà÷, ñîîòâåòñòâóþùèõ ñèñòåìåìàëüíîñòè(f1 (x,t) , . .
. , fn (x,t) ),ñòâóþùåé ìîìåíòó êàæäîìóX è ñîîòâåòñòâóþ(P (x0 ), f1 , . . . , fn ), ãäåñ ìíîæåñòâîì âîçìîæíûõ ñîñòîÿíèéD ýòî êðèòåðèè îïòè-çàäàííûå íà ìíîæåñòâå òðàåêòîðèé ïîäñèñòåìû, ñîîòâåò-t ∈ S,ñòâåííîå ñåìåéñòâî çàäà÷ ýòî ÑÄÎÇ, îïðåäåëÿåìîå òàê:fit (x) ∗ fit+1 (xt+1 ) ∗ · · · ∗ fim (xm ),ãäåx ∈ X . Åñòåfi (x,t) (x, xt+1 , . . . , xm ) =íà÷èíàþùèõñÿ â êàæäîé òî÷êå∗ ïîëóãðóïïîâàÿ îïåðàöèÿ íà óïîðÿäî÷åííîéïîëóãðóïïå.Ñëàáàÿ äèíàìè÷åñêàÿ óñòîé÷èâîñòü äëÿ ÑÄÎÇ îçíà÷àåò, ÷òî êîíå÷íûé ó÷àñòîê îïòèìàëüíîé òðàåêòîðèè òàêæå îïòèìàëåí, äèíàìè÷åñêàÿ ñîâìåñòèìîñòü ÷òî, ïðèñîåäèíèâ ê îïòèìàëüíîé òðàåêòîðèè äðóãîé îïòèìàëüíûé êîíå÷íûé ó÷àñòîê, ìû ïîëó÷èìòàêæå îïòèìàëüíóþ òðàåêòîðèþ. Ïîçèöèîííàÿ äèíàìè÷åñêàÿ óñòîé÷èâîñòü îçíà÷àåò,÷òî îäíî ñåìåéñòâî ïîçèöèîííûõ óïðàâëåíèéu(x, t)äîñòàâëÿåò ðåøåíèå ñðàçó âñåõ çà-äà÷ â ÑÄÎÇ.
Èç ïîçèöèîííîé äèíàìè÷åñêîé óñòîé÷èâîñòè ñëåäóåò ñëàáàÿ äèíàìè÷åñêàÿóñòîé÷èâîñòü, íî íå äèíàìè÷åñêàÿ ñîâìåñòèìîñòü.Ïîñòðîåíû ýåêòèâíûå àëãîðèòìû íàõîæäåíèÿ ïàðåòîâñêèõ îïòèìóìîâ â äèíàìè÷åñêîé ñèñòåìå äëÿ êîíå÷íîãî ìíîæåñòâà àëüòåðíàòèâ. Âñå îíè îñíîâàíû íà ââåäåííîéÁåëëìàíîì èäåå ðåêóððåíòíûõ ñîîòíîøåíèé äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ. åêóð-ðåíòíàÿ ñòðàòåãèÿ (ðåêóððåíòíîå óïðàâëåíèå ), ñîîòâåòñòâóþùåå ïðèíöèïó îïòèìàëüíîñòèSelf ýòî ïîçèöèîííîå óïðàâëåíèåu,óäîâëåòâîðÿþùåå ñëåäóþùèì ðåêóððåíò-íûì ñîîòíîøåíèÿì:u(x, t) ∈ argu(x,t) Sel(f1 (x,t) ,...,fn (x,t) ) ({h ∈ P (x, t) | ∀t′ > t h(t′ + 1) = π(h(t′ ), t′ , u(h(t′ ), t′ ))}Ïîêàçàíî, ÷òî åñëè ÑÄÎÇ äèíàìè÷åñêè ñîâìåñòèìî, òî ëþáîå ðåêóððåíòíîå óïðàâëåíèå ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâî.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
