運(yùn)籌學(xué)基礎(chǔ)圖論方法

(一)網(wǎng)路的最大流的相關(guān)概念st53424(0)3(0)2(0)1(0)1(0)5(0)3(0)2(0)5(0)

定義網(wǎng)路上支路的容量為其最大通過(guò)能力,記為cij,支路上的實(shí)際流量記為fij圖中規(guī)定一個(gè)發(fā)點(diǎn)s，一個(gè)收點(diǎn)tcij(

fij)

容量限制條件：0≤fij≤cij，當(dāng)支路上fij=cij，稱為飽和弧平衡條件：viA(vi)B(vi)滿足上述條件的網(wǎng)路流稱為可行流，總存在最大可行流（二）截集與截集容量st42319(4)6(1)9(9)2(0)5(4)7(5)8(8)10(8)5(5)截集：把網(wǎng)路中的發(fā)點(diǎn)和收點(diǎn)分開(kāi)，并使s→t的流中斷的正向弧的集合，也叫做割。

福特-富克森定理：網(wǎng)路的最大流等于最小截集容量

一般包含s

點(diǎn)的成分中的節(jié)點(diǎn)集合用V表示，包含t

點(diǎn)的成分中的節(jié)點(diǎn)集合用表示

截集容量是指截集中弧的容量之和網(wǎng)路的最大流就是最小截集容量為14截集1=｛（s,1），（s,2）｝（三）確定網(wǎng)路最大流的標(biāo)號(hào)法

從任一個(gè)初始可行流出發(fā)，如0流。

若在當(dāng)前可行流下再也找不到增廣鏈，則已得到最大流!

增廣鏈?zhǔn)菑陌l(fā)點(diǎn)到收點(diǎn)的一條鏈，該鏈上所有指向?yàn)閟→t的前向弧，存在f＜c；所有指向?yàn)閠→s的后向弧，存在f＞0，這樣的鏈叫增廣鏈。

基本算法：找一條從s到t點(diǎn)的增廣鏈。st54323(0)5(3)1(1)5(1)1(1)qs2=4q5t=2q45=3q43=1q32=1增廣量q=min

qij=min(4,1,1,3,2)=1st54323(1)5(4)1(0)5(2)1(0)

增廣過(guò)程：前向弧

f'ij=fij+θ,后向弧

f'ij=fij–θ,增廣后仍是可行流欲求增廣量找最小截集的標(biāo)號(hào)法步驟第一步：標(biāo)號(hào)過(guò)程，找一條增廣鏈1、給源點(diǎn)s

標(biāo)號(hào)[s+,q(s)=]，表示從s點(diǎn)有無(wú)限流出潛力2、找出與已標(biāo)號(hào)節(jié)點(diǎn)i

相鄰的所有未標(biāo)號(hào)節(jié)點(diǎn)j，若(1)(i,j)是前向弧且飽和，則節(jié)點(diǎn)

j

不標(biāo)號(hào)（即此路不通）；(2)(i,j)是前向弧且未飽和，則節(jié)點(diǎn)

j

標(biāo)號(hào)為[i+,θ(j)]，表示從節(jié)點(diǎn)i

正向流出，可增廣θ(j)=min[θ(i),cij

fij]；(3)(j,i)是后向弧，若

fji=0，則節(jié)點(diǎn)j

不標(biāo)號(hào)（即此路不通）

；(4)(j,i)是后向弧，若fji>0，則節(jié)點(diǎn)j

標(biāo)號(hào)為[i

,θ(j)]，表示從節(jié)點(diǎn)j

流向

i，可增廣θ(j)=min[θ(i),

fji]；最大流最小截集的標(biāo)號(hào)法步驟3、重復(fù)步驟2，可能出現(xiàn)兩種情況：(1)節(jié)點(diǎn)t

獲得標(biāo)號(hào)，找到一條增廣鏈，由節(jié)點(diǎn)t

標(biāo)號(hào)回溯可找出該增廣鏈；到第二步(2)節(jié)點(diǎn)t

尚未標(biāo)號(hào)，但無(wú)法繼續(xù)標(biāo)記，說(shuō)明網(wǎng)路中已不存在增廣鏈，當(dāng)前流v(f)就是最大流；所有獲標(biāo)號(hào)的節(jié)點(diǎn)在V

中，未獲標(biāo)號(hào)節(jié)點(diǎn)在

中，V與間的弧即為最小截集，最小截集容量即為該網(wǎng)絡(luò)最大流量；算法結(jié)束最大流最小截的標(biāo)號(hào)法步驟第二步：增廣過(guò)程1、對(duì)增廣鏈中的前向弧，令f=f+q(t)，q(t)為節(jié)點(diǎn)t

