Диссертация (Рандомизированные алгоритмы распределения ресурсов в адаптивных мультиагентных системах), страница 8

Áîëåå òîãî, àêòèâíàÿ ñòàäèÿ äóãè çàêàí÷èâàåòñÿâ ñèëó óñðåäíÿåìîñòè ïðîïóñêíûõ ñïîñîáíîñòåé.  ìîìåíò âðåìåíè, êîãäà âñå äóãè ïðîøëè ñâîè àêòèâíûå ñòàäèè, ñèñòåìà áóäåò íàõîäèòñÿ âñîñòîÿíèè x+ , òàê êàê äëÿ ðàññìîòðåííîãî óïðàâëåíèÿ êîíå÷íîå ñîñòîÿíèå òàêîå æå, êàê è äëÿ óñðåäíåííîé çàäà÷è.Ïîêàæåì, ÷òî ìîìåíò âðåìåíè, êîãäà äóãà (i, j) âûõîäèò èç àêòèâíîéñòàäèè, îãðàíè÷åí ñâåðõó çíà÷åíèåìT(2.4)Tj () + τ̃ τj ()è ñíèçó çíà÷åíèåì(2.5)Ti () + τ̃ τi ().Ðàññìîòðèì äóãó (i, j).

Èñïîëüçóÿ íèæíþþ îöåíêó äëÿ cij ïîëó÷àåìu∗ij1×uij dµ ≥ avg(cij )(1 − )+τi ()(1 + ) avg(cij )Ti ()+σij()Zt51×(t − Ti () − σij+ () + σij− ()).Ïðèðàâíèâàÿ ïðàâóþ ÷àñòü ê τ̃ u∗ij ïîëó÷àåì(1 − )(t − Ti () − σij+ () + σij− ()) = τ̃ .τi ()(1 + )Ðåøàÿ ïî t ïîëó÷àåì âåðõíþþ ãðàíèöó íà âûõîä èç àêòèâíîé ñòàäèè äëÿäóãè (i, j)t = Ti () + σij+ () − σij− + τ̃ τi ()1+1−÷òî íå ïðåâîñõîäèò (2.4) èç-çà ïîëîæèòåëüíîñòè σij è îïðåäåëåíèé Ti ()è τi (). Äàëåå, èñïîëüçóÿ âåðõíþþ îöåíêó cij ïîëó÷àåìu∗ij1uij ≤ avg(cij )(1 + )×+τi ()(1 + ) avg(cij )Ti ()+σij()Zt×(t − Ti () − σij+ () + σij+ ()).Ïðèðàâíèâàÿ ïðàâóþ ÷àñòü ê τ̃ u∗ij ïîëó÷àåìt = Ti () + τ̃ τi ().Òåïåðü ïðîâåðèì íåîòðèöàòåëüíîñòü ñîñòîÿíèÿ.

Èç äèíàìèêè ñèñòåìûèìååìxi (t) = xi (0) +XZu∗ji >0t−σjiuji dµ −0XZu∗ij >0tuij dµ.0Ïîñìîòðèì íà íåêîòîðóþ âåðøèíó i. Èç îöåíîê (2.4) è (2.5) ìîæíî çàêëþ÷èòü, ÷òî àêòèâíàÿ ñòàäèÿ ëþáîé âõîäÿùåé äóãè çàêàí÷èâàåòñÿ ðàíüøå àêòèâíîé ñòàäèè ëþáîé èñõîäÿùåé äóãè. Åñëè â êàêîé-òî ìîìåíò âõîäÿùèå äóãè çàêàí÷èâàþò àêòèâíóþ ñòàäèþ, íî èñõîäÿùèå äóãè âñå åùåíàõîäÿòñÿ â àêòèâíîé ñòàäèè, çíà÷èò, ÷òî âåñü âõîäÿùèé ïîòîê óæå áûëïîëó÷åí è, ñëåäîâàòåëüíî, ïîñëå ýòîãî ìîìåíòà ñîñòîÿíèå ìîæåò òîëüêî óìåíüøèòüñÿ. Òàêèì îáðàçîì, îñòàëîñü ïðîâåðèòü, áóäåò ëè ñîñòîÿ52íèå íåîòðèöàòåëüíûì, ïîêà âñå èíöèäåíòíûå äóãè íàõîäÿòñÿ â àêòèâíîéñòàäèè. Èñïîëüçóÿ íèæíþþ îöåíêó äëÿ cji , äëÿ ëþáîé âõîäÿùåé äóãèïîëó÷àåìZt−σjit−σjiZuji dµ =+Tj ()+σji()0uji dµ ≥u∗ji1×avg(cji )(1 − )τj ()(1 + ) avg(cji )+−×(t − σji − Tj () − σji() + σji()) ≥1 ∗u (t − Ti ()).τi () jiÏîñëåäíåå íåðàâåíñòâî ïîëó÷åíî èç îïðåäåëåíèÿ Ti () è τi ().

