Диссертация (1150610), страница 3
Текст из файла (страница 3)
Ãîëüäáåðãà.  ïóíêòå 3.3 ïðèâåäåíûðåçóëüòàòû ñèìóëèðîâàíèÿ ïðîöåññîâ ðàñïðåäåëåíèÿ çàãðóçêè ñ èñïîëüçîâàíèåì ðàçðàáîòàííûõ ìåòîäîâ è ìåòîäà, îñíîâàííîãî íà ïðîòîêîëåëîêàëüíîãî ãîëîñîâàíèÿ.Âçàêëþ÷åíèèäèññåðòàöèè ïîäâåäåíû èòîãè ïðîâåäåííîãî è çàâåð-øåííîãî â ðàìêàõ ïîñòàâëåííûõ çàäà÷ èññëåäîâàíèÿ.11Ãëàâà 1Ïîòîêîâûå ïðîöåññû è èõïðèëîæåíèå â çàäà÷àõìóëüòèàãåíòíîãîðàñïðåäåëåíèÿ ðåñóðñîâ1.1Ïîòîêîâûå ïðîöåññû ïîñëåäíèå äåñÿòèëåòèÿ ñåòåâûå òåõíîëîãèè îáðåòàþò âñå áîëüøóþàêòóàëüíîñòü, è óæå ñåé÷àñ âîçìîæíîñòü ðåøàòü ðàçëè÷íûå çàäà÷è, âîçíèêàþùèå â ñåòåâûõ ñèñòåìàõ, ÿâëÿåòñÿ îäíèì èç ñàìûõ âàæíûõ ïðèëîæåíèé êîìïüþòåðíûõ è êèáåðíåòè÷åñêèõ íàóê.
Êàê è äëÿ ìíîãèõ äðóãèõêðóïíûõ îáëàñòåé, ñóùåñòâóåò îãðîìíîå ìíîæåñòâî çàäà÷ ðàçëè÷íûõ ïîñâîåé ñòðóêòóðå è âîçìîæíûì ïîäõîäàì ê ðåøåíèþ, â ýòîé îáëàñòè ñêîðåå âñåãî äàæå íå ñóùåñòâóåò óíèâåðñàëüíûõ ïîäõîäîâ ê ðåøåíèþ 95%âñåõ âîçíèêàþùèõ çàäà÷. Ê õîðîøî èçó÷åííûì òåîðåòè÷åñêèì ìîäåëÿì,êîòîðûå ÷àùå âñåãî ïðèìåíèìû â òåîðèè è ïðàêòèêå, ìîæíî ïðè÷èñëèòüòîëüêî íàèáîëåå îáùèå òåîðèþ ãðàôîâ, òåîðèþ äèíàìè÷åñêèõ ñèñòåì,ìåòîäû ìàòåìàòè÷åñêîé îïòèìèçàöèè è ò. ï.Äâå îñíîâíûõ çàäà÷è, ðàññìàòðèâàåìûå â ýòîé ðàáîòå, èìåþò ñïåöèôèêó ïîòîêîâûõ ïðîöåññîâ â ñåòÿõ.
Ïîòîêîâûé ïðîöåññ çàêëþ÷àåòñÿâ äâèæåíèè ÷àñòèö âíóòðè íåêîòîðîé çàìêíóòîé ñèñòåìû, ïðè ýòîì íè12îäíà ÷àñòèöà íå ïîêèäàåò ñèñòåìó, è íè îäíà ÷àñòèöà íå ïðîíèêàåò âñèñòåìó èçâíå.  ýòîé ðàáîòå áóäóò ðàññìàòðèâàòüñÿ ñåòåâûå ñèñòåìû,âçàèìîäåéñòâèå êîòîðûõ òðàäèöèîííî ìîäåëèðóåòñÿ ñ ïîìîùüþ òåîðèèãðàôîâ: âåðøèíû ãðàôà ÿâëÿþòñÿ ïðîìåæóòî÷íûì ìåñòîì äëÿ õðàíåíèÿïîòîêà, à äóãè (ðåáðà) ÿâëÿþòñÿ ñðåäñòâîì öèðêóëÿöèè ïîòîêà ïî ãðàôó (çäåñü è äàëåå ïðè èñïîëüçîâàíèè òåðìèíà äóãà ïîäðàçóìåâàåòñÿ,÷òî äâèæåíèå âîçìîæíî â îäíó ñòîðîíó, à ïðè èñïîëüçîâàíèè òåðìèíà ðåáðî â îáå ñòîðîíû.
 äàëüíåéøèõ ðàçäåëàõ ýòîò íþàíñ áóäåòôîðìàëèçîâàí áîëåå ñòðîãî, íî ñòîèò èìåòü â âèäó, ÷òî â ïîòîêîâûõçàäà÷àõ îòñóòñòâóåò êà÷åñòâåííîå ðàçëè÷èå ìåæäó îðèåíòèðîâàííûì èíåîðèåíòèðîâàííûì ñëó÷àÿìè). Äðóãèìè ñëîâàìè, ÷àñòèöû ïîòîêà ìîãóò ïåðåìåùàòüñÿ îò îäíîé âåðøèíû äî äðóãîé ïî ðåáðó, ñîåäèíÿþùåéýòè âåðøèíû.  êà÷åñòâå ïðàêòè÷åñêèõ ïðèìåðîâ ïîòîêîâûõ ïðîöåññîâìîæíî ïðèâåñòè ñëåäóþùèå ñèòóàöèè:• Äâèæåíèå äàííûõ â èíôîðìàöèîííûõ ñåòÿõ.
