運籌學(xué)基礎(chǔ)-圖論方法(2).ppt

1、6.4 最大流量問題,當以物體、能量或信息等作為流量流過網(wǎng)絡(luò)時，怎樣使流過網(wǎng)絡(luò)的流量最大，或者使流過網(wǎng)絡(luò)的流量費用或時間最小。通常把設(shè)計為樣的流量模型問題，叫做網(wǎng)絡(luò)的流量問題。 本節(jié)主要討論最大流量問題。即在一定條件下，要求流過網(wǎng)絡(luò)的流量為最大。,在有一個起點和一個終點的網(wǎng)絡(luò)中，最大流量問題是企圖找出，在一定時期內(nèi)，能在起點進入，并通過這個網(wǎng)絡(luò)，在終點輸出的最大流量。,(一) 網(wǎng)路的最大流的相關(guān)概念,定義網(wǎng)路上支路的容量為其最大通過能力,記為 cij ,支路上的實際流量記為 fij,圖中規(guī)定一個發(fā)點s，一個收點t,cij( fij ),容量限制條件：0fij cij，當支路上 fij = ci

2、j，稱為飽和弧,平衡條件：,滿足上述條件的網(wǎng)路流稱為可行流，總存在最大可行流,（二）截集與截集容量,截集：把網(wǎng)路中的發(fā)點和收點分開，并使st的流中斷的正向弧的集合，也叫做割。,福特-富克森定理：網(wǎng)路的最大流等于最小截集容量,一般包含 s 點的成分中的節(jié)點集合用V表示，包含 t 點的成分中的節(jié)點集合用 表示,截集容量是指截集中弧的容量之和,網(wǎng)路的最大流就是最小截集容量為14,截集1=（s,1），（s,2）,（三）確定網(wǎng)路最大流的標號法,從任一個初始可行流出發(fā)，如 0 流。,若在當前可行流下再也找不到增廣鏈，則已得到最大流!,增廣鏈是從發(fā)點到收點的一條鏈，該鏈上所有指向為st的前向弧，存在fc；所

3、有指向為ts的后向弧，存在f0，這樣的鏈叫增廣鏈。,基本算法：找一條從 s 到 t 點的增廣鏈。,增廣過程：前向弧 fij=fij+, 后向弧 fij=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), cijfij ； (3) (

4、j, i)是后向弧，若 fji=0，則節(jié)點 j 不標號（即此路不通） ； (4) (j, i)是后向弧，若 fji0，則節(jié)點 j 標號為i, (j)，表示從節(jié)點 j 流向 i，可增廣 (j)=min(i), fji ；,最大流最小截集的標號法步驟,3、重復(fù)步驟 2，可能出現(xiàn)兩種情況：,(1)節(jié)點 t 獲得標號，找到一條增廣鏈，由節(jié)點 t 標號回溯可找出該增廣鏈；到第二步,(2) 節(jié)點 t 尚未標號，但無法繼續(xù)標記，說明網(wǎng)路中已不存在增廣鏈，當前流 v(f) 就是最大流；所有獲標號的節(jié)點在 V 中，未獲標號節(jié)點在 中，V 與 間的弧即為最小截集，最小截集容量即為該網(wǎng)絡(luò)最大流量；算法結(jié)束,最大流最

5、小截的標號法步驟,第二步：增廣過程 1、對增廣鏈中的前向弧，令 f=f +q (t)，q(t) 為節(jié)點 t 的標記值 2、對增廣鏈中的后向弧，令 f=fq (t) 3、非增廣鏈上的所有支路流量保持不變 第三步：抹除圖上所有標號，回到第一步 以上算法是按廣探法描述的，但在實際圖上作業(yè)時，按深探法進行更快捷 一次只找一條增廣鏈，增廣一次換一張圖 最后一次用廣探法，以便找出最小截集,最大流最小截集的標號法舉例,(s+,),(s+,2),(2-,2),(1+,2),(3-,1),(4+,1),第一條鏈：(s+,)(s+,2) (2-,2) (1+,2) (3-,1) (4+,1),q = 1,前向弧

