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

網(wǎng)絡(luò)流(Network

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

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

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

=(V,E,C

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

=(V,E,C

)中任一條邊vivj有流量

fij

,稱集合f

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

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

,有0≤fij

≤Cij

;4/97/7②

(平衡條件)對(duì)于中間點(diǎn)vk有∑fik

=∑fkj

,即中間點(diǎn)vk的輸入量=輸出量.12/12v1

v311/16

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

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

=∑fjt

=Wf

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

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

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

fij

表示某條

線上通過的

量,容量Cij表示某條

線能承擔(dān)的最大

量,Wf

表示

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

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

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

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

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

,將點(diǎn)v分成兩個(gè)點(diǎn)v'和v",令C(v'v"

)

=Cv

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

。為Ci,j

Ci,j

fi,j為Cj

,i

fi,jG'

G(V

,

E,C

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

的增廣鏈。令：

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

是新的可行流則f

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

=0作初始可行流;②作增量網(wǎng)絡(luò)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

標(biāo)號(hào)法這種方法分為以下兩個(gè)過程：A.標(biāo)號(hào)過程：通過標(biāo)號(hào)過程尋找一條可增廣軌。

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

這兩個(gè)過程的步驟分述如下。C.標(biāo)號(hào)過程：給發(fā)點(diǎn)標(biāo)號(hào)為(s

,)。若頂點(diǎn)x

已經(jīng)標(biāo)號(hào)，則對(duì)x

的所有未標(biāo)號(hào)的鄰接頂點(diǎn)y

按以下規(guī)則標(biāo)號(hào)：①若(x,y)

A

，且fxy

uxy

時(shí)，令

y

min{uxy

fxy

,

x

}，則給頂點(diǎn)

y

標(biāo)號(hào)為(x

,

)

，若

f

u

，則不給頂點(diǎn)

y

標(biāo)號(hào)。y

xy

xy②

(

y,

x)

A

，且

f

0

，令

min{

f

,

}

，則給

y

標(biāo)號(hào)為(x

,

)

，若

f

0

，則不給y

標(biāo)號(hào)。yx

y

yx

x

y

yx（iii）不斷地重復(fù)步驟（ii）直到收點(diǎn)t

被標(biāo)號(hào)，或不再有頂點(diǎn)可以標(biāo)號(hào)為止。當(dāng)t

被標(biāo)號(hào)時(shí)，表明存在一條從s

到t

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

點(diǎn)不能被標(biāo)號(hào)，且不存在其它可以標(biāo)號(hào)的頂點(diǎn)時(shí)，表明不存在從s

到t

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

t

。ii.若u

的標(biāo)號(hào)為(v

,

），則f

f

；若u

的標(biāo)號(hào)為(v

,

)

，則

f

f

。t

vu

vu

t

t

uv

uv

tiii.若u

s

，把全部標(biāo)號(hào)去掉，并回到標(biāo)號(hào)過程（A）。否則，令u

v

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

(s,t,V

,A,U

)中的最大流x

的算法的程序設(shè)計(jì)具體步驟如下：對(duì)每個(gè)節(jié)點(diǎn)j

，其標(biāo)號(hào)包括兩部分信息(pred(j),

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

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

f(j)。STEP0

置初始可行流x

（如零流）；對(duì)節(jié)點(diǎn)t

標(biāo)號(hào)，即令max

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

若maxf(j)

0

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

取消所有節(jié)點(diǎn)j

V

的標(biāo)號(hào)，即令maxf(j)

0

，pred(

j)

0

；令LIST={s

}，對(duì)節(jié)點(diǎn)s

標(biāo)號(hào)，即令maxf(s)

充分大的正值。STEP3

如果LIST

且maxf(t)0

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

已經(jīng)有標(biāo)號(hào)（即max

f(t)

0

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

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

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

沒有標(biāo)號(hào)（即LIST=

且maxf(t)

0

），轉(zhuǎn)STEP1。STEP4

從LIST

中移走一個(gè)節(jié)點(diǎn)i

；尋找從節(jié)點(diǎn)i

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

沒有標(biāo)號(hào)（即pred(

j)

0

），對(duì)j

進(jìn)行標(biāo)號(hào)，即令max

f(j)

min{max

f(i),uij

xij

}，pred(

j)

i

，并將j

加入LIST

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

沒有標(biāo)號(hào)（即pred(

j)

0

），對(duì)j

進(jìn)行標(biāo)號(hào)，即令max

f(j)

min{maxf(i),xij

}，pred(

j)

i

，并將j

加入LIST

中。最小費(fèi)用流問題這里

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

={f

ij

}使得總費(fèi)用b(

f

)

bij

fijviv

j

E最小.特別地,當(dāng)要求f為最大流時(shí),此問題即為最小費(fèi)用最大流問題.設(shè)網(wǎng)絡(luò)G

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

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

=(V,Ef

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

,F

的定義如下：當(dāng)f

ij

=0時(shí),vivj∈Ef

,F(vivj

)=bij

;當(dāng)f

ij

=Cij時(shí),vjvi∈Ef

,F(vjvi

)=-bij

;當(dāng)0＜f

ij＜Cij時(shí),vivj∈Ef

,F(vivj

)=bij

,vjvi∈Ef

,F(vjvi

)

=

-

bij

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

=(V,Ef

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

,若最短路

存在轉(zhuǎn)向③;

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

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