Äëÿ ëþáîéèñõîäÿùåé äóãè èìååìZtZuij =0t+Ti ()+σij()uij ≤u∗ij1avg(cij )(1 + )×τi ()(1 + ) avg(cij )×(t − Ti () − σij+ () + σij+ ()) =1 ∗u (t − Ti ()).τi () ijÑóììèðóÿ ïî âñåì èíöèäåíòíûì i äóãàìX1 X ∗uji −u∗ij  (t − Ti ()) ≥ ∗xi (t) ≥ xi (0) +τi () u∗ >0u∗ >0jiåñëèPij−ïîëîæèòåëüíî, òî î÷åâèäíûì îáðàçîì xi (t) ≥0 âûïîëíÿåòñÿ äëÿ t ≥ Ti (). Èíà÷å, òàê êàê ðàññìàòðèâàåìîå âðåìÿ tîãðàíè÷åíî ñâåðõó (2.4), ïîëó÷àåì, ÷òî t ≤ Ti () + τ̃ τi (), â ñèëó îïðåäå∗u∗ji >0 uji∗u∗ij >0 uijP53ëåíèé u∗ è τ̃∗ ≥ xi (0) +X1 X ∗u∗ij  τ̃ τi () = x+uji −i ≥ 0.τi () u∗ >0u∗ >0ijjiÒàê êàê ãðàô è ôóíêöèè ïðîïóñêíûõ ñïîñîáíîñòåé ôèêñèðîâàíû, äëÿäàííîãî ñóùåñòâóåò êîíå÷íîå ÷èñëî êîíôèãóðàöèé äëÿ Ti () è τi () (òàêêàê ÷èñëî àöèêëè÷åñêèõ ïîäãðàôîâ äàííîãî ãðàôà êîíå÷íî).

Òàêèì îáðàçîì, ñóùåñòâóåò êîíå÷íûå âåðõíèå îöåíêè íà Ti () è τi () âíå çàâèñèìîñòèîò u∗ . Îáîçíà÷èìT () =maxacyclic G0 ⊂GTi ().Äëÿ τi () îöåíêà ìîæåò áûòü çàïèñàíà ÿâíûì îáðàçîìτi () ≤1+1−n−1,ïðè ýòîì ðàâåíñòâî äîñòèãàåòñÿ íà ïîòîêå, èäóùåì âäîëü îäíîãî ïóòèèç n âåðøèí. Ó÷èòûâàÿ ýòè îöåíêè ïîëó÷àåì, ÷òî äëÿ ëþáûõ x− è x+âûïîëíÿåòñÿτ ∗ (x− , x+ , σ, c) ≤1+1−n−1τ ∗ (x− , x+ , 0m , avg(c)) + T ().Ò å î ð å ì à 2.2.Ðàññìîòðèì (2.1) ñ ôèêñèðîâàííûìè óñðåäíÿåìûìèíåîòðèöàòåëüíûìè ôóíêöèÿìè ïðîïóñêíûõ ñïîñîáíîñòåé ce (t), íåêî∞òîðûì íåîòðèöàòåëüíûì âåêòîðîì σ è ïîñëåäîâàòåëüíîñòÿìè {x−k }k=1 ,∞{x+k }k=1 , äëÿ êîòîðûõ âûïîëíÿåòñÿ+lim τ ∗ (x−k , xk , σ, c) = +∞,k→∞òîãäà+τ ∗ (x−k , xk , σ, c)lim= 1.−+k→∞ τ ∗ (xk , xk , 0m , avg(c))54Äîêàçàòåëüñòâî. ≤: ïðèìåíÿÿ òåîðåìó 2 äëÿ íåêîòîðîãî 0 < < 1,+x−k è xk , ïðè ïåðåõîäå ê ïðåäåëó ïîëó÷àåì+τ ∗ (x−k , xk , σ, c)≤lim−+k→∞ τ ∗ (xk , xk , 0m , avg(c))1+1−n−1.Óñòðåìèâ ê íóëþ ïîëó÷àåì æåëàåìîå íåðàâåíñòâî.