的標(biāo)記值2、對(duì)增廣鏈中的后向弧，令f=f

q(t)3、非增廣鏈上的所有支路流量保持不變第三步：抹除圖上所有標(biāo)號(hào)，回到第一步

以上算法是按廣探法描述的，但在實(shí)際圖上作業(yè)時(shí)，按深探法進(jìn)行更快捷一次只找一條增廣鏈，增廣一次換一張圖最后一次用廣探法，以便找出最小截集最大流最小截集的標(biāo)號(hào)法舉例st42319(4)6(1)9(9)2(0)5(4)7(5)8(8)10(8)5(5)(s+,)(s+,2)(2-,2)(1+,2)(3-,1)(4+,1)第一條鏈：(s+,)→(s+,2)→(2-,2)→(1+,2)→(3-,1)→(4+,1)q=1前向弧f'ij=fij+θ后向弧f'ij=fij–θst42319(4)6(1)9(9)2(0)5(4)7(5)8(8)10(8)5(5)st42319(5)6(0)9(9)2(0)5(3)7(6)8(8)10(9)5(5)(s+,)(s+,1)(2-,1)(1+,1)第二條鏈：(s+,)→(s+,1)→(2-,1)→(1+,1)截止最大流量為5+9＝14最小截集又例：利用標(biāo)號(hào)法（確定最小截集）求最大流量第二條鏈：(s+,)→(s+,1)截止(s+,)(2+,1)第一條鏈：(s+,)→(s+,2)→(2+,1)→(5+,1)→(3-,1)→(1+,1)→(4+,1)最小截集最大流量為5+3+5＝13(s+,2)st52413(2)2(0)5(4)3(3)3(3)6(4)5(5)6(6)8(6)32(0)4(4)2(2)(5-,1)(3-,1)(1+,1)(4+,1)增廣量q=1(s+,)(s+,1)前向弧f'ij=fij+θ后向弧f'ij=fij–θst52413(2)2(0)5(4)3(3)3(3)6(4)5(5)6(6)8(6)32(0)4(4)2(2)st52413(3)2(0)5(5)3(2)3(3)6(5)5(5)6(6)8(7)32(0)4(4)2(1)（四）應(yīng)用舉例［例］某河流中有幾個(gè)島嶼，從兩岸至各島嶼及島嶼之間的橋梁如圖。在一次軍事行動(dòng)中，問(wèn)至少炸斷幾座橋，才能完全切斷兩岸的交通聯(lián)系？ADBCDEFAFDECB2(0)1(0)3(0)1(0)2(0)1(0)2(0)1(0)1(0)

AFDECB2(0)1(0)3(0)1(0)2(0)1(0)2(0)1(0)1(0)(A+,)(A+,2)(B+,2)(D+,1)AFDECB2(1)1(1)3(0)1(0)2(0)1(0)2(1)1(0)1(0)(A+,)(A+,2)(C+,1)(D+,1)(E+,1)AFDECB2(1)1(1)3(1)1(0)2(1)1(0)2(1)1(1)1(1)(A+,)(A+,1)(E+,1)AFDECB2(1)1(1)3(2)1(0)2(1)1(1)2(1)1(1)1(1)(A+,)(A+,1)(B+,1)(D-,1)至少炸斷橋A－E，D－E，D－F，才能完全切斷兩岸的交通聯(lián)系q=1q=1q=1［例］匹配問(wèn)題

有三根相同的軸（編號(hào)為1,2,3），又有三個(gè)的齒輪（編號(hào)為4,5,6），由于精度不高，不能任意匹配，配合情況如圖所示，部如何選擇裝配方案，以得到軸和齒輪的最大數(shù)。1234561(0)123456St1(0)1(0)1(0)1(0)1(0)1(0)1(0)1(0)1(0)1(0)1(0)(s+,)(s+,1)(1+,1)(4+,1)1(1)123456St1(0)1(0)1(1)1(0)1(0)1(0)1(0)1(0)1(1)1(0)1(0)(s+,)(s+,1)(2+,1)(5+,1)(s+,)(s+,1)(3+,1)1(1)123456St1(1)1(0)1(1)1(0)1(1)1(0)1(0)1(0)1(1)1(1)1(0)(5+,1)(2+,1)(6+,1)1(1)123456St1(1)1(1)1(1)1(0)1(0)1(1)1(1)1(0)1(1)1(1)1(1)1－4，2－6，3－5q=1q=1q=1（五）多端網(wǎng)路問(wèn)題18764352(15,0)(10,0)(20,0)(5,0)(5,0)(5,0)(5,0)(5,0)(10,0)(10,0)(10,0)(10,0)發(fā)點(diǎn)120發(fā)點(diǎn)220收點(diǎn)115收點(diǎn)220(5,0)事實(shí)上18764352(15,10)(10,10)(20,5)(5,5)(5,5)(5,5)(5,5)(5,0)(10,5)(10,10)(10,5)(10,0)虛發(fā)點(diǎn)虛收點(diǎn)st(20,15)(20,15)(20,15)(15,15)(5,0)S13254截止最大流量為15+5+5+5＝303簡(jiǎn)化標(biāo)注：求最大流量1653429()6()9()2()5()7()8()10()5()簡(jiǎn)化標(biāo)注：求最大流量1653429()6()9()2()5()7(

)8()10()5()1356Θ=71246Θ=512356Θ=21243截止截止，最大流量＝9+5＝14（或者最大流量＝7+5+2＝147775557299（六）利用EXCEL求網(wǎng)絡(luò)最大流量第一步：建立各結(jié)點(diǎn)間的流量矩陣?yán)肊XCEL求網(wǎng)絡(luò)最大流量第二步：定義最大流量方案