×àñòèöû ïîòîêà ïàêåòû äàííûõ, ðåáðà êàíàëû ñâÿçè, âåðøèíû ëîãè÷åñêèå è âû÷èñëèòåëüíûå óñòðîéñòâà.• Äâèæåíèå àâòîìîáèëåé ïî äîðîãàì. Çäåñü ÷àñòèöàìè ïîòîêà ÿâëÿþòñÿ ìàøèíû, ðåáðà äîðîãè / óëèöû, óçëû ïåðåñå÷åíèå äîðîã/ óëèö.• Äâèæåíèå æèäêîñòè / ãàçà ïî òðóáîïðîâîäó. ×àñòèöû ïîòîêà æèäêîñòü èëè ãàç, ðåáðà òðóáû, óçëû òðóáîïðîâîäíûå êðàíû,ðàñïðåäåëèòåëüíûå ñòàíöèè.Ñâîéñòâà, îãðàíè÷åíèÿ è ïàðàìåòðû äâèæåíèÿ ïîòîêà ïî ðåáðó ìîãóòâàðüèðîâàòüñÿ â çàâèñèìîñòè îò çàäà÷è, íî â öåëîì äëÿ ïîòîêîâûõ çàäà÷ïðèíÿòû ñëåäóþùèå õàðàêòåðíûå ñâîéñòâà äâèæåíèÿ ïîòîêà:1.
Îáúåì ïîòîêà, êîòîðûé ìîæåò ïðîéòè ïî ðåáðó çà åäèíèöó âðåìåíè (èëè çà ëþáîé êîíå÷íûé èíòåðâàë âðåìåíè) îãðàíè÷åí, òî÷íóþâåðõíþþ ãðàíèöó ýòîãî îáúåìà ïðèíÿòî íàçûâàòü ïðîïóñêíîé ñïî-ñîáíîñòüþ ðåáðà.13Длина, время переходаПропускнаяспособностьÐèñ. 1.1:Ïàðàìåòðû äóãè â òðàíñïîðòíîé ñåòè.2. ×àñòèöû ïîòîêà ïðîõîäÿò ïî ðåáðó íå ìãíîâåííî, à íà ïðîòÿæåíèèíåêîòîðîãî èíòåðâàëà âðåìåíè.Êàê èçîáðàæåíî íà ðèñ. 1.1, â ñëó÷àå òðàíñïîðòíûõ ïîòîêîâ ýòè âåëè÷èíû ìîãóò áûòü èíòåðïðåòèðîâàíû êàê øèðèíà è äëèíà äîðîãè ñîîòâåòñòâåííî.Êëþ÷åâûì àñïåêòîì ýòîé ðàáîòû ÿâëÿåòñÿ èçó÷åíèå äèíàìè÷åñêèõìîäåëåé ïîòîêîâûõ ïðîöåññîâ, ò.å.
òàêèõ ìîäåëåé, êîòîðûå ó÷èòûâàþòèçìåíåíèÿ ñî âðåìåíåì ðàçëè÷íûõ àñïåêòîâ ñèñòåìû è îêðóæàþùåé ñðåäû. Âî ìíîãèõ ñëó÷àÿõ èçó÷åíèå ïðîòåêàþùèõ âî âðåìåíè ïîòîêîâûõïðîöåññîâ ìîæåò áûòü ñâåäåíî ê ðàññìîòðåíèþ ñòàöèîíàðíûõ ïîòîêîâûõçàäà÷. Òàê, íàïðèìåð, â [37, 39, 55, 103] ðàññìîòðåíû ñòàòè÷åñêèå ìåòîäûìîäåëèðîâàíèÿ òðàíñïîðòíûõ ïîòîêîâ, â [62] è [99] ðàññìîòðåíû äèíàìè÷åñêèå ïîòîêîâûå ïðîöåññû, çàäà÷è íàõîæäåíèÿ îïòèìàëüíîãî ïðîöåññà ñî ñòàòè÷åñêèìè ïðîïóñêíûìè ñïîñîáíîñòÿìè ñâåäåíû ê ñòàòè÷åñêèìïîòîêîâûì çàäà÷àì. Ðàáîòû [62, 81, 99] èìåþò ïîñòàíîâêè, ñõîæèå ñ ðàññìàòðèâàåìûìè â ýòîé ðàáîòå, è, â òîì ÷èñëå, ïîêàçûâàþò àêòóàëüíîñòüýòèõ çàäà÷. Ýòè ðàáîòû èìåþò ïðÿìîå îòíîøåíèå ê çàäà÷å î ìàêñèìàëü-íîì ïîòîêå è çàäà÷å î ïîòîêå ìèíèìàëüíîé ñòîèìîñòè, ââåäåííûìâ [64]. Íåñìîòðÿ íà áîëåå ïîëóâåêà ñ ìîìåíòà ïîÿâëåíèÿ, ïîñòàíîâêèýòèõ çàäà÷, äîïóñêàþùèå íåîïðåäåëåííîñòè íåêîòîðûõ õàðàêòåðèñòèê,ïîÿâèëèñü îòíîñèòåëüíî íåäàâíî (ñì.
[67, 72, 98]). Ïðè ýòîì, íà äàííûé14ìîìåíò îòñóòñòâóþò ðàáîòû, èçó÷àþùèå ïîòîêîâûå çàäà÷è â óñëîâèÿõäèíàìè÷åñêè èçìåíÿþùèõñÿ ïàðàìåòðîâ è âíåøíèõ íåêîíòðîëèðóåìûõâîçìóùåíèé. Àíàëèç ïîâåäåíèÿ ïîòîêîâûõ ïðîöåññîâ â òàêèõ ñèòóàöèÿõÿâëÿåòñÿ îäíèì èç îñíîâíûõ òåîðåòè÷åñêèõ âêëàäîâ ýòîé ðàáîòû.1.1.1Îïòèìàëüíûå äèíàìè÷åñêèå ïðîöåññûÒðàäèöèîííî, äèíàìèêà óïðàâëÿåìîé ñèñòåìû (ñ íåïðåðûâíûì âðåìåíåì) îïèñûâàåòñÿ óðàâíåíèåì(1.1)ẋ = f (x, u),ãäå x(t) = (x1 (t), .
. . , xn (t))T ∈ X âåêòîð ñîñòîÿíèÿ (ôàçîâûå ïåðåìåííûå), u(t) = (u1 (t), . . . , um (t))T ∈ U óïðàâëÿþùåå âîçäåéñòâèå. Äà-ëåå, çàäàíà íåêîòîðàÿ ôóíêöèÿ g(x, u) öåëåâîé ôóíêöèîíàë ìèíèìèçà-öèè, êîòîðûé ìîæíî èíòåðïðåòèðîâàòü êàê ñëîæíîñòü èëè ñòîèìîñòüóïðàâëåíèÿ u â ñîñòîÿíèè x, â ôàçîâîì ïðîñòðàíñòâå âûäåëåíû äâà âåêòîðà (êðàåâûå óñëîâèÿ) x− , x+ ∈ X . Îïòèìàëüíîé òðàåêòîðèåé ñèñòå-ìû (1.1), ïåðåâîäÿùåé ñèñòåìó èç ñîñòîÿíèÿ x− â ñîñòîÿíèå x+ ïî îòíî-øåíèþ ê ôóíêöèîíàëó g(·, ·) ÿâëÿåòñÿ òðàåêòîðèÿ x : [0, τ ] → Rn , x(t) ∈X è ñîîòâåòñòâóþùåå åé óïðàâëåíèå u : [0, τ ] → Rm , u(t) ∈ U , êîòîðàÿ âìåñòå ñ óïðàâëåíèåì u óäîâëåòâîðÿåò óðàâíåíèþ äèíàìèêè (1.1),ìèíèìèçèðóåò ôóíêöèîíàë (1.2)(1.2)Zτg(x(t), u(t))dt0è óäîâëåòâîðÿåò ãðàíè÷íûì óñëîâèÿì (1.3)(1.3)x(0) = x− , x(τ ) = x+ . ñëó÷àå g(·, ·) ≡ 1 çíà÷åíèå ôóíêöèîíàëà (1.2) ðàâíî τ , à çàäà÷à çàêëþ-÷àåòñÿ â íàõîæäåíèè íàèìåíüøåãî âîçìîæíîãî âðåìåíè ïåðåâîäà ñèñòåìû èç ñîñòîÿíèÿ x− â ñîñòîÿíèå x+ .
Äàëåå â ðàáîòå áóäóò ðàññìàòðè15âàòüñÿ òîëüêî òàêèå çàäà÷è.Îñíîâíûìè èíñòðóìåíòàìè àíàëèçà çàäà÷ îïòèìàëüíûõ ïðîöåññîâÿâëÿþòñÿ óðàâíåíèå Áåëëìàíà (äèíàìè÷åñêîå ïðîãðàììèðîâàíèå [46] èïðèíöèï ìàêñèìóìà [30]). Åñëè ïðàâàÿ ÷àñòü (1.1) íå çàâèñèò îò x, òîíè óðàâíåíèå Áåëëìàíà, íè ïðèíöèï ìàêñèìóìà íå äàþò íèêàêîé ïîëåçíîé èíôîðìàöèè. Ñ òî÷êè çðåíèÿ òåîðèè îïòèìàëüíîãî óïðàâëåíèÿòàêèå çàäà÷è ÿâëÿþòñÿ âûðîæäåííûìè, à îñíîâíàÿ ñëîæíîñòü çàêëþ÷àåòñÿ â íàõîæäåíèè ðåøåíèé íåêîòîðûõ ñòàòè÷åñêèõ îïòèìèçàöèîííûõçàäà÷.
Äàëüíåéøèé àíàëèç ôîðìàëüíî ïîêàçûâàåò âûðîæäåííîñòü òàêîãî êëàññà çàäà÷ (ôîðìóëèðîâêè ïðèíöèïà ìàêñèìóìà è óðàâíåíèÿ Áåëëìàíà äëÿ çàäà÷ îïòèìàëüíîãî óïðàâëåíèÿ ïðèâåäåíû â [30]).Ïóñòü ψ ∈ Rn , îïðåäåëèì ôóíêöèþ H êàêH(ψ, x, u) = ψ T f (x, u).Ñîãëàñíî ïðèíöèïó ìàêñèìóìà, åñëè u∗ (t) òàêîå óïðàâëåíèå (1.1), ÷òîâûïîëíÿþòñÿ ãðàíè÷íûå óñëîâèÿ (1.3) è ïðè ýòîì τ ïðèíèìàåò ìèíèìàëüíîå âîçìîæíîå çíà÷åíèå, òî ñóùåñòâóåò òàêàÿ ôóíêöèÿ ψ(t) ∈ Rn ,÷òî âäîëü òðàåêòîðèè äâèæåíèÿ âûïîëíÿþòñÿ óñëîâèÿ(1.4)∀t ∈ [0, τ ] : H(ψ(t), x(t), u∗ (t)) = sup H(ψ(t), x(t), u),u∈U(1.5)∂Hdψ=−.dt∂xè(1.6)H(ψ(τ ), x(τ ), u∗ (τ )) ≥ 0.Ïóñòü òåïåðü f (x, u) íå çàâèñèò îò x, ò.å. f (x, u) = F (u). Òîãäà îáå÷àñòè (1.4) íå çàâèñÿò îò x. Òîãäà â ñèëó (1.5) ψ(t) íå çàâèñèò îò t, à çíà÷èò äëÿ ëþáîé äîïóñòèìîé òðàåêòîðèè x(t) ìîæíî âçÿòü ψ òîæäåñòâåííî16ðàâíîé 0n = (0, .
. . , 0)T .| {z }nÑîãëàñíî ïðèíöèïó äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, ñóùåñòâóåòôóíêöèÿ ω(x), òàêàÿ ÷òî(1.7)sup ∇ω(x)T f (x, u) = 1,u∈Uω(x) ≤ 0, ω(x+ ) = 0. Ôèçè÷åñêèé ñìûñë ôóíêöèè ω(·) çàêëþ÷àåòñÿ âòîì, ÷òî −ω(x) ìèíèìàëüíîå âðåìÿ, çà êîòîðîå ìîæíî äîáðàòüñÿ èçx â x+ . Ïðè ôèêñèðîâàííîì x óïðàâëåíèå u, íà êîòîðîì (1.7) äîñòèãàåòìàêñèìóìà, ÿâëÿåòñÿ ëîêàëüíûì îïòèìàëüíûì óïðàâëåíèåì â òî÷êå x.Òàêèì îáðàçîì, îïòèìàëüíîå óïðàâëåíèå u∗ (t) óäîâëåòâîðÿåò∀t ∈ [0, τ ] : ∇ω(x(t))T f (x(t), u∗ (t)) = 1.Äëÿ òðàåêòîðèè x(t), ïîðîæäàåìîé îïòèìàëüíûì óïðàâëåíèåì u∗ (t),âåêòîð ψ(t) = ∇ω(x(t))T óäîâëåòâîðÿåò (1.5), (1.6) è (1.4), ïðè ýòîì âïîñëåäíåì ïðàâàÿ ÷àñòü ðàâíà åäèíèöå, ÷òî íå ïîçâîëÿåò âçÿòü ψ(t) ≡ 0näëÿ f (x, u) = F (u).
Ïîäñòàâèâ F (u) âìåñòî f (x, u) â (1.7) ïîëó÷àåì,÷òî ∇ω(x) íå çàâèñèò îò x, à çíà÷èò ω(·) åñòü ëèíåéíàÿ ôóíêöèÿ, ÷òîïîçâîëÿåò ñäåëàòü âûâîä, ÷òî îïòèìàëüíîå óïðàâëåíèå ïðèõîäèò â òî÷êóx+ ïî ïðÿìîé (ïðè óñëîâèè ñóùåñòâîâàíèÿ ôóíêöèè ω ).Ïóñòü òåïåðü F (u) = Bu, âåêòîð ñîñòîÿíèÿ x(t) ïðèíàäëåæèò â ëþáîé ìîìåíò âðåìåíè íåêîòîðîìó âûïóêëîìó ìíîæåñòâó X , ìíîæåñòâîäîïóñòèìûõ óïðàâëÿþùèõ âîçäåéñòâèé U òàêæå ÿâëÿåòñÿ âûïóêëûì.Ñîáðàâ âìåñòå âñå óñëîâèÿ, ïîëó÷àåì ñëåäóþùóþ çàäà÷óìèíèìèçèðîâàòü(1.8)ïðè óñëîâèèτ,ẋ = Bu, x(0) = x− ; x(τ ) = x+ ,x(t) ∈ X, u(t) ∈ U.Ïðåäïîëîæèì òåïåðü, ÷òî (τ ∗ , u∗ ) îïòèìàëüíîå ðåøåíèå (1.8). Ðàñ17ñìîòðèì1ū ≡ ∗ττ∗Zu∗ .0Òàê êàê ∀t ∈ [0, τ ∗ ] : u∗i (t) ∈ U è U âûïóêëî ïîëó÷àåì1ū(t) ≡ ∗τZ0τ∗u∗ ∈ U. ñèëó ñèñòåìû ïîëó÷àåì, ÷òî∗τ∗Z−−x(τ ) = x +ZB ū = x +0τ∗Bu∗ = x+ .0Òàê êàê óïðàâëÿþùåå âîçäåéñòâèå ïîñòîÿííî, ïîðîæäàåìàÿ òðàåêòîðèÿèìååò âèä x(t) = x− +x− ), â ñèëó âûïóêëîñòè îãðàíè÷åíèéxi (t) ∈ X è ôàêòà, ÷òî x è x äîïóñòèìûå ñîñòîÿíèÿ, ïîëó÷àåì, ÷òîū äîïóñòèìîå óïðàâëåíèå.
Òàê êàê ïðè ýòîì îíî ïåðåâîäèò ñèñòåìóâ ñîñòîÿíèå x+ çà îïòèìàëüíîå âðåìÿ τ ∗ , òî ū ÿâëÿåòñÿ îïòèìàëüíûìóïðàâëåíèåì. Òàêèì îáðàçîì âûïîëíåíî ñëåäóþùåå óòâåðæäåíèå.Ë å ì ì à 1.1.t+τ ∗ (x −−+Åñëè â çàäà÷å (1.8) ïðîïóñêíûå ñïîñîáíîñòè íå çàâèñÿòîò âðåìåíè, ce (t) ≡ c̄e , òî ñóùåñòâóåò îïòèìàëüíîå óïðàâëåíèå, íåçàâèñÿùåå îò âðåìåíè, ò. å. ôóíêöèÿ u(t) ≡ ū, ÿâëÿþùàÿñÿ ðåøåíèåì(1.8).Òåïåðü, ó÷èòûâàÿ âûøåñêàçàííîå, ìîæíî èçáàâèòüñÿ îò äèíàìè÷åñêîé ñîñòàâëÿþùåé (1.8): òàê êàê ëþáàÿ ëèíåéíàÿ òðàåêòîðèÿ, ïåðåâîäÿùàÿ ñèñòåìó èç x− â x+ äîïóñòèìà (â ñèëó âûïóêëîñòè X ), òî äëÿíàõîæäåíèÿ ìèíèìàëüíîãî âðåìåíè ïåðåõîäà äîñòàòî÷íî ðåøàòü ñëåäóþùóþ çàäà÷ó îïòèìèçàöèèìèíèìèçèðîâàòü(1.9)τ,(ïðè óñëîâèèτ Bu = x+ − x− ,u ∈ U.Òàêèì îáðàçîì, äëÿ ïîñòðîåíèÿ îïòèìàëüíîãî ïðîöåññà â çàäà÷å (1.8)18äîñòàòî÷íî ðåøèòü ñòàòè÷åñêóþ îïòèìèçàöèîííóþ çàäà÷ó (1.9).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