≥: Ïóñòü u∗ (t) îïòèìàëüíîå óïðàâëåíèå çàäà÷è ñ ïàðàìåòðàìè+x−k , xk , σ, c. Îáîçíà÷èìRτα(τ, c) = maxijcij dµ.avg(cij )τ0+Äëÿ êðàòêîñòè ïîëîæèì τ̃ = τ ∗ (x−k , xk , σ, c). Ïîñòðîèì ðåøåíèå óñðåä-íåííîé çàäà÷è ñëåäóþùèì îáðàçîìR τ̃ūij ≡uij dµ.α(τ̃ , c))τ̃0Âðåìÿ, ñîîòâåòñòâóþùåå òàêîìó óïðàâëåíèþ, ðàâíî α(τ̃ , c)τ̃ . Èç îïðåäåëåíèÿ âûòåêàåòR τ̃0 ≤ ūij ≤ R0τ̃0uij (t)dtcij (t)dtavg(c) ≤ avg(c).Òàê êàê íà ãðàíè÷íûõ ìîìåíòàõ âðåìåíè ñîñòîÿíèå íåîòðèöàòåëüíî, èçëèíåéíîñòè ïîëó÷àåì íåîòðèöàòåëüíîñòü ñîñòîÿíèÿ íà âñåì èíòåðâàëå.Èñïîëüçóÿ óñðåäíÿåìîñòü cij , ïîëó÷àåì+lim α(τ ∗ (x−k , xk , σ, c), c) = 1,k→∞÷òî è äîêàçûâàåò íóæíîå íåðàâåíñòâî.

 òåîðåìå 2 ðàñêðûòà íàèáîëåå òðóäíàÿ ÷àñòü äîêàçàòåëüñòâà è, áîëååòîãî, ïðåäëîæåí ñïîñîá ïîñòðîåíèÿ ñîîòâåòñòâóþùåãî óïðàâëåíèÿ. Òåîðåìà 3 ïîêàçûâàåò àñèìïòîòè÷åñêóþ îïòèìàëüíîñòü ïîñòðîåííîãî óïðàâëåíèÿ.552.1.3Ïîäáîð ïàðàìåòðîâ àëãîðèòìà âñòîõàñòè÷åñêîì ñëó÷àå ýòîì ïîäðàçäåëå áóäóò ïîäðîáíî ðàññìîòðåíû äâà ñòîõàñòè÷åñêèõñëó÷àÿ.Ïåðâûé ñëó÷àé ñîîòâåòñòâóåò îäíîìó èç ïðèìåðîâ óñðåäíÿåìûõ ôóíêöèé. Ïóñòü ξ0 , ξ1 , . . . ïîñëåäîâàòåëüíîñòü íåîòðèöàòåëüíûõ íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èí, Eξ = M > 0, E(ξ − M )2 = D2 ,(2.6)ce (t) = ξ[t] .Ðàññìîòðèì îäíó êîíêðåòíóþ äóãó è îöåíèì σ èç ëåìì 2.1 è 2.2 äëÿòàêîé ôóíêöèè ce (t). Êàêîâà âåðîÿòíîñòü òîãî, ÷òî äëÿ 0 < < 1 âåëè÷èíà σ > 0 óäîâëåòâîðÿåò ëåììàì 2.1 è 2.2 (−σ äëÿ ëåììû 2 è σ äëÿëåììû 3)? Íåðàâåíñòâà èç ýòèõ ëåìì èìåþò âèä∀k ≥ 0 : ∀k : (1 − )M (k − σ) <kXξi < (1 + )M (k + σ).i=1Íåìíîãî óâåëè÷èâ ïðàâóþ ÷àñòü (íà 2M σ ) ïîëó÷àåì kX∀k ≥ 0 : (ξi − M ) < M (k + (1 − )T ).i=1Îñíîâíàÿ ñëîæíîñòü çäåñü ñîñòîèò â òîì, ÷òî íåîáõîäèìî âûïîëíåíèåíåðàâåíñòâà äëÿ âñåõ k , â òî âðåìÿ êàê ñòàíäàðòíûå íåðàâåíñòâà äëÿîöåíêè ñóìì íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èí îáû÷íî îöåíèâàþò òîëüêîâñå ñóììó äëÿ íåêîòîðîãî îïðåäåëåííîãî k .

