常見數(shù)學模型-8網(wǎng)絡流

網(wǎng)絡流(Network

Flow)問題定義1設G=(V,E

)為有向圖,在V中指定一點稱為發(fā)點(源,Source)(記為vs),和另一點稱為收點(匯,Sink)(記為vt),其余點叫做中間點.對每一條邊vivj∈E,對應一個非負實數(shù)Cij

,稱為它的容量(Capacity).這樣的G稱為容量網(wǎng)絡,簡稱網(wǎng)絡,記作G

=(V,E,C

).定義2網(wǎng)絡G

=(V,E,C

)中任一條邊vivj有流量

fij

,稱集合f

={fij}為網(wǎng)絡G上的一個流(Flow).稱為可行流(Feasiblesv2v4t8/130/10滿足下述條件的流fFlow)

：①(限制條件)對每一邊vivj

,有0≤fij

≤Cij

;4/97/7②

(平衡條件)對于中間點vk有∑fik

=∑fkj

,即中間點vk的輸入量=輸出量.12/12v1

v311/16

15/20f(u,v)/c(u,v)1/44/4如果f

是可行流,則對收、發(fā)點vt、vs有∑fsi

=∑fjt

=Wf

,即從vs點發(fā)出的物質(zhì)總量=vt點輸入的量.Wf稱為網(wǎng)絡流f

的總流量.上述概念可以這樣來理解,如G是一個

網(wǎng)絡,則發(fā)點vs表示發(fā)送站,收點vt表示接收站,中間點vk表示中間轉(zhuǎn)運站,可行流

fij

表示某條

線上通過的

量,容量Cij表示某條

線能承擔的最大

量,Wf

表示

總量.可行流總是存在的.比如所有邊的流量fij

=0就是一個可行流(稱為零流).所謂最大流( um

Flow)問題就是在容量網(wǎng)絡中,尋找流量最大的可行流.求最大可行流的算法.實際問題中,一個網(wǎng)絡會出現(xiàn)下面兩種情況：⑴發(fā)點和收點都不止一個.解決的方法是再虛設一個發(fā)點vs和一個收點

vt,發(fā)點vs到所有點邊的容量都設為無窮大,所有原收點到收點vt

邊的容量都設為無窮大.⑵網(wǎng)絡中除了邊有容量外,點也有容量.解決的方法是將所有有容量的點分成兩個點,如點v有容量Cv

,將點v分成兩個點v'和v",令C(v'v"

)

=Cv

.求最大流的方法增量網(wǎng)絡——根據(jù)原網(wǎng)絡的每條弧變作一條順向弧和一條逆向弧，且把順向弧的容量定義，逆向弧的容量定義，這樣得到的網(wǎng)絡稱為原網(wǎng)絡G=(V,E,C)關于流f的增量網(wǎng)絡，記為

。為Ci,j

Ci,j

fi,j為Cj

,i

fi,jG'

G(V

,

E,C

)例如：原始網(wǎng)絡G增量網(wǎng)絡G’求網(wǎng)絡最大流的方法：(1)增量網(wǎng)絡與原網(wǎng)絡的關系增量網(wǎng)絡的順向弧的數(shù)表示原網(wǎng)絡對應弧上最大可增加的流量。增量網(wǎng)絡的逆向弧的數(shù)表示原網(wǎng)絡對應弧上最大可減少的流量。若在增量網(wǎng)絡中能找到從s到t的一條路P，且每條弧容量為正數(shù)，則稱P為f

的增廣鏈。令：

則δ>0，稱為增廣量。對原網(wǎng)絡的流f作如下調(diào)整：（7.1）則

是新的可行流則f

對應的流已是最大流。，若增量網(wǎng)絡中不存在增廣鏈，v1v3v2v4t11/16s流量/容量7/130/101/412/1210/144/97/715/203/4v1v3v2v4t5s61131257增量網(wǎng)絡4增廣鏈流網(wǎng)絡(2)思路①以零流f

=0作初始可行流;②作增量網(wǎng)絡N(f);③尋找增廣鏈P（用類似Dijkstra的方法）。若無，則結(jié)束；④令

；⑤按下式調(diào)整流量，得新流f

；⑥轉(zhuǎn)②。sv4v2v3v1t420(1)12sv4v2v3v1t4/161310

44/974/144/4204/12(2)sv4v2v3v1t4/161310

44/974/144/4204/12(2)(3)sv4v2v3v1t1210484(3)sv4v2v3v1t12104844sv4v2v3v1t11/16137/1044/97/711/144/47/204/12(4)sv4v2v3v1t11/16137/1044/97/711/144/47/204/12(4)(5)sv4v2v3v1t511744311(5)sv4v2v3v1t511744311sv4v2v3v1t11/168/1310

1/44/97/711/144/415/2012/12(6)sv4v2v3v1t11/168/1310

1/44/97/711/144/415/2012/12(6)(7)sv4v2v3v1t513335127451115354(7)sv4v2v3v1t51333512745111554311sv4v2v3v1t11/1612/1310

1/497/711/144/419/2012/12(8)sv4v2v3v1t11/1612/1310

1/497/711/144/419/2012/12(8)sv4v2v3v1t512113912741(9)111931sv2

v4v3v1t512113912741(9)111931sv4v2v

v1

3t12/1310

1/497/711/144/411/16

