數(shù)學(xué)建模-網(wǎng)絡(luò)最大流問(wèn)題

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

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

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

,其它的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的每一個(gè)弧（vi

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

=0圖10-24表示的就是這個(gè)網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案），每一個(gè)弧上的流量fij就是運(yùn)輸量。例如：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對(duì)于實(shí)際的網(wǎng)絡(luò)系統(tǒng)上的流，有幾個(gè)顯著的特點(diǎn)：(1)發(fā)點(diǎn)的凈流出量和收點(diǎn)的凈流入量必相等。(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零。(3)每一個(gè)弧上的流量不能超過(guò)它的最大通過(guò)能力（即容量）稱滿足下列條件的流為可行流：（1）容量限制條件：對(duì)于每一個(gè)弧（vi,vj）∈A

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

（簡(jiǎn)記為0fij

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

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

即總流量=發(fā)點(diǎn)的凈輸出量=收點(diǎn)的凈輸入量容量網(wǎng)絡(luò)的可行流總是存在的，如當(dāng)所有弧的流均取零，即對(duì)所有的i,j,有f(vi,vj)=0就是一個(gè)可行流可行流中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)

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

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

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

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

的關(guān)于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)是一個(gè)增廣鏈顯然圖中增廣鏈不止一條

4、截集與截量容量網(wǎng)絡(luò)D=（V，A，C），vs為始點(diǎn)，vt為終點(diǎn)。如果把V分成兩個(gè)非空集合使，則所有始點(diǎn)屬于V1，而終點(diǎn)屬于的弧的集合稱為是分離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截集中所有弧的容量之和，稱為這個(gè)截集的容量，記為，也稱截量，則有：13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設(shè)則截集為：截量為2413(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設(shè)，則截集為截量為20sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)截集與可行流無(wú)關(guān)，而只與網(wǎng)絡(luò)本身有關(guān)最小截量是個(gè)定值對(duì)應(yīng)的截量也不相同，其中截量最小的截集稱為最小截集。

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

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

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

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

Ford–Fulkerson標(biāo)號(hào)法；實(shí)質(zhì)：判斷是否存在增廣鏈,并設(shè)法把增廣鏈找出來(lái),并予以調(diào)整,最終使圖中無(wú)增廣鏈.二．尋求最大流的標(biāo)號(hào)法此算法從網(wǎng)絡(luò)中的一個(gè)可行流f

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

標(biāo)號(hào)過(guò)程vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)例14

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

解：

1.標(biāo)號(hào)過(guò)程。1）首先給vs標(biāo)號(hào)（0，+∞）

2）看vs:在弧(vs

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

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

故給v1標(biāo)號(hào)（vs,l(v1)),

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

v1標(biāo)號(hào)為：（vs,4），此時(shí)vs為已檢查的標(biāo)號(hào)點(diǎn)。(vs,4)(0,+)。（3）看v1:在弧（v1

,v3）上,f13=c13=2,不具備標(biāo)號(hào)條件.

在弧(v2

,v1)上,f21=1>0,

故給v2標(biāo)號(hào)（-v1,l(v2)）,

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

v2標(biāo)號(hào)（-v1,1），此時(shí)v1為已檢查的標(biāo)號(hào)點(diǎn)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標(biāo)號(hào)（v2,l(v4)）其中l(wèi)(v4)=min[l(v2),(c24–f24)]=min[1,1]=1.

在?。╲3

,v2)上，f32

=1>0,

故給v3標(biāo)號(hào)（-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中任意選一個(gè)，比如v3

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

=1<c3t=2,

故給vt標(biāo)號(hào)(v3,l(vt)),

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

因?yàn)関t被標(biāo)上號(hào)，根據(jù)標(biāo)號(hào)法，轉(zhuǎn)入調(diào)整過(guò)程。

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

fij].

這時(shí)，vj成為標(biāo)號(hào)未檢查的點(diǎn)。

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

2.調(diào)整過(guò)程

利用反向追蹤找增廣鏈，調(diào)整增廣鏈的流量，去掉舊的標(biāo)號(hào)，對(duì)新的可行流重新進(jìn)行標(biāo)號(hào)。具體做法如下：（1）按照vt和其它已檢查的標(biāo)號(hào)點(diǎn)的第一個(gè)標(biāo)號(hào)，反向追蹤，找出增廣鏈μ

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

(3)再去掉所有的標(biāo)號(hào)，對(duì)新的可行流f’={f’ij},重新進(jìn)行標(biāo)號(hào)過(guò)程，直到找到網(wǎng)絡(luò)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在μ-上其它的不變?cè)鰪V鏈的調(diào)整量為1，則有：

調(diào)整后的可行流f*如圖,再對(duì)這個(gè)可行流從新進(jìn)行標(biāo)號(hào)過(guò)程，尋找增廣鏈。一直到標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，不存在從vS到vt的增廣鏈，算法結(jié)束。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是標(biāo)號(hào)的集合，是未標(biāo)號(hào)的集合。此時(shí)，網(wǎng)絡(luò)中的可行流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)例:用標(biāo)號(hào)法求下圖中s→t的最大流量,并找出該網(wǎng)絡(luò)的最小割.ε(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)絡(luò)的最大流vsv1vtv5v4v3v24310413354278解：給定初始可行流為全零流，即f（0）

=0給vs標(biāo)號(hào)（0，+∞），檢查vs：給v1

標(biāo)號(hào)(vs,4),給v2

標(biāo)號(hào)(vs,3),給v3

標(biāo)號(hào)(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

標(biāo)號(hào)(v1,1)，檢查完畢；(v1,1)檢查v2：給v5

標(biāo)號(hào)(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

標(biāo)號(hào)(v5,3)，檢查完畢；(v5,3)因?yàn)榻K點(diǎn)vt

已標(biāo)號(hào)，故找出一條從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,