Диссертация (1150610), страница 4
Текст из файла (страница 4)
Ñòîèòîáðàòèòü âíèìàíèå, ÷òî ïðè τ > 0 ìîæíî ïîäåëèòü ïåðâîå óñëîâèå (1.9)íà τ è ñäåëàòü çàìåíó λ = τ1 , ïîëó÷àÿ ïðè ýòîììàêñèìèçèðîâàòüλ,(ïðè óñëîâèèBu = λ(x+ − x− ),u ∈ U.Òàêàÿ çàäà÷à ïðîùå, ÷åì (1.9), òàê êàê ñîäåðæèò òîëüêî ëèíåéíûå íåðàâåíñòâà. Ó÷èòûâàÿ âûïóêëîñòü U , çàäà÷à ïîäïàäàåò ïîä êëàññ çàäà÷ âûïóêëîé îïòèìèçàöèè, ïîäðîáíî èçó÷åííîé âî ìíîãèõ ðàáîòàõ (ñì. [52,90]).1.1.2Äèíàìè÷åñêèå ïîòîêîâûå ïðîöåññûÇäåñü è äàëåå áóäåì ïðåäïîëàãàòü, ÷òî äàí íåêîòîðûé îðèåíòèðîâàííûé ãðàô G = hV, Ei, îïèñûâàþùèé ñåòü è âçàèìîäåéñòâèå âíóòðèýòîé ñåòè.
V ìíîæåñòâî âåðøèí, E ∈ V × V ìíîæåñòâî äóã è ïóñòü|V | = n, |E| = m.  ýòîé ñåòè öèðêóëèðóåò ïîòîê, äëÿ êîòîðîãî ìîæíîâûáèðàòü èíòåíñèâíîñòü (èëè ñêîðîñòü) äâèæåíèÿ ïî äóãå. Åñëè ïî äóãå(i, j) ∈ E çà íåêîòîðûé èíòåðâàë âðåìåíè ïðîøåë åäèíè÷íûé ïîòîê, òîýòî îçíà÷àåò, ÷òî ýòîò åäèíè÷íûé ïîòîê ñíà÷àëà íàõîäèëñÿ íà âåðøèíå i,çàòåì ïåðåáðàëñÿ íà âåðøèíó j . Äàëåå ñ÷èòàåì, ÷òî íà êàæäîé âåðøèíåñîäåðæèòñÿ íåîãðàíè÷åííîå õðàíèëèùå, êîòîðîå ìîæåò õðàíèòü ÷àñòèöû ïîòîêà, è îáîçíà÷èì ÷åðåç xi (t) êîëè÷åñòâî ïîòîêà, íàõîäÿùååñÿ íàâåðøèíå i â ìîìåíò âðåìåíè t.  ñèëó ôèçè÷åñêèõ ïðè÷èí îñíîâíîå âîçíèêàþùåå îãðàíè÷åíèå ïðîïóñêíàÿ ñïîñîáíîñòü äóã, îãðàíè÷èâàþùàÿñâåðõó êîëè÷åñòâî ïåðåäàâàåìîãî ïîòîêà ïî äóãå çà åäèíèöó âðåìåíè.Îáîçíà÷èì çà c = (c1 , .
. . , cm )T âåêòîð ïðîïóñêíûõ ñïîñîáíîñòåé. Äëÿïîòîêîâûõ ïðîöåññîâ x− ÿâëÿåòñÿ íà÷àëüíûì ðàñïðåäåëåíèåì ïîòîêà ïî19ñåòè, x+ æåëàåìîå ðàñïðåäåëåíèå. Ïóñòü B ìàòðèöà èíöèäåíòíîñòè: 1, e âûõîäèò èç i,Bie =−1, e âõîäèò â i,0â îñòàëüíûõ ñëó÷àÿõ.Îïòèìàëüíûì ïîòîêîâûì ïðîöåññîì áóäåì íàçûâàòü ðåøåíèå ñëåäóþùåé çàäà÷èìèíèìèçèðîâàòü(1.10)ïðè óñëîâèèτ,ẋ = Bu, x(0) = x− ; x(τ ) = x+ ,x(t) ≥ 0, 0 ≤ u (t) ≤ c .eeÊàê è â (1.8), ïåðåìåííûìè ÿâëÿþòñÿ óïðàâëÿþùåå âîçäåéñòâèå u(t) èïåðåìåííûå ñîñòîÿíèÿ x(t), ïðè ýòîì x îäíîçíà÷íî çàäàåòñÿ ÷åðåç u.Ïðèìåíÿÿ ðàññóæäåíèÿ, îïèñàííûå â ïðåäûäóùåé ãëàâå, ïîëó÷àåì, ÷òîîïòèìàëüíîå óïðàâëåíèå ìîæíî èñêàòü ñðåäè ïîñòîÿííûõ ôóíêöèé. Áîëåå òîãî, òàêîå îïòèìàëüíîå ñòàòè÷åñêîå óïðàâëåíèå ÿâëÿåòñÿ ðåøåíèåìçàäà÷èìèíèìèçèðîâàòüτ,(ïðè óñëîâèèèëèìàêñèìèçèðîâàòü(1.11)λ,(ïðè óñëîâèèτ Bu = x+ − x− ,0 ≤ ue ≤ ceBu = λ(x+ − x− ),0 ≤ ue ≤ ce .Ïîñëåäíÿÿ ïîñòàíîâêà ÿâëÿåòñÿ çàäà÷åé ëèíåéíîãî ïðîãðàììèðîâàíèÿ, àçíà÷èò ê íåé ïðèìåíèìî áîëüøîå êîëè÷åñòâî ìåòîäîâ, äîñòóïíûõ â ñòàíäàðòíûõ ïàêåòàõ (Matlab, Mathematica è ïðî÷èå).
Êàê îêàçûâàåòñÿ, ýòàçàäà÷à ñâîäèòñÿ ê äîâîëüíî ïîäðîáíî èçó÷åííîé çàäà÷å ïàðàìåòðè÷åñêî20Ðàñøèðåííûé ãðàô (ôîðìóëèðîâêà ÷åðåç τ ). Äëÿ íàãëÿäíîñòè äóãè ïðîèíäåêñèðîâàíû äâóìÿ áóêâàìè íà÷àëîì è êîíöîì äóãè.Ðèñ. 1.2:ãî ïîòîêà. Ñòîèò îòìåòèòü, ÷òî óðàâíåíèå Bu = p ðàçðåøèìî òîëüêîPnòîãäà, êîãäà i=1 pi = 0.−0000Îáîçíà÷èì di = x+i − xi . Ðàññìîòðèì ãðàô G = hV , E i, ãäå V =V ∪ {s, t} ðàñøèðåíèå V ôèêòèâíûìè âåðøèíàìè èñòîêà s è ñòîêà t,E = E ∪ Es ∪ Et , Es = {(s, i)|i ∈ V, di < 0}, Et = {(i, t)|i ∈ V, di > 0}.Ïóñòü ïðîïóñêíûå ñïîñîáíîñòè c0e íà ãðàôå G0 èìåþò âèäe ∈ E, ce ,c0e =−λdi , e = (s, i) ∈ Es ,λdie = (i, t) ∈ Et .Ïðè ôèêñèðîâàííîì λ ñóùåñòâîâàíèå äîïóñòèìîãî âåêòîðà u, ñîîò-âåòñòâóþùåãî ýòîìó λ â (1.11) ðàâíîñèëüíî ñóùåñòâîâàíèþ s-t ïîòîêà âãðàôå G0 , íàñûùàþùåãî âñå äóãè, èíöèäåíòíûå ñ s (èëè, ÷òî òî æå ñàìîå, íàñûùàþùåãî âñå äóãè, èíöèäåíòíûå ñ t, ýòîò ôàêò ïîäðîáíî îïèñàíâ [22]).
Äðóãèìè ñëîâàìè, äîïóñòèìîñòü òîãî èëè èíîãî çíà÷åíèÿ λ â çàäà÷å (1.11) ìîæíî ïðîâåðèòü, ðåøèâ çàäà÷ó î ìàêñèìàëüíîì ïîòîêå. Íà21Ðàñøèðåííûé ãðàô (ôîðìóëèðîâêà ÷åðåç λ). Äëÿ íàãëÿäíîñòè äóãè ïðîèíäåêñèðîâàíû äâóìÿ áóêâàìè íà÷àëîì è êîíöîì äóãè.Ðèñ. 1.3:ðèñ. 1.3 èçîáðàæåí ãðàô G0 . Íà ðèñ. 1.2 èçîáðàæåí ýêâèâàëåíòíûé åìóãðàô ñ ôîðìóëèðîâêîé (1.11) ÷åðåç τ , íàãëÿäíî âèäíî, ÷òî âûïîëíåíèåóñëîâèÿ τ Bu = x+ − x− ñîîòâåòñòâóåò óñëîâèþ íàñûùåíèÿ âñåõ äóã âè-äà (s, i) è (i, t).
Ìèíèìàëüíîå çíà÷åíèå τ , äëÿ êîòîðîãî âîçìîæåí òàêîéïîòîê ÿâëÿåòñÿ ðåøåíèåì (1.11).Ñ äðóãîé ñòîðîíû, åñëè (λ, u) äîïóñòèìàÿ òî÷êà (1.11), òî ∀λ0 < λ,0λ0 , λλ u òîæå äîïóñòèìàÿ òî÷êà (1.11). Ñëåäîâàòåëüíî, ìàêñèìàëüíîåçíà÷åíèå λ ìîæíî íàéòè ìåòîäîì áèñåêöèè (äèõîòîìèÿ, äåëåíèå îòðåçêàïîïîëàì), äëÿ êîòîðîãî íóæíî ïîäîáðàòü íà÷àëüíûé îòðåçîê, êîòîðûéñîäåðæèò îïòèìàëüíîå çíà÷åíèå λ. Ëåâóþ ãðàíèöó ýòîãî îòðåçêà ìîæíîâçÿòü ðàâíîé íóëþ.
Ïðàâóþ ãðàíèöó ìîæíî âçÿòü èç íåðàâåíñòâàλXdi >0Òàêèì îáðàçîì, îáîçíà÷èâ r0 =di ≤Xe∈EPcP e∈E ed >0 dii22ce .ïîëó÷àåì, ÷òî äëÿ íàõîæäåíèÿ-òî÷íîãî ðåøåíèÿ çàäà÷è (1.11) äîñòàòî÷íî ðåøèòü íå áîëåå ÷åìlog2r0çàäà÷ ìàêñèìàëüíîãî ïîòîêà íà ãðàôå G0 (ñ ðàçëè÷íûìè çíà÷åíèÿìè λ).Êàê îïèñàíî â [65], ïî ðÿäó êîìáèíàòîðíûõ ñîîáðàæåíèé öåëåñîîáðàçíà àäàïòàöèÿ ìåòîäà ïðîòàëêèâàíèÿ ïðåäïîòîêà, ðàçðàáîòàííîãî â [68],äëÿ ðåøåíèÿ ýòîé çàäà÷è.
Îáùèé àëãîðèòì, ïðåäëîæåííûé â [65], ìîæíî îïèñàòü êàê ïðèìåíåíèå ïîäîáíîé ìåòîäó Íüþòîíà ïðîöåäóðû âìåñòîìåòîäà áèñåêöèè (ïîäðîáíåå â ñëåäóþùåì ðàçäåëå).1.1.3Ñòîõàñòè÷åñêèå ïîòîêîâûå ïðîöåññû ïåðâîé ïîëîâèíå ïðîøëîãî âåêà ïîÿâèëèñü ïåðâûå ìîäåëè, ó÷èòûâàþùèå íåòî÷íîñòü ôèçè÷åñêèõ ìîäåëåé.  îòëè÷èè îò ìîäåëåé ïðåäøåñòâåííèêîâ ïðåäëàãàëîñü ðåøàòü çàäà÷ó â óñëîâèÿõ, êîãäà ÷àñòü ïàðàìåòðîâ ñèñòåìû ÿâëÿåòñÿ íåèçâåñòíîé è íåêîíòðîëèðóåìîé.
Íåñìîòðÿíà òî, ÷òî çàäà÷è ñ íåèçâåñòíûìè ïàðàìåòðàìè ðåøàþòñÿ â ìàòåìàòèêåïîâñåìåñòíî, ïîëíîñòüþ èçó÷åíû òîëüêî íàèáîëåå òðèâèàëüíûå èç çàäà÷. Îïèñàíèå îïðåäåëåííîãî êëàññà íåîïðåäåëåííîñòåé, â óñëîâèÿõ êîòîðûõ ìîæíî äîáèòüñÿ îïðåäåëåííîãî ïðàêòè÷åñêîãî ðåçóëüòàòà, ÿâëÿëîñü äîâîëüíî ñâåæåé èäååé è íà òåêóùèé ìîìåíò èñïîëüçóåòñÿ ïîâñåìåñòíî. Òàê, íàïðèìåð, â ðàáîòå [89] âïåðâûå ïîÿâëÿåòñÿ ìåòîä ÌîíòåÊàðëî;  [104] (ôèëüòð Âèíåðà-Êîëìîãîðîâà), [75] (ôèëüòð ÊàëìàíàÁüþñè) ïîÿâëÿþòñÿ ìåòîäû ïðåäñêàçàíèÿ ïîâåäåíèÿ è îöåíêè íåèçâåñòíûõ ïàðàìåòðîâ ñëó÷àéíûõ ïðîöåññîâ; â [96] âïåðâûå ïîÿâëÿåòñÿ ïîíÿòèå ñòîõàñòè÷åñêîé àïïðîêñèìàöèè, ðàçâèòîå â ìíîãî÷èñëåííûõ ðàáîòàõ,âêëþ÷àþùèõ ïðîöåäóðó Êèôåðà-Âîëüôîâèöà [79], ìíîãîðàçìåðíóþ ñòîõàñòè÷åñêóþ àïïðîêñèìàöèþ Áëþìà [49], óñðåäíåíèÿ Ïîëÿêà [28], ìåòîäSP SA, ïðåäëîæåííûå Ñïàëëîì [100], ðàíäîìèçèðîâàííûå ìåòîäû ñòîõàñòè÷åñêîé àïïðîêñèìàöèè Ãðàíè÷èíà [1214]; â [47] ïðåäëîæåíî îáîáùåíèå ìåòîäà äèíàìè÷åñêîãî ïðîãðàììèðîâàèÿ äëÿ ñòîõàñòè÷åñêèõ ïðîöåññîâ; â [54] ïðåäëîæåí ñöåíàðíûé ïîäõîä äëÿ çàäà÷ ñî ñòîõàñòè÷åñêèìè23îãðàíè÷åíèÿìè.Èìåÿ ñâîþ ñîáñòâåííóþ ñïåöèôèêó, ñ òî÷êè çðåíèÿ ñòîõàñòè÷åñêèõïðîöåññîâ ñòàíäàðòíûå ïîòîêîâûå çàäà÷è ñòàëè èçó÷àòüñÿ îòíîñèòåëüíîíåäàâíî (ñì.
[67, 72, 98]). Ýòè ðàáîòû, îäíàêî, èçó÷àþò ñâîéñòâà ìàêñèìàëüíîãî ïîòîêà êàê ôóíêöèþ îò çíà÷åíèé ïðîïóñêíûõ ñïîñîáíîñòåé,çíà÷åíèå ìàêñèìàëüíîãî ïîòîêà f ∗ â çàäà÷å (2.9) åñòü ôóíêöèÿ îò ïàðàìåòðîâ c1 , . . . , cm , ãäå ci ∈ [0, +∞).  òàêîé ïîñòàíîâêå îòñóòñòâóåò àíà-ëèç ïðîöåññà öèðêóëÿöèè ïîòîêà. Ñ äðóãîé ñòîðîíû, â ðàáîòàõ [81, 99]èçó÷àþòñÿ ïðîöåññû öèðêóëÿöèè ïîòîêà â ñåòè. Êëþ÷åâûì íàïðàâëåíèåì èññëåäîâàíèÿ ýòèõ ðàáîò ÿâëÿåòñÿ íàõîæäåíèå îïòèìàëüíîãî ïîòîêàâ óñëîâèÿõ ïîëîæèòåëüíîãî âðåìåíè ïåðåõîäà ïî äóãå.  ýòèõ ðàáîòàõôîðìàëüíî ðàññìàòðèâàþòñÿ ôóíêöèè ïîòîêà fe ∈ L1 [0, T ] äëÿ íåêîòîðîãî èíòåðâàëà [0, T ], îäíàêî ïðîïóñêíûå íå ìåíÿþòñÿ âî âðåìåíè. ýòîé ðàáîòå îñíîâíîé èíòåðåñ çàêëþ÷àåòñÿ â èññëåäîâàíèè ñëåäóþùåì ñòîõàñòè÷åñêîì îáîáùåíèè (1.10)ìèíèìèçèðîâàòü(1.12)ïðè óñëîâèèτ,ẋ = Bu, x(0) = x− ; x(τ ) = x+ ,x(t) ≥ 0, 0 ≤ u (t) ≤ c + ξ (t).eee ãëàâå 2 áóäóò îïèñàíû äâà ïîäõîäà ê ïîñòðîåíèþ ðåøåíèÿ (1.12):ïîäõîä íà îñíîâå êîíöåïöèè óñðåäíÿåìûõ ôóíêöèé è àäàïòèâíûé ìóëüòèàãåíòíûé ïîäõîä.24Задача линейногопрограммированияЗадача выпуклогопрограммированияЗадача о потокеминимальнойстоимостиНелинейныепотоковые задачиЗадача омаксимальномдинамическом потокеЗадача опараметрическомпотокеЗадачи о многотипныхпотокахЗадача омаксимальном потокеÐèñ.
1.4:1.2Ïîòîêîâûå çàäà÷è â èíôîðìàòèêå.Ìåòîä ïðîòàëêèâàíèÿ ïðåäïîòîêà äëÿïîòîêîâûõ çàäà÷ ëèíåéíîãîïðîãðàììèðîâàíèÿÏîòîêîâûå çàäà÷è ïðåäñòàâëÿþò ñîáîé öåëóþ îòäåëüíóþ îáëàñòü èíôîðìàòèêè. Íà ðèñ. 1.4 ïîêàçàíû îñíîâíûå òèïû ïîòîêîâûõ çàäà÷ è çàâèñèìîñòü ìåæäó íèìè. Íàèáîëåå ðåëåâàíòíûìè ê ýòîé ðàáîòå ÿâëÿþòñÿçàäà÷à î ìàêñèìàëüíîì ïîòîêå, çàäà÷à î ïàðàìåòðè÷åñêîì ïîòîêå è çàäà÷à î ìàêñèìàëüíîì äèíàìè÷åñêîì ïîòîêå. Ïåðâûå äâå èãðàþò àêòèâíóþðîëü â ðåøåíèè (1.8).
 çàäà÷å î ìàêñèìàëüíîì ïîòîêå ïðåäïîëàãàåòñÿ,÷òî ïðè ïåðåõîäå îò îäíîé âåðøèíû íà äðóãóþ ÷àñòèöà ïîòîêà ìãíîâåííîïðîõîäèò ïî äóãå è îêàçûâàåòñÿ íà ìåñòå íàçíà÷åíèÿ. Òåì íå ìåíåå, êîëè÷åñòâî ÷àñòèö ïîòîêà, ïðîõîäÿùèõ ïî ðåáðó çà åäèíèöó âðåìåíè, îãðàíè÷åíî.  çàäà÷å î ìàêñèìàëüíîì äèíàìè÷åñêîì ïîòîêå ïðåäïîëàãàåòñÿ,÷òî ÷àñòèöà ïîòîêà ñîâåðøàåò äâèæåíèå ïî ðåáðó â òå÷åíèå íåêîòîðîãî25ïðîìåæóòêà âðåìåíè.  äàëüíåéøåì àíàëèçå ïîäîáíàÿ âåëè÷èíà òàêæåáóäåò ïðèñóòñòâîâàòü â ìîäåëÿõ, îäíàêî ñâÿçü ñ çàäà÷åé äèíàìè÷åñêîãîïîòîêà áóäåò ìèíèìàëüíà. Ïîäðîáíîå îïèñàíèå çàäà÷è î ìàêñèìàëüíîìäèíàìè÷åñêîì ïîòîêå ìîæíî íàéòè â [81, 99]. çàäà÷å î ïàðàìåòðè÷åñêîì ïîòîêå ðàññìàòðèâàåòñÿ ñëåäóþùèé âîïðîñ: åñëè ïðîïóñêíûå ñïîñîáíîñòè äóã çàâèñÿò îò íåêîòîðîãî ñêàëÿðíîãîãëîáàëüíîãî ïàðàìåòðà, êàê âåëè÷èíà ìàêñèìàëüíîãî ïîòîêà çàâèñèò îòçíà÷åíèÿ ýòîãî ïàðàìåòðà? Êëþ÷åâîé âîïðîñ èññëåäîâàíèÿ ýòîé çàäà÷èäîâîëüíî ïðîñò: â êàêèõ ñëó÷àÿõ âîçìîæíî ðåøåíèå òàêîé çàäà÷è áûñòðåå, ÷åì íåïîñðåäñòâåííîå ðåøåíèå çàäà÷è î ìàêñèìàëüíîì ïîòîêå äëÿâñåõ âîçìîæíûõ çíà÷åíèé ïàðàìåòðà?  ðàáîòå [65] ïðåäëîæåí íàèáîëååñóùåñòâåííûé âêëàä ïî ýòîé çàäà÷å.
Äëÿ îáøèðíîãî êëàññà âûðàáîòàíìåòîä íàõîæäåíèÿ ðåøåíèÿ çàäà÷è ïàðàìåòðè÷åñêîãî ïîòîêà, êîòîðûéïî âðåìåíè ðàáîòû ýêâèâàëåíòåí ðåøåíèþ îäíîé çàäà÷è î ìàêñèìàëüíîì ïîòîêå ìåòîäîì ïðîòàëêèâàíèÿ ïðåäïîòîêà. Çàäà÷è î ìíîãîòèïíûõïîòîêàõ (àíãë.multicommodity ows) ÿâëÿþòñÿ ðàñøèðåíèåì çàäà÷è î ìàêñèìàëüíîìïîòîêå íà ñëó÷àé, êîãäà â ñåòè åñòü íåñêîëüêî òèïîâ ïîòîêîâ ñî ñâîèìè ñîáñòâåííûìè èñòîêàìè è ñòîêàìè, êîòîðûå äåëÿò îäíè ïðîïóñêíûåñïîñîáíîñòè (ñì.
[66, 74]). Òàêèå îãðàíè÷åíèÿ ÿâëÿþòñÿ òèïè÷íûìè äëÿòðàíñïîðòíûõ ïîòîêîâ. Ê íåëèíåéíûì ïîòîêîâûì çàäà÷àì ìîæíî îòíåñòè çàäà÷è ïîòîêîâ ñ ìèíèìàëüíîé ýíòðîïèåé [7, 8], ýëåêòðè÷åñêèå ïîòîêè [84], à òàêæå íåêîòîðûå ïðèìåðû ïðèâåäåíû â [37, 52].1.2.1Çàäà÷à î ìàêñèìàëüíîì ïîòîêåÒðàäèöèîííî çàäà÷à î ìàêñèìàëüíîì ïîòîêå ñòàâèòñÿ â ñëåäóþùåìâèäå:(1.13)ìàêñèìèçèðîâàòüïðè óñëîâèèPf−ee∈in(t)e∈out(t) fe ,Pe∈in(i) fe −e∈out(i) fe = 0, i ∈ V, i 6= s, t,0 ≤ fe ≤ ce ,val(f ) =(PP26ãäå ïåðåìåííûìè ÿâëÿþòñÿ âåëè÷èíû ïîòîêà ïî äóãàì f1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
