運籌學基礎圖論方法

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

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

fij)

容量限制條件：0≤fij≤cij，當支路上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ā)點和收點分開，并使s→t的流中斷的正向弧的集合，也叫做割。

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

一般包含s

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

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

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

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

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

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

基本算法：找一條從s到t點的增廣鏈。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)

增廣過程：前向弧

f'ij=fij+θ,后向弧

f'ij=fij–θ,增廣后仍是可行流欲求增廣量找最小截集的標號法步驟第一步：標號過程，找一條增廣鏈1、給源點s

標號[s+,q(s)=]，表示從s點有無限流出潛力2、找出與已標號節(jié)點i

相鄰的所有未標號節(jié)點j，若(1)(i,j)是前向弧且飽和，則節(jié)點

j

不標號（即此路不通）；(2)(i,j)是前向弧且未飽和，則節(jié)點

j

標號為[i+,θ(j)]，表示從節(jié)點i

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

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

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

不標號（即此路不通）

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

標號為[i

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

流向

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

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

獲得標號，找到一條增廣鏈，由節(jié)點t

標號回溯可找出該增廣鏈；到第二步(2)節(jié)點t

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

中，未獲標號節(jié)點在

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

的標記值2、對增廣鏈中的后向弧，令f=f

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

以上算法是按廣探法描述的，但在實際圖上作業(yè)時，按深探法進行更快捷一次只找一條增廣鏈，增廣一次換一張圖最后一次用廣探法，以便找出最小截集最大流最小截集的標號法舉例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最小截集又例：利用標號法（確定最小截集）求最大流量第二條鏈：(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)（四）應用舉例［例］某河流中有幾個島嶼，從兩岸至各島嶼及島嶼之間的橋梁如圖。在一次軍事行動中，問至少炸斷幾座橋，才能完全切斷兩岸的交通聯(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［例］匹配問題

有三根相同的軸（編號為1,2,3），又有三個的齒輪（編號為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)路問題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ā)點120發(fā)點220收點115收點220(5,0)事實上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ā)點虛收點st(20,15)(20,15)(20,15)(15,15)(5,0)S13254截止最大流量為15+5+5+5＝303簡化標注：求最大流量1653429()6()9()2()5()7()8()10()5()簡化標注：求最大流量1653429()6()9()2()5()7(

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

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

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

設網(wǎng)絡有n個點，cij為該弧的容量，bij為在弧(i,j)上通過單位流量時的費用，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ào)運到收點（或從發(fā)點按最大流量調(diào)運到收點），使總調(diào)運費用最小的問題。求最小費用流的步驟第一步：從零流f0開始，找一條使總費用最小的增廣鏈

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

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

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

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

弧(i,j)為反向弧時，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最小流量費用＝∑(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最小流量費用＝∑(q*∑W)=

63