Диссертация (1149954), страница 2
Текст из файла (страница 2)
Ïðè íàëè÷èè íåñêîëüêèõ äåéñòâóþùèõ ëèö (àãåíòîâ)èñïîëüçóåòñÿ ìàòåìàòè÷åñêèé àïïàðàò òåîðèè èãð.Åñëè ñèñòåìà ÿâëÿåòñÿ äèíàìè÷åñêîé, åå ðàçâèòèå âî âðåìåíè ìîæíî îðìàëèçîâàòü,èñïîëüçóÿ óïðàâëÿåìûå äèíàìè÷åñêèå ñèñòåìû [4℄. Çàäà÷à îïòèìèçàöèè â òàêîé ñèñòåìå ÷àùåâñåãî ðåøàåòñÿ ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ [6℄.Îïòèìàëüíîå óïðàâëåíèå â ïîçèöèîííîé èãðå òàêæå ìîæíî íàéòè ìåòîäîì äèíàìè÷åñêîãî6ïðîãðàììèðîâàíèÿ [67℄ èëè ñâåñòè åå ê êîìáèíàòîðíîé èãðå, êîòîðàÿ ðåøàåòñÿ àëãåáðàè÷åñêèìè ìåòîäàìè [68℄.Çàäà÷è îïòèìèçàöèè ñåòåé ðåøàþòñÿ ñ èñïîëüçîâàíèåì äâóõ ïîäõîäîâ: ñâåäåíèåì ê çàäà÷åöåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ [34, 63, 30℄ è êîìáèíàòîðíî-àëãåáðàè÷åñêèìèìåòîäàìè, îïèðàþùèìèñÿ íà ñâîéñòâà ãðàîâ è óïîðÿäî÷åííûõ àëãåáðàè÷åñêèõ ñòðóêòóð ýòè ìåòîäû â êàæäîé çàäà÷å ñâîè [61, 78, 1, 30℄. Òàêæå âîçìîæíî ñî÷åòàíèå ýòèõ äâóõ ïîäõîäîâ [84℄. Íàèáîëåå ðàçâèòà òåîðèÿ ïîòîêîâ â ñåòÿõ, à òàêæå ïîòîêîâ â ñåòÿõ ñ óñèëåíèÿìèè ìíîãîïðîäóêòîâûõ ïîòîêîâ, ê îïòèìèçàöèè êîòîðûõ ñâîäÿòñÿ ìíîãèå äðóãèå îïòèìèçàöèîííûå çàäà÷è íà ñåòÿõ [78, 84, 86℄.
×àùå âñåãî ðàññìàòðèâàëèñü àääèòèâíûå ïîòîêè, äëÿêîòîðûõ âåëè÷èíà ïîòîêà â âåðøèíå ñêëàäûâàåòñÿ èç âåëè÷èí ïîòîêîâ â äóãàõ, çàêàí÷èâàþùèõñÿ â ýòîé âåðøèíå. Íî ìíîãèå ýêîíîìè÷åñêèå ñèñòåìû íåàääèòèâíû, è èõ òàêèì îáðàçîìñìîäåëèðîâàòü íå ïîëó÷èòñÿ.Äëÿ îðìàëèçàöèè óïðàâëåíèÿ ìíîãîàãåíòíûìè ñåòÿìè èñïîëüçóþòñÿ ñåòåâûå èãðû [79,73, 72, 70, 17℄.
Ïðè ýòîì ñåòåâûå èãðû â êàæäîé ðàáîòå îïðåäåëÿþòñÿ ïî-ñâîåìó: îáùåãîîïðåäåëåíèÿ ñåòåâîé èãðû íå ïîñòðîåíî. Åñòü äâà êëàññà ñåòåâûõ èãð: èãðû îðìèðîâàíèÿñåòåé è èãðû íà ñåòÿõ [42℄. ×àùå âñåãî ðàññìàòðèâàþòñÿ ñòàòè÷åñêèå ñåòåâûå èãðû, à òàêæåîòäåëüíûå ÷àñòíûå ñëó÷àè äèíàìè÷åñêèõ ñåòåâûõ èãð. Íî ìíîãèå ýêîíîìè÷åñêèå ñèñòåìûÿâëÿþòñÿ äèíàìè÷åñêèìè è èìåþò ñâîéñòâà, äëÿ ìîäåëèðîâàíèÿ êîòîðûõ òðåáóþòñÿ è èãðûîðìèðîâàíèÿ ñåòåé, è èãðû íà ñåòÿõ.Ìíîãèå ñëîæíûå ñèñòåìû â ÷àñòíîñòè ëîãèñòè÷åñêèå ÿâëÿþòñÿ îäíîâðåìåííî è äèíàìè÷åñêèìè, è ðàñïðåäåëåííûìè â ïðîñòðàíñòâå. Î÷åâèäíî, äëÿ ìîäåëèðîâàíèÿ òàêèõ ñèñòåìñëåäóåò èñïîëüçîâàòü äèíàìè÷åñêèå ñåòè. Ïðè ýòîì, îáû÷íî, îãðàíè÷èâàþòñÿ îïèñàòåëüíûìïîäõîäîì: îðìàëèçàöèåé ìíîæåñòâà âîçìîæíûõ ñîñòîÿíèé äèíàìè÷åñêîé ñåòè áåç ââåäåíèÿêðèòåðèåâ êà÷åñòâà è ïîñòàíîâêè îïòèìèçàöèîííûõ çàäà÷.
Äëÿ ýòîãî èñïîëüçîâàëèñü àâòîìàòíûå ñåòè [59℄, êëåòî÷íûå àâòîìàòû [88℄, óíêöèè âîçäåéñòâèÿ âõîäîâ íà âûõîäû [14℄,ðàñêðàøåííûå ñåòè Ïåòðè [75℄.Íî â ýêîíîìè÷åñêèõ ñèñòåìàõ âàæåí îïòèìèçàöèîííûé àñïåêò, è åãî íàäî ó÷èòûâàòü ïðèîðìàëèçàöèè. Çàäà÷è îïòèìèçàöèè äèíàìè÷åñêèõ ñåòåé ÷àùå âñåãî ðàññìàòðèâàëèñü ëèøüäëÿ íåïðåðûâíîãî ëèíåéíîãî ñëó÷àÿ ýòî çàäà÷è îïòèìèçàöèè äèíàìè÷åñêèõ ïîòîêîâ èîïòèìèçàöèè â ýêîíîìè÷åñêîé ìîäåëè Íåéìàíà.
Ìåæäó òåì, àêòóàëüíû òàêæå çàäà÷è îïòèìèçàöèè äèíàìè÷åñêèõ ñåòåé â íåëèíåéíîì è â äèñêðåòíîì ñëó÷àå.Òàêèì îáðàçîì, àêòóàëüíà îðìàëèçàöèÿ•íåàääèòèâíûõ îïòèìèçàöèîííûõ çàäà÷ â ñåòÿõ, â òîì ÷èñëå äèíàìè÷åñêèõ èõ ìîæíîîïèñàòü îáîáùåííûìè ïîòîêàìè â ñåòÿõ;7•äèíàìè÷åñêèõ ñåòåâûõ èãð, îáîáùàþùèõ êàê èãðû îðìèðîâàíèÿ ñåòåé, òàê è èãðû íàñåòÿõ.Öåëüäàííîé ðàáîòû ïîñòðîåíèå ìàòåìàòè÷åñêîé ìîäåëè óïðàâëÿåìîé ìíîãîàãåíòíîéäèíàìè÷åñêîé ñèñòåìû â äèñêðåòíîì ïðîñòðàíñòâå ñ äèñêðåòíûì âðåìåíåì è àëãîðèòìîâ îïòèìàëüíîãî óïðàâëåíèÿ òàêîé ñèñòåìîé. Ñ òî÷êè çðåíèÿ ìàòåìàòèêè, äëÿ ýòîãî òðåáóåòñÿïîñòàíîâêà è ðåøåíèå äèíàìè÷åñêèõ ñåòåâûõ çàäà÷ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè è çàäà÷ íàõîæäåíèÿ ðàâíîâåñèé â äèíàìè÷åñêèõ ñåòåâûõ èãðàõ. Äëÿ ýòîãî íóæíî èññëåäîâàòüñëåäóþùèå îáúåêòû:1. ñòàòè÷åñêèå ïîòîêè â ñåòÿõ ñ íåëèíåéíûìè óñèëåíèÿìè;2.
äèíàìè÷åñêèå ïîòîêè â ñåòÿõ ñ íåëèíåéíûìè óñèëåíèÿìè;3. äèíàìè÷åñêèå ñåòåâûå èãðû è ðàâíîâåñèÿ â ýòèõ èãðàõ.Íàó÷íàÿ íîâèçíàðàáîòû: äîêàçàíû òåîðåìû îá àëãîðèòìàõ, ïîçâîëÿþùèõ ïîëó÷àòüîïòèìàëüíûå óïðàâëåíèÿ äëÿ ñî÷åòàíèÿ òðåõ òèïîâ îïòèìèçàöèîííûõ çàäà÷: äèíàìè÷åñêèõ îïòèìèçàöèîííûõ çàäà÷, ñåòåâûõ îïòèìèçàöèîííûõ çàäà÷ è ìíîãîêðèòåðèàëüíûõ çàäà÷(íåñòðàòåãè÷åñêèõ çàäà÷ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè è çàäà÷ íàõîæäåíèÿ ðàâíîâåñèÿâ èãðàõ).
àíåå ðàññìàòðèâàëèñü îòäåëüíî äàííûå êëàññû çàäà÷, à òàêæå èõ ïåðåñå÷åíèÿ:íàõîæäåíèå îïòèìàëüíûõ äèíàìè÷åñêèõ ñåòåé, ìíîãîêðèòåðèàëüíàÿ äèíàìè÷åñêàÿ îïòèìèçàöèÿ, íàõîæäåíèå ðàâíîâåñèÿ â äèíàìè÷åñêèõ èãðàõ, ñåòåâûõ èãðàõ, ìíîãîêðèòåðèàëüíàÿîïòèìèçàöèÿ ñåòåé.Íî ïåðåñå÷åíèå âñåõ 3 êëàññîâ çàäà÷, òî åñòü äèíàìè÷åñêèå ñåòåâûå ìíîãîêðèòåðèàëüíûåçàäà÷è, ðàíåå ïî÷òè íå ðàññìàòðèâàëèñü â îáùåì âèäå. Ýòî è ñäåëàíî â äàííîé äèññåðòàöèîííîé ðàáîòå. Ïðè ýòîì â äàííîì øèðîêîì êëàññå îïòèìèçèðóåìûõ ñèñòåì âîçíèêàþòïðèíöèïèàëüíî íîâûå ñâîéñòâà, íåñâîäèìûå ê ïðîñòîé ñóììå ñâîéñòâ äèíàìè÷åñêèõ, ñåòåâûõè ìíîãîêðèòåðèàëüíûõ îïòèìèçèðóåìûõ ñèñòåì â ÷àñòíîñòè, âîçíèêàþò ãðàû, ðàçâåðíóòûå âî âðåìåíè, è ìíîãîêðèòåðèàëüíûå ïîòîêîâûå çàäà÷è â ýòèõ ãðààõ, ïðè ðåøåíèèêîòîðûõ ÷àñòü äóã ìîæíî èãíîðèðîâàòü.Òåîðåòè÷åñêàÿ çíà÷èìîñòü ðàáîòûñ òî÷êè çðåíèÿ ñèñòåìíîãî àíàëèçà ñîñòîèò â ìàòå-ìàòè÷åñêîì îïèñàíèè øèðîêîãî êëàññà ñèñòåì.
 íàñòîÿùåå âðåìÿ â íàóêå ïðèíÿò ñèñòåìíûéïîäõîä. Ïðè ýòîì ñëîæíûå ñèñòåìû èññëåäóþòñÿ ïóòåì ðàçáèåíèÿ íà áîëåå ïðîñòûå ÷àñòè èèññëåäîâàíèÿ âçàèìîäåéñòâèÿ ÷àñòåé ìåæäó ñîáîé. Òàêèì îáðàçîì, äèñêðåòíûå ñèñòåìû à ê íèì îòíîñÿòñÿ ïî÷òè âñå èñêóññòâåííûå ñèñòåìû (ñîöèàëüíûå, ýêîíîìè÷åñêèå, è.ò.ï.) ìîäåëèðóþòñÿ ãðààìè (ñåòÿìè), âåðøèíû êîòîðûõ ïîäñèñòåìû, à äóãè âçàèìîäåéñòâèÿïîäñèñòåì ìåæäó ñîáîé.8Ñëîæíûå ñèñòåìû, îáû÷íî, ÿâëÿþòñÿ îòêðûòûìè, ðàñïðåäåëåííûìè â ïðîñòðàíñòâå, ðàçâèâàþùèìèñÿ è ìåíÿþò ñâîþ ñòðóêòóðó ñ òå÷åíèåì âðåìåíè. Íî íà êðàòêîñðî÷íûõ èíòåðâàëàõ âðåìåíè ìîæíî ïðåíåáðå÷ü äèíàìè÷íîñòüþ, à íà ñðåäíåñðî÷íûõ èíòåðâàëàõ èçìåíåíèåì ñòðóêòóðû ñèñòåìû.Êðîìå òîãî, âî ìíîãèõ ñèñòåìàõ: ñîöèàëüíûõ, ýêîíîìè÷åñêèõ, áèîëîãè÷åñêèõ, è.ò.ï. âàæåí îïòèìèçàöèîííûé àñïåêò.
Ïðè ýòîì îïòèìèçàöèÿ, îáû÷íî, ïðîèçâîäèòñÿ íå ïî îäíîìó êðèòåðèþ, à ïî íåñêîëüêèì, ÷òîáû ó÷åñòü ñëîæíîñòü ñèñòåìû è íåîïðåäåëåííîñòü ååïîâåäåíèÿ. Äëÿ èññëåäîâàíèÿ ñèñòåì è ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ â íèõ ñòðîÿòñÿ ìàòåìàòè÷åñêèå ìîäåëè.Ýòî çíà÷èò, ÷òî ìàòåìàòè÷åñêèå ìîäåëè äèíàìè÷åñêèõ ñåòåâûõ ìíîãîêðèòåðèàëüíûõ ñèñòåì íà ñðåäíåñðî÷íûõ èíòåðâàëàõ âðåìåíè èìåþò áîëüøóþ îáùåíàó÷íóþ öåííîñòü.Ïðàêòè÷åñêàÿ çíà÷èìîñòüðàáîòû çàêëþ÷àåòñÿ, âî-ïåðâûõ, â ïîñòðîåíèè îáùåé ìà-òåìàòè÷åñêîé ìîäåëè óïðàâëÿåìîé ðàñïðåäåëåííîé â ïðîñòðàíñòâå è âðåìåíè ñèñòåìû, âêîòîðîé ó÷èòûâàåòñÿ îïòèìèçàöèîííûé àñïåêò.
Òàêóþ ìîäåëü ìîæíî èñïîëüçîâàòü äëÿ êîìïüþòåðíîãî ìîäåëèðîâàíèÿ è õðàíåíèÿ èíîðìàöèè î ñëîæíûõ ñîöèàëüíûõ è ýêîíîìè÷åñêèõñèñòåìàõ. Ïðè ýòîì, ïîêà ìû íå ðàññìàòðèâàåì îïòèìèçàöèîííûå çàäà÷è, ìîæíî õðàíèòü âðàçíûõ ìåñòàõ ëîêàëüíóþ èíîðìàöèþ î ðàçíûõ âåðøèíàõ ðàçâåðíóòîãî âî âðåìåíè ãðàà.Íî, êàê òîëüêî âîçíèêàåò çàäà÷à îïòèìèçàöèè, íåîáõîäèìà èíîðìàöèÿ î ñå÷åíèè ãðàà âêàæäûé ìîìåíò âðåìåíè.Âî-âòîðûõ, â äàííîé äèññåðòàöèîííîé ðàáîòå ïîñòðîåíû àëãîðèòìû íàõîæäåíèÿ îïòèìàëüíûõ ñåòåé, êîòîðûå ìîæíî ðåàëèçîâàòü íà âû÷èñëèòåëüíîé ìàøèíå (íåêîòîðûå èç íèõóæå ðåàëèçîâàíû). Íà èõ îñíîâå ìîæíî ñòðîèòü àëãîðèòìû ïðèíÿòèÿ îïòèìàëüíûõ ðåøåíèéâ ýêîíîìè÷åñêèõ, ñîöèàëüíûõ, òåõíîëîãè÷åñêèõ ñèñòåìàõ.
Ýòî ïîçâîëèò ïîâûñèòü ýåêòèâíîñòü óïðàâëåíèÿ ðàñïðåäåëåííûìè ðàçâèâàþùèìèñÿ ìíîãîêðèòåðèàëüíûìè ñèñòåìàìè.Íåëüçÿ äàòü òî÷íóþ îöåíêó ïîâûøåíèÿ ýåêòèâíîñòè, ïîêà íåò îäíîçíà÷íûõ ñðåäñòâ èçìåðåíèÿ ñòåïåíè äîñòèæåíèÿ îïòèìóìà â ñëîæíûõ ìíîãîêðèòåðèàëüíûõ äèíàìè÷åñêèõ çàäà÷àõ, íàïðèìåð, îïòèìèçàöèè ýêîíîìè÷åñêèõ ñèñòåì.  äàííîé ðàáîòå êàê ðàç è ïîñòðîåíûìàòåìàòè÷åñêèå ìîäåëè äëÿ äîñòàòî÷íî øèðîêîãî êëàññà ìíîãîêðèòåðèàëüíûõ ñèñòåì.Ìåòîäû èññëåäîâàíèÿ:â ðàáîòå èñïîëüçóåòñÿ ìàòåìàòè÷åñêèé àïïàðàò àëãåáðû, êîì-áèíàòîðèêè, òåîðèè ãðàîâ è òåîðèè èãð.Îñíîâíûå ðåçóëüòàòû:1.
Àëãîðèòìíàõîæäåíèÿîïòèìàëüíîãîïîòîêàâñåòÿõñíåïðåðûâíûìèêóñî÷íî-ëèíåéíûìè óñèëåíèÿìè â äóãàõ.2. Ìîäåëü óïðàâëÿåìîé ëîãèñòè÷åñêîé ñèñòåìû, ðàñïðåäåëåííîé â äèñêðåòíîì ïðîñòðàí-9ñòâå è ðàçâèâàþùåéñÿ âî âðåìåíè.3. Îáùàÿ îðìàëèçàöèÿ ñåòåâîé èãðû, âêëþ÷àþùàÿ â ñåáÿ êàê èãðû îðìèðîâàíèÿ ñåòåé,òàê è èãðû íà ñåòÿõ. Ýòó îðìàëèçàöèþ ìîæíî ïðèìåíÿòü ê ìîäåëèðîâàíèþ øèðîêîãîêëàññà ìíîãîàãåíòíûõ ýêîíîìè÷åñêèõ ñèñòåì, ðàñïðåäåëåííûõ â äèñêðåòíîì ïðîñòðàíñòâå.
Àëãîðèòìû íàõîæäåíèÿ ðàâíîâåñèé â òàêîé ñåòåâîé èãðå, êîòîðûå, õîòÿ è èìåþòýêñïîíåíöèàëüíóþ âðåìåííóþ ñëîæíîñòü, áîëåå ýåêòèâíû, ÷åì àëãîðèòìû ïîëíîãîïåðåáîðà.4. Ôîðìàëèçàöèÿ äèíàìè÷åñêîé ñåòåâîé èãðû è àëãîðèòìû íàõîæäåíèÿ ðàâíîâåñèé â íåé.Ñòðóêòóðà è îáúåì ðàáîòû.àáîòà ñîñòîèò èç ââåäåíèÿ, 3 ãëàâ, çàêëþ÷åíèÿ, ñïèñ-êà öèòèðóåìîé ëèòåðàòóðû è 5 ïðèëîæåíèé.
 1-é ãëàâå ðàññìàòðèâàþòñÿ îïòèìèçàöèîííûå çàäà÷è, â ÷àñòíîñòè, àëãîðèòìû íàõîæäåíèÿ îïòèìàëüíûõ ïîòîêîâ â ñåòè ñ íåëèíåéíûìè óñèëåíèÿìè. Âî 2-é ãëàâå ðàññìàòðèâàþòñÿ çàäà÷è ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè, â÷àñòíîñòè, äëÿ ïîòîêîâ â ñåòÿõ.  3-é ãëàâå ðàññìàòðèâàþòñÿ èãðîâûå çàäà÷è, â ÷àñòíîñòè,äèíàìè÷åñêèå ñåòåâûå èãðû.  êàæäîé ãëàâå 3 ðàçäåëà: â 1-ì ðàçäåëå äàåòñÿ îáùåå îïðåäåëåíèå óïðàâëÿåìîé äèíàìè÷åñêîé ñèñòåìû, âî 2-ì ðàññìàòðèâàåòñÿ óïðàâëÿåìàÿ ñòàòè÷åñêàÿñèñòåìà, ðàñïðåäåëåííàÿ â äèñêðåòíîì ïðîñòðàíñòâå, â 3-ì óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñèñòåìà, ðàñïðåäåëåííàÿ â äèñêðåòíîì ïðîñòðàíñòâå. ïðèëîæåíèÿõ ïðèâåäåíû âñïîìîãàòåëüíûå ñâåäåíèÿ î êóñî÷íî-ëèíåéíûõ óíêöèÿõ,ïðèìåðû ê îñíîâíûì àëãîðèòìàì è òåîðåìàì, ïîëó÷åííûì â ðàáîòå, è èñõîäíûå êîäû ïðîãðàìì.
Ñïèñîê ëèòåðàòóðû âêëþ÷àåò 88 íàèìåíîâàíèé. àáîòà èçëîæåíà íà 136 ñòðàíèöàõè 48 ñòðàíèöàõ ïðèëîæåíèÿ, ñîäåðæèò 9 ðèñóíêîâ.Ïî òåìå äèññåðòàöèè îïóáëèêîâàíî 9 ðàáîò [37℄[39℄, [44℄[49℄, èç íèõ 6 ñòàòåé [44, 45, 46,47, 49, 39℄ è òåçèñû 2 äîêëàäîâ [37, 48℄.10ëàâà 1Äèíàìè÷åñêèå îïòèìèçàöèîííûå çàäà÷èíà ñåòÿõ ñ óñèëåíèÿìè äàííîé ãëàâå ïîñòàâëåíà îáùàÿ çàäà÷à íàõîæäåíèÿ îïòèìàëüíîé äèíàìè÷åñêîé ñåòè. àññìîòðåíû óïðàâëÿåìûå äèíàìè÷åñêèå ñèñòåìû ìàòåìàòè÷åñêàÿ îðìàëèçàöèÿ óïðàâëÿåìûõ ñèñòåì, ðàçâèâàþùèõñÿ â äèñêðåòíîì âðåìåíè. Ïîñòðîåíà ìîäåëü óïðàâëÿåìîé äèíàìè÷åñêîé ñèñòåìû, ðàñïðåäåëåííîé â ïðîñòðàíñòâå ýòî îáîáùåííûé ïîòîê â ñåòè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
