Диссертация (1149954), страница 18
Текст из файла (страница 18)
ðóáëåé. Çàìåòèì, ÷òî äàæå â ñàìîì ìåäëåííîì ñëó÷àå, êîãäà èðìà80ïîñëåäîâàòåëüíî ðåêîíñòðóèðóåò 5 äîìîâ, ó íåå óéäåò íà ýòî 10 ëåò. Ñëåäîâàòåëüíî, ìîæíîñ÷èòàòü, ÷òî íàøà ìîäåëü îãðàíè÷åíà âî âðåìåíè ãîðèçîíòîìÁóäåì îáîçíà÷àòü ÷åðåç(x1 , x2 )T = 10. ñîîòâåòñòâåííî êîëè÷åñòâî íîâûõ äîìîâ è ðåêîíñòðó-èðîâàííûõ ñòàðûõ äîìîâ. Ïîñòðîèì ãðà ñîáûòèé, âåðøèíû êîòîðîãî ïîñòðîåííûå è ðåêîíñòðóèðîâàííûå äîìà, à äóãè ïàìÿòü î ñîñòîÿíèè âåðøèí è âûáðàííîì â ýòèõ âåðøèíàõóïðàâëåíèè (ò.å. ðåøåíèè âîçäåéñòâîâàòü íà äîì òåì èëè èíûì ñïîñîáîì).
Òàêèì îáðàçîì,äóãè ìîãóò áûòü 3-õ òèïîâ:1. Ñòàðûé äîì, ñ êîòîðûì íè÷åãî íå äåëàþò.2. Ñíåñåííûå ñòàðûå äîìà, íà ìåñòå êîòîðûõ ñòðîÿò íîâûé äîì.3. Ñòàðûé äîì, êîòîðûé ïîäâåðãàåòñÿ ðåêîíñòðóêöèè.Áóäåì óñëîâíî îáîçíà÷àòü âåêòîð ñîñòîÿíèé ðàáîò ÷åðåç(x′1 , x′2 ). Øòðèõè â äàííîì ñëó÷àå ýòî íå ïðîèçâîäíûå, õîòÿ îíè òîæå îáîçíà÷àþò èçìåíåíèÿ ñîîòâåòñòâóþùèõ âåëè÷èí. Ïðèýòîì áóäåì ïèñàòü, íàïðèìåð,x′i = 11 + 32 ,åñëè èìååòñÿ 1 ðàáîòà, êîòîðóþ îñòàëîñü äåëàòü1 ãîä, è 3 ðàáîòû, êîòîðûå îñòàëîñü äåëàòü 2 ãîäà.åøåíèå çàäà÷è ðàñïðåäåëåíèÿ ðåñóðñîâ íà ñòðîèòåëüñòâî äîìîâÊîëè÷åñòâî òåððèòîðèèâåðøèí (äîìîâ)xsó èðìû îäíîçíà÷íî îïðåäåëÿåòñÿ ñîñòîÿíèåì îïèñàííûõ âûøåè äóã (ïðîöåññîâ, ïðîèñõîäÿùèõ ñ äîìàìè)òèé åñòü åùå îäíà âåðøèíày,x′ .Êðîìå òîãî, â ãðàå ñîáû-îïðåäåëÿþùàÿ êîëè÷åñòâî äåíåæíûõ ðåñóðñîâ. Ýòà âåðøèíà,âîîáùå ãîâîðÿ, ìîæåò íàõîäèòüñÿ â áåñêîíå÷íîì êîëè÷åñòâå ñîñòîÿíèé, ïîñêîëüêó ìû èçìåðÿåì êîëè÷åñòâî äåíåã âåùåñòâåííûìè ÷èñëàìèR+ .Íî åñëè ìû áóäåì ðåøàòü çàäà÷óìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ ïðÿìûì õîäîì (îò íà÷àëà ê êîíöó), ñ èêñèðîâàííûì íà÷àëüíûì êîëè÷åñòâîì äåíåãy1 (0),òî êîëè÷åñòâî ñîñòîÿíèé äåíåæíîãî ðåñóðñàîêàçûâàåòñÿ êîíå÷íûì.Òàêèì îáðàçîì, â ãðàå ñîáûòèé îñòàåòñÿ 2 âåðøèíû, ñîîòâåòñòâóþùèå ïîÿâëåíèþ íîâûõäîìîâ è ðåêîíñòðóèðîâàííûõ äîìîâ.
àçâåðíóòûé âî âðåìåíè ãðà èçîáðàæåí íà ðèñóíêå2.1 (ñòðåëêè íà äóãàõ íå óêàçàíû, íî ïîíÿòíî, ÷òî âñå äóãè âåäóò ñëåâà íàïðàâî).Áóäåì òåïåðü ðàññìàòðèâàòü âñå âîçìîæíûå âàðèàíòû ñîñòîÿíèé â ìîìåíòû âðåìåíè0, 1, 2, . . . , 10. Íà ãðàå, ðàçâåðíóòîì âî âðåìåíè, ýòî ñîñòîÿíèÿ âåðøèí è äóã, êîòîðûå ìîæíîóñëîâíî îáîçíà÷èòü öèðàìè. Íî òîãäà äëÿ êàæäîãî âîçìîæíîãî ïëàíà ñòðîèòåëüíûõ ðàáîòïðèäåòñÿ ðèñîâàòü ñâîé ãðà, ðàçâåðíóòûé âî âðåìåíè.
Âìåñòî ýòîãî ìû áóäåì îïèñûâàòüäëÿ êàæäîãî ãîäà êîëè÷åñòâî äîìîâx1 , x2 , êîëè÷åñòâîñòðîÿùèõñÿ äîìîâx′1 , x′2 , êîëè÷åñòâî81èñ. 2.1: ðà, ðàçâåðíóòûé âî âðåìåíèðàáî÷èõw,êîëè÷åñòâî ñâîáîäíîé òåððèòîðèèsè êîëè÷åñòâî äåíåã ó èðìûy.Ïî ìåòî-äó äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, áóäåì íà êàæäîì øàãå îñòàâëÿòü òîëüêî âàðèàíòû,îïòèìàëüíûå ïî Ïàðåòî ò.å. èñêëþ÷àòü äîìèíèðóåìûå âàðèàíòû. ïðèëîæåíèè A.2 ðàññ÷èòàíû ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ âñå âîçìîæíûåâàðèàíòû, íà÷èíàÿ ñ 0-ãî ãîäà è çàêàí÷èâàÿ 10-ì ãîäîì. Ïîëó÷èëèñü ñëåäóþùèå îïòèìàëüíûåðåøåíèÿ:•Çà 2 ãîäà ìîæíî ïîëó÷èòü ïðèáûëü2480ìëí.
ðóá., ðåêîíñòðóèðîâàâ 5 äîìîâ.•Çà 3 ãîäà ìîæíî ïîëó÷èòü ïðèáûëü4144ìëí. ðóá., ñíåñÿ 3 äîìà, ïîñòðîèâ íà èõ ìåñòå2 íîâûõ äîìà è 2 äîìà ðåêîíñòðóèðîâàâ.•Çà 6 ëåò ìîæíî ïîëó÷èòü ïðèáûëü4778 ìëí. ðóá., ñíåñÿ 5 äîìîâ è ïîñòðîèâ íà èõ ìåñòå3 íîâûõ äîìà.Òàêèì îáðàçîì, ìíîæåñòâî Ïàðåòî â äàííîé çàäà÷å îêàçàëîñü ñîâñåì íåáîëüøèì îíîñîñòîèò èç 3-õ ýëåìåíòîâ.82ëàâà 3Äèíàìè÷åñêèå ñòðàòåãè÷åñêèåìíîãîêðèòåðèàëüíûå çàäà÷è íà ñåòÿõ äàííîé ãëàâå ðàññìîòðåíà çàäà÷à íàõîæäåíèÿ ðàâíîâåñèÿ â äèíàìè÷åñêèõ ñåòåâûõ èãðàõ.Îíà ïîñòðîåíà ïî îáðàçöó ïðåäûäóùåé ãëàâû, òîëüêî âìåñòî çàäà÷ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ðàññìàòðèâàþòñÿ èãðû.
Ôîðìàëüíî èãðîâûå çàäà÷è ÷àñòíûé ñëó÷àé ìíîãîêðèòåðèàëüíûõ. Íî â èãðàõ íå âûïîëíÿåòñÿ àêñèîìà íåçàâèñèìîñòè îò ìíîæåñòâà àëüòåðíàòèâ,è ïîòîìó èõ èçó÷åíèå èäåò ñîâåðøåííî ïî èíîìó ïóòè, ÷åì èçó÷åíèå ìíîãîêðèòåðèàëüíûõçàäà÷.Ïðè ýòîì îïòèìóì Ïàðåòî ìîæíî ñ÷èòàòü ÷àñòíûì ñëó÷àåì ðàâíîâåñèÿ â êîàëèöèîííîéèãðå [9℄.  ýòîì ñìûñëå, èãðîâûå çàäà÷è ýòî áîëåå îáùèé êëàññ çàäà÷, ÷åì ìíîãîêðèòåðèàëüíûå. Ïîýòîìó â äàííîé ãëàâå îíè ðàññìîòðåíû áîëåå ïîâåðõíîñòíî è ìåíåå ïîäðîáíî, ÷åììíîãîêðèòåðèàëüíûå çàäà÷è â ïðåäûäóùåé ãëàâå.
 ÷àñòíîñòè, åñëè çàäà÷à ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ïîòîêîâ ðåøåíà äëÿ îáøèðíîãî êëàññà ìíîæåñòâ è óíêöèé, òî çàäà÷àíàõîæäåíèÿ ðàâíîâåñèÿ â èãðàõ ðåøàåòñÿ òîëüêî äëÿ êîíå÷íûõ ìíîæåñòâ.àññìîòðåííûå çàäà÷è ýòî ñî÷åòàíèå òðåõ êëàññîâ îïòèìèçàöèîííûõ çàäà÷:1. Äèíàìè÷åñêèå îïòèìèçàöèîííûå çàäà÷è ñ äèñêðåòíûì âðåìåíåì.2.
Èãðîâûå çàäà÷è, êîòîðûå â îáùåì ñëó÷àå ìîäåëèðóþòñÿ êîàëèöèîííûìè èãðàìè [9℄.àññìàòðèâàåòñÿ âàæíûé ÷àñòíûé ñëó÷àé, êîòîðûé ñâîäèòñÿ ê êîàëèöèîííîìó ðàâíîâåñèþ â èãðå â íîðìàëüíîé îðìå.3. Ñåòåâûå îïòèìèçàöèîííûå çàäà÷è. Êàê è â ïðåäûäóùåé ãëàâå, ìû ñâîäèì çàäà÷ó îïðåäåëåíèÿ ïàðàìåòðîâ ñåòè ê îáîáùåííîé çàäà÷å îïòèìèçàöèè ïîòîêà â ñåòè.Ñîîòâåòñòâåííî ýòè 3 êëàññà çàäà÷ ïîðîæäàþò òàêèå ñî÷åòàíèÿ:831. Äèíàìè÷åñêèå èãðîâûå çàäà÷è. àññìàòðèâàþòñÿ òîëüêî èãðîâûå çàäà÷è ñ äèñêðåòíûìâðåìåíåì, ò.å. ìíîãîøàãîâûå èãðû. ×òî êàñàåòñÿ ïåðåäà÷è èíîðìàöèè, ïðåäïîëàãàåòñÿíàëè÷èå ó âñåõ àãåíòîâ ïîëíîé èíîðìàöèè î ñîñòîÿíèè ñèñòåìû.
Ïîýòîìó âñå ðàññìàòðèâàåìûå äèíàìè÷åñêèå èãðû ñ ïîëíîé èíîðìàöèåé, ò.å., îòñóòñòâóåò ðàçáèåíèå íàèíîðìàöèîííûå ìíîæåñòâà. Íî ïðè ýòîì äîïóñêàåòñÿ âîçìîæíîñòü îäíîâðåìåííûõõîäîâ â èãðàõ.2. Èãðîâûå ñåòåâûå çàäà÷è ò.å. ñåòåâûå èãðû. àññìàòðèâàåòñÿ ñàìûé îáùèé êëàññ çàäà÷ ïàðàìåòðè÷åñêèå ñåòåâûå èãðû, â êîòîðûõ èãðîêè óïðàâëÿþò ïîòîêàìè â ñåòè.3. Äèíàìè÷åñêèå èãðîâûå ñåòåâûå çàäà÷è ò.å. äèíàìè÷åñêèå ñåòåâûå èãðû.Ïîñòðîåíû îïðåäåëåíèå è àëãîðèòìû íàõîæäåíèÿ ðàâíîâåñèé â ñòàòè÷åñêèõ è äèíàìè÷åñêèõ ñåòåâûõ èãðàõ.3.1Êîàëèöèîííûå ïðèíöèïû îïòèìàëüíîñòè â äèíàìè÷åñêèõ èãðàõ äàííîì ðàçäåëå äàåòñÿ äîñòàòî÷íî îáùåå îïðåäåëåíèå äèíàìè÷åñêîé èãðû ñ èêñèðîâàííîéïðîäîëæèòåëüíîñòüþ, èññëåäóåòñÿ ñóùåñòâîâàíèå è äèíàìè÷åñêàÿ óñòîé÷èâîñòü êîàëèöèîííûõ ðåøåíèé.
Ïîêàçàíî, ÷òî íàõîæäåíèå âñåõ êîàëèöèîííûõ ðàâíîâåñèé ñâîäèòñÿ ê ðåøåíèþñåìåéñòâà âñïîìîãàòåëüíûõ êîìáèíàòîðíûõ èãð.3.1.1Îïðåäåëåíèå äèíàìè÷åñêîé èãðû ñ îäíîâðåìåííûìè õîäàìèèãðîêîâÁóäåì ðàññìàòðèâàòü ñàìîå îáùåå îïðåäåëåíèå äèíàìè÷åñêîé èãðû èç [67℄, ñ íåçíà÷èòåëüíûìè ìîäèèêàöèÿìè:Îïðåäåëåíèå27.Äèíàìè÷åñêàÿ(N, X, T, x0 , (D, U, π), i, {U j }j∈N , {H j }j∈N ),• N ìíîæåñòâî èãðîêîâ,• Xïðîñòðàíñòâî èãðû• Tâðåìÿ èãðû,íûìè ÷èñëàìèèãðàýòîíàáîðΓ=ãäå|N| = n ∈ N;(â îáùåì ñëó÷àå, ïðîèçâîëüíîå òîïîëîãè÷åñêîå ïðîñòðàíñòâî);ò.å., ìíîæåñòâî ìîìåíòîâ âðåìåíè, êîòîðûå ìîæíî ñ÷èòàòü íàòóðàëü-T = {1, 2, .
. . , m};84• x0 ∈ Xíà÷àëüíàÿ ïîçèöèÿ ;• (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) ìíîæåñòâî óïðàâëåíèé j -ãî èãðîêà â òî÷êå (x, t) òàêîå, ÷òî U(x, t) =Qjj∈i(x,t) U (x, t);• H i : P (x0 ) → Ri óíêöèÿ âûèãðûøàæàåìûõ òðàåêòîðèé, èñõîäÿùèõ èçÇàìå÷àíèåi-ãîx0 , Rièãðîêà, ãäåP (x0 ) ìíîæåñòâî íåïðîäîë- óïîðÿäî÷åííàÿ ïîëóãðóïïà.3.1.1.
Òàêèì îáðàçîì, íàøå îïðåäåëåíèå äèíàìè÷åñêîé èãðû îòëè÷àåòñÿ îò äàí-íîãî â [67℄ òåì, ÷òî:1. ßâíî îïðåäåëÿåòñÿ óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñèñòåìà òàêèì îáðàçîì, äèíàìè÷åñêàÿ èãðà ñòàíîâèòñÿ ÷àñòíûì ñëó÷àåì äèíàìè÷åñêîé çàäà÷è óïðàâëåíèÿ.2. àññìàòðèâàþòñÿ âûèãðûøè èç ïðîèçâîëüíîãî óïîðÿäî÷åííîãî ìíîæåñòâà, â ñîîòâåòñòâèè ñ ñîâðåìåííîé òåíäåíöèåé ðàññìàòðèâàòü âûèãðûøè ñàìîãî îáùåãî âèäà [53℄.Ýòî, êàê óæå ñêàçàíî â ðàçäåëå 2.1, ýêâèâàëåíòíî âûèãðûøàì èç ïðîèçâîëüíîé óïîðÿäî÷åííîé ïîëóãðóïïû. Ýòîò ñëó÷àé âêëþ÷àåò â ñåáÿ è ëåêñèêîãðàè÷åñêèå èãðû [5℄.Çàìå÷àíèå3.1.2. Èíîãäà, äëÿ óäîáñòâà, åñëèj ∈/ i(x, t),èçâîëüíîå îäíîòî÷å÷íîå ìíîæåñòâî.  ýòîì ñëó÷àå÷òî∀x, t i(x, t) = NÇàìå÷àíèåáóäåì îïðåäåëÿòüU(x, t) =(ò.å., âñå èãðîêè õîäÿò îäíîâðåìåííî).Qj∈NU j (x, t)U j (x, t)êàê ïðî-è ìîæíî ñ÷èòàòü,3.1.3.
Óïðàâëÿåìóþ äèíàìè÷åñêóþ ñèñòåìó ñ äèñêðåòíûì âðåìåíåì ìîæíî ìî-äåëèðîâàòü ãðàîì. Ïðè ýòîì óíêöèÿ âûèãðûøà çàäàíà íà ìíîæåñòâå íåïðîäîëæàåìûõïóòåé ãðàà.Áóäåì ðàññìàòðèâàòü, â ïåðâóþ î÷åðåäü, îäèí âèä óíêöèé âûèãðûøàèíòåãðàëüíûé âûèãðûøH i : îáîáùåííûéH j (x(t1 ), . . . x(tm )) = f j (x(t1 ), t1 )∗· · ·∗f j (x(tm ), tm ). Åãî ÷àñòíûìèñëó÷àÿìè ÿâëÿþòñÿ èíòåãðàëüíûé âûèãðûø èç óïîðÿäî÷åííîãî ïîëóìîäóëÿ, èíòåãðàëüíûéâûèãðûø ñ äèñêîíòîì èç óïîðÿäî÷åííîãî ïîëóïîëÿ, òåðìèíàëüíûé âûèãðûø.Ìîæíî ïî-ðàçíîìó îïðåäåëÿòü ñòðàòåãèè èãðîêîâ, è â çàâèñèìîñòè îò ýòîãî, ïîëó÷àòüðàçíûå îïðåäåëåíèÿ äèíàìè÷åñêîé èãðû. Áóäåì ðàññìàòðèâàòü ïðîñòåéøèé ñëó÷àé:85Îïðåäåëåíèå 28.
Ïîçèöèîííàÿ (ñèíòåçèðóþùàÿ) ñòðàòåãèÿ S ýòî ñòðàòåãèÿ ñ ãëóáèíîésj (x, t) = uj (x, t), çàâèñÿùàÿ îò òåêóùåé ïîçèöèè è ìîìåíòà âðåìåíè.Qïðîèçâåäåíèå ìíîæåñòâ ñòðàòåãèé S =j∈N Sj áóäåì íàçûâàòü ìíîæåñòâîìïàìÿòè 0, ò.å., óíêöèÿÄåêàðòîâîñèòóàöèé.Ôàêòè÷åñêè, äèíàìè÷åñêàÿ èãðà ñ ïîçèöèîííûìè ñòðàòåãèÿìè ýòî èãðà íà ãðàå, êîòîðûé îïèñûâàåò ñîîòâåòñòâóþùóþ äèíàìè÷åñêóþ ñèñòåìó.Ëþáàÿ èãðà îïðåäåëÿåòñÿ ïóòåì ñâåäåíèÿ åå ê èãðå â íîðìàëüíîé îðìå. Ñëåäîâàòåëüíî,îñòàëîñü ïîíÿòü, êàê óíêöèÿ âûèãðûøà çàâèñèò îò íàáîðà ñòðàòåãèé èãðîêîâ (ñèòóàöèè)s = (s1 , .
. . , sn ). Êàæäàÿ ñèòóàöèÿ ýòî îòîáðàæåíèås : X × T → U(x, t)â ìíîæåñòâî óïðàâ-ëåíèé.Îïðåäåëåíèå 29.òðàåêòîðèåéÁóäåì ãîâîðèòü, ÷òî íàáîð ñòðàòåãèéh : T → X,s : X × T → U(x, t) ñîâìåñòèìåñëè ñîîòâåòñòâóþùåå ïîçèöèîííîå óïðàâëåíèåñîâìåñòèìî ñ ýòîé òðàåêòîðèåé, ò.å.ñu : X × T → U(x, t)∀t ∈ T h(t + 1) = π(h(t), t, u(h(t), t)).Óòâåðæäåíèå 3.1.1.
Äëÿ ëþáîãî íàáîðà ñòðàòåãèé s = (s1 , . . . , sn ) ñóùåñòâóåò åäèíñòâåí-íàÿ ñîâìåñòèìàÿ ñ íèì òðàåêòîðèÿ h = p(s).È íàîáîðîò, äëÿ êàæäîé òðàåêòîðèè ñóùåñòâóåò õîòÿ áû îäíà (âîçìîæíî, íå åäèíñòâåííàÿ) ñîâìåñòèìàÿ ñ íåé ñèòóàöèÿ.Äîêàçàòåëüñòâî.Ïóñòü äàíà ñèòóàöèÿîäíîãî èãðîêà, áåðåìh(2), h(3),h(1) = x0s.Àíàëîãè÷íî äèíàìè÷åñêîé îïòèìèçàöèè â ñëó÷àåè äàëüøå, èñõîäÿ èç îïðåäåëåíèÿ, ïîñëåäîâàòåëüíî ñòðîèìè ò.ï.Îáðàòíîå óòâåðæäåíèå äîêàçûâàåòñÿ àíàëîãè÷íî óòâåðæäåíèþ 2.1.2 äëÿ ìíîãîêðèòåðèàëüíûõ çàäà÷. Ïðè ýòîì ñèòóàöèÿ ïî óìîë÷àíèþs∗ (x, t)âñåãäà ñóùåñòâóåò ïî êîíå÷íîñòèìíîæåñòâà ïîçèöèé â èãðå è ìîìåíòîâ âðåìåíè (÷òîáû ïîñòðîèòü óíêöèþ èç êîíå÷íîãîìíîæåñòâà â íåïóñòîå, íå íóæíî äàæå ïðèâëåêàòü àêñèîìó âûáîðà).Òåïåðü îïðåäåëèì óíêöèþ âûèãðûøà òàê:H i (s1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
