數(shù)學建模-網(wǎng)絡最大流問題

1.7網(wǎng)絡最大流問題本節(jié)內容的安排基本概念與基本定理尋求最大流的標號法1.應用背景在許多實際的網(wǎng)絡系統(tǒng)中都存在著流量和最大流問題。例如鐵路運輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題,控制系統(tǒng)中的信息流問題，常見的人流，物流，水流，氣流，電流，現(xiàn)金流等。在一定條件下,求解給定系統(tǒng)的最大流量,就是網(wǎng)絡最大流問題.網(wǎng)絡系統(tǒng)最大流問題是圖與網(wǎng)絡理論中十分重要的最優(yōu)化問題，它對于解決生產(chǎn)實際問題起著十分重要的作用。一

引言2.問題描述 連通網(wǎng)絡G(V,A)中有m個節(jié)點,n條弧,弧eij上的流量上界為cij,求從起始節(jié)點vs到終點vt的最大流量的問題就是最大流問題。3.引例

連接某產(chǎn)品產(chǎn)地v1和銷地v6的交通網(wǎng)如下：v2v5348v3v1v4v65106111735（a）?。╲i，vj）：從vi到vj的運輸線，弧旁數(shù)字：這條運輸線的最大通過能力—容量。v2v5313v3v1v4v61563222（b）制定一個運輸方案，使從v1運到v6的產(chǎn)品數(shù)量最多?；∨詳?shù)字：運輸數(shù)量—流量。問題：這個運輸網(wǎng)絡中，從v1到v6的最大輸送量是多少？1、網(wǎng)絡與流設一個賦權有向圖D=（V,A）,在V中指定一個發(fā)點vs和一個收點vt

,其它的點叫做中間點。對于D中的每一個?。╲i

,vj）∈A,都有一個非負數(shù)cij,叫做弧的容量。我們把這樣的圖D叫做一個容量網(wǎng)絡，簡稱網(wǎng)絡，記做D=（V，A，C）?；〉娜萘浚菏菍W(wǎng)絡上的每條弧(vi,vj)都給出一個最大的通過能力，記為c(vi,vj)或簡寫為cij。二、基本概念sts’t’對有多個發(fā)點和多個收點的網(wǎng)絡,可以另外虛設一個總發(fā)點和一個總收點,并將其分別與各發(fā)點、收點連起來（見圖），就可以轉換為只含一個發(fā)點和一個收點的網(wǎng)絡。所以一般只研究具有一個發(fā)點和一個收點的網(wǎng)絡流：加在網(wǎng)絡各條弧上的一組負載量f(vi,vj)：加在弧(vi,vj)上的負載量簡記為fij，為非負數(shù)網(wǎng)絡上的流：是指定義在弧集合上的一個函數(shù)f={f(vi,vj)},其中f(vi,vj)稱為?。╲i,vj)上的流量，流也可看作一個雙下標變量弧的流量f(vi,vj)：表示弧(vi,vj)上每單位時間內的實際通過能力弧的容量c(vi,vj)：表示?。╲i,vj)上每單位時間內的最大通過能力零流：網(wǎng)絡上所有的fij

=0圖10-24表示的就是這個網(wǎng)絡上的一個流（運輸方案），每一個弧上的流量fij就是運輸量。例如：f12=1,f13=2,f24=3等等。v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt圖10-24v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt對于實際的網(wǎng)絡系統(tǒng)上的流，有幾個顯著的特點：(1)發(fā)點的凈流出量和收點的凈流入量必相等。(2)每一個中間點的流入量與流出量的代數(shù)和等于零。(3)每一個弧上的流量不能超過它的最大通過能力（即容量）稱滿足下列條件的流為可行流：（1）容量限制條件：對于每一個?。╲i,vj）∈A

有0f(vi,vj)c(vi,vj)

（簡記為0fij

cij）2、可行流與最大流（2）平衡條件：①對于發(fā)點vs，有②對于收點vt

，有式子中V(f)稱為可行流f的流量,即發(fā)點的凈輸出量（或收點的凈輸入量）。③對于中間點:流入量=流出量。即對每個i(i≠s,t)有f(vi,vj)-f(vj,vi)=0(is，t)(簡記為fij-fji=0(is，t))

即總流量=發(fā)點的凈輸出量=收點的凈輸入量容量網(wǎng)絡的可行流總是存在的，如當所有弧的流均取零，即對所有的i,j,有f(vi,vj)=0就是一個可行流可行流中fij＝cij

