Диссертация (1149954), страница 28
Текст из файла (страница 28)
Êàê è â ëþáîé êîíå÷íîé èãðå, â êîíå÷íîéäèíàìè÷åñêîé ñåòåâîé èãðå ñóùåñòâóåò ìàêñèìèííàÿ (îñòîðîæíàÿ) ñòðàòåãèÿ ëþáîãî èãðîêà. Îêàçûâàåòñÿ, äëÿ äèíàìè÷åñêîé ñåòåâîé èãðû âåðíî ñâîéñòâî ìàêñèìèíà, àíàëîãè÷íîåñâîéñòâó ìàêñèìèíà â ñòàòè÷åñêîé èãðå:Óòâåðæäåíèå 3.3.2.  äèíàìè÷åñêîé ñåòåâîé èãðå ñîãëàñèÿ ñóùåñòâóåò òàêàÿ ìàêñèìèí-íàÿ ñòðàòåãèÿ i-ãî èãðîêà, â êîòîðîé íåò äóã èç ìíîæåñòâà M p , ñîåäèíÿþùèõ i-ãî èãðîêàñ îñòàëüíûìè.
Ïðè ýòîì îñòàëüíûå èãðîêè ñîãëàñóþò ñâîè èíòåðåñû, ò.å., ïàðàìåòðûëþáîé äóãè (j, k) ∈ M p ñîâïàäàþò ñ ñîîòâåòñòâóþùèìè ñòðàòåãèÿìè èãðîêîâ j, k .Äîêàçàòåëüñòâî.Ìàêñèìèí äëÿ èãðîêàiâ äèíàìè÷åñêîé èãðå äèíàìè÷åñêè óñòîé÷èâûéïðèíöèï îïòèìàëüíîñòè. Ïðè ýòîì, êàê äîêàçàíî â ïðåäûäóùåì ðàçäåëå äëÿ ëþáûõ äèíàìè÷åñêèõ èãð ñ îáîáùåííûì èíòåãðàëüíûì âûèãðûøåì, âñåãäà ñóùåñòâóåò ìàêñèìèí, óäîâëåòâîðÿþùèé ðåêóððåíòíûì ñîîòíîøåíèÿì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ. Äîêàæåì126òåïåðü ïî èíäóêöèè ïî ÷èñëó ìîìåíòîâ âðåìåíè, ÷òî ñóùåñòâóåò ìàêñèìèí, èçîëèðóþùèéèãðîêà i, â êîòîðîì îñòàëüíûå èãðîêè ñîãëàñóþò ñâîè äåéñòâèÿ.Áàçà èíäóêöèè î÷åâèäíà íà ïîñëåäíåì øàãå ðàçûãðûâàåòñÿ ñòàòè÷åñêàÿ èãðà, äëÿ êîòîðîé ñóùåñòâóåò èçîëèðóþùèé ìàêñèìèí ïî äîêàçàííîìó ðàíåå óòâåðæäåíèþ. Åñëè äëÿèãðû äëèíîékøàãîâ ñóùåñòâóåò èçîëèðóþùèé ìàêñèìèí, òî äëÿ èãðû äëèíîék+1øàãñóùåñòâóåò ìàêñèìèí, êîòîðûé ïî ðåêóððåíòíûì ñîîòíîøåíèÿì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ ñâîäèòñÿ ê ìàêñèìèííîìó âûáîðó íà ïåðâîì øàãå èãðû èçkøàãîâ.
Òàêîé ìàêñèìèíìîæíî âûáðàòü èçîëèðóþùèì ïî ñâîéñòâó ñòàòè÷åñêîé èãðû, â ïîñëåäóþùåé èãðå èçk øàãîâîí òàêæå áóäåò èçîëèðóþùèì ïî èíäóêöèîííîìó ïðåäïîëîæåíèþ.iÒàêèì îáðàçîì, â äèíàìè÷åñêîé ñåòåâîé èãðå äëÿ êàæäîãî èãðîêàìèííàÿ ñèòóàöèÿs,â êîòîðîé ìíîæåñòâîMpïóñòî. Áîëåå òîãî: äëÿ îñòàëüíûõ èãðîêîâ äóãè(i, j) ∈ M päîëæíî áûòüupi (j, t) = upj (i, t),äóã âçàèìîäåéñòâèÿMpñ äðóãèìè èãðîêàìèèìåþò òàêîå ñâîéñòâî: äëÿ ëþáîé äóãèïðè ýòîì ñîñòîÿíèå âåðøèíñëåäóþùèé ìîìåíò âðåìåíè îïðåäåëÿåòñÿ ñîñòîÿíèåì äâóõ äóãðàçîì,iñóùåñòâóåò ìàêñè-si (t + 1), sj (t + 1)upi (j, t) = upj (i, t).âÒàêèì îá-êàæäàÿ äóãà âçàèìîäåéñòâèÿ èãðîêîâ ýêâèâàëåíòíà 1 ñòðóêòóðíîé äóãå è2 äèíàìè÷åñêèì.Ïîëó÷àåì ðåêóððåíòíûéàëãîðèòìíàõîæäåíèÿ ìàêñèìèíà äëÿ ïðîèçâîëüíîãî èãðîêà i:t ∈ T äëÿ êàæäîãî ñîñòîÿíèÿQp{sj (t) ∈ Sj , udj ∈ Ujd = i Uijd , upkl ∈ U(k,l)}j,k,l∈N, k6=l6=i .ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ íà êàæäîì øàãåx∈Xèùåì ìàêñèìèí äëÿ èãðîêàïîn(n−1)/2O(xmsn und up), ãäå x êîëè÷åñòâî âîçìîæíûõ ñîñòîÿíèé ñåQpds = maxi |Si |, ud = maxi,si ,t j=1,...,n |U(i,j)(si , t)|, up = maxi,j,si |U(i,j)(si )|.
Çàìåòèì, ÷òî,Ñëîæíîñòü àëãîðèòìà òè,ièñïîëüçóÿ ñòàíäàðòíûé àëãîðèòì äëÿ äèíàìè÷åñêîé èãðû ñ ïîçèöèîííûìè ñòðàòåãèÿìè èèãíîðèðóÿ ñåòåâóþ ñòðóêòóðó èãðû, ìû ïîëó÷èëè áû áîëüøóþ ñëîæíîñòü àëãîðèòìà 2O(xmsn und unp ).àâíîâåñèå ïî Íýøó â äèíàìè÷åñêîé ñåòåâîé èãðå òàê æå, êàê è â ñòàòè÷åñêîé, îáëàäàåòñâîéñòâîì ñîãëàñîâûâàòü ñòðàòåãèè èãðîêîâ:Óòâåðæäåíèå 3.3.3. Äëÿ êàæäîé (êîàëèöèîííî) ðàâíîâåñíîé ñèòóàöèè, îïðåäåëÿþùåéóïðàâëåíèå u(x, t) â äèíàìè÷åñêîé ñåòåâîé èãðå, äëÿ êàæäîé äóãè (i, j) ∈ M p ìîæíî óïðàâ-ëåíèÿì ui (j, x, t), uj (i, x, t) ïðèñâîèòü îäíî çíà÷åíèå uij (x, t) = inf(ui (j, x, t), uj (i, x, t)).
Ïðèýòîì ïàðàìåòðû ñåòè íå èçìåíÿòñÿ, à ñèòóàöèÿ îñòàíåòñÿ ðàâíîâåñíîé.Äîêàçàòåëüñòâî.Àíàëîãè÷íî äîêàçàòåëüñòâó óòâåðæäåíèÿ äëÿ ñòàòè÷åñêîé èãðû. ëàâíàÿîñîáåííîñòü äóã èçMpâ òîì, ÷òî, çàìåíèâ óïðàâëåíèÿ îáîèõ èãðîêîâuij (x, t) = inf(ui (j, x, t), uj (i, x, t)),i, jíà îäíî çíà÷åíèåìû íå èçìåíèì ïàðòèþ è ðàçâå ÷òî óìåíüøèì âîçìîæíî-127ñòè èãðîêîâ íà êàæäîì øàãå. Ýòî çíà÷èò, ÷òî åñëè äî ìîäèèêàöèè ñòðàòåãèé âñå îòêëîíåíèÿ áûëè íåâûãîäíû èãðîêàì (èëè êîàëèöèÿì), ïîñëå ìîäèèêàöèè êîëè÷åñòâî îòêëîíåíèéóìåíüøèòñÿ, è îíè âñå ïî-ïðåæíåìó áóäóò íåâûãîäíû.àññìîòðèìàëãîðèòìèëüòðîâàííîãî ïåðåáîðà äëÿ íàõîæäåíèÿ àáñîëþòíî ðàâíîâåñ-íûõ òðàåêòîðèé â äèíàìè÷åñêîé ñåòåâîé èãðå, êîòîðûé ðàáîòàåò òàê:1. Íà êàæäîì øàãå íàõîäèì âñå ñòàáèëüíûå ñåòè è ñîîòâåòñòâóþùèå âåêòîðû âûèãðûøåéìåòîäîì ïåðåáîðà ñåòåé è ïðîâåðêè êàæäîé ñåòè íà ðàâíîâåñíîñòü. Ïðè ýòîì äîñòàòî÷íî(x, t)â êàæäîé ïîçèöèèêàæäîé äóãè èçMpðàññìàòðèâàòü òîëüêî òå íàáîðû õîäîâ, â êîòîðûõ ïàðàìåòðûîáà èãðîêà óñòàíàâëèâàþò ðàâíûìè.2.
Çíàÿ ñòàáèëüíûå ñåòè â ìîìåíòt + 1,íàõîäèì ñòàáèëüíûå ñåòè â ìîìåíòtòåì æåàëãîðèòìîì, ÷òî è â îáùåé äèíàìè÷åñêîé èãðå ñ ïîçèöèîííûìè ñòðàòåãèÿìè.Òåîðåìà 18(óñëîâèÿ ðàâíîâåñèÿ â äèíàìè÷åñêîé ñåòåâîé èãðå).1. Åñëèñèòóàöèÿs(êîàëèöèîííî) ðàâíîâåñíà è ðàâíîâåñèå äèíàìè÷åñêè óñòîé÷èâî, òî âûïîëíÿåòñÿK -óñëîâèå.2. Åñëè âûèãðûø îáîáùåííûé èíòåãðàëüíûé è âûïîëíÿåòñÿ K -óñëîâèå, òî ñèòóàöèÿs (êîàëèöèîííî) ðàâíîâåñíà.3. Âñå (êîàëèöèîííûå) ðàâíîâåñèÿ â äèíàìè÷åñêîé ñåòåâîé èãðå ìîæíî íàéòè àëãîðèòìîì èëüòðîâàííîãî ïåðåáîðà äëÿ íàõîæäåíèÿ àáñîëþòíûõ ðàâíîâåñèé â äèíàìè÷åñêîé ñåòåâîé èãðå.Äîêàçàòåëüñòâî.1. Ñëåäóåò èç òåîðåìû îá óñëîâèÿõ ðàâíîâåñèÿ â äèíàìè÷åñêîé èãðå.2.
Ñëåäóåò èç òåîðåìû îá óñëîâèÿõ ðàâíîâåñèÿ â äèíàìè÷åñêîé èãðå.3. Ñëåäóåò èç óòâåðæäåíèÿ 3.3.3.Ñëîæíîñòüðèè(âñåõ(O(xmnsàëãîðèòìààáñîëþòíîíàõîæäåíèÿðàâíîâåñíûõn+1 n+1 n(n+3)/2 2ud upv )).Ñëîæíîñòüàáñîëþòíîòðàåêòîðèé)ïåðâîãîðàâíîâåñíîéàëãîðèòìàn(n+1)/2+ncc2c sn+c udn+c up(O(xmvw(O(xmvw 2n 2n n(n+1)s ud up(n),+ ch))).àâòîðîãîàëãîðèòìàn(n+3)/2O(xmnsn+1 un+1updíàõîæäåíèÿëèöèîííî ðàâíîâåñíîé òðàåêòîðèè (âñåõ òàêèõ òðàåêòîðèé) òðàåêòî-àáñîëþòíîêîà-n(n+1)/2+ncO(xmc2c sn+c udn+cupn(n+1)O(xms2n u2nd up))(n + ch))Èñõîäÿ èç ñëîæíîñòè àëãîðèòìà íàõîæäåíèÿ ìàêñèìèíîâ,ïîëó÷àåì ñëîæíîñòü àëãîðèòìà äëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷ äëÿ íàõîæäåíèÿ âñåõ128ðàâíîâåñíûõ òðàåêòîðèéêîàëèöèîííûõ ðàâíîâåñèé n(n+1)/2)n(n+1)/2v)).O((x2 m2 + xmv)nsn+1 un+1updO(xmc(sudunp )c (xm + sn und upçà ñ÷åò äóã âçàèìîäåéñòâèÿ èçMpè äëÿ íàõîæäåíèÿ âñåõÍåñëîæíî âèäåòü, ÷òîýòî ñóùåñòâåííî ìåíüøå, ÷åì â îáùèõ àëãîðèòìàõ äëÿäèíàìè÷åñêèõ èãð ñ ïîçèöèîííûìè ñòðàòåãèÿìè.3.4Çàêëþ÷åíèåÈòàê, â äèññåðòàöèîííîé ðàáîòå îðìàëèçîâàíû óïðàâëÿåìûå äèíàìè÷åñêèå ìíîãîêðèòåðèàëüíûå ñèñòåìû, ðàñïðåäåëåííûå â ïðîñòðàíñòâå.
Ïðè èõ èññëåäîâàíèè ïîëó÷åíû ñëåäóþùèåðåçóëüòàòû:1. Äîêàçàíà òåîðåìà 1 î äîñòèæåíèè ìàêñèìàëüíîãî çíà÷åíèÿ îïòèìàëüíûì ïîòîêîì, ïîçâîëÿþùàÿ ñâåñòè äàííóþ çàäà÷ó ê ñåìåéñòâó çàäà÷ ñ âîãíóòûìè êóñî÷íî-ëèíåéíûìèóñèëåíèÿìè, è òåîðåìà 2 î êîìïîçèöèè ïîòîêîâ, ñâîäÿùàÿ çàäà÷ó ñ âîãíóòûìè êóñî÷íîëèíåéíûìè óñèëåíèÿìè ê çàäà÷å ñ ëèíåéíûìè óñèëåíèÿìè.
Íà îñíîâå ýòèõ òåîðåì ïîñòðîåí àëãîðèòì íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà â ñåòè ñ íåïðåðûâíûìè êóñî÷íîëèíåéíûìè óñèëåíèÿìè â äóãàõ. Ïîëó÷åíà îöåíêà ñëîæíîñòè äàííîãî àëãîðèòìà, ïîêàçûâàþùàÿ, ÷òî îí áîëåå ýåêòèâåí, ÷åì îáû÷íûå àëãîðèòìû êóñî÷íî-ëèíåéíîãîïðîãðàììèðîâàíèÿ.2. Ïîñòðîåíà ìîäåëü óïðàâëÿåìîé ëîãèñòè÷åñêîé ñèñòåìû, ðàñïðåäåëåííîé â äèñêðåòíîìïðîñòðàíñòâå è ðàçâèâàþùåéñÿ âî âðåìåíè.
Ôîðìàëèçîâàíà çàäà÷à íàõîæäåíèÿ îïòèìàëüíûõ óïðàâëåíèé â øèðîêîì êëàññå òàêèõ ñèñòåì, êîòîðàÿ ñâîäèòñÿ ê çàäà÷å î äèíàìè÷åñêîì ïîòîêå ìèíèìàëüíîé ñòîèìîñòè èëè ê çàäà÷å î ïàðåòîâñêîì äèíàìè÷åñêîìïîòîêå.3. Ïîñòðîåíà îáùàÿ îðìàëèçàöèÿ ñåòåâîé èãðû, âêëþ÷àþùàÿ â ñåáÿ êàê èãðû îðìèðîâàíèÿ ñåòåé, òàê è èãðû íà ñåòÿõ. Ýòó îðìàëèçàöèþ ìîæíî ïðèìåíÿòü ê ìîäåëèðîâàíèþ øèðîêîãî êëàññà ìíîãîàãåíòíûõ ýêîíîìè÷åñêèõ ñèñòåì, ðàñïðåäåëåííûõ â äèñêðåòíîì ïðîñòðàíñòâå. Ïîñòðîåíû àëãîðèòìû íàõîæäåíèÿ ðàâíîâåñèé â òàêîé ñåòåâîéèãðå, êîòîðûå, õîòÿ è èìåþò ýêñïîíåíöèàëüíóþ âðåìåííóþ ñëîæíîñòü, áîëåå ýåêòèâíû, ÷åì àëãîðèòìû ïîëíîãî ïåðåáîðà.4.
Ôîðìàëèçîâàíà äèíàìè÷åñêàÿ ñåòåâàÿ èãðà, îáîáùàþùàÿ èçâåñòíûå îïðåäåëåíèÿ ñòàòè÷åñêèõ ñåòåâûõ èãð è ìíîãîøàãîâûõ èãð. Ïðè ýòîì âîçìîæíû óíêöèè âûèãðûøà,ïðèíèìàþùèå çíà÷åíèÿ íà ïðîèçâîëüíûõ óïîðÿäî÷åííûõ ïîëóãðóïïàõ. Ïîñòðîåí àëãîðèòì íàõîæäåíèÿ âñåõ àáñîëþòíûõ ðàâíîâåñèé è êîàëèöèîííûõ ðàâíîâåñèé ñ ïîìî-129ùüþ ãðàà, ðàçâåðíóòîãî âî âðåìåíè.
Äîêàçàíà òåîðåìà 18 îá óñëîâèÿõ ñóùåñòâîâàíèÿ(êîàëèöèîííîãî) ðàâíîâåñèÿ, ïîçâîëÿþùàÿ ñâåñòè çàäà÷ó íàõîæäåíèÿ ðàâíîâåñèÿ ê êîíå÷íîìó íàáîðó ìàêñèìèííûõ çàäà÷ äëÿ äèíàìè÷åñêîãî ïîòîêà.Òåìà äàííîé äèññåðòàöèè äîïóñêàåò øèðîêèå è äàëåêî èäóùèå îáîáøåíèÿ.  ÷àñòíîñòè, âîçìîæíî ðàññìîòðåíèå èíîðìàöèîííûõ ïîòîêîâ â ñèñòåìå è, ñîîòâåòñòâåííî, ââåäåíèå íåïîëíîé èíîðìàöèè. Âðåìÿ â ðàññìàòðèâàåìûõ ñèñòåìàõ ìîæåò áûòü íåïðåðûâíûì,ïðèòîì, ÷òî ïðîñòðàíñòâî îñòàåòñÿ äèñêðåòíûì.Ïðåäñòàâëÿåò áîëüøîé èíòåðåñ èññëåäîâàíèå íåêîòîðûõ ÷àñòíûõ ñëó÷àåâ ðàññìîòðåííûõçàäà÷: ïîòîêîâ ñ ðàçðûâíûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè, ìîäåëèðóþùèå, íàïðèìåð,ïðîöåññ ïåðåìåùåíèÿ ïðîäóêöèè ìåæäó ñêëàäàìè; èãð óïðàâëåíèÿ ïîòîêàìè áåç óñèëåíèéñ êóñî÷íî-ëèíåéíûìè óíêöèÿìè ñòîèìîñòè; òî æå, íî ñ ëèíåéíûìè óñèëåíèÿìè, êóñî÷íîëèíåéíûìè óñèëåíèÿìè.
Ïîäîáíûå èãðû ìîãóò ìîäåëèðîâàòü, íàïðèìåð, òðàíñïîðòíûå ïîòîêè â ãîðîäå.Ëèòåðàòóðà[1℄Àâäîøèí Ñ.Ì., Áåëîâ Â.Â.Îáîáùåííûé ìåòîä âîëíû äëÿ ðåøåíèÿ ýêñòðåìàëüíûõçàäà÷ íà ãðààõ // ÆÂÌ è ÌÔ, ÀÍ ÑÑÑ. 1979. Ò. 19, 3. Ñ. 739755.[2℄Àâäîøèí Ñ.Ì., Áåëîâ Â.Â., Ìàñëîâ Â.Ï., Ïèòåðêèí Â.Ì.Îïòèìèçàöèÿ ãèáêèõ ïðîèç-âîäñòâåííûõ ñèñòåì.
Ì.: èí-ò ýëåêòðîí. ìàøèíîñòðîåíèÿ, 1987. 91 ñ.[3℄Àøìàíîâ Ñ.À. Ìàòåìàòè÷åñêèåìîäåëè è ìåòîäû â ýêîíîìèêå. Ì.: èçä.-âî Ìîñê. óí.-òà,1980. 199 ñ.[4℄Áàðáàøèí Å.À.Ê òåîðèè îáîáùåííûõ äèíàìè÷åñêèõ ñèñòåì // Ó÷åáíûå çàïèñêè ÌÓ.1949. 135. Ñ. 110133.[5℄Áåëòàäçå .Í.Ìíîæåñòâà ðàâíîâåñíûõ ñèòóàöèé â ëåêñèêîãðàè÷åñêèõ áåñêîàëèöèîí-íûõ èãðàõ. // Áþëëåòåíü Àêàäåìèè Íàóê ðóçèíñêîé ÑÑ.
1980. Ò. 98, 1. Ñ. 4144.[6℄Áåëëìàí .Äèíàìè÷åñêîå ïðîãðàììèðîâàíèå. / Ïåð. ñ àíãë. È.Ì. Àíäðååâà, À.À. Êîð-áóò, È. Â. îìàíîâñêèé, È. Í. Ñîêîëîâà, ïîä ðåä. Í. Í. Âîðîáüåâà. Ì.: èçäàòåëüñòâîÈíîñòðàííàÿ ëèòåðàòóðà, 1960. 340 .[7℄Áåðæ Ê.Òåîðèÿ ãðàîâ è åå ïðèìåíåíèÿ. Ì.: èçäàòåëüñòâî èíîñòðàííîé ëèòåðàòóðû,1958. 320 ñ.[8℄ Ââåäåíèå â ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå òðàíñïîðòíûõ ïîòîêîâ (ïîä ðåä. À.Â.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
