Диссертация (1149954), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Åñëè èíòåíñèâíîñòè ïðîöåññîâ âåëèêè, òî äèñêðåòíóþ ìîäåëü Íåéìàíà ìîæíîïðèáëèæåííî îïèñàòü íåïðåðûâíîé. Åñëè îíè ìàëû, ìîæíî èñêàòü îïòèìàëüíûå çíà÷åíèÿìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ (ñì. äàëåå).Ïðèìåð 8. àñêðàøåííàÿ ñåòü Ïåòðè[75℄ ýòî äâóäîëüíàÿ ñåòü, â êîòîðîé âåðøèíû ïåð-âîé äîëè (ñîñòîÿíèÿ ) ñóììàòîðû-óñèëèòåëè è ðàñïðåäåëèòåëè äèñêðåòíîãî ïîòîêà ñ ñîõðàíåíèåì è óñèëåíèÿìè â äóãàõ, à âåðøèíû âòîðîé äîëè (ïåðåõîäû ) ñóììàòîðû-óñèëèòåëèè ðàçìíîæèòåëè äèñêðåòíîãî ïîòîêà ñ óñèëåíèÿìè â äóãàõ è ñòàíäàðòíûì óñèëåíèåì â âåðøèíàõgx (f1 , . . . , fn ) = min(f1 , .

. . fn ).Äèíàìè÷åñêèé ìíîãîïðîäóêòîâûé ïîòîê â òàêîé ñåòè ýòî ðàçâèòèå ðàñêðàøåííîé ñåòè Ïåòðè âî âðåìåíè. Òàêèì îáðàçîì, äèñêðåòíóþ ìîäåëüÍåéìàíà ìîæíî ìîäåëèðîâàòü ðàñêðàøåííîé îäíîïðîäóêòîâîé (àêòè÷åñêè, îäíîöâåòíîé ñðàçíîé èíòåíñèâíîñòüþ öâåòà) ñåòüþ Ïåòðè, â êîòîðîé ñîñòîÿíèÿ ýòî îòðàñëè, à ïåðåõîäû ýòî ïðîäóêòû.Ïðîèçâîëüíûé äèñêðåòíûé ïîòîê â ñåòè ñ ìíîæåñòâîì ñîñòîÿíèéQl∈LSl ×Qm∈MUmñâîäèòñÿ ê äèñêðåòíîé óïðàâëÿåìîé ñèñòåìå ñ äèñêðåòíûì âðåìåíåì. Çàäà÷ó îïòèìèçàöèè âòàêîé ñèñòåìå âñåãäà ìîæíî ñâåñòè ê çàäà÷å îïòèìèçàöèè â (íåïðåðûâíîé) ìîäåëè Íåéìàíà[41℄ ïðàâäà, ðàçìåðíîñòü ìîäåëè Íåéìàíà ðàñòåò ýêñïîíåíöèàëüíî ñ ðîñòîì êîëè÷åñòâàâåðøèí è äóã ñåòè. íåêîòîðûõ ñëó÷àÿõ áîëåå ýåêòèâíûì áóäåò ñâåäåíèå ê äèñêðåòíîé ìîäåëè Íåéìàíà(îïòèìèçàöèîííûå çàäà÷è â òàêîé ìîäåëè ñâîäÿòñÿ ê çàäà÷àì öåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ).

 ÷àñòíîñòè, ïîñêîëüêó ëþáàÿ óíêöèÿ íà äèñêðåòíîì ìíîæåñòâå ÿâëÿåòñÿêóñî÷íî-ëèíåéíîé, äèíàìè÷åñêàÿ ñåòü ñ öåëî÷èñëåííûìè ïîòîêàìè è âîãíóòûìè óíêöèÿìèóñèëåíèÿ òàêæå ñâîäèòñÿ ê äèñêðåòíîé ìîäåëè Íåéìàíà.Òàêèì îáðàçîì, ìîäåëü Íåéìàíà îêàçûâàåòñÿ óíèâåðñàëüíîé â òîì ñìûñëå, ÷òî ê íåéìîæíî ñâåñòè ëþáóþ äèíàìè÷åñêóþ ñåòü ñ âîãíóòûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè: åñëèïîòîêè âåùåñòâåííûå ê íåïðåðûâíîé ìîäåëè Íåéìàíà, åñëè ïîòîêè öåëî÷èñëåííûå êäèñêðåòíîé.

Íî ñåòåâîå ïðåäñòàâëåíèå âñå-òàêè áûâàåò ïîëåçíî, ïîòîìó ÷òî, êàê ìû óâèäèìäàëüøå, â íåêîòîðûõ ÷àñòíûõ ñëó÷àÿõ íàïðèìåð, â ñëó÷àå ñåòåé ñ óñèëåíèÿìè â äóãàõ ïîçâîëÿåò áîëåå ýåêòèâíî íàéòè îïòèìàëüíîå ðåøåíèå.491.3.3Ñâåäåíèå çàäà÷è íàõîæäåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãîïîòîêà ê ñòàòè÷åñêîé çàäà÷åÄëÿ ìàêñèìàëüíûõ ïîòîêîâ â ñåòè áåç óñèëåíèé è äëÿ ïîòîêîâ íàèáûñòðåéøåãî ïðèáûòèÿáåç óñèëåíèé ìîæíî íàéòè ìàêñèìàëüíûé ïîòîê ñîîòâåòñòâåííî ñ ïîìîùüþ äèíàìè÷åñêîãîàëãîðèòìà Ôîðäà-Ôàëêåðñîíà è àëãîðèòìà Ìàéíèêè [34℄. Äëÿ ïîòîêîâ ìèíèìàëüíîé ñòîèìîñòè â ñåòè áåç óñèëåíèé íå ñóùåñòâóåò ýåêòèâíûõ òî÷íûõ àëãîðèòìîâ, íî èçâåñòíî,÷òî ñóùåñòâóþò îïòèìàëüíûå ïîòîêè áåç ñîõðàíåíèÿ [71℄. Èõ ìîæíî íàéòè, ðàññìîòðåâ ñåòü,ðàçâåðíóòóþ âî âðåìåíè [34℄ ò.å.

ñâåäÿ äèíàìè÷åñêóþ çàäà÷ó ê ñòàòè÷åñêîé. Çäåñü ìûïîêàæåì, ÷òî òàêîå æå ñâåäåíèå ê ñòàòè÷åñêîé çàäà÷å âîçìîæíî äëÿ ïîòîêîâ â ñåòè ñ ïðîèçâîëüíûìè óñèëåíèÿìè.Îïðåäåëåíèå 16.äåèöèòàìèìîñòèvt,Ïóñòü äàíà äèíàìè÷åñêàÿ ñåòüïðîïóñêíûìè ñïîñîáíîñòÿìèct ,(L, M, s, e)ñî ñòîêîìóíêöèÿìè óñèëåíèÿgats′ ,äîïóñòèìûìèè óíêöèÿìè ñòîè-ptm .Ñåòü, ðàçâåðíóòàÿ âî âðåìåíèìóëüòèãðà(L′ , M ′ , s, e) ýòî ñòàòè÷åñêàÿ ñåòü(L, M, s, e)T ,ãðà êîòîðîé ýòîèñõîäíîé ñåòè, ðàçâåðíóòûé âî âðåìåíè. Åå äîïóñòèìûå äåèöèòû,ïðîïóñêíûå ñïîñîáíîñòè, óíêöèè óñèëåíèÿ è ñòîèìîñòè îïðåäåëÿþòñÿ ïàðàìåòðàìè äèíàìè÷åñêîé ñåòè â ñîîòâåòñòâóþùèå ìîìåíòû âðåìåíè:v((x, t)) = v t (x)c(m′ ) = ct1 (m), s(m) = (x, t1 )g(x,t) = gxtpm′ = ptm1 , s(m) = (x, t1 )Ïîñêîëüêóðàññìàòðèâàþòñÿ((x, t), (x, t + 1)).ìîñòü, à óñèëåíèåïîòîêèÇàìå÷àíèåñîõðàíåíèåì,äîáàâëÿþòñÿäóãè ñîõðàíåíèÿ äóãàõ ñîõðàíåíèÿ áåñêîíå÷íàÿ ïðîïóñêíàÿ ñïîñîáíîñòü, íóëåâàÿ ñòîè-gîò íèõ íå çàâèñèò.Ñòîê ñåòè, ðàçâåðíóòîé âî âðåìåíè îò âñåõ ñòîêîâñ(s′′ , T ), êîòîðîìó, ðàçóìååòñÿ, èäóò äóãè ñîõðàíåíèÿ(s′ , t′ ), t′ ∈ T .1.3.3.

Ìîæíî, ðàçóìååòñÿ, ðàññìàòðèâàòü è äèíàìè÷åñêèå çàäà÷è, â êîòîðûõïðåäóñìàòðèâàåòñÿ ñòîèìîñòü õðàíåíèÿ ïîòîêà â âåðøèíå â òå÷åíèå çàäàííîãî âðåìåíè. Âýòîì ñëó÷àå íóæíî ïðåäóñìîòðåòü ñòîèìîñòü äóã ñîõðàíåíèÿ.Óòâåðæäåíèå 1.3.2.  äèíàìè÷åñêîé ñåòè êàæäîìó äèíàìè÷åñêîìó ïîòîêó ñ ìíîæå-ñòâîì ìîìåíòîâ èçìåíåíèÿ ïîòîêà, ïðèíàäëåæàùåìó T , ñîîòâåòñòâóåò ñòàòè÷åñêèéïîòîê â ñåòè, ðàçâåðíóòîé âî âðåìåíè T , è íàîáîðîò. Ïðè ýòîì âåëè÷èíà è ñòîèìîñòü50äèíàìè÷åñêîãî ïîòîêà ðàâíû âåëè÷èíå è ñòîèìîñòè ñîîòâåòñòâóþùåãî ñòàòè÷åñêîãî ïîòîêà. Ñîîòâåòñòâèå ìåæäó ñòàòè÷åñêèì è äèíàìè÷åñêèì ïîòîêîì îïðåäåëÿåòñÿ ïî îðìóëàìsx (t) = s′(x,t)′sx (t) = f((x,t−1),(x,t))(1.12)f (m, t) = f ′ ((m′ , t))s((m′ , t)) = s(m), e((m′ , t + 1)) = e(m).Äîêàçàòåëüñòâî.Ñîîòâåòñòâèå äèíàìè÷åñêîãî ïîòîêà è ñòàòè÷åñêîãî ïîòîêà â ñåòè, ðàç-âåðíóòîé âî âðåìåíè, óæå äîêàçàíî â ðàçäåëå 1.1 äëÿ áîëåå îáùèõ ñèñòåì â äèñêðåòíîìïðîñòðàíñòâå.Òåîðåìà 5(ñâåäåíèå äèíàìè÷åñêîé çàäà÷è ê ñòàòè÷åñêîé).Ïóñòü â äèíàìè÷åñêîé ñåòè Nóíêöèè v t , g t , ct , pt íåïðåðûâíû äëÿ âñåõ t ∈ T .

Ïóñòü äàíà çàäà÷à íàõîæäåíèÿ îïòèìàëü-íîãî äèíàìè÷åñêîãî ïñåâäîïîòîêà íà êîíå÷íîì èíòåðâàëå âðåìåíè èëè ïîñòðîåíèÿ ïîòîêàíàèñêîðåéøåãî ïðèáûòèÿ.Òîãäà ñóùåñòâóåò îïòèìàëüíûé äèíàìè÷åñêèé ïñåâäîïîòîê f ′ , êîòîðîìó ñîîòâåò-ñòâóåò îïòèìàëüíûé ñòàòè÷åñêèé ïñåâäîïîòîê f â ñåòè ñîáûòèé, ðàçâåðíóòîé âî âðåìåíè. Ïðè ýòîì ñòàòè÷åñêèé è äèíàìè÷åñêèé ïîòîê ñîîòâåòñòâóþò äðóã äðóãó ïî îðìóëàì(1.12).Äîêàçàòåëüñòâî.Ñóùåñòâîâàíèå îïòèìàëüíîãî ïîòîêà ñëåäóåò èç íåïðåðûâíîñòè âñåõ öåëå-âûõ óíêöèé è êîìïàêòíîñòè ìíîæåñòâà ïîòîêîâ, à óòâåðæäåíèå òåîðåìû èç óòâåðæäåíèÿ1.3.2.Ñëåäñòâèå 5.1.

Óòâåðæäåíèå òåîðåìû 5 âåðíî:1. äëÿ çàäà÷è ïîñòðîåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãî ïîòîêà äî çàäàííîãî ìîìåíòà T ;2. äëÿ çàäà÷è ïîñòðîåíèÿ ïîòîêà íàèñêîðåéøåãî ïðèáûòèÿ [34℄.Äîêàçàòåëüñòâî.1. Îãðàíè÷åíèå ïîòîêà ïî âðåìåíè íå ìåíÿåò äîñòàòî÷íûõ óñëîâèé âòåîðåìå î ñâåäåíèè äèíàìè÷åñêîé çàäà÷è ê ñòàòè÷åñêîé.2. Çàäà÷à ïîñòðîåíèÿ ïîòîêà íàèñêîðåéøåãî ïðèáûòèÿ, î÷åâèäíî, ýêâèâàëåíòíà çàäà÷åëåêñèêîãðàè÷åñêîé ìàêñèìèçàöèè ïîòîêà â âîçðàñòàþùóþ ïîñëåäîâàòåëüíîñòü ìîìåíòîâT = 1, 2, .

. . , T . ñâîþ î÷åðåäü, çàäà÷à íàõîæäåíèÿ ëåêñèêîãðàè÷åñêîãî ìàêñè-ìóìà âåëè÷èíû ïîòîêà ýêâèâàëåíòíà çàäà÷å íàõîæäåíèÿ ìàêñèìóìà â óïîðÿäî÷åííîéàáåëåâîé ãðóïïå âåêòîðîâ, äëÿ êîòîðîé â ñëó÷àå ñóùåñòâîâàíèÿ ðåøåíèÿ òàêæå âåðíàòåîðåìà î ñâåäåíèè äèíàìè÷åñêîé çàäà÷è ê ñòàòè÷åñêîé.51Ïóñòü â èñõîäíîé ñåòèâðåìåíè1, 2, . . . , T ,nâåðøèí èî÷åâèäíî, èìååòmäóã.

Ñåòü, ðàçâåðíóòàÿ âî âðåìåíè, äëÿ ïåðèîäàN = nTâåðøèí èM = mTäóã.Òàêèì îáðàçîì, ñëåäóþùèå äèíàìè÷åñêèå çàäà÷è ñâîäÿòñÿ ê ñòàòè÷åñêèì, äëÿ êîòîðûõìû óæå ïîñòðîèëè àëãîðèòìû ðåøåíèÿ â ðàçäåëå 1.2:1. Îïòèìàëüíûå äèñêðåòíûå ïîòîêè (à òàêæå ïîòîêè â ñåòè ñ êóñî÷íî-ïîñòîÿííûìè óñèëåíèÿìè) â ñåòÿõ ñ êîíå÷íûìè ïðîïóñêíûìè ñïîñîáíîñòÿìè ìîæíî íàéòè ïåðåáîðîì.Îäíàêî êîëè÷åñòâî âàðèàíòîâ, êîòîðûå íóæíî ïåðåáðàòü â äèíàìè÷åñêîé çàäà÷å, äîñòàòî÷íî âåëèêî (îíî îöåíèâàåòñÿ â êîíöå ýòîãî ðàçäåëà). Äëÿ ïðîèçâîëüíûõ (êóñî÷íî)ëèíåéíûõ óñèëåíèé è ñâåðòîê (â ÷àñòíîñòè, êóñî÷íî-ïîñòîÿííûõ) è äèñêðåòíûõ ïîòîêîâ çàäà÷à ðåøàåòñÿ ìåòîäàìè öåëî÷èñëåííîãî (Ê)ËÏ.  ÷àñòíîñòè, çàäà÷à îïòèìèçàöèè ðàñêðàøåííîé ñåòè Ïåòðè ñâîäèòñÿ ê çàäà÷å ÖËÏ.2.

Äëÿíåïðåðûâíûõêóñî÷íî-ëèíåéíûõóñèëåíèéçàäà÷óìîæíîðåøèòüìåòîäàìèêóñî÷íî-ëèíåéíîãî ïðîãðàììèðîâàíèÿ (ÊËÏ).3. Äëÿ âîãíóòûõ êóñî÷íî-ëèíåéíûõ óñèëåíèé åå ìîæíî ðåøèòü ìåòîäàìè ËÏ.  ÷àñòíîñòè, ìîäåëü Íåéìàíà, îïèñûâàþùàÿ ïðîèçâîäñòâî, çàíèìàþùåå ðàçíîå êîëè÷åñòâîâðåìåíè, ïðè âîçìîæíîñòè ñîõðàíåíèÿ ïðîäóêòîâ ñâîäèòñÿ ê çàäà÷å ËÏ.4. Äëÿ íåïðåðûâíûõ êóñî÷íî-ëèíåéíûõ óñèëåíèé â äóãàõ çàäà÷à ðåøàåòñÿ èçëîæåííûì âïðåäûäóùåì ðàçäåëå ïîëóïåðåáîðíûì àëãîðèòìîì ñëîæíîñòèO(k 2M )F (kM, N).Êðîìå òîãî, äëÿ äèñêðåòíûõ ïîòîêîâ è ïðîèçâîëüíûõ óñèëåíèé çàäà÷à ðåøàåòñÿ ìåòîäîìäèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, êàê ïîêàçàíî â ñëåäóþùåì ïîäðàçäåëå.1.3.4Àëãîðèòì íàõîæäåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãî ïîòîêàìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿàññìîòðèì ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ [6℄ äëÿ äèñêðåòíûõ ïîòîêîâ. Äëÿ ïîòîêîâ â ñåòè ñ íåïðåðûâíûìè (äàæå êóñî÷íî-ëèíåéíûìè) óñèëåíèÿìè ïðèìåíÿòü åãî êóäàñëîæíåå.Î÷åâèäíî, äèíàìè÷åñêàÿ ñåòü ýòî óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñèñòåìà, ðàñïðåäåëåííàÿâ ïðîñòðàíñòâå.

Åå ñîñòîÿíèå â ìîìåíò âðåìåíèâî âðåìåíè. Ïóñòü èìååòñÿ ñèñòåìàâåòñòâóåò ãðà ñnâåðøèíàìè èmnt îïðåäåëÿåòñÿòî÷êàìè èmñå÷åíèåì ñåòè, ðàçâåðíóòîéñâÿçÿìè ìåæäó òî÷êàìè, êîòîðîé ñîîò-äóãàìè. Åå ñîñòîÿíèå â ìîìåíò âðåìåíètîïðåäåëÿåòñÿñîñòîÿíèÿìè âåðøèí è äóã. Òàêèì îáðàçîì, åñëè êàæäàÿ âåðøèíà ìîæåò íàõîäèòüñÿ âñîñòîÿíèÿõ, à äóãà âO(k)O(p) ñîñòîÿíèÿõ, îáùåå ÷èñëî ñîñòîÿíèé ñèñòåìû ïîðÿäêà O(k n pm ).52Îáùàÿ ñòîèìîñòü ïîòîêà ñêëàäûâàåòñÿ èç ñòîèìîñòåé, âçÿòûõ âî âñå ìîìåíòû âðåìåíè.Ñëåäîâàòåëüíî, ìû èìååì äåëî ñ çàäà÷åé íàõîæäåíèÿ ìàêñèìàëüíîé èíòåãðàëüíîé ïîëåçíîñòè, êîòîðàÿ ñâîäèòñÿ ê çàäà÷å íàõîæäåíèÿ ìàêñèìóìà ïî òðàåêòîðèè ÎÄÑ ñ äèñêðåòíûìâðåìåíåì. Òàêàÿ çàäà÷à ðåøàåòñÿ ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ.

Çàäà÷à íàõîæäåíèÿ ìàêñèìàëüíîãî ïîòîêà, âõîäÿùåãî â ñòîê, è ïîòîêà íàèñêîðåéøåãî ïðèáûòèÿ ýòî çàäà÷è ñ òåðìèíàëüíîé ïîëåçíîñòüþ, êîòîðûå òàêæå ðåøàþòñÿ ìåòîäîì äèíàìè÷åñêîãîïðîãðàììèðîâàíèÿ.Ïîëó÷àåì ñëåäóþùèéàëãîðèòìíàõîæäåíèÿ îïòèìàëüíîãî äèñêðåòíîãî äèíàìè÷åñêîãîïîòîêà, êîòîðûé ïðèìåíÿåòñÿ â êàæäûé èçO(T )ìîìåíòîâ âðåìåíè, ðàññìàòðèâàåìûõ ïîóáûâàíèþ:1.

Характеристики

Список файлов диссертации