Òåì íå ìåíåå, â íàøåì ñëó÷àåïðèìåíèìî íåðàâåíñòâî Õàéåêà-Ðåíüè, à èìåííîÒ å î ð å ì à2.3(Íåðàâåíñòâî Õàéåêà-Ðåíüè). Ïóñòü {ξi }∞i=1 ïî-ñëåäîâàòåëüíîñòü íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èí, Eξi = 0, Eξi2 < ∞,PSn = ni=1 ξi , òîãäà äëÿ ëþáîé ïîñëåäîâàòåëüíîñòè {αi }∞i=1 , 0 < αi ≤56αi+1 Xn|Si |Eξi2Pr max≥1 ≤2 .i≤n αiαii=1Âîçüìåì αi = M (k + (1 − )T ) k!XPr ∀k ≤ n : (ξi − M ) < M (k + (1 − )T ) =i=1 k!X1 − Pr ∃k ≤ n : (ξi − M ) ≥ M (k + (1 − )T ) ≥i=11−nXi=1D2≥M 2 (i + (1 − )T )2D21− 2.M (1 − )TPn11Ïîñëåäíåå íåðàâåíñòâî ïîëó÷åíî â ñèëó i=1 (i+a)2 < a . Òàêèì îáðàçîì,÷òîáû äëÿ ôóíêöèè âèäà (2.6) âûïîëíÿëèñü ëåììà 2.1 è 2.2 ñ ïàðàìåòðîì è âåðîÿòíîñòüþ p ñëåäóåò âûáðàòü σ èç ðàâåíñòâà(2.7)D2.σ(, p) = 2M (1 − )(1 − p)Âòîðîé ïðèìåð ìåíåå òðèâèàëüíûé:• Ïðåäïîëîæèì, ÷òî ïîòîê ïîäåëåí íà êóñêè âåëè÷èíîé ξ1 , ξ2 , .

. . íåîòðèöàòåëüíûå íåçàâèñèìûå îäèíàêîâî ðàñïðåäåëåííûå ñëó÷àéíûå âåëè÷èíû, ïðè ýòîì äî íåïîñðåäñòâåííîé ïåðåäà÷è òàêîãî êóñêà ïî äóãå ìû íå çíàåì ðåàëèçàöèþ ξi (íî çíàåì Eξ ).• Ïóñòü ïðîïóñêíàÿ ñïîñîáíîñòü äóãè ïîñòîÿííà è ðàâíà c̄. Òàêèìîáðàçîì, ÷òîáû ïåðåäàòü ïîòîê âåëè÷èíû ξi íåîáõîäèìî âðåìÿ ξc̄i .• Âìåñòî òîãî, ÷òîáû ñ÷èòàòü íåîäíîðîäíûì ïîòîê, ìîæíî ñ÷èòàòüíåîäíîðîäíîé ïðîïóñêíóþ ñïîñîáíîñòü: ïîëîæèì, ÷òî ïî äóãå ïî57î÷åðåäè ïåðåäàþòñÿ ξ1 , ξ2 , . . ., îáîçíà÷èì τ0 = 0, τi = τi−1 +ξic̄ ,òîãäà ïðîïóñêíàÿ ñïîñîáíîñòü áóäåò èìåòü âèäc(τ ) =c̄, τ ∈ [τi−1 , τi ].ξiÀíàëîãè÷íî ïðåäûäóùåìó ñëó÷àþ, îöåíèì âåðîÿòíîñòü òîãî, ÷òîëåììû 2.1 è 2.2 íå âûïîëíÿþòñÿ äëÿ è σ .

Ïðåäïîëîæèì, ÷òîavg(c) =c̄M.c̄Pr ∀l :(1 − )(τl − σ) <MZ0τlc̄cdµ < (1 + )(τl + σ) =Mc̄c̄(1 − )(τl − σ) < l < (1 + )(τl + σ) .Pr ∀l :MMÏîñìîòðèì îòäåëüíî íà ëåâîå íåðàâåíñòâîlXξi <i=1Ml+ σc̄.(1 − )Ïðàâîå íåðàâåíñòâî èìååò àíàëîãè÷íûé âèälXξi >i=1Ml− σc̄.(1 + )Ïðè 0 < < 1 âûïîëíÿþòñÿ íåðàâåíñòâàÈñïîëüçóÿ èõ ïîëó÷àåì11−≥1+ è11−≥ 1 + .Z τlc̄c̄Pr ∀l :(1 − )(τl − σ) <cdµ < (1 + )(τl + σ) ≥MM0 l!XPr ∀l : (ξi − M ) < lM + σ .i=1È ñíîâà, ýòó âåðîÿòíîñòü ìîæíî îöåíèòü ñ ïîìîùüþ íåðàâåíñòâà58Õàéåêà-Ðåíüè.

