Автореферат (1149953), страница 3
Текст из файла (страница 3)
Ïðèâåäåíû ïðèìåðû îïòèìèçàöèîííûõ çàäà÷ñ ïðèíöèïîì îïòèìàëüíîñòè Áåëëìàíà äàæå ñ îäíèì êðèòåðèåì, â êîòîðûõ ïîçèöèîííîäèíàìè÷åñêè óñòîé÷èâîå óïðàâëåíèå íå ïîðîæäàåò äèíàìè÷åñêè ñîâìåñòèìóþ òðàåêòîðèþ è íå âñå ðåêóððåíòíûå óïðàâëåíèÿ îïòèìàëüíû. Òî åñòü ïðèíöèï îïòèìàëüíîñòèÁåëëìàíà âûïîëíåòñÿ, íî äèíàìè÷åñêîå ïðîãðàììèðîâàíèå íåïðèìåíèìî. Ïðè÷èíà íååñòåñòâåííîñòü ñåìåéñòâà çàäà÷.Äëÿ èíòåãðàëüíîé ïîëåçíîñòè íà ïîëîæèòåëüíîì óïîðÿäî÷åííîì ïîëóêîëüöåR åñòå-ñòâåííîå ñåìåéñòâî çàäà÷ äèíàìè÷åñêè óñòîé÷èâî. Äëÿ îïòèìóìîâ Ïàðåòî ðåêóððåíòíîåðåøåíèå îïòèìàëüíî è ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâî.
Íî ïðè ýòîì â ñëó÷àå íàðóøåíèÿ ñòðîãîñòèR ñëåâà ìîæåòíå âûïîëíÿòüñÿ ïðèíöèï îïòèìàëüíîñòè Áåëëìàíà. Òîåñòü, ìû âèäèì îáðàòíóþ ñèòóàöèþ: äèíàìè÷åñêîå ïðîãðàììèðîâàíèå ïðèìåíèìî, à âîòïðèíöèï îïòèìàëüíîñòè Áåëëìàíà íå âûïîëíÿåòñÿ (íî âñå ðàâíî ñóùåñòâóåò õîòÿ áû10îäíà äèíàìè÷åñêè óñòîé÷èâàÿ òðàåêòîðèÿ). åêóððåíòíûå ñîîòíîøåíèÿ äèíàìè÷åñêîãîïðîãðàììèðîâàíèÿ äëÿ óïðàâëÿåìîé ÑÄÎÇ âûãëÿäÿò òàê:gm (x) = f m (x) = (f1m , . .
. , fnm )(x)...u(x, i − 1) ∈ argu(x,i−1) Pf i−1 (x,u(x,i−1))⊕gi (π(x,i−1,u(x,i−1))) (U(x, i − 1))gi−1 (x) = f i−1 (x, u(x, i − 1)) ⊕ gi (π(x, i − 1, u(x, i − 1)))...P(çäåñü ìíîæåñòâî îïòèìóìîâ Ïàðåòî, à⊕ ïîýëåìåíòíàÿ îïåðàöèÿ íà âåêòîðàõ,êîòîðàÿ ïðèìåíÿåòñÿ ê âñåì ýëåìåíòàì ìíîæåñòâ).Äàëåå ðàññìîòðåíû çàäà÷è ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ïîòîêîâ â ñåòÿõ ñíåëèíåéíûìè óñèëåíèÿìè. Äëÿ ìíîãîêðèòåðèàëüíûõ çàäà÷ ìèíèìèçàöèè ñòîèìîñòè ïîòîêà â ñåòè ñ íåïðåðûâíûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè îïòèìóì Ïàðåòî ìîæíîíàéòè îáîáùåííûì ñèìïëåêñ-ìåòîäîì.
Äëÿ çàäà÷è íàõîæäåíèÿ îïòèìàëüíûõ ïî Ïàðåòî äèñêðåòíûõ ïîòîêîâ ïîñòðîåí àëãîðèòì èëüòðîâàííîãî ïåðåáîðà, îáîáùàþùåãîðåøåòî Ýðàòîñåíà, äàíà îöåíêà åãî ýåêòèâíîñòè.Äàëåå ðàññìîòðåíà ìíîãîêðèòåðèàëüíàÿ îïòèìèçàöèÿ äèíàìè÷åñêèõ ïîòîêîâ â ñåòÿõñ íåëèíåéíûìè óñèëåíèÿìè.  äàííîé ðàáîòå ïîñòðîåíû àëãîðèòìû ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè äèíàìè÷åñêèõ ïîòîêîâ äâóõ âèäîâ.
Âî-ïåðâûõ, ìíîãîêðèòåðèàëüíóþîïòèìèçàöèþ äèíàìè÷åñêîãî ïîòîêà ìîæíî ñâåñòè ê îïòèìèçàöèè ñòàòè÷åñêîãî ïîòîêà â ãðàå, ðàçâåðíóòîì âî âðåìåíè. Âî-âòîðûõ, îïòèìàëüíûå ïî Ïàðåòî äèñêðåòíûåäèíàìè÷åñêèå ïîòîêè ìîæíî íàéòè ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ. ãëàâå 3 ðàññìîòðåíû äèíàìè÷åñêèå ñåòåâûå ìíîãîàãåíòíûå çàäà÷è. Çà îñíîâíîéïðèíöèï îïòèìàëüíîñòè ïðèíÿòî îáîáùåíèå ðàâíîâåñèÿ Íýøà, ñèëüíîãî ðàâíîâåñèÿ,k -ðàâíîâåñèÿè îïòèìóìà Ïàðåòî, êîòîðîå ìû áóäåì íàçûâàòü êîàëèöèîííûì ðàâíîâå-ñèåì. Ïóñòü çàäàíî ìíîæåñòâî èãðîêîâIè ìíîæåñòâî âîçìîæíûõ êîàëèöèé èãðîêîâIC ⊆ 2 .
Ñèòóàöèÿ s ∈ S ÿâëÿåòñÿ êîàëèöèîííûì ðàâíîâåñèåì, åñëè äëÿ ëþáîé êîàëèQ′öèè c ∈ C äëÿ ëþáîãî åå îòêëîíåíèÿ sC ∈i∈c Si îáùèé âåêòîð âûèãðûøà êîàëèöèèíå óâåëè÷èòñÿ ò.å., åñëè ó êîãî-òî îäíîãî âûèãðûø óâåëè÷èòñÿ, òî ó êîãî-òî äðóãîãî óìåíüøèòñÿ:∃i Hi (s) < Hi (s||s′C ) ∨ ∀i Hi (s) = Hi (s||s′C ).Êîàëèöèîííîå ðàâíîâåñèå ýòî ÷àñòíûé ñëó÷àé ðàâíîâåñèÿ â êîàëèöèîííîé èãðå.Îïòèìóì Ïàðåòî ýòî ÷àñòíûé ñëó÷àé êîàëèöèîííîãî ðàâíîâåñèÿ. Íî, åñëè âïðåäûäóùåé ãëàâå ðàññìàòðèâàëèñü îïòèìóìû Ïàðåòî äëÿ âåùåñòâåííûõ ñîñòîÿíèéñåòè, îïðåäåëÿåìûõ êóñî÷íî-ëèíåéíûìè óíêöèÿìè, òî â äàííîé ãëàâå ðàññìîòðåíûòîëüêî äèñêðåòíûå ìíîæåñòâà ñîñòîÿíèé ñåòè.Âñå ðàññìàòðèâàåìûå äèíàìè÷åñêèå èãðû ñ ïîëíîé èíîðìàöèåé, ò.å., îòñóòñòâóåòðàçáèåíèå íà èíîðìàöèîííûå ìíîæåñòâà.
Ïðè ýòîì, îäíàêî, äîïóñêàåòñÿ âîçìîæíîñòüîäíîâðåìåííûõ õîäîâ â èãðàõ.11Ïðèâîäèòñÿ îáùåå îïðåäåëåíèå äèíàìè÷åñêîé èãðû: Äèíàìè÷åñêàÿ èãðà ýòî íàáîðΓ = (N, X, T, x0 , (D, U, π), i, {U j }j∈N , {H j }j∈N ),ãäå• N ìíîæåñòâî èãðîêîâ,|N| = n ∈ N;• X ïðîñòðàíñòâî èãðû (â îáùåì ñëó÷àå, ïðîèçâîëüíîå òîïîëîãè÷åñêîå ïðîñòðàí-ñòâî);• T âðåìÿ èãðû, ò.å., ìíîæåñòâî ìîìåíòîâ âðåìåíè, êîòîðûå ìîæíî ñ÷èòàòü íà-òóðàëüíûìè ÷èñëàìè• x0 ∈ XT = {1, 2, . . . , m}; íà÷àëüíàÿ ïîçèöèÿ ;• (D, U, π) óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñèñòåìà ñ äèñêðåòíûì âðåìåíåì T íà ìíîæåñòâå ñîñòîÿíèé X ñ ìíîæåñòâîì óïðàâëåíèé U(x, t), çàäàííûì â êàæäîé ïîçèöèè (x, t) ∈ X × T ;• i : X × T → 2N óíêöèÿ i(x, t)x â ìîìåíò âðåìåíè t;• U j (x, t), j ∈ i(x, t) ìíîæåñòâîQU(x, t) = j∈i(x,t) U j (x, t);• H i : P (x0 ) → Riîïðåäåëÿåò èãðîêîâ, äåëàþùèõ õîä â ñîñòîÿíèèóïðàâëåíèé óíêöèÿ âûèãðûøàäîëæàåìûõ òðàåêòîðèé, èñõîäÿùèõ èçÎñíîâíûåðåçóëüòàòûäîêàçàíûäëÿj -ãîèãðîêà â òî÷êåi-ãî èãðîêà, ãäå P (x0 ) x0 , Ri óïîðÿäî÷åííàÿïîçèöèîííûõ(x, t)òàêîå, ÷òîìíîæåñòâî íåïðîïîëóãðóïïà.ñòðàòåãèé(áåçïàìÿòè)jsj (x1 , .
. . , xt ) = uj (x, t), îáîáùåííîãî èíòåãðàëüíîãî âûèãðûøà H (x(t1 ), . . . x(tm )) =g j (x(t1 ), t1 ) ∗ · · · ∗ g j (x(tm ), tm ), ãäå ∗ ïîëóãðóïïîâàÿ îïåðàöèÿ (÷àñòíûå ñëó÷àè èíòåãðàëüíûé âûèãðûø è òåðìèíàëüíûé âûèãðûø) è äëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷jt+1t(xt+1 ) ∗ · · · ∗ fjn (xn ).â ïîäûãðàõ â ðàçâåðíóòîé îðìå: H(x,t) (x, xt+1 , . . .
, xn ) = fj (x) ∗ fjÄëÿ ñòðîãî ñëåâà óïîðÿäî÷åííîé ïîëóãðóïïû âûèãðûøåé (â ÷àñòíîñòè, äëÿ óïîðÿäî÷åííîé ãðóïïû è äëÿ òåðìèíàëüíîãî âûèãðûøà) êîàëèöèîííîå ðàâíîâåñèå äèíàìè÷åñêè óñòîé÷èâûé ïðèíöèï. Ìîæíî ââåñòè îáû÷íûì îáðàçîì ðåêóððåíòíóþ ñèòóàöèþ,îïðåäåëÿåìóþ ïîñëåäîâàòåëüíî ñ êîíöà èãðû ðåøåíèåì ñîîòâåòñòâóþùèõ ïîäûãð âΓ(x,m−i) íà i-ì øàãå, íà÷èíàþùèõñÿ ñ ìîìåíòà âðåìåíè m − t èç âñåõïîçèöèé x. Äëÿ îáîáùåííîãî èíòåãðàëüíîãî âûèãðûøà åñëè ðåêóððåíòíàÿðàçâåðíóòîé îðìåâîçìîæíûõñèòóàöèÿ ñóùåñòâóåò, òî îíà îïòèìàëüíà è ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâà.  ïîî÷åðåäíîé êîíå÷íîé ìíîãîøàãîâîé èãðå ò.å.
èãðå, â êîòîðîé íà êàæäîì øàãå õîääåëàåò òîëüêî îäèí èãðîê, ðåêóððåíòíàÿ ñèòóàöèÿ âñåãäà ñóùåñòâóåò.12Íàõîæäåíèå âñåõ (êîàëèöèîííûõ) ðàâíîâåñèé ñâîäèòñÿ ê ðåøåíèþ ñåìåéñòâà âñïîìîãàòåëüíûõ êîìáèíàòîðíûõ èãðHi (x, t)Γvi (x, t),â êîòîðûõ−1, H (x, t) ≯ vivHi (x, t) =,1,Hi (x, t) > v âåêòîð âûèãðûøåé i-ãî èãðîêà (èëè êîàëèöèè èãðîêîâ) â ïîäûãðå â ðàçâåðíó-òîé îðìåΓ(x,t) .àññìàòðèâàåòñÿ ñëåäóþùåå óñëîâèå íà ñèòóàöèþ, êîòîðîå ìû áóäåìíàçûâàòü K-óñëîâèåì : äëÿ ëþáîãî ìîìåíòà âðåìåíèìîìåíò èãðîêàΓvi i (x′ , tãäå+ 1)i ∈ i(x, t)täëÿ ëþáîãî õîäÿùåãî â ýòîòäëÿ ëþáîãî àëüòåðíàòèâíîãî õîäàâåðõíåå çíà÷åíèå ðàâíî−1u′ 6= si (x(t), t)â èãðåè îñòàëüíûå èãðîêè èñïîëüçóþò âûèãðûøíóþñòðàòåãèþ. Åñëè âûïîëíÿåòñÿ ïðèíöèï Áåëëìàíà, òî ýòî íåîáõîäèìîå óñëîâèå ðàâíîâåñíîñòè, à åñëè âûèãðûø îáîáùåííûé èíòåãðàëüíûé, òî äîñòàòî÷íîå. Îòñþäà ñëåäóåò àëãîðèòì èëüòðîâàííîãî ïåðåáîðà äëÿ íàõîæäåíèÿ âñåõ ðàâíîâåñèé îáðàòíûìõîäîì.Äëÿ ìîäåëèðîâàíèÿ ëîãèñòè÷åñêèõ ñåòåé öåëåñîîáðàçíî îáîáùèòü äâà êëàññà ñåòåâûõ èãð: èãðû îðìèðîâàíèÿ ñåòåé è èãðû íà ñåòÿõ.
Ýòî îáîáùåíèå ïàðàìåòðè÷åñêèå ãðóïïîâûå ñåòåâûå èãðû. Ïàðàìåòðè÷åñêàÿ ñåòåâàÿ èãðà ýòî ñåòåâàÿ èãðàΓS,U = (N, ((Si )i∈N , (U(i,j) )i,j∈N , (Ui (si ))i∈N,si ∈Si ), G, g, (Hi )i∈N ),• N = {1, . . . n}• Siãäå ìíîæåñòâî èãðîêîâ; àáñòðàêòíîå ìíîæåñòâî ñîñòîÿíèé• U(i,j) ìíîæåñòâî ñîñòîÿíèé ñâÿçèi-ãîèãðîêà ;ìåæäó i-ì èïîëóðåøåòêîé ñ íóëåì (ò.å. äëÿ êàæäîé ïàðûj -ì èãðîêîì, ÿâëÿþùååñÿ íèæíåéa, b ∈ U(i,j) çàäàåòñÿ èíèìóìinf(a, b) ∈ U(i,j) );• Ui (si ) ìíîæåñòâî âîçìîæíûõ íàáîðîâñîñòîÿíèé ñâÿçåé•i-ãîèãðîêà ñ äðóãèìè èãðîêàìè;Xi òðàòåãèé i-ãî èãðîêà ýòî ìíîæåñòâî(ui1 , . . . ui,i−1 , ui,i+1, .
. . , uin )) òàêèõ, ÷òî ui ∈ Ui (si );ìíîæåñòâî• G(S, U) ìíîæåñòâî âîçìîæíûõ ñåòåéU = (U(i,j) )i,j∈N ;•(ui1 , . . . , ui,i−1, ui,i+1, . . . , uin ), uij ∈ Uijìàòðèöà ñìåæíîñòèg(x)íàáîðîâñ ñîñòîÿíèÿìè âåðøèíxi = (si ∈ Si , ui =S = (Si )i∈Nè ðåáåðïîëó÷èâøåéñÿ ñåòè îïðåäåëÿåòñÿ ïî îðìóëåg(x) = inf(x, xT ),ãäåx ìàòðèöà, ñòðîêè êîòîðîé ñòðàòåãèè èãðîêîâ (íà äèàãîíàëè ñòîÿò ñî-ñòîÿíèÿ èãðîêîâ), àinf ïîýëåìåíòíàÿ îïåðàöèÿ íàä ìàòðèöàìè (íà äèàãîíàëèïîëàãàåì äëÿ ïðîèçâîëüíîãî ìíîæåñòâà13inf(z, z) = z );• Hi : G(S, U) → R ïðîèçâîëüíàÿ óíêöèÿ âûèãðûøài-ãîèãðîêà, îïðåäåëåííàÿíà ìíîæåñòâå ñåòåé è ïðèíèìàþùàÿ çíà÷åíèÿ èç óïîðÿäî÷åííîé ïîëóãðóïïûR.Ïàðàìåòðè÷åñêèå ñåòåâûå èãðû åñòåñòâåííûì îáðàçîì âîçíèêàþò èç ñåòåâûõ èãð íàìóëüòèãðàå:Óòâåðæäåíèå. Ìíîæåñòâî ñåòåâûõ èãð íà ìóëüòèãðààõ è ïñåâäîãðààõ ýêâèâà-ëåíòíî (ò.å.
èçîìîðíî ïðè ïåðåõîäå ê íîðìàëüíîé îðìå) ìíîæåñòâó ïàðàìåòðè÷åñêèõ ñåòåâûõ èãð.×àñòíûå ñëó÷àè ïàðàìåòðè÷åñêîé ñåòåâîé èãðû: ñåòåâàÿ èãðà íà íåîðèåíòèðîâàííîìãðàå, ñåòåâàÿ èãðà íà îðèåíòèðîâàííîì ãðàå, èãðà â íîðìàëüíîé îðìå. Èãðà ñîãëà-xi ∈ Xi (xi = (u(i,1) , . . . u(i,n) )) èx′i ≤ xi (â ñìûñëå ïîýëåìåíòíîãî ÷àñòè÷íîãî ïîðÿäêà íà ïîëóðåøåòêàõ) ñëåäóåò x′i ∈ Xi .Ò.å. åñëè èãðîê i èìååò ïðàâî ïðåäëîæèòü èãðîêó j îáðàçîâàòü ñâÿçü ñ áîëüøèìè ïàñèÿ ýòî ïàðàìåòðè÷åñêàÿ ñåòåâàÿ èãðà, â êîòîðîé èçðàìåòðàìè, òî èìååò ïðàâî ïðåäëîæèòü îáðàçîâàòü ñâÿçü ñ ìåíüøèìè ïàðàìåòðàìè.x ÿâëÿåòñÿ (êîàëèöèîííûì) ðàâíîg = inf(x, xT ), òî ñèòóàöèÿ x′ , â êîòîðîéÎêàçûâàåòñÿ, ÷òî â èãðå ñîãëàñèÿ, åñëè ñèòóàöèÿâåñèåì è ïðèâîäèò ê ðåçóëüòèðóþùåé ñåòèx′ = x′T = g ,òàêæå áóäåò (êîàëèöèîííûì) ðàâíîâåñèåì.Ïîýòîìó ìîæíî ðàññìàòðèâàòü íå ðàâíîâåñíûå ñèòóàöèè, à (êîàëèöèîííî) ñòàáèëü-íûå ñåòè è èñêàòü ðàâíîâåñèÿ ïåðåáîðîì ñåòåé è âîçìîæíûõ îòêëîíåíèé êîàëèöèé.
Äëÿìàêñèìèíà âåðíî óòâåðæäåíèå îá èçîëèðóþùåé ìàêñèìèííîé ñèòóàöèè: ñóùåñòâóåò òàêàÿ ìàêñèìèííàÿ ñèòóàöèÿ äëÿ ëþáîé êîàëèöèè÷òîi ∈ C, j ∈/ C,áóäåòu(i,j) = 0(êîàëèöèÿSC,÷òî äëÿ ëþáîãî ðåáðà(i, j)òàêîãî,èçîëèðîâàíà îò îñòàëüíûõ èãðîêîâ). Ýòîçíà÷èò, ÷òî ìàêñèìèí òàêæå ìîæíî èñêàòü ïåðåáîðîì ñåòåé, à íå ñèòóàöèé.  ðåçóëüòàòåïîëó÷àåì, ÷òî â ïàðàìåòðè÷åñêèõ ñåòåâûõ èãðàõ ìîæíî íàéòè:1. àâíîâåñíûå ñåòè çà âðåìÿO(|G(S, U)|(|S1|2.
Ìàêñèìèííóþ ñòðàòåãèþ çà âðåìÿQj|U(j,1) | + · · · + |Sn |O(|G(S, U)|4. èáðèäíîâðåìÿ|Sn |QjñåòèçàPi,j|U(j,n) |)).|U(i,j) |).O(|G(S, U)|(|S1||U(j,n) |)).5. Ñèëüíî ðàâíîâåñíûå ñåòè çà âðåìÿjO(|G(S, U)|).3. Ïîïàðíî ðàâíîâåñíûå ñåòè çà âðåìÿðàâíîâåñíûåQQj|U(j,1) | + · · · +O(|G(S, U)|2 n2 ).PQO(|G(S, U)| S∈C (|S| i∈S,j∈N |Si ||U(i,j)|))O(|G(S, U)|2(n2 + h)), ãäå O(h) ñëîæ-6. Êîàëèöèîííî ðàâíîâåñíûå ñåòè çà âðåìÿïðè èñïîëüçîâàíèè îäíîãî àëãîðèòìà èíîñòü ïðîâåðêè òîãî, âêëþ÷àåò ëè â ñåáÿ äàííîå ìíîæåñòâî êàêóþ-ëèáî êîàëèöèþ ïðè èñïîëüçîâàíèè äðóãîãî àëãîðèòìà.14 ïàðàìåòðè÷åñêîé ñåòåâîé èãðå êàæäûé èãðîê ñîîòíîñèòñÿ ñ îäíîé âåðøèíîé ãðàà. Òàêèì îáðàçîì, âîçíèêàþùàÿ ñèñòåìà (ñåòü) âêëþ÷àåò â ñåáÿ ìíîæåñòâî àãåíòîâ(èãðîêîâ), óïðàâëÿþùèõ ýòîé ñèñòåìîé.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