的弧叫做飽和弧，fij＜cij的弧叫做非飽和弧。fij＞0

的弧為非零流弧，fij＝0

的弧叫做零流弧。13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)

圖中為零流弧，都是非飽和弧。就是要求一個流{fij},使其流量v(f)達到最大,并且滿足

0fijcij網(wǎng)絡的最大流:求網(wǎng)絡的最大流，即是指滿足容量限制條件和平衡條件的條件下，使v(f)值達到最大.容量網(wǎng)絡D，若μ為網(wǎng)絡中從vs到vt的一條鏈，給μ定向為從vs到vt，μ上的弧分為兩類：凡與μ方向相同的稱為前向弧，凡與μ方向相反的稱為后向弧，其集合分別用μ+和μ-表示。

鏈的方向：若μ是聯(lián)結vs和vt的一條鏈，定義鏈的方向是從vs到vt。3、增廣鏈stf1<c1f4<c4f5<c5f2>0f3>0增廣鏈：f

是一個可行流，如果滿足：即中的每一條弧都是非飽和弧即中的每一條弧都是非零流弧則稱μ為從vs到vt

的關于f的一條增廣鏈。stf1<c1f4<c4f5<c5f2>0f3>0v2v53-34-18-3v3v1v4v65-110-511-66-317-23-25-2μ=(v1,v2,v3,v4,v5,v6)μ+={(v1,v2),(v2,v3),(v3,v4),(v5,v6)}μ-={(v5,v4)}后向弧13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)是一個增廣鏈顯然圖中增廣鏈不止一條

4、截集與截量容量網(wǎng)絡D=（V，A，C），vs為始點，vt為終點。如果把V分成兩個非空集合使，則所有始點屬于V1，而終點屬于的弧的集合稱為是分離vs和vt的截集（或割）v2v53(3)4（1）8(3）v3v1v4v65（1）10（5)11(6)6（30)17(2)3（2）5（2）

=(v1,v2,v3)V11=(v4,v5,v6)

=(v1,v2,v3)V11=(v4,v5,v6)截集為紅色弧集：v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2vsv1v2v4v3vt374556378V1截集中所有弧的容量之和，稱為這個截集的容量，記為，也稱截量，則有：13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設則截集為：截量為2413(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設，則截集為截量為20sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)截集與可行流無關，而只與網(wǎng)絡本身有關最小截量是個定值對應的截量也不相同，其中截量最小的截集稱為最小截集。

設f為網(wǎng)絡D=（V，A，C）的任一可行流，流量為v(f)，為任一截集，則有結論1：由于V與V的分解方法不同，所以截集就不相同即任何一個可行流的流量都不會超過任一截集的容量滿足條件那么f*一定是D上的最大流，而如果網(wǎng)絡上的一個可行流f*,和網(wǎng)絡中的一個截集

一定是D的最小截集。結論2：定理8：可行流f是D的最大流的充分必要條件是不存在從vs到vt

的關于f的一條增廣鏈。在網(wǎng)絡中st的最大流量等于它的最小割集的容量，即定理9最大流最小截量定理：最小截集的容量最大流的流量網(wǎng)絡中可行流的流量網(wǎng)絡割所含弧的流量和割所含弧的容量和弧的流量f(vi,vj)弧的容量c(vi,vj)弧(vi,vj)

定理8為我們提供了一個尋求網(wǎng)絡系統(tǒng)最大流的方法。亦即，如果網(wǎng)絡D中有一個可行流f，只要判斷網(wǎng)絡是否存在關于可行流f的增廣鏈。如果沒有增廣鏈，那么f一定是最大流。如有增廣鏈，那么可以按照定理8中必要性，不斷改進和增大可行流f的流量，最終可以得到網(wǎng)絡中的一個最大流。這種算法由Ford和Fulkerson于1956年提出,故又稱

Ford–Fulkerson標號法；實質：判斷是否存在增廣鏈,并設法把增廣鏈找出來,并予以調整,最終使圖中無增廣鏈.二．尋求最大流的標號法此算法從網(wǎng)絡中的一個可行流f