l!XPr ∃l : (ξi − M ) ≥ lM + σ ≤i=1D2kXi=11<(iM + σ)2D2.M σ ïîñëåäíåì ïåðåõîäå áûëî èñïîëüçîâàíî íåðàâåíñòâîPk11i=1 αi+β < αβ ïðè α, β > 0. Òàêèì îáðàçîì, ÷òîáû ëåììû 2.1è 2.2 âûïîëíÿëèñü äëÿ ñ âåðîÿòíîñòüþ p äîñòàòî÷íî âçÿòü σ èçðàâåíñòâà(2.8)2.2D2σ(, p) =M pÀäàïòèâíûé ìåòîä îñíîâàííûé íàðàíäîìèçèðîâàííîé ñòîõàñòè÷åñêîéàïïðîêñèìàöèè ýòîì ðàçäåëå îïèñûâàåòñÿ ðàñïðåäåëåííûé àëãîðèòì ðåøåíèÿ çàäà÷è î ìàêñèìàëüíûì ïîòîêå.

Òàêîé àëãîðèòì èìååò åñòåñòâåííóþ ðåàëèçàöèþ â ìóëüòèàãåíòíûõ ñèñòåìàõ. Çà îñíîâó âçÿò ìåòîä áàëàíñèðîâàíèÿäóã, îïèñàííûé â [102]. Îêàçûâàåòñÿ, ýòîò ìåòîä ìîæíî ñôîðìóëèðîâàòüâ òåðìèíàõ ïðîåêòèâíûé ãðàäèåíòíîãî ñïóñêà [21].  ðàìêàõ ýòîé ðàáîòûáóäóò èññëåäîâàíû äâå âàðèàöèè ìåòîäà: ñèíõðîííûé (îáû÷íûé ïðîåêòèâíûé ãðàäèåíòíûé ñïóñê) è ðàíäîìèçèðîâàííûé àñèíõðîííûé (ñïåöèàëüíûé âèä ðàíäîìèçèðîâàííîãî àëãîðèòìà ñòîõàñòè÷åñêîé àïïðîêñèìàöèè [15]). Âòîðîé âàðèàíò áîëüøå ïîõîäèò íà ìåòîä, îïèñàííûé â [102] ñòîé ëèøü ðàçíèöåé, ÷òî èñïîëüçóåòñÿ ñëó÷àéíûé âûáîð äóã. Ðåçóëüòàòûýòîãî ðàçäåëà îïóáëèêîâàíû â [25].59Âàæíî îòìåòèòü, ÷òî ðåçóëüòàòû ýòîãî ðàçäåëà òàêæå îáîáùàþò èäåèïðîåêòèâíîãî ãðàäèåíòíîãî ñïóñêà [21], ðàíäîìèçèðîâàííîãî àëãîðèòìàñòîõàñòè÷åñêîé àïïðîêñèìàöèè [15, 71], àëãîðèòìîâ ñïëåòåí [51] è ïðîòîêîëîâ êîíñåíñóñà [59,91].

Ïî ñðàâíåíèþ ñ êëàññè÷åñêèìè ðåçóëüòàòàìèäëÿ ïðîåêòèâíîãî ãðàäèåíòíîãî ñïóñêà ïîëó÷åíà ýêñïîíåíöèàëüíàÿ ñêîðîñòü ñõîäèìîñòè äëÿ êâàäðàòè÷íîé ôóíêöèè, íå ÿâëÿþùåéñÿ ñèëüíîâûïóêëîé. Ïî ñðàâíåíèþ ñ ðàíäîìèçèðîâàííûìè àëãîðèòìàìè ñòîõàñòè÷åñêîé àïïðîêñèìàöèè, ðàññìàòðèâàåìûõ â [15], â ýòîé ðàáîòå ðåøàåòñÿçàäà÷à ñ îãðàíè÷åíèÿìè â âèäå íåðàâåíñòâ. Àëãîðèòìû êîíñåíñóñà ïîîáùåìó ñòèëþ ñõîæè ñ ñèíõðîííîé âåðñèåé ðàçðàáîòàííîãî àëãîðèòìà,à àëãîðèòìû ñïëåòåí ñõîæè ñ ðàíäîìèçèðîâàííîé âåðñèåé.

