Диссертация (1149954), страница 6
Текст из файла (страница 6)
Íî óäîáíåå íå ðàññìàòðèâàòü çàòðàòû íà îáñëóæèâàíèå ëîêàëüíûõïðîöåññîâ, à ñâåñòè èõ ê çàòðàòàì íà îáñëóæèâàíèå ïîòîêîâ. Ýòî ëåãêî ñäåëàòü, åñàääèòèâíî çàâèñèò îò âåëè÷èí âõîäÿùèõ âlïîòîêîâ. Åñëè æå çàâèñèìîñòüíåàääèòèâíàÿ, ìîæíî äîáàâèòü èêòèâíóþ âåðøèíól′è äóãóëèpl (sl )ñëóæèâàíèÿ1.2.2p(l,l′ ) = pl ,(l, l′ )ñî ñòîèìîñòüþ îá-à âñå äóãè, èñõîäÿùèå èç l , ïåðåêëþ÷èòü íàl′ .Îáùàÿ ïîñòàíîâêà çàäà÷è íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà âñåòè ñ óñèëåíèÿìè â âåðøèíàõÎïðåäåëåíèå 9.
Ñåòü ñ îáîáùåííûìè ïîòîêàìèìàN = ((L, M, s, e), F, {Sl }l∈L , {Ui }i∈L , c, g, v)• (L, M, s, e)••FÑîñòîÿíèåf (m)êàæäîé äóãèmRn );ïðèíèìàåò çíà÷åíèÿ èçUm = [0; cm ] ⊂ F ,ãäåcm ∈ F(êîòîðàÿ ìîæåò áûòü è áåñêîíå÷íîé); äîïóñòèìûå èçëèøêè â âåðøèíàõ;• gi : F | e−1 (i)| → F•Sl ñîâïàäàþò ñ ÷àñòè÷íî ïðåäóïîðÿäî÷åííîé àáåëåâîé(íàïðèìåð, âåêòîðíûì ïðîñòðàíñòâîìïðîïóñêíàÿ ñïîñîáíîñòü• vi : L → Fâ äèñêðåòíîì ïðîñòðàíñòâå, â êîòîðîé: ìóëüòèãðà;Âñå ìíîæåñòâà ñîñòîÿíèé âåðøèíãðóïïîé ýòî ñòàòè÷åñêàÿ ðàñïðåäåëåííàÿ ñèñòå- óíêöèÿ óñèëåíèÿ, çàäàííàÿ â êàæäîé âåðøèíå; îòñóòñòâèå âõîäíûõ âîçäåéñòâèé ñîñòîÿíèåðûõ ïðåäåëàõ îò 0 äîsi âåðøèíû i ìîæíî âàðüèðîâàòü â íåêîòî-vi , à ïðè íàëè÷èè âõîäíûõ âîçäåéñòâèé ýòîò èçëèøåê äîáàâëÿåòñÿ24ê ñîñòîÿíèþ âåðøèíû, ïîðîæäåííîìó èç ñîñòîÿíèé âõîäíûõ äóã ïðåîáðàçîâàíèåìgi ,òî åñòüSi (f ) = (−∞; gi ({f (m)}e(m)=i ) + vi ];•Êàæäàÿ âåðøèíàñîñòîÿíèé äóã1.iïðèíàäëåæèò ê îäíîìó èç äâóõ âèäîâ, â çàâèñèìîñòè îò ìíîæåñòâàUi (si ),âûõîäÿùèõ èç ýòîé âåðøèíû:àñïðåäåëèòåëü :YUi (si ) =s(m)=i[0; c(m)] ∩ {(f1 , .
. . , fk ) | f1 + · · · + fk ≤ si },òî åñòü ïîòîê ìîæíî ïðîèçâîëüíûì îáðàçîì ðàñïðåäåëèòü ìåæäó äóãàìè;2.àçìíîæèòåëü :YUi (si ) =s(m)=i[0; c(m)] ∩ {(si , si , . . . , si )},òî åñòü îäèí è òîò æå ïîòîê òèðàæèðóåòñÿ (ðàçìíîæàåòñÿ) ïî âñåì äóãàì.Îïðåäåëåíèå 10.
Îáîáùåííûé ïñåâäîïîòîê â ñåòè((sl )l∈L , (um)m∈M )òîåñòüèçëèøåêñòîêîìýòîïñåâäîïîòîê,ïðèíèìàåò[gi ({f (m)}e(m)=i ); gi ({f (m)}e(m)=i ) + vi ]âàåìîéf =ñåòè ñ îáîáùåííûìè ïîòîêàìè.Îáîáùåííûé ïîòîê â ñåòèâåðøèíû, ýòî äîïóñòèìîå ñîñòîÿíèåòîëüêîóêîòîðîãîñîñòîÿíèåíåîòðèöàòåëüíûåêàæäîéçíà÷åíèÿ:äëÿ âñåõ âåðøèí, êðîìå îäíîé âåðøèíûs′′ ∈ L,si∈íàçû-(äëÿ ñòîêà âûïîëíÿåòñÿ óñëîâèå ïñåâäîïîòîêà).Ìíîæåñòâî ïîòîêîâ áóäåì îáîçíà÷àòüðèâàþòñÿ ñëåäóþùèå òèïû óíêöèègFs′′ (N),ïñåâäîïîòîêîâ F ′ (N). ðàáîòå ðàññìàò- ïðåîáðàçîâàòåëÿ âõîäíûõ ñèãíàëîâ â ñîñòîÿíèÿâåðøèíû:1.Ñóììàòîð : gi (x1 , . . . , xk ) = x1 + · · · + xk ;2.Ñóììàòîð-óñèëèòåëü : gi (x1 , . . .
, xk ) = a1 x1 + · · · + ak xk ,P3.èF ìîäóëü íàä êîëüöîìai ∈ P ;Ñóììàòîð-óñèëèòåëü ñ íåïðåðûâíûìè êóñî÷íî-ëèíåéíûìè (ÍÊË) óñèëåíèÿìè â äóãàõ : gi (x1 , . . . , xk ) = gi1 (x1 ) + · · · + gik (xk ),4.åñëèãäågij ÍÊË-óíêöèè;Ñóììàòîð-óñèëèòåëü ñ ÍÊË-óñèëåíèÿìè â âåðøèíàõâîëüíàÿ ÍÊË-óíêöèÿgi (x1 , . . . , xk ).(ñàìûé îáùèé ñëó÷àé): ïðîèç-25Îïðåäåëåíèå 11.Ïóñòü çàäàíî óïîðÿäî÷åííîå ïîëîæèòåëüíîå ïîëóêîëüöî çíà÷åíèéè äëÿ êàæäîé äóãèn ∈ M óíêöèÿ ñòîèìîñòè(ïñåâäî)ïîòîêà ìèíèìàëüíîé ñòîèìîñòèRpm : F → R.
Çàäà÷à íàõîæäåíèÿ çàäà÷à íàõîæäåíèÿ (ïñåâäî)ïîòîêà â ñåòè ñâåðøèíàìè ñóììàòîðàìè ñ óñèëåíèåì-ðàçìíîæèòåëÿìè è ñóììàòîðàìè ñ óñèëåíèåìðàñïðåäåëèòåëÿìè, êîòîðûé ìèíèìèçèðóåò çíà÷åíèå ñóììûmin(s,f )∈Fs′′ (N )Xpm (f (m)).m∈M.Çàìå÷àíèå1.2.1. Ôóíêöèè ñòîèìîñòè ìîãóò áûòü êàê âîçðàñòàþùèìè, òàê è óáûâàþùèìè.Óáûâàþùàÿ ñòîèìîñòü â äóãå îçíà÷àåò, ÷òî ïîòîê â äàííîé äóãå ïðèíîñèò äîõîä. Åñëè âñåóíêöèèpmâîçðàñòàþò, òî ðåøåíèåì â áîëüøèíñòâå èíòåðåñíûõ ñëó÷àåâ îêàçûâàåòñÿ íóëå-âîé ïîòîê.Êàê ïîêàçàíî â ðàçäåëå 1.2.3, çàäà÷à íàõîæäåíèÿ îáîáùåííîãî ïîòîêà ìèíèìàëüíîé ñòîèìîñòè äåéñòâèòåëüíî îáîáùàåò êëàññè÷åñêóþ çàäà÷ó íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà âñåòè [61℄.Ïðèìåð 2. [11℄ ðàññìàòðèâàåòñÿ çàäà÷à ìèíèìèçàöèè ñòîèìîñòè ïîòîêà, â êîòîðîé âåð-øèíû äåëÿòñÿ íà 2 ãðóïïû: ðàçìíîæèòåëè ñ îäíèì âõîäîì è ñóììàòîðû-óñèëèòåëè ñ îäíèìâûõîäîì.Çàìå÷àíèåãîâîðÿò î1.2.2.
 ñëó÷àå, êîãäà àáåëåâà ãðóïïà ïîòîêîâìíîãîïðîäóêòîâûõ (k -ïðîäóêòîâûõ)F ýòî ãðóïïà âåêòîðîâF = F ′k ,ïîòîêàõ. ×àñòè÷íûé ïðåäïîðÿäîê íà ýòîéãðóïïå ìîæíî ââåñòè ðàçíûìè ñïîñîáàìè:1. Åñëè ëèíåéíûé ïðåäïîðÿäîê çàäàåòñÿ îðìóëîé(x1 , . . . xk ) ≤ (y1 , . . . yk ) ⇔ x1 + · · · + xk ≤ y1 + · · · + yk(1.3)òî ðå÷ü èäåò î êëàññè÷åñêèõ ìíîãîïðîäóêòîâûõ ïîòîêàõ ïðè èõ ïðîòåêàíèè ÷åðåçäóãó çíà÷åíèÿ ñêëàäûâàþòñÿ.2. Åñëè ÷àñòè÷íûé ïîðÿäîê çàäàåòñÿ ïîýëåìåíòíî:(x1 , . .
. xk ) ≤ (y1 , . . . yk ) ⇔ x1 ≤ y1 , . . . , xk ≤ yk(1.4)òî ýòî íåçàâèñèìûå äðóã îò äðóãà ìíîãîïðîäóêòîâûå ïîòîêè (âïðî÷åì, èõ âçàèìíàÿçàâèñèìîñòü ìîæåò çàäàâàòüñÿ â óíêöèÿõ óñèëåíèÿ).263. Åñëè íà ãðóïïå çàäàí ëèíåéíûé ëåêñèêîãðàè÷åñêèé ïîðÿäîê, òî ýòîëåêñèêîãðàè÷å-ñêèå ïîòîêè.Èòàê, ìû ïîñòàâèëè çàäà÷ó íàõîæäåíèÿ îïòèìàëüíîãî (ïñåâäî)ïîòîêà â ñàìîì îáùåìâèäå.
 äàííîì ðàçäåëå ïîñòðîåíû àëãîðèòìû åå ðåøåíèÿ äëÿ òðåõ ÷àñòíûõ ñëó÷àåâ, êîòîðûåîõâàòûâàþò âñå îñíîâíûå çàäà÷è îïòèìèçàöèè ïîòîêà, âñòðå÷àþùèåñÿ â ëèòåðàòóðå:1.Äèñêðåòíûé ïîòîêè∀m cm < ∞.ïåðåáîðíûé•â ñåòè ñ êîíå÷íûìè ïðîïóñêíûìè ñïîñîáíîñòÿìè äóã. Ò.å. ýòîì ñëó÷àå ìîæíî íàéòè îïòèìàëüíûé ïîòîê, èñïîëüçóÿ ñëåäóþùèéàëãîðèòì:Äëÿ êàæäîé âåðøèíû-ðàçìíîæèòåëÿâåðøèíûslîò 0 äîmins(m)=l c(m).lïåðåáèðàåì âñå âîçìîæíûå ñîñòîÿíèÿ ýòîéÑîñòîÿíèÿ äóã, âûõîäÿùèõ èç âåðøèíû-ðàçìíîæèòåëÿ, ñîâïàäàþò ñ ñîñòîÿíèåì âåðøèíû:•Äëÿ êàæäîé âåðøèíû-ðàñïðåäåëèòåëÿèíöèäåíòíûõ åé äóãf (m)s(m)=l∨e(m)=l .lf (m) = ss(m) .ïåðåáèðàåì âñå âîçìîæíûå ñîñòîÿíèÿÑîñòîÿíèå âåðøèíû-ðàñïðåäåëèòåëÿ îä-íîçíà÷íî îïðåäåëÿåòñÿ ñîñòîÿíèÿìè èíöèäåíòíûõ åé äóã:Psl =s(m)=lgi ({f (m)}e(m)=l ).•f (m) −Âûáèðàåì èç âñåõ ïîëó÷åííûõ ïîòîêîâ îïòèìàëüíûé.QÊîëè÷åñòâî ïîòîêîâ, êîòîðûå íàäî ïåðåáðàòü ïîðÿäêàL′F = Zk+ ìíîæåñòâî âåðøèí-ðàçìíîæèòåëåé,ðàñïðåäåëèòåëåé, àM′l∈L′|vl | ·Qm∈M ′àëüíûì ïî ðàçìåðó ãðàà:m′O(V C ),ãäåVãäå ìíîæåñòâî äóã, âûõîäÿùèõ èç âåðøèí-|(x1 , .
. . , xk )| = x1 x2 . . . xk . Âðåìÿ ïåðåáîðà îêàçûâàåòñÿn′|c(m)|,ýêñïîíåíöè- ìàêñèìàëüíûé èçëèøåê â âåðøèíå,C ìàêñèìàëüíàÿ ïðîïóñêíàÿ ñïîñîáíîñòü äóãè. íåêîòîðûõ ñëó÷àÿõ, êîíå÷íî, äèñêðåòíûå ïîòîêè ìîæíî íàéòè áîëåå ïðîñòûìèàëãîðèòìàìè. Äèñêðåòíûé ïîòîê ìèíèìàëüíîé ñòîèìîñòè â ñåòè ñ ñóììàòîðàìèðàñïðåäåëèòåëÿìè ìîæíî íàéòè àëãîðèòìîì Ôîðäà-Ôàëêåðñîíà [34℄, à íàõîæäåíèå äèñêðåòíîãî ïîòîêà ìèíèìàëüíîé ñòîèìîñòè â ñåòè ñ ñóììàòîðàìè-óñèëèòåëÿìè ýòî çàäà÷à öåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ [63℄.2.
ÏóñòüF = Rk ,ãäåR óïîðÿäî÷åííîå ïîëå, ïîðÿäîê íàèëè (1.4), à óíêöèè óñèëåíèÿgmFè óíêöèè ñòîèìîñòèçàäàåòñÿ ïî îðìóëàì (1.3)pm íåïðåðûâíûå êóñî÷íî-ëèíåéíûå. Òîãäà, î÷åâèäíî, çàäà÷à íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà â ñåòè ñ íåïðåðûâíûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè è ñòîèìîñòÿìè ýòî çàäà÷à ìèíèìèçàöèè íåïðåðûâíîé êóñî÷íî-ëèíåéíîé óíêöèè íà ïðîèçâåäåíèè ìíîãîãðàííûõ ìíîæåñòâ. Ñëåäîâàòåëüíî, îíà ñâîäèòñÿ â çàäà÷å êóñî÷íî-ëèíåéíîãî ïðîãðàììèðîâàíèÿ. Ýòà çàäà÷à ðå-27èñ. 1.1:øàåòñÿ ïîëóïåðåáîðíûì àëãîðèòìîì, â êîòîðîì ïîñëåäîâàòåëüíî ïåðåáèðàþòñÿ çàäà÷èëèíåéíîãî ïðîãðàììèðîâàíèÿ [21℄ êàæäóþ èç íèõ ìîæíî ðåøèòü ñèìïëåêñ-ìåòîäîì.3. Ïóñòü òåïåðü óíêöèè óñèëåíèÿñòèpmgm âîãíóòûå êóñî÷íî-ëèíåéíûå, à óíêöèè ñòîèìî- âûïóêëûå êóñî÷íî-ëèíåéíûå (ïîäñëó÷àé ñëó÷àÿ 2).
Òîãäà çàäà÷à íàõîæäåíèÿïîòîêà ìèíèìàëüíîé ñòîèìîñòè ýòî çàäà÷à ìèíèìèçàöèè âûïóêëîé êóñî÷íî-ëèíåéíîéóíêöèè íà ïðîèçâåäåíèè âûïóêëûõ ìíîãîãðàííûõ ìíîæåñòâ. Ñëåäîâàòåëüíî, îíà ñâîäèòñÿ ê çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ, êîòîðóþ äàëåå ìîæíî ðåøèòü ñèìïëåêñìåòîäîì.Âåðíî è îáðàòíîå: ëþáóþ çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ ìîæíî, êàê èçâåñòíî,ñâåñòè ê çàäà÷å íàõîæäåíèÿ ñåäëîâîé òî÷êè â ìàòðè÷íîé èãðåmaxx1 ,...xn ≥0, x1 +···+xn =1min(a1 · x, a2 · x, .
. . am · x)(1.5)à ýòà çàäà÷à ýêâèâàëåíòíà ìàêñèìèçàöèè ïîòîêà â ñåòè, èçîáðàæåííîé íà ðèñ. 1.1.Çäåñü ïðîïóñêíûå ñïîñîáíîñòè âñåõ äóã áåñêîíå÷íû. Ïîòîê ìîùíîñòèíèêà ïî äóãàì â êîëè÷åñòâåâåðøèíàìèäåò èç èñòî÷-x1 , . . . xn , çàòåì â âåðøèíàõ A1 , . . . An ïåðåðàñïðåäåëÿåòñÿ ïîB1 , . . . Bn , äîìíîæàÿñü â äóãå (Ai , Bj ) íà êîýèöèåíò aij , çàòåì ñêàïëèâàåò-ñÿ â âåðøèíàõîïåðàöèÿ1min.B1 , . . .
Bm ,ïîñëå ÷åãî â ñòîêå íàä ïðèõîäÿùèìè ïîòîêàìè ïðîèçâîäèòñÿÏîëó÷àåì çàäà÷ómaxx1 ,...xn ≥0x1 +···+xn =1x1 1,...xmn ≥0x11 +···+x1n ≤x1...mx1 +···+xmn ≤xmmin(a1 · x1 + a2 · x2 + . . . am · xm )28êîòîðàÿ, êàê íåñëîæíî äîêàçàòü, ýêâèâàëåíòíà çàäà÷å (1.5). Òàêèì îáðàçîì, çàäà÷à ìàêñèìèçàöèè ïîòîêà â ñåòè äàæå ñ ïðîñòåéøèìè âîãíóòûìè êóñî÷íî-ëèíåéíûìè óíêöèÿìè óñèëåíèÿ â âåðøèíàõ ýêâèâàëåíòíà îáùåé çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ èóïðîùåíèþ íå ïîääàåòñÿ.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