出發(fā)（如果D中沒有f，可以令f是零流），運用標號法，經(jīng)過標號過程和調整過程，最終可以得到網(wǎng)絡中的一個最大流。下面用給頂點標號的方法來定義定理8中的V1*.在標號過程中，有標號的頂點是V1*中的點，沒有標號的點不是V1*中的點。如果vt有了標號，表示存在一條關于f的增廣鏈。如果標號過程無法進行下去，并且vt未被標號，則表示不存在關于f的增廣鏈。此時，就得到了網(wǎng)絡中的一個最大流和最小截集。在標號過程中，網(wǎng)絡中的點分為兩種：已標號的點（分為已檢查和未檢查）和未標號的點。每個標號點的標號包含兩部分：第一個標號表示這個標號是從那一點得到的，以便找出增廣鏈。第二個標號是從上一個標號點到這個標號點的流量的最大允許調整值，是為了用來確定增廣鏈上的調整量θ。標號過程開始，先給vs標號（0，+∞）。這時，vs是標號未檢查的點，其它都是未標號點。一般地，取一個標號未檢查點vi，對一切未標號點vj1．

標號過程vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)例14

求圖10-25的網(wǎng)絡最大流，弧旁的權數(shù)表示（cij,fij）。

解：

1.標號過程。1）首先給vs標號（0，+∞）

2）看vs:在弧(vs

,v2)上,fs2=cs3=3,不具備標號條件。在弧(vs

,v1)上,fs1=1<cs1=5,

故給v1標號（vs,l(v1)),

其中l(wèi)(v1)=min[l(vs),(cs1–fs1)]=min[+∞,5–1]=4.

v1標號為：（vs,4），此時vs為已檢查的標號點。(vs,4)(0,+)。（3）看v1:在?。╲1

,v3）上,f13=c13=2,不具備標號條件.

在弧(v2

,v1)上,f21=1>0,

故給v2標號（-v1,l(v2)）,

其中l(wèi)(v2)=min[l(v1),f21]=min[4,1]=1.

v2標號（-v1,1），此時v1為已檢查的標號點vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(0,+)(–v1,1)vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(0,+)(vs,4)(–v1,1)(v2,1)(-v2,1)(v3,1)（4）看v2:在?。╲2

,v4）上，f24

=3<c24=4,

故給v4標號（v2,l(v4)）其中l(wèi)(v4)=min[l(v2),(c24–f24)]=min[1,1]=1.

在?。╲3

,v2)上，f32

=1>0,

故給v3標號（-v2，l(v3)),

其中

l(l(v3

)=min[l(v2),f32]=min[1,1]=1。vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(0,+)(vs,4)(–v1,1)(v2,1)(-v2,1)(v3,1)（5）在v3

,v4中任意選一個，比如v3

,在?。╲3,vt）上，f3t

=1<c3t=2,

故給vt標號(v3,l(vt)),

其中l(wèi)(vt)=min[l(v3),(c3t-f3t)]=min[1,1]=1.

因為vt被標上號，根據(jù)標號法，轉入調整過程。

（1）如果在前向?。╲i,vj）上，有fij<cij,那么給vj標號（vi,l(vj)）.其中l(wèi)(vj)=min[l(vi),cij–

fij].

這時，vj成為標號未檢查的點。

（2）如果在后向?。╲j,vi）上，有fji>0,那么給vj標號（-vi,l(vj)）.其中l(wèi)(vj)=min[l(vi),fji].這時，vj成為標號未檢查點。于是vi成為標號已檢查的點。重復以上步驟，如果所有的標號都已經(jīng)檢查過，而標號過程無法進行下去，則標號法結束。這時的可行流就是最大流。但是，如果vt被標上號，表示得到一條增廣鏈μ，轉入下一步調整過程?？偨Y標號過程

2.調整過程

利用反向追蹤找增廣鏈，調整增廣鏈的流量，去掉舊的標號，對新的可行流重新進行標號。具體做法如下：（1）按照vt和其它已檢查的標號點的第一個標號，反向追蹤，找出增廣鏈μ

，確定調整量θ。（2)得新的可行流。

(3)再去掉所有的標號，對新的可行流f’={f’ij},重新進行標號過程，直到找到網(wǎng)絡D的最大流為止。非增廣鏈上的弧vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(5,2)(1,0)(1,0)(2,2)(cij,fij)f*=fs1+θ=1+1=2在μ+上f3t+θ=1+1=2在μ+上f*=f21–θ=1–1=0在μ-上f32

–