Ñâÿçü ìåæäóðàçðàáîòàííûìè ìåòîäàìè àëãîðèòìàìè ñïëåòåí, ïðîòîêîëàìè êîíñåíñóñà ñîñòîèò â ñëåäóþùåì: êîíñåíñóñ è ñïëåòíè ìèíèìèçèðóþò ôóíêöèîíàë yT BB T y, â òî âðåìÿ êàê ðàçðàáîòàííûé àëãîðèòì ìèíèìèçèðóåòôóíêöèîíàë xT B T Bx (â îáîèõ ñëó÷àÿõ B ìàòðèöà èíöèäåíòíîñòè íåêîòîðîãî ãðàôà). Êëþ÷åâûì ðàçëè÷èåì ÿâëÿåòñÿ íàëè÷èå äîïîëíèòåëüíûõ îãðàíè÷åíèé â çàäà÷å, çàäàííûõ íåðàâåíñòâàìè. Ëåììà 2.6 ÿâëÿåòñÿêëþ÷åâîé äëÿ ïîëó÷åíèÿ îöåíîê ñõîäèìîñòè, àíàëîãè÷íûõ [51, 91].Ïðåäïîëàãàåòñÿ, ÷òî çàäàí íåêîòîðûé îðèåíòèðîâàííûé ãðàô G =hV, Ei ñ âûäåëåííûìè âåðøèíàìè èñòîêà s è ñòîêà t. Òðàäèöèîííî çàäà÷à î ìàêñèìàëüíîì ïîòîêå ñòàâèòñÿ â ñëåäóþùåì âèäå:(2.9)PPìàêñèìèçèðîâàòü val(x) = e∈in(t) xe − e∈out(t) xe ,(PPx−ee∈in(i)e∈out(i) xe = 0, i ∈ V, i 6= s, t,ïðè óñëîâèè0 ≤ xe ≤ ce ,ãäå ïåðåìåííûìè ÿâëÿþòñÿ âåëè÷èíû ïîòîêà ïî äóãàì x1 , . .

. , xm (çäåñüè äàëåå x = (x1 , . . . , xm )T ), in(i) ìíîæåñòâî âõîäÿùèõ â i äóã, out(i) ìíîæåñòâî äóã, âûõîäÿùèõ èç i. Ïåðâîå óñëîâèå îçíà÷àåò, ÷òî ïîòîê íåçàäåðæèâàåòñÿ â ïðîìåæóòî÷íûõ âåðøèíàõ. Åäèíñòâåííûå äâå âåðøèíûñ íåîòðèöàòåëüíîé ðàçíîñòüþ âõîäÿùèõ / èñõîäÿùèõ ïîòîêîâ s è t.60Áîëåå òîãî,Xe∈in(t)xe −Xe∈out(t)xe = − Xe∈in(s)xe −Xxe  .e∈out(s)Çàäà÷ó (2.9) ìîæíî çàïèñàòü â áîëåå êîìïàêòíîé ôîðìå èñïîëüçóÿ ìàòðèöó èíöèäåíòíîñòè B : 1, e âûõîäèò èç i,Bie =−1, e âõîäèò â i,0â îñòàëüíûõ ñëó÷àÿõststÎáîçíà÷èâ âåêòîð χst : χsts = −1, χt = 1, χi = 0, i 6= s, t çàäà÷à (2.9)ïåðåïèñûâàåòñÿ â âèäåìàêñèìèçèðîâàòüïðè óñëîâèè2.2.1v,(Bx = vχst ,0 ≤ xe ≤ ce ,Îáùàÿ ñõåìà ìåòîäà áàëàíñèðîâàíèÿ äóãÌåòîä áàëàíñèðîâàíèÿ äóã ñîñòîèò èç èíèöèàëèçàöèè è ïîñëåäîâàòåëüíîì ïðèìåíåíèè íåêîòîðûõ ëîêàëüíûõ èçìåíåíèé ïîòîêà:FunctionforInitialize(G, c)(i, j) ∈ E doif i = s èëè j = txij ← cij ;thenxij ← 0;return x;Âåëè÷èíó [Bx]i =Px−ee∈in(i)e∈out(i) xe îáû÷íî ïðèíÿòî íàçûâàòüèçáûòêîì âåðøèíû i.