6、fij=fij+,后向弧 fij=fij ,(s+, ),(s+, 1),(2-, 1),(1+, 1),第二條鏈：(s+,)(s+,1) (2-,1) (1+,1)截止,最大流量為5+914,最小截集,又例：利用標號法（確定最小截集）求最大流量,第二條鏈：(s+,)(s+,1) 截止,(s+,),(2+,1),第一條鏈：(s+,)(s+,2) (2+,1) (5+,1) (3-,1) (1+,1) (4+,1),最小截集,最大流量為5+3+513,(s+,2),(5-,1),(3-,1),(1+,1),(4+,1),增廣量q = 1,(s+,),(s+,1),前向弧 fij=fij+,后向弧

7、 fij=fij ,（四）應(yīng)用舉例,例某河流中有幾個島嶼，從兩岸至各島嶼及島嶼之間的橋梁如圖。在一次軍事行動中，問至少炸斷幾座橋，才能完全切斷兩岸的交通聯(lián)系？,(A+,),(A+,2),(B+,2),(D+,1),(A+,),(A+,2),(C+,1),(D+,1),(E+,1),(A+,),(A+,1),(E+,1),(A+,),(A+,1),(B+,1),(D-,1),至少炸斷橋AE，DE，DF，才能完全切斷兩岸的交通聯(lián)系,q = 1,q = 1,q = 1,例匹配問題,有三根相同的軸（編號為1,2,3），又有三個的齒輪（編號為4,5,6），由于精度不高，不能任意匹配，配合情況如圖所示，部

8、如何選擇裝配方案，以得到軸和齒輪的最大數(shù)。,(s+,),(s+,1),(1+,1),(4+,1),(s+,),(s+,1),(2+,1),(5+,1),(s+,),(s+,1),(3+,1),(5+,1),(2+,1),(6+,1),14，26，35,q = 1,q = 1,q = 1,（五）多端網(wǎng)路問題,事實上,S,1,3,2,5,4,截止,最大流量為15+5+5+530,3,簡化標注：求最大流量,簡化標注：求最大流量,=7,=5,=2,截止,截止，最大流量9+514（或者最大流量7+5+214,7,7,7,5,5,5,7,2,9,9,（六）利用EXCEL求網(wǎng)絡(luò)最大流量,第一步：建立各結(jié)點間

9、的流量矩陣,利用EXCEL求網(wǎng)絡(luò)最大流量,第二步：定義最大流量方案,第三步：利用規(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)運一單位流量的最小費用，也就等價于求該兩點之間的最短距離。 因此，最小費用流是最短距離和最大流量的綜合考量。,最小費用流量圖例,設(shè)網(wǎng)絡(luò)有n個點，cij為該弧的容量，bij

10、為在弧(i,j)上通過單位流量時的費用，fij為弧(i,j)上的流量。,(cij , bij ) fij,試求將發(fā)點物資調(diào)運到收點（或從發(fā)點按最大流量調(diào)運到收點），使總調(diào)運費用最小的問題。,求最小費用流的步驟,第一步：從零流f0開始，找一條使總費用最小的增廣鏈,該鏈上的總費用為：qW(i,j)； 其中，q是該鏈上增加的流量， W(i,j)是該鏈上增廣一單位流量，弧(i,j) “增加”的費用。,第二步：重復(fù)第一步，一直到再也找不到增廣鏈為止,注：用標號法的簡單形式,增廣鏈：是從發(fā)點到收點的一條鏈，該鏈上所有指向為st的前向弧，存在fc；所有指向為ts的后向弧，存在f0，這樣的鏈叫增廣鏈。,費用：弧(i,j)為前向弧時， W(i,j)= bij； 弧(i,j)為反向弧時， W(i,j)= -bij,例,(cij , bij ) fij,=3,=2,=5,截止,最大流量8+412,W =14,W =17,W =20,=2,W =21,最小流量費用(q *W )=218,又例,(cij ,