第三步：利用規(guī)劃求解30(30)80(80)60(60)10(10)100(70)70(70)20(20)10(10)40(40)§6.5最小費(fèi)用流量問(wèn)題

實(shí)際物資調(diào)配問(wèn)題，既要考慮流量通過(guò)各條弧時(shí)的容量限制，也需要考慮調(diào)動(dòng)費(fèi)用的節(jié)省，這就是最小費(fèi)用流要研究的問(wèn)題。若在最小費(fèi)用流問(wèn)題中，將單位流量通過(guò)弧的費(fèi)用當(dāng)成是距離，則求從發(fā)點(diǎn)至收點(diǎn)調(diào)運(yùn)一單位流量的最小費(fèi)用，也就等價(jià)于求該兩點(diǎn)之間的最短距離。因此，最小費(fèi)用流是最短距離和最大流量的綜合考量。最小費(fèi)用流量圖例

設(shè)網(wǎng)絡(luò)有n個(gè)點(diǎn)，cij為該弧的容量，bij為在弧(i,j)上通過(guò)單位流量時(shí)的費(fèi)用，fij為弧(i,j)上的流量。s32t1(7,6)0(5,2)0

(6,1)0

(2,3)0

(3,2)0

(8,4)0

(4,1)0(cij,bij)fij

試求將發(fā)點(diǎn)物資調(diào)運(yùn)到收點(diǎn)（或從發(fā)點(diǎn)按最大流量調(diào)運(yùn)到收點(diǎn)），使總調(diào)運(yùn)費(fèi)用最小的問(wèn)題。求最小費(fèi)用流的步驟第一步：從零流f0開(kāi)始，找一條使總費(fèi)用最小的增廣鏈

該鏈上的總費(fèi)用為：q×∑W(i,j)；其中，q是該鏈上增加的流量，

W(i,j)是該鏈上增廣一單位流量，弧(i,j)“增加”的費(fèi)用。第二步：重復(fù)第一步，一直到再也找不到增廣鏈為止注：用標(biāo)號(hào)法的簡(jiǎn)單形式

增廣鏈：是從發(fā)點(diǎn)到收點(diǎn)的一條鏈，該鏈上所有指向?yàn)閟→t的前向弧，存在f＜c；所有指向?yàn)閠→s的后向弧，存在f＞0，這樣的鏈叫增廣鏈。

費(fèi)用：弧(i,j)為前向弧時(shí)，W(i,j)=bij；

弧(i,j)為反向弧時(shí)，W(i,j)=-bij例s32t1(4,9)0(8,4)0

(10,9)0

(3,2)0

(2,5)0

(8,7)0

(5,8)0(cij,bij)fijΘ=3Θ=2Θ=5截止最大流量＝8+4＝12∑W

=14s32t1(4,9)0(8,4)3

(10,9)0

(3,2)3

(2,5)0

(8,7)0

(5,8)3∑W

=17s32t1(4,9)2

(8,4)3

(10,9)0

(3,2)3

(2,5)0

(8,7)0

(5,8)5∑W

=20s32t1(4,9)2(8,4)8

(10,9)5(3,2)3

(2,5)0

(8,7)5

(5,8)5Θ=2∑W

=21最小流量費(fèi)用＝∑(q*∑W)=218s32t1(4,9)4(8,4)8

(10,9)5(3,2)3

(2,5)2

(8,7)7

(5,8)5s13t824538s1t8924s23t7948105s21t759322s23179-2153又例(cij,bij)fijΘ=3Θ=1Θ=1截止最大流量＝4+5＝9∑W

=6∑W

=6∑W

=7Θ=3∑W

=8最小流量費(fèi)用＝∑(q*∑W)=

63