Диссертация (1149954), страница 3
Текст из файла (страница 3)
Ïîñòðîåíûàëãîðèòìû íàõîæäåíèÿ îïòèìàëüíûõ îáîáùåííûõ ïîòîêîâ â ñåòè â íåêîòîðûõ âàæíûõ ÷àñòíûõ ñëó÷àÿõ, äàíà îöåíêà ñëîæíîñòè àëãîðèòìîâ.1.1Óïðàâëÿåìûå ðàñïðåäåëåííûå â ïðîñòðàíñòâå äèíàìè÷åñêèå ñèñòåìû1.1.1Îáùàÿ ìîäåëü ñëîæíîé äåòåðìèíèðîâàííîé ìèêðîýêîíîìè÷åñêîé ñèñòåìû ðàáîòå ïîñòðîåíà ìàòåìàòè÷åñêàÿ ìîäåëü ñëîæíîé äåòåðìèíèðîâàííîé ìèêðîýêîíîìè÷åñêîé ñèñòåìû. àññìîòðåíèå ïðîèçâîäèòñÿ íà ñðåäíåñðî÷íûõ èíòåðâàëàõ âðåìåíè äîñòàòî÷íî áîëüøèõ äëÿ òîãî, ÷òîáû îõâàòèòü ïðîöåññû ïðîèçâîäñòâà, íî äîñòàòî÷íî ìàëûõ äëÿòîãî, ÷òîáû ìîæíî áûëî ïðåíåáðå÷ü èçìåíåíèåì ñòðóêòóðû ìèêðîýêîíîìè÷åñêîé ñèñòåìû,ïîÿâëåíèåì íîâûõ òåõíîëîãèé, è.ò.ï. Ïðåäïîëàãàåòñÿ, ÷òî âñå âíåøíèå àêòîðû ëèáî äåòåðìèíèðîâàííûå, ëèáî ÿâëÿþòñÿ âîçäåéñòâèåì öåëåïîëàãàþùèõ àãåíòîâ ñ èçâåñòíûìè öåëÿìè.
Ò.å. îòñóòñòâóþò ñòîõàñòè÷åñêèå âîçäåéñòâèÿ.Âàæíàÿ çàäà÷à èçó÷åíèå ñîöèàëüíûõ è ýêîíîìè÷åñêèõ ñèñòåì. Ñèñòåìà ñïåðâà äîëæíàáûòü èçó÷åíà ìåòîäàìè ñèñòåìíîãî àíàëèçà, ïîòîì ìîæåò áûòü íåîáõîäèìî ïîñòðîåíèå ìàòå-11ìàòè÷åñêîé ìîäåëè. Àñïåêòû ñîöèàëüíûõ è ýêîíîìè÷åñêèõ ñèñòåì, äåëàþùèå èõ ñëîæíûìèäëÿ ìîäåëèðîâàíèÿ:•ýòî äèíàìè÷åñêèå ñèñòåìû èõ ñîñòîÿíèå•ýòî îòêðûòûå ñèñòåìû òî åñòü âçàèìîäåéñòâóþùèå ñ îêðóæàþùåé ñðåäîé; ñëåäîâà-x(t)ìåíÿåòñÿ ñ òå÷åíèåì âðåìåíè;òåëüíî, îíè íåàâòîíîìíû: ïàðàìåòðû îïèñûâàþùèõ èõ óðàâíåíèé è íåðàâåíñòâ ìåíÿþòñÿ ñ òå÷åíèåì âðåìåíè:•x(t + 1) ∈ F (x(t), t)(â ñëó÷àå äèñêðåòíîãî âðåìåíè);îíè ðàñïðåäåëåíû â ïðîñòðàíñòâå, òî åñòü ñîñòîÿò èç ìíîæåñòâà ïîäñèñòåìa1 , . . .
, ak ,íàõîäÿùèõñÿ â ðàçíûõ ìåñòàõ è âçàèìîäåéñòâóþùèõ äðóã ñ äðóãîì;•ýòî ìíîãîêðèòåðèàëüíûå ñèñòåìû: àãåíòû, ó÷àñòâóþùèå â óïðàâëåíèè èìè, èìåþò ìíîæåñòâî ðàçíûõ öåëåé è, ñëåäîâàòåëüíî, ðóêîâîäñòâóþòñÿ íå îäíèì êðèòåðèåì îïòèìàëüíîñòè, à ìíîæåñòâîì êðèòåðèåâ•y1 , . . . , yn ;ïðè ýòîì ðàçíûå àãåíòû ìîãóò ðóêîâîäñòâîâàòüñÿ ðàçíûìè êðèòåðèÿìè îïòèìàëüíîñòè.Ñ äðóãîé ñòîðîíû, ñîöèàëüíîå èëè ýêîíîìè÷åñêîå ïðîñòðàíñòâî ìîäåëèðîâàòü ïðîùå, ÷åìèçè÷åñêîå, ïîñêîëüêó îíî ÷àùå âñåãî äèñêðåòíî. Ýòî ïîíÿòíî: ñîöèàëüíîå ïðîñòðàíñòâî ýòî èñêóñòâåííîå ïðîñòðàíñòâî, ñîçäàííîå ëþäüìè, à êîëè÷åñòâî ëþäåé êîíå÷íî è, ñëåäîâàòåëüíî, êîëè÷åñòâî ñîöèàëüíûõ ïîäñèñòåì, êîòîðûå îíè ñîçäàþò (íàïðèìåð, îáùåñòâåííûõîðãàíèçàöèé) òîæå êîíå÷íî.
Âðåìÿ æå â ñîöèàëüíûõ ñèñòåìàõ ìîæåò áûòü êàê äèñêðåòíûì,òàê è íåïðåðûâíûì.  äàííîé ðàáîòå ðàññìàòðèâàåòñÿ áîëåå ïðîñòîé ñëó÷àé äèñêðåòíîãîâðåìåíè.Äèñêðåòíîå ïðîñòðàíñòâî, â êîòîðîì ìåæäó ýëåìåíòàìè âîçìîæíî òîëüêî ïàðíûå âçàèìîäåéñòâèÿ òî åñòü âçàèìîäåéñòâèÿ ìåæäó ïàðàìè ýëåìåíòîâ ìîæíî ñìîäåëèðîâàòüîðèåíòèðîâàííûì ãðàîì èëè ìóëüòèãðàîì.Îïðåäåëåíèå 1. ðà ýòî íàáîðìíîæåñòâîì âåðøèí,M ⊆L×LàÎïðåäåëåíèå 2. Ìóëüòèãðà(ìíîæåñòâîâåðøèí ), M(L, M),ãäåL ïðîèçâîëüíîå ìíîæåñòâî, íàçûâàåìîå ìíîæåñòâî ïàð âåðøèí, íàçûâàåìûõ ýòî íàáîð(L, M, s, e),ãäåLäóãàìè. ïðîèçâîëüíîå ìíîæåñòâî ïðîèçâîëüíîå ìíîæåñòâî (ìíîæåñòâîäóã ),às, e : M → Lóíêöèè, ñîïîñòàâëÿþùèå êàæäîé äóãå ñîîòâåòñòâåííî íà÷àëüíóþ è êîíå÷íóþ âåðøèíó äóãè. ìóëüòèãðàå âîçìîæíû ïàðàëëåëüíûå äóãè.
ðà ýòî ìóëüòèãðà, ó êîòîðîãîs(a, b) = a, e(a, b) = b.ãîl ∈LÄèñêðåòíîå ïðîñòðàíñòâî ìîäåëèðóåòñÿ ãðàîì, âåðøèíû êîòîðî- ýòî ýëåìåíòû, à äóãè(l1 , l2 ) ∈ M âçàèìîäåéñòâèÿ ìåæäó íèìè. Ïîñêîëüêó, â12ýêîíîìèêå, â îòëè÷èå îò èçèêè, äåéñòâèå íå ðàâíî ïðîòèâîäåéñòâèþ è ÷àñòî âñòðå÷àåòñÿ îäíîíàïðàâëåííîå âîçäåéñòâèå, ãðà âçàèìîäåéñòâèé îðèåíòèðîâàííûé. Åñëè îäèí ýëåìåíòâîçäåéñòâóåò íà äðóãîé ñðàçó íåñêîëüêèìè ñïîñîáàìè, ìîæåò áûòü óäîáíåå âìåñòî ãðààèñïîëüçîâàòü ìóëüòèãðà.Îïðåäåëåíèå 3. Ñåòüðîãî çàäàíû óíêöèè ýòî ãðà((L, M), f, g) èëè ìóëüòèãðà ((L, M, s, e), f, g) äëÿ êîòî-f : L → A (íàãðóæåííûå âåðøèíû ), g : M → B (íàãðóæåííûå äóãè ),ïðèíèìàþùèå çíà÷åíèÿ èç ïðîèçâîëüíûõ ìíîæåñòâA, B .Ïîñêîëüêó ýëåìåíòû è âçàèìîäåéñòâèÿ ìîãóò èìåòü îïðåäåëåííûå ñâîéñòâà, âåðøèíû èäóãè ãðàà äîëæíû áûòü ïîìå÷åíû ýëåìåíòàìè îïðåäåëåííûõ ìíîæåñòâ, ò.å.
äèñêðåòíîåïðîñòðàíñòâî ìîäåëèðóåòñÿ ñåòüþ. Òàêèì îáðàçîì, ìàòåìàòè÷åñêèå ìîäåëè ñîöèàëüíûõ èýêîíîìè÷åñêèõ ñèñòåì îñíîâàíû íà óïðàâëÿåìûõ äèíàìè÷åñêèõ ñèñòåìàõ è ñåòÿõ. Êàê èçâåñòíî, âðåìÿ ýòî îäíî èç èçìåðåíèé ïðîñòðàíñòâà-âðåìåíè. Çíà÷èò, ñåòè òàêæå ìîãóòîïèñûâàòü è ïðîñòðàíñòâåííî-âðåìåííûå ïðîöåññû, ò.å. ðàçâèòèå îáúåêòîâ, ðàñïðåäåëåííûõâ ïðîñòðàíñòâå. ñëó÷àå, êîãäà ñòðóêòóðà âçàèìîäåéñòâèé íå ìåíÿåòñÿ, ãðà(L, M),ñòåìó, íå ìåíÿåòñÿ ñî âðåìåíåì, à ìåíÿþòñÿ òîëüêî ïàðàìåòðû âåðøèíîïèñûâàþùèé ñè-fl (t), l ∈ Lè äóãgm (t), m ∈ M .1.1.2ÏóñòüÓïðàâëÿåìûå ñèñòåìû ñ äèñêðåòíûì âðåìåíåìX ìåòðè÷åñêîå ïðîñòðàíñòâî (ïðîñòðàíñòâîñîñòîÿíèé ñèñòåìû ).
Ïóñòü Tëà âðåìåíè, ò.å. óïîðÿäî÷åííîå ìíîæåñòâî ìîìåíòîâ âðåìåíè. Òðàåêòîðèåé ñèñòåìûþò óíêöèþx : T → X , êîòîðàÿ êàæäîìó ìîìåíòóøêà-íàçûâà-âðåìåíè ñîïîñòàâëÿåò ñîñòîÿíèå ñèñòåìûâ ýòîò ìîìåíò âðåìåíè. Âîçìîæíû ðàçíûå ñïîñîáû ââåäåíèÿïó÷êà òðàåêòîðèé P (x, t) òîåñòü ìíîæåñòâà âîçìîæíûõ òðàåêòîðèé ñèñòåìû, íà÷èíàþùèõñÿ â òî÷êåt.x â ìîìåíòâðåìåíèÍàïðèìåð, ñ ïîìîùüþ îáîáùåííîé äèíàìè÷åñêîé ñèñòåìû (ÎÄÑ) [4℄:Îïðåäåëåíèå 4. Îáîáùåííàÿ äèíàìè÷åñêàÿ ñèñòåìàD : X × T × T → 2X ,1.íàXñ âðåìåíåìT ýòî óíêöèÿîáëàäàþùàÿ ñëåäóþùèìè ñâîéñòâàìè:D(x, t1 , t2 ) 6= ∅ íåïóñòîåêîìïàêòíîå ìíîæåñòâî ïðè t1≤ t2 . ÎÄÑ îïðåäåëÿåòáóäóùååïî ïðîøëîìó, ò.å.
âûâîäèò ñëåäñòâèÿ èç ïðè÷èí.2.D(x, t, t) = {x} (ðåëåêñèâíîñòü ïðè ïåðåõîäå îò ìîìåíòà âðåìåíè t ê òîìó æå ñàìîìóìîìåíòó, ìíîæåñòâî âîçìîæíûõ ñîñòîÿíèé íå ìåíÿåòñÿ)3.t ≤ t1 ≤ t2 ⇒ D(x, t, t2 ) =Sy∈D(x,t,t1 )D(y, t1, t2 ) (òðàíçèòèâíîñòü ).134. ÔóíêöèÿD(x, t1 , t2 ) íåïðåðûâíàïî ñîâîêóïíîñòè ïåðåìåííûõ(x, t1 ) è ïî ïåðåìåííîé t2â ìåòðèêå Õàóñäîðà.Òðàåêòîðèÿt1 , t2 ∈ TÎÄÑ ýòî óíêöèÿx : T → X,êîòîðàÿ äëÿ ëþáûõ äâóõ ìîìåíòîâ âðåìåíèóäîâëåòâîðÿåò ñîîòíîøåíèþx(t2 ) ∈ D(x(t1 ), t1 , t2 ).(1.1) ðàáîòå ðàññìàòðèâàåòñÿ òîëüêî äèñêðåòíîå óïîðÿäî÷åííîå ìíîæåñòâî ìîìåíòîâ âðåìåíèT.Èç äèñêðåòíîñòè ñëåäóåò, ÷òî åãî ìîæíî ïðîíóìåðîâàòü:T = {t1 , t2 , .
. . , ts }.Óñëîâèÿêîìïàêòíîñòè è íåïðåðûâíîñòè óíêöèé äîñòèæèìîñòè ñëèøêîì îãðàíè÷èâàþùèå è âðàáîòå íå èñïîëüçóþòñÿ.Îïðåäåëåíèå 5.TÏóñòü äèñêðåòíîå âðåìÿ. Òîãäà óíêöèÿDÎÄÑ ñ äèñêðåòíûìâðåìåíåì, åñëè äëÿ íåå âûïîëíÿþòñÿ ñâîéñòâà íåïóñòîòû, ðåëåêñèâíîñòè è òðàíçèòèâíîñòè.Çàìå÷àíèå1.1.1. Ïðè ýòîì ìîãóò íå âûïîëíÿòüñÿ ñâîéñòâà íåïðåðûâíîñòè è êîìïàêòíîñòèìíîæåñòâ äîñòèæèìîñòè.Îïðåäåëåíèå 6. Óïðàâëÿåìàÿ (àâòîíîìíàÿ) äèíàìè÷åñêàÿ ñèñòåìà ñ äèñêðåòíûì âðåìå-íåìñ ìíîæåñòâîì ñîñòîÿíèéñ äèñêðåòíûì âðåìåíåì,òàêàÿ, ÷òîSu(t)∈UUX ýòî íàáîð(D, U, π), ãäå D óíêöèÿ äîñòèæèìîñòè â ÎÄÑ ìíîæåñòâî óïðàâëåíèé, àπ: X × U → Xóíêöèÿ ïåðåõîäàπ(x(t), u(t)) = D(x(t), t, t + 1).Óïðàâëÿåìàÿ íåàâòîíîìíàÿ äèíàìè÷åñêàÿ ñèñòåìà ñ äèñêðåòíûì âðåìåíåìñòâîì ñîñòîÿíèéXè âðåìåíåìÎÄÑ ñ äèñêðåòíûì âðåìåíåì,ïåðåõîäàUT ýòî íàáîð(D, U, π),D ìíîæåñòâî óïðàâëåíèé, à óíêöèÿ äîñòèæèìîñòè âπ: X × T × U → Xóíêöèÿòàêàÿ, ÷òî[u∈U(ò.å.
óíêöèÿÇàìå÷àíèåπñþðúåêòèâíà ïî{π(x, t, u)} = D(x(t), t, t + 1)uäëÿ êàæäîãî1.1.2. Òàêèì îáðàçîì, óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñ äèñêðåòíûì âðåìåíåì ýêâè-(X, U, π)ñîñòîÿíèé è óïðàâëåíèé (âõîäíûõ ñèãíàëîâ àâòîìàòà), àÓïðàâëÿåìàÿ íåàâòîíîìíàÿ äèíàìè÷åñêàÿ ñèñòåìàT(1.2)(x, t)).âàëåíòíà àâòîìàòó áåç âûõîäà (ïåðåõîäíîé ñèñòåìå)âðåìåíåìãäåñ ìíîæå-π[59℄, ãäåXèU ìíîæåñòâî óíêöèÿ ïåðåõîäà.(D, U, π) ñìíîæåñòâîì ñîñòîÿíèéXèòàêæå ýêâèâàëåíòíà àâòîìàòó áåç âûõîäà, ïðè÷åì åãî ïðîñòðàíñòâî ñîñòîÿíèé ýòî ïðîñòðàíñòâî-âðåìÿX × T,à óíêöèÿ ïåðåõîäà π ′ ((x, t), u) = (π(x, t, u), t + 1).14Óòâåðæäåíèå 1.1.1. Ó ÎÄÑ ñ äèñêðåòíûì âðåìåíåì äëÿ ëþáîé íà÷àëüíîé òî÷êè x0 èëþáîãî ïðîãðàììíîãî óïðàâëåíèÿ u : T → U ñóùåñòâóåò åäèíñòâåííàÿ ñîâìåñòèìàÿ ñ íèìòðàåêòîðèÿ x : T → X , ò.å.
òàêàÿ, ÷òî π(x(t), t, u(t)) = x(t + 1), âûõîäÿùàÿ èç òî÷êè x0 .Âåðíî è îáðàòíîå: äëÿ êàæäîé òðàåêòîðèè ñèñòåìû ñóùåñòâóåò ñîâìåñòèìîå ñ íåéïðîãðàììíîå óïðàâëåíèå.Äîêàçàòåëüñòâî.Èíäóêöèåé ïî ÷èñëó ìîìåíòîâ âðåìåíè. Áàçà èíäóêöèè:äóêöèîííûé ïåðåõîä: åñëè ïîñòðîåíî íà÷àëî òðàåêòîðèèπ(x(t), t, u(t).x(t)k,äî ìîìåíòàx(0) = x0 .áåðåìx(t + 1) =Ñîîòíîøåíèå (1.1) ñëåäóåò èç òðàíçèòèâíîñòè.Îáðàòíîå óòâåðæäåíèå òàêæå äîêàçûâàåòñÿ ïî èíäóêöèè. Ñóùåñòâîâàíèå óïðàâëåíèÿíà êàæäîì øàãå ñëåäóåò èç ñóþðúåêòèâíîñòè óíêöèèÇàìå÷àíèåu(t)π.1.1.3. Òàêèì îáðàçîì, ÎÄÑ ñ äèñêðåòíûì âðåìåíåì îäíîçíà÷íî îïðåäåëÿåòñÿD(x, t) = D(x, t, t + 1).óíêöèåéÈí-Óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñèñòåìà ñ äèñêðåòíûì âðåìå-íåì îäíîçíà÷íî îïðåäåëÿåòñÿ ìíîæåñòâàìèU(x, t)è óíêöèåéπ îòîáðàæåíèåDìîæíîîïðåäåëèòü ïî îðìóëå (1.2).Âåðíî è îáðàòíîå: åñëè ÎÄÑ íà ìíîæåñòâåD,Xñ äèñêðåòíûì âðåìåíåìTòî åé ñîîòâåòñòâóåò óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñèñòåìà, äëÿ êîòîðîéπ(x, t, u) = u.çàäàíà óíêöèåéU(x, t) = D(x, t)èÒàêèì îáðàçîì, îáû÷íûå ÎÄÑ ñ äèñêðåòíûì âðåìåíåì è óïðàâëÿåìûå ýêâèâà-ëåíòíû.
Äàëåå óïðàâëåíèå â íåêîòîðûõ ñëó÷àÿõ îïðåäåëÿåòñÿ ÿâíî, à â íåêîòîðûõ íåò, èçñîîáðàæåíèé óäîáñòâà.Êàê èçâåñòíî [25℄, êàæäóþ ÎÄÑ ñ äèñêðåòíûì âðåìåíåì ìîæíî íàãëÿäíî èçîáðàçèòüãðàîìà äóãè(X ′ , M),m ∈ Mìíîæåñòâî âåðøèí êîòîðîãî èìåþò âèäX′ = X × Tm = ((x1 , t), (x2 , t + 1)),ãäå(ïðîñòðàíñòâî-âðåìÿ ñèñòåìû),x2 ∈ D(x1 , t, t + 1).Ýòîò ãðà äèàãðàììà ïåðåõîäîâ ñîîòâåòñòâóþùåãî àâòîìàòà áåç âûõîäà. Ïóòü â ãðàå ýòî äâèæåíèåÎÄÑ, à ìíîæåñòâî ïóòåé, âûõîäÿùèõ èç òî÷êè ïó÷îê òðàåêòîðèé.Çàìå÷àíèå1.1.4. ðà ÎÄÑ ÿâëÿåòñÿ âûðîâíåííûì äëÿ êàæäîé åãî âåðøèíûäëèíû âñåõ ïóòåé, âåäóùèõ ââûðîâíåííûé ãðàâåðøèíûx(X ′ , M)xèç êîðíåâûõ âåðøèí, îäèíàêîâû. Ïðîèçâîëüíûé êîíå÷íûéòàêæå ìîæíî ñ÷èòàòü ãðàîì ÎÄÑ, â êîòîðîì äëÿ êàæäîéåå öåëî÷èñëåííîå âðåìÿâåðøèíû ãðàà âx.x ∈ X′t äëèíà ïóòåé, âåäóùèõ èç ïðîèçâîëüíîé êîðíåâîé îáîáùåííîé ÎÄÑ, êîòîðîé ñîîòâåòñòâóåò ãðà(X ′ , M),âîçìîæ-íà ïðîèçâîëüíàÿ ïðîäîëæèòåëüíîñòü âðåìåíè îò íà÷àëüíîãî ñîñòîÿíèÿ äî êîíå÷íîãî.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