θ=1–1=0在μ-上其它的不變增廣鏈的調整量為1，則有：

調整后的可行流f*如圖,再對這個可行流從新進行標號過程，尋找增廣鏈。一直到標號過程無法進行下去，不存在從vS到vt的增廣鏈，算法結束。vsv1v2v3v4vt(3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(cij,fij)vsv1v2v3v4vt(3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(cij,fij)(0,+)(vs,3)最大流的流量v(f*)=fs1+fs2=5.最小截集它的容量也為5.得到的截集為最小截集（V1，），其中V1是標號的集合，是未標號的集合。此時，網(wǎng)絡中的可行流f*即是最大流，sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)(0,)(s,2)(-v2,2)(v1,2)(-v3,1)(v4,1)例:用標號法求下圖中s→t的最大流量,并找出該網(wǎng)絡的最小割.ε(v2)=min{ε(s),(cs2-fs2)}=2ε(v1)=min{ε(v2),f12}=min{2,4}=2ε(v3)=min{ε(v1),(c13-f13)}=min{2,5}=2ε(v4)=min{ε(v3),f43}=min{2,1}=1ε(t)=min{ε(v4),(c4t-f4t)}=min{1,2}=1sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)V*(f)==９＋５－０＝１４sv2v4v3v1t7(6)8(8)9(5)5(3)2(0)9(9)6(0)10(9)5(5)(-v2,1)(0,)(v1,1)(s,1)KK(0+,)(s+,6)(2,6)(3+,1)(4+,1)(0+,)(s+,5)(2+,2)(5,2)(4+,2)例：(0+,)(s+,3)(2,3)最小截集最大流的流量為：14+12+5+4=35例：求下圖所示網(wǎng)絡的最大流vsv1vtv5v4v3v24310413354278解：給定初始可行流為全零流，即f（0）

=0給vs標號（0，+∞），檢查vs：給v1

標號(vs,4),給v2

標號(vs,3),給v3

標號(vs,10),vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(0,+)(vs,4)(vs,3)(vs,10)檢查v1：給v4

標號(v1,1)，檢查完畢；(v1,1)檢查v2：給v5

標號(v2,3)，檢查完畢；vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(v2,3)檢查v5：給vt

標號(v5,3)，檢查完畢；(v5,3)因為終點vt

已標號，故找出一條從vs到vt的增廣鏈μ：vs—

v2—v5—vt.取=3vsv1vtv5v4v3v2（4,0）（10,0）（3,3）（3,0）（3,0）（4,0）（1,0）（2,0）（5,3）（4,0）（7,0）（8,3）vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(vs,4)(v1,3)(vs,10)(v1,1)vsv1vtv5v4v3v2（4,0）（10,0）（3,3）（3,0）（3,0）（4,0）（1,0）（2,0）（5,3）（4,0）（7,0）（8,3）(v2,2)(0,+)(v5,2)vsv1vtv5v4v3v2（4,2）（10,0）（3,3）（3,2）（3,0）（4,0）（1,0）（2,0）（5,5）（4,0）（7,0）（8,5）(vs,2)(v3,3)(vs,10)(v2,3)vsv1vtv5v4v3v2（4,2）（10,0）（3,3）（3,2）（3,0）（4,0）（1,0）（2,0）（5,5）（4,0）（7,0）（8,5）(v3,4)(0,+)(v4,3)vsv1vtv5v4v3v2（4,2）（10,3）（3,3）（3,2）（3,3）（4,0）（1,0）（2,0）（5,5）（4,3）（7,3）（8,5）vsv1vtv5v4v3v2（4,2）（10,3）（3,3）（3,2）（3,3）（4,0）（1,0）（2,0）（5,5）（4,3）（7,3）（8,5）vsv1vtv5v4v3v2（4,2）（10,6）（3,3）（3,2）（3,3）（4,3）（1,0）（2,0）（5,5）（4,3）（7,3）（8,8）(0,+)(vs,2)(vs,7)(v3,4)(v5,2)(v5,3)vsv1vtv5v4v3v2（4,3）（10,6）（3,3）（3,2）（3,3）（4,3）（1,1）（2,0）（5,5）（4,3）（7,4）（8,8）vsv1vtv5v4v3v2（4,2）（10,6）（3,3）（3,2）（3,3）（4,3）（1,0）（2,0）（5,5）（4,3）（7,3）（8,8）(0,+)(vs,2)(vs,