19/20因無增廣路，故最大流如下所示：12/12(10)Ford-Fulkerson

標號法這種方法分為以下兩個過程：A.標號過程：通過標號過程尋找一條可增廣軌。

B.增流過程：沿著可增廣軌增加網(wǎng)絡的流量。

這兩個過程的步驟分述如下。C.標號過程：給發(fā)點標號為(s

,)。若頂點x

已經(jīng)標號，則對x

的所有未標號的鄰接頂點y

按以下規(guī)則標號：①若(x,y)

A

，且fxy

uxy

時，令

y

min{uxy

fxy

,

x

}，則給頂點

y

標號為(x

,

)

，若

f

u

，則不給頂點

y

標號。y

xy

xy②

(

y,

x)

A

，且

f

0

，令

min{

f

,

}

，則給

y

標號為(x

,

)

，若

f

0

，則不給y

標號。yx

y

yx

x

y

yx（iii）不斷地重復步驟（ii）直到收點t

被標號，或不再有頂點可以標號為止。當t

被標號時，表明存在一條從s

到t

的可增廣軌，則轉(zhuǎn)向增流過程（B）。如若t

點不能被標號，且不存在其它可以標號的頂點時，表明不存在從s

到t

的可增廣軌，算法結(jié)束，此時所獲得的流就是最大流。增流過程令u

t

。ii.若u

的標號為(v

,

），則f

f

；若u

的標號為(v

,

)

，則

f

f

。t

vu

vu

t

t

uv

uv

tiii.若u

s

，把全部標號去掉，并回到標號過程（A）。否則，令u

v

，并回到增流過程（ii）。求網(wǎng)絡N

(s,t,V

,A,U

)中的最大流x

的算法的程序設計具體步驟如下：對每個節(jié)點j

，其標號包括兩部分信息(pred(j),

maxf(j))該節(jié)點在可能的增廣路中的前一個節(jié)點pred(

j)，以及沿該可能的增廣路到該節(jié)點為止可以增廣的最大流量max

f(j)。STEP0

置初始可行流x

（如零流）；對節(jié)點t

標號，即令max

f(t)=任意正值（如1）。STEP1

若maxf(j)

0

，繼續(xù)下一步；否則停止，已經(jīng)得到最大流，結(jié)束。STEP2

取消所有節(jié)點j

V

的標號，即令maxf(j)

0

，pred(

j)

0

；令LIST={s

}，對節(jié)點s

標號，即令maxf(s)

充分大的正值。STEP3

如果LIST

且maxf(t)0

，繼續(xù)下一步；否則：（3a）如果t

已經(jīng)有標號（即max

f(t)

0

），則找到了一條增廣路，沿該增廣路對流x

進行增廣（增廣的流量為maxf(t)，增廣路可以根據(jù)pred

回溯方便地得到），轉(zhuǎn)STEP1。（3b）如果t

沒有標號（即LIST=

且maxf(t)

0

），轉(zhuǎn)STEP1。STEP4

從LIST

中移走一個節(jié)點i

；尋找從節(jié)點i

出發(fā)的所有可能的增廣?。海?a）對非飽和前向弧(i,j)，若節(jié)點j

沒有標號（即pred(

j)

0

），對j

進行標號，即令max

f(j)

min{max

f(i),uij

xij

}，pred(

j)

i

，并將j

加入LIST

中。（4b）對非空后向弧(j,i)，若節(jié)點j

沒有標號（即pred(

j)

0

），對j

進行標號，即令max

f(j)

min{maxf(i),xij

}，pred(

j)

i

，并將j

加入LIST

中。最小費用流問題這里

要進一步探討不僅要使網(wǎng)上的流達到最大,或者達到要求的預定值,而且還要使流的費用是最小的,這就是最小費用流問題.最小費用流問題的一般提法：已知網(wǎng)絡G=(V,E,C),每條邊vivj∈E除了已給容量Cij外,還給出了單位流量的費用bij(≥0).所謂最小費用流問題就是求一個總流量已知的可行流f

={f

ij

}使得總費用b(

f

)

bij

fijviv

j

E最小.特別地,當要求f為最大流時,此問題即為最小費用最大流問題.設網(wǎng)絡G

=(V,E,C),取初始可行流f

為零流,求解最小費用流問題的迭代步驟：①構(gòu)造有向賦權(quán)圖Gf

=(V,Ef

,F),對于任意的vivj∈E,Ef

,F

的定義如下：當f

ij

=0時,vivj∈Ef

,F(vivj

)=bij

;當f

ij

=Cij時,vjvi∈Ef

,F(vjvi

)=-bij

;當0＜f

ij＜Cij時,vivj∈Ef

,F(vivj

)=bij

,vjvi∈Ef

,F(vjvi

)

=

-

bij

.然后轉(zhuǎn)向②.②求出含有負權(quán)的有向賦權(quán)圖Gf

=(V,Ef

,F)中發(fā)點vs到收點vt的最短路

,若最短路

存在轉(zhuǎn)向③;

否則f是所求的最小費用最大流,停止.③增流.

ij

f

,i

jij

ij

i

j

f

,

v

v

,Ciji

jv

v

與相同,i

jv

v

.v

v

與相反.令

=min

{ij|vivj∈

},重新定義流f

={f

ij}為

fij

fij

,

viv