1、管理運籌學-管理科學方法,李軍,桂林電子科技大學商學院,Sub title,OR:SM,第7 章 圖與網(wǎng)絡分析 內(nèi)容提要,2,第一節(jié) 第二節(jié) 第三節(jié) 第四節(jié) 第五節(jié),圖論的概念 最小樹問題 最短路問題 網(wǎng)絡最大流 最小費用流,OR:SM,OR:SM,哥尼斯堡，原屬 波蘭，現(xiàn)屬俄羅 斯，名為加里寧 格勒,3,OR:SM,18世紀，哥尼斯堡城（當時東普魯士柯尼斯堡，今日俄羅斯加里寧 格勒）中有一條普雷格爾河，河上有七座橋?qū)⒑又械膬蓚€小島與河岸 連接起來。,茶余飯后，人們提出了這樣的問題：一個散步者能否從某地出發(fā)，,走遍七座橋且每座橋恰好經(jīng)過一次，最后回到原地？,4,OR:SM,第7 章 網(wǎng)絡分析

2、1736年瑞士數(shù)學家歐拉將兩岸和小島抽象 為四個點，將橋抽象為七條邊，此問題歸結(jié)為 一筆畫問題。,陸地A,A,島D,島C,D,C,B 陸地B 歐拉回答的根據(jù)是：若圖是連通的，且圖中奇點(和奇數(shù)條邊相關聯(lián)的點) 的數(shù)目為0或2時，則圖能“一筆畫”。奇點的數(shù)目為零時，則圖中任一點即是 “一筆畫”的起點又是終點。奇點的數(shù)目為2時，則兩點中任一點為“一筆畫” 的起點，而另一點為終點。前圖中奇點數(shù)目為4，不滿足“一筆畫”規(guī)則，因 此是無解的。 哥尼斯堡七橋問題，用圖論的方法得到了簡捷的證明，所以歐拉被人們 公認為圖論的創(chuàng)始人，人們稱他為“圖論之父”。,5,OR:SM,OR:SM,第一節(jié),圖論的概念,一、

3、圖的內(nèi)涵 1、圖的定義 圖論的圖與一般幾何圖形或代數(shù)函數(shù)圖形是完全不同的 圖論中的圖:由一些點和連接點的線所組成的“圖形” 點和線的位置是任意的 線的曲直、長短與實際無關，代表的只是點與點之間的相互關系 例：表示蘇州v1 、杭州v2 、上海v3 、南京v4倉儲網(wǎng)點之間的物流運輸線路關系,v2,e4,e1,e5 v1 e2 v3,e3,e6, v4,e2,e3,v2 e4 v3 e5,e6,e5 e2,e1, v4 e3 v1,6, v1,e1, v2,e4, v3,e6, v4,OR:SM,OR:SM,第一節(jié),圖論的概念,一、圖的內(nèi)涵 2、圖的分類 不帶箭頭的連線稱為“邊”，如公路運輸線路；

4、帶箭頭的連線稱為“弧”，如供排水的管道運輸線路。,1、無向圖 由點和邊的集合所構(gòu)成,2、有向圖 由點和弧的集合所構(gòu)成, 鏈：無向網(wǎng)絡中，前后相繼點和邊 路徑：有向網(wǎng)絡圖中，前后相繼并且,7,的交替序列稱為一條鏈。 圈：閉合的鏈稱為一個圈。,方向一致的點弧序列稱為一條路徑。 回路：閉合的路徑稱為一個回路。 OR:SM,OR:SM,8,第一節(jié) 圖與網(wǎng)絡的基本概念 圖及其分類 3、簡單圖 無環(huán)，且任意兩點間 不多于一條邊,圖論的概念 4、多重圖 有環(huán)，或有多重邊,OR:SM,OR:SM,第一節(jié) 圖與網(wǎng)絡的基本概念 母圖、子圖、支撐子圖,圖論的概念,9,母圖,子圖,支撐子圖（生成子圖）,OR:SM,O

5、R:SM,第一節(jié),圖論的概念,圖與網(wǎng)絡的基本概念 網(wǎng)絡（賦權(quán)圖） 在實際問題中，只用圖來描述所研究的對象間的關系往往是不夠的，而常 常還需要考慮與點或邊有關的某些數(shù)量指標（即“權(quán)”），其可以代表諸如距離、 費用、通過能力（容量）等等。 網(wǎng)絡點或邊帶有某種數(shù)量指標的圖,2,2,3,4,2,2,3,4,6,1,3,7,6,1,3,7,10,5,5,OR:SM,OR:SM,第一節(jié),圖論的概念,圖與網(wǎng)絡的基本概念 連通圖 在眾多各類圖中有一類在實際應用中占有重要地位的圖 連通圖在圖中，任意兩點間至少存在著一條鏈。,11,連通圖,不連通圖,OR:SM,OR:SM,第二節(jié) 最小樹問題 樹及其性質(zhì) 無圈且連

6、通的無向圖稱為樹。例如，企業(yè)的組織結(jié)構(gòu)，文 件的目錄管理等都可以用一個樹狀圖來表示。 性質(zhì)： 樹中任兩點之間必有且只有一條鏈； 樹中去掉任一條邊，則成為不連通圖； 樹中不相鄰兩頂點之間添一條邊，則得到一個圈； 頂點個數(shù)nv與邊的個數(shù)ne的關系：ne = nv 1。,12,OR:SM, v , v T,i,j,OR:SM,第二節(jié),最小樹問題,支撐樹：如果圖G（V，E）的支撐子圖T=（V，E/）是樹，則 稱T為G的支撐樹。 權(quán)數(shù)總和為最小的那棵支撐樹，稱為最小樹。w (T ) w ij 求解方法： 破圈法；避圈法 例：一家企業(yè)分別要在6間辦公室鋪設網(wǎng)線接入口，網(wǎng)線的可行走 線方式如下圖所示，如何鋪

7、設網(wǎng)線才能使網(wǎng)線總長為最短？,8,v2,4,v5,6,v1,3,5,6,v6,2,6,v3,8,v4,最短網(wǎng)線總長度為最小樹權(quán)之和2+3+4+6+6=21,13,OR:SM,OR:SM,14,第二節(jié),最小樹問題,方法一：破圈法 ：任取一個圈，從圈中去掉一條權(quán)最大的邊。 在余下的圖中，重復這個步驟，一直到一個不含圈的圖為止， 這時的圖便是最小樹。,6,v3,5,v5,4,v1,1,7,3,v6,5,4,v2,2,v4,這就得到了該圖的一個最小支撐樹。,14,2011-03-25,OR:SM,OR:SM,15,第二節(jié),最小樹問題,方法二 ：避圈法：開始選一條權(quán)最小的邊（也可從一點開 始），以后每一

8、步中，總從未被選取的邊中選一條權(quán)最小 的邊，并使之與已選取的邊不構(gòu)成圈。,6,v3,5,v5,4,v1,1,7,3,v6,5,4,v2,2,v4,這就得到了該圖的一個最小支撐樹。,15,2011-03-25,OR:SM,OR:SM,第三節(jié) 一、最短路問題,最短路問題 Shortest Route (Path) Problems, 路權(quán)：弧(vi, vj)的權(quán)為wij；路權(quán)是路p中各條弧權(quán)之和 最短路：在所有從vs到vt 的路p中，求一條路權(quán)最短的路,狄克斯特拉(Dijkstra)算法 算法說明：,w(P*) minw(P) P, 1959年提出，目前公認的最短路算法 適合于求解所有弧權(quán)wij

9、0的最短路問題 算法假設：有向圖D是完備圖 圖D中任意兩點vi , vj 之間，恰有兩條弧(vi , vj)和(vj , vi) 若vivj 不存在弧, 可設想一條從vi vj 的弧, 權(quán)wij=+； 若vi vj 有重復的弧，則保留弧權(quán)最小的弧,16,OR:SM,OR:SM,17,OR:SM,OR:SM,第三節(jié) 一、雙標號算法,最短路問題,18, ,基本思路: 從始點vs 出發(fā)，逐步探尋，給每個點標號； 標號分永久標號P(vk)和臨時標號T(vk) 兩種： 永久標號P(vk) 是從點 vs vk 的最短路權(quán) 臨時標號T(vk) 是從點 vs vk 最短路權(quán)的上界 算法的每一步從臨時標號集中選

10、最小者變?yōu)橛谰脴颂枺?經(jīng)過逐次改變，就可以得到從點vs 到各點的最短路。 標號形式： 單標號法是對每一點賦予一個路權(quán)標號 雙標號法是對每一點賦予兩個標號：路標、路權(quán),OR:SM,OR:SM,第三節(jié),最短路問題,一、雙標號算法 例：用雙標號法求下圖網(wǎng)絡最短路,v1,2,v5,3,7,4,1,8,vs,10,9,v2 4,1 3,v4,6,7,1,vt,19,v3,2,v6,OR:SM,2,OR:SM,vs,第三節(jié) 一、雙標號算法,最短路問題,第一步： 3,(vs ,3) v1 7,2 4,v5,1,(vs , ),8,(vs , 0),vs,9,v2,(vs ,9) 1,v4,(vs , ) 7

11、,vt,(vs , ),10,4,3,6,1,20,v3 (vs ,10),v6 (vs , ),OR:SM,2,OR:SM,第三節(jié) 一、雙標號算法,最短路問題,第二步：,(vs ,3),(v1 ,5),v1,2,v5,3,7,4,1,8,(vs , 0),vs,9,v2,(vs ,9) 1,v4,(v1 , 7),7,vt,(vs , ),10,4,3,6,1,21,v3 (vs ,10),v6 (vs , ),OR:SM,2,OR:SM,第三節(jié) 一、雙標號算法,最短路問題,第三步：,(vs ,3),(v1 ,5),v1,2,v5,3,7,4,1,8,(vs , 0),vs,9,v2,(vs

12、 ,9) 1,v4,(v5 , 6),7,vt,(v5 ,13),10,4,3,6,1,22,v3 (vs ,10),v6 (vs , ),OR:SM,2,OR:SM,第三節(jié),最短路問題,一、雙標號算法 最終：依此類推，重復上述標號過程。得最短路。,(vs ,3),(v1 ,5),v1,2,v5,3,7,4,1,8,(vs , 0),vs,9,v2,(vs ,9),1,v4,(v5 , 6),7,vt,(v6 ,12),10,4,3,6,1,23,v3 (v4 ,9),v6 (v3 ,11),OR:SM,OR:SM,即時練習： 某一個配送中心要給一個快餐店送快餐原料，應按 照什么路線送貨才能使

13、送貨時間最短。,(4,1),(18,3),(25,4),2,16,4,7,6,4,6,1,12,2,8,7,(27,5),18,3 (16,2),6,5,5,(22,3),24,OR:SM,OR:SM,第三節(jié),最短路問題,二、最短路的應用 1、網(wǎng)絡的中心 所謂網(wǎng)絡的中心是指一個網(wǎng)絡中，選擇某一點，使之其 余各點到該中心點的距離之和為最小。 例：如果要在下表中6個銷售點中選一個作為倉庫所在地，應 該建在哪個經(jīng)銷點，使其余各銷售點都離它較近？,25,OR:SM,OR:SM,第三節(jié),最短路問題,二、最短路的應用 2、網(wǎng)絡的重心 引進點的權(quán)系數(shù)，將權(quán)系數(shù)與最短距離陣各列對應元素加權(quán) 求和，再從中選擇最

14、小的即為網(wǎng)絡重心。,26,OR:SM,OR:SM,27,第三節(jié),最短路問題,3、設備更新問題:制訂一設備更新問題，使得總費用最??？,第1年,第2年,第3年,第4年,第5年,購買費 使用年數(shù) 維修費,13 0-1 8,14 1-2 10,16 2-3 13,19 3-4 18,24 4-5 27,解設以vi(i=1,2,3,4,5)表示“第i年初購進一臺新設備”這種 狀態(tài)，以v6表示“第5年末”這種狀態(tài)；以弧(vi, vj)表示“第i年 初購置的一臺設備一直使用到第j年初”這一方案，以wij表示這 一方案所需購置費和維護費之和。于是，該問題就可歸結(jié)為從 圖中找出一條從v1到v6的最短路問題。其網(wǎng)

15、絡模型如下：,27,2011-03-25,OR:SM,OR:SM,28,設備更新的網(wǎng)絡模型,(21),v2,32,(44) v4,63,21,44,22,45,27,37,(0)v1,31,89 62,24,(78) v6,用Dijkstra標 號法，求得最 短路為: v1 v3v6,v3,(31),47,34,v5 (62),32,28,2011-03-25,OR:SM,OR:SM,*設備更新問題。某公司使用一臺設備，在每年年初，公司就要決定是購買 新的設備還是繼續(xù)使用舊設備。如果購置新設備，就要支付一定的購置 費，當然新設備的維修費用就低。如果繼續(xù)使用舊設備，可以省去購置 費，但維修費用就

16、高了。請設計一個五年之內(nèi)的更新設備的計劃，使得五 年內(nèi)購置費用和維修費用總的支付費用最小。 表1：設備每年年初的價格表,年份 年初價格,1 11,2 11,3 12,4 12,5 13,表2：設備維修費如下表,使用年數(shù) 每年維修,0-1 5,1-2 6,2-3 8,3-4 11,4-5 18,費用,29,OR:SM,OR:SM,解： 將問題轉(zhuǎn)化為最短路問題，如下圖： 用vi表示“第i年年初購進一臺新設備”,弧（vi,vj）表示第i年年初購進的 設備一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,把所有弧的權(quán)數(shù)計算如下表：,1 2 3,1,2 16,3 22 16,4 30 22 1

17、7,5 41 30 23,6 59 41 31,30,4 5 6,17,23 18,OR:SM,22,23,18,OR:SM,(繼上頁) 把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。 59,22,30,41,23,v1,16,v2,16 v3 17,v4,17 v5,18,v6,22,30,23,31,41 最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條： v1 v3 v6和 v1 v4 v6 59,V1 （0,s）,16,（16,1） (22,1),41 30 (30,1) V2 16 v3 17 v4 30,17 31,23 (41,1) v5,v6 (53,3) (53

18、,4),41,31,OR:SM,OR:SM,第四節(jié) 網(wǎng)絡最大流Maximal,flows in Networks,許多系統(tǒng)包含了流量問題，例如鐵、公路系統(tǒng)中的車輛流、 工業(yè)流程中的物流、通風網(wǎng)絡中的風流、供水系統(tǒng)中的水流、控 制系統(tǒng)中的信息流和金融系統(tǒng)中的資金流等。對這些系統(tǒng)求最大 流量的問題就轉(zhuǎn)化為圖論中求網(wǎng)絡中一個相容的最大流問題，運 輸上稱之為網(wǎng)絡的最大通過能力。,32,OR:SM,OR:SM,引例：一個公路交通運輸網(wǎng)絡如圖7-10所示，它聯(lián)接了產(chǎn)地vs和 銷售地點vt。其中每一條?。╲i，vj）表示vi到vj的運輸線，弧旁 的數(shù)字表示該支線的最大通過能力。要求制定一個運輸方案， 使vs

19、到vt的運輸量達到最大。 這就是一個求網(wǎng)絡最大流的問題?？山o出一個運輸方案， 用圓圈中的數(shù)字表示。它表明有8個單位的運量從vs運往vt。問 題在于運量是否還能增加，或者說如何求最大運量？這是本節(jié) 要解決的一類主要問題。,9,v1,5,5,v3,8,vs,4,4 ,vt,2,33,7 v2 6 圖7-10 公路交通運輸網(wǎng)絡圖,v4,6,OR:SM,OR:SM,第四節(jié),網(wǎng)絡最大流,一、相關概念與定理 1、弧容量與容量網(wǎng)絡 對于有向圖 D=(V,A),，弧 (vi , v j )的容量表示弧的最大流通能力。 在V中指定一點稱為發(fā)點(記為vs )，另一點稱收點(記為vt)，其余點 叫中間點，這樣的賦權(quán)

20、有向圖就稱為一個容量網(wǎng)絡，記N=(V,A,B) 2、弧的流量與可行流 弧的實際通過量稱為該弧的流量。弧集A上的流量集合 f xij 稱 為網(wǎng)絡上的流。 滿足下述條件的流稱為可行流。,34,容量限制：對每條弧 (vi , v j ) A 平衡條件：中間點流出量=流入量,，都有,0 xij bij,OR:SM,(,OR:SM,第四節(jié),網(wǎng)絡最大流,一、相關概念與定理 3、前向弧與后向弧 是從vs 到vt 的鏈，方向從vs vt ，則鏈上的弧分為兩類 前向弧：弧的方向與鏈的方向相同，記+ 后向弧：弧的方向與鏈的方向相反，記- 4、飽和弧與非飽和弧 弧 vi , v j ) 的流量 xij 與之容量 b

21、ij 比較： 滿足 xij bij 的弧稱為飽和弧，弧的流量不能再擴充； 滿足 xij bij 的弧稱為非飽和弧，弧的流量允許再被擴大。 5、零弧與非零弧 滿足 xij 0 的弧稱為零弧。由于 xij 0 ， 所以弧的流量不能減小； 滿足 xij 0 的弧稱為非零弧?；〉牧髁靠梢员粶p小， 但要滿足 xij 0。,35,OR:SM,OR:SM,第四節(jié),網(wǎng)絡最大流,一、相關概念與定理 6、流量可以擴充的路 設 f xij 是一可行流，是從vs 到vt 的鏈，若鏈滿足： 上的所有前向弧為非飽和弧，即滿足 xij bij ，可以擴充流量 上的所有后向弧為非零弧，即滿足 xij 0 ，可以減少流量； 則

22、稱是一條關于可行流 f 的可擴充流量的路，亦稱增廣鏈。 7、流量可以擴充的路 可行流中，網(wǎng)絡發(fā)點的流出量（或網(wǎng)絡收點的流入量）就 是網(wǎng)絡的流量。 一個容量網(wǎng)絡的諸可行流中，網(wǎng)絡流量最大的可行流，稱 為最大流,36,OR:SM,OR:SM,圖與網(wǎng)絡分析,Graph Theory and Network Analysis,網(wǎng)絡流（Flow）與最大流問題 理論 1、流量截量定理 容量網(wǎng)絡上任何一個可行流的流量不超過任何一個截集的截量。 2、增廣鏈調(diào)整定理 在增廣鏈上對可行流進行調(diào)整可以得到一個流量更大的可行流。 3、最大流定理 可行流是最大流的充分必要條件是不存在關于該可行流的增廣鏈。,37,OR:

23、SM,OR:SM,第四節(jié),網(wǎng)絡最大流,二、求最大流標號法 1956年，福特和富爾克遜提出了尋求網(wǎng)絡最大流的基本方法，稱為福 特-富爾克遜算法（Fold-Fulkerson Algorithm）。 標號過程 給定可行流X=xij ，標號判斷有無增廣鏈 先給vs 標上(vs, +)，vs已標號尚未檢查，其余未標號 取一個已標號但未檢查的點vi進行檢查，對未標號點vj ： 前向弧(vi, vj)可以擴充流量(xijrij) vj尚未標號，則給vj 標號(vi，+)，vj 成為己標號尚未檢查的點 后向弧(vk, vi)可以減少流量(xki0) vk尚未標號，則給vk 標號(vi, -)，vk成為己標號

24、尚未檢查的點 vi 成為已標號已檢查的點，在其標號下劃橫線 檢查收點vt 是否已標號： vt被標上號則找到增廣鏈，進行流量調(diào)整；否則轉(zhuǎn)第步 若所有標號都已檢查，vt又未標號，則不存在增廣鏈,38,OR:SM,rij xij, ij,OR:SM,第四節(jié),網(wǎng)絡最大流,二、求最大流標號法 流量調(diào)整過程 反向追蹤找出vs 到vt 的增廣鏈 計算增廣鏈上可調(diào)整的流量, min xij,(vi , v j ) (vi , v j ) , 調(diào)整可行流的流量，得新的可行流xij , x ij x ij x ij x ,( v i , v j ) ( v i , v j ) ( v i , v j ) , 抹去

25、所有標號，對新的可行流X =xij，重新進入標號過程,39,OR:SM,OR:SM,第四節(jié),網(wǎng)絡最大流,二、求最大流標號法 例：下圖表示了企業(yè)所處的供應市場（v1和v2）、配送中心（v3 和v4、以及銷售市場（v5、v6和 v7）組成的網(wǎng)絡，各弧上括號里的 前一個數(shù)字表示弧的容量，后一個數(shù)字是目前的實際流量。 試求這個供應-銷售網(wǎng)絡的最大流方案。,v1,(10,6),v3,(4,4),v5,(5,5),(4,3),(6,3),v6,v2,(15,9),v4,(6,6),v7,40,OR:SM,OR:SM,第四節(jié),網(wǎng)絡最大流,二、求最大流標號法 供應-銷售網(wǎng)絡的可行流,v1,(10,6),v3,

26、(4,4),v5,(5,4),(15,6),(5,5),vs,(4,3),(6,3),v6,(10,8),vt,(12,12),v2,(15,9),v4,(6,6),v7,(8,6),41,OR:SM,vt,OR:SM,第四節(jié),網(wǎng)絡最大流,二、求最大流標號法 供應-銷售網(wǎng)絡的可擴充路,(+vs ,9) v1,(10,6),(+ v1 ,4) v3,(4,4),v5,(5,4),(15,6),(5,5),(+ v6 ,2),(+ vs ,) vs,(4,3),(6,3),(10,8) v6 (+ v4 ,3),(12,12),v2 (- v3 ,3),(15,9),v4 (+ v2 ,3) (6

27、,6),v7,(8,6),42,OR:SM,OR:SM,第四節(jié),網(wǎng)絡最大流,二、求最大流標號法 調(diào)整后的可行流,v1,(10,8),v3,(4,4),v5,(5,4),(15,8),(5,5),vs,(4,1),(6,5),v6,(10,10),vt,(12,12),v2,(15,11),v4,(6,6),v7,(8,6),最大流量為 f xs1 xs 2 x5t x6t x7 t 20,43,OR:SM,OR:SM,第四節(jié),網(wǎng)絡最大流,三、網(wǎng)絡的瓶頸識別 1、截集-截量與最小截集 截集： 對于網(wǎng)絡N=(V,A,R)，將V分為兩個非空集合S和S，使 發(fā)點vsS，收點vtS 所有起點屬于S而終點

28、屬于S的弧的集合稱為截集 (S,S) 截量：截集(S,S) 中所有弧的容量之和 r(S,S) 最小截集：截量最小的截集 2、最大流-最小截量定理 網(wǎng)絡中，任一可行流的流量恒不超過任一截集的截量，稱為 流量-截量定理。 最小截量的大小影響總流量的提高,44,OR:SM,2,7,1,5,OR:SM,(4,1),第四節(jié) K,網(wǎng)絡最大流 (2,1),V2,3(2),V5,5(5),3(3),4(4),8(6),(0,+)V1,3(3),V4,(6,1),2(2),2(0),V7,(5,1),6(4),V3 (1,2),2(0) K,5(4),V6 (3,1),6(6),45,最大流=13,截集：v1,

29、v2;v1,v4;v3,v6,OR:SM,(3,1),(0,+),(5,1),7,OR:SM,(4,1),第四節(jié) （1，2）,網(wǎng)絡最大流 (2,1),12(10),V2,4(3),5(4),3(3),V5,9(9),K,(0,+) V1,6(5),3(3) 5(4),V4 (2,1),4(4),2(2) V6 (7,1) 2(2) 9(6),V8 (7,1),5(4),46,V3 (1,1) 最大流=9+7=16,V7 (3,1) K 截集：v5,v8;v6,v7;v3,v7,OR:SM,20,30,S ,20,10,47 CBE=5,例 ：某公司下屬三家工廠A、B、C生產(chǎn)能力分別為30、20

30、、10個單位/天，每天產(chǎn)品要通過下圖所 示運輸網(wǎng)絡運到F、G、H三個倉庫。工廠車隊作出調(diào)度，安排了每條運輸?shù)缆返囊惶爝\輸量。 問：這樣的安排能否完成全部產(chǎn)品的進庫任務？為了完成進庫任務，應如何調(diào)整各運輸?shù)缆飞?的運輸量？(為了使用最大流標號法，對下圖在工廠左側(cè)虛設發(fā)貨點，發(fā)貨量分別為30、 20、10 ， 經(jīng)A、B、C三個工廠，作為它們的生產(chǎn)量，并沿St的路徑給出一可行流。),A ,15 ,15,5 ,5,F,10,20 ,5 15 5 10 ,5 20 ,20 B 10 ,10 10 10 ,10 ,20 Smin=(S,C),(B,C),(B,D), 20 (E,D),(E,G),(E,F

31、) C 容量為C(v*,v*)=10+10+,E 10 ,10 D,5 ,5 ,20 20 30 ,20,G,10 ,5 ,20 20,0 H, T ,20,10+10+5+5=50 最大流量(F*)= C(v*,v*)=5060。 故當前安排不足以完成產(chǎn)品進庫任務，還差10個單位的運輸量。 第一步：給出一個初始可行流。題目巳給出。 第二步：給頂點標號找增廣鏈。無增廣鏈，當前可行流為最大流。 第三步：確實最小割和最大流量。 第四步：抽調(diào)弧(A,B)和(B,E)上各個單位運輸能力去加強關鍵弧(B,D)，使BD=20,CAB=15, OR:SM OR:SM,G,OR:SM,S ,+10 ,20 3

32、0 20 ,20 10 ,10, B,A 15 ,15 15 ,5 +10 5 ,5 20 ,10 +10 10 ,10 ,20 20 C,E D,5 ,5 5 ,5 10 ,10 ,20 20 30 ,20 +10,F ,10 10 ,5 ,20 20,0 H, T ,20 +10,第五步：在新可行流中,繼續(xù)給頂點標號找增廣鏈。 找到增廣鏈L=S，A，B，D，H，T，故當前可行流為非最大流。 第六步：沿增廣鏈L方向調(diào)整10個單位的流量，得一新可行流。,48,OR:SM,OR:SM,A ,15 ,15,5 ,5,F,10,S ,30 30 20 ,20 10 ,10, B,15 ,15 5 ,

33、5 20 ,20 10 ,10 ,20 20 C,E 10 ,10 D,5 ,5 ,20 20 30 ,30,G,10 ,5 ,20 20,0 H, T ,30,Smin=(S,A),(S,B),(S,C) 容量為 C(v*,v*)=30+20+10=60 最大流量(F*)= C(v*,v*)=60。 故當前安排足以完成產(chǎn)品進庫任務。,49,OR:SM,2,OR:SM,問題提出- 最小費用最大流問題 不僅考慮流量，而且還要考慮輸送的費用 最大流量的流量分布圖往往不只一個，誰最優(yōu)？,容量cij，費用bij,研究的目標：是要找到 一個最大流F*=fij使總,10,4 1 8,1,5,2,7,1 2

34、,6,5,的輸送費用最小，即： Min b(F*) =bij fij*,50,3,10,3,4,4,2,OR:SM,OR:SM,基本原理 找費用最小的可行流，找出該可行流的增廣鏈，沿鏈調(diào) 整流量；直到找不到費用最小的增廣鏈為止。 費用最小的增廣鏈含義 是費用最小的鏈 可以增大流量的鏈,51,OR:SM,2,OR:SM,標量型的費用用方向圖的表示方法,2 容量cij 費用bij 流量fij,賦權(quán)系數(shù)wij -1,10,4,0 1,7,1,5,1,4,1,5,2,5,2,6,0,5,-2,6,5,8,1,5,3,10,3,0,4,4,2,0,-1,1,3,3,4,2 僅有正向弧,52,wij=bi

35、j | fij0 反向弧,僅有反向弧 既有正向弧，又有反向弧,OR:SM,OR:SM,最小費用最大流算法步驟 生成法： 取 fij (0) 0 作為初始最小費用可行流(總費 用為0) 對 fij (0) =構(gòu)造一個賦權(quán)有向圖W(f(0),在圖上 找到從發(fā)點到收點的最短路(最小費用的有向圖) ，若存在最短路，則尋找增廣鏈L，在增廣鏈上 對 fij (0) 進行調(diào)整。 對 fij (1) 重復上步驟，直到在賦權(quán)有向圖中不存 在最短路。則獲得最小費用最大流。,53,OR:SM,2,OR:SM,最小費用最大流-例,容量,費用,流量,第1步：令所有流量為0, fij (0) =0,10,4,0 1,7,

36、1,0,8,1,0,5,2,0,2,6,0,5,54,3,10,3,0,4,4,2,0,OR:SM,OR:SM,第2步：構(gòu)造賦權(quán)有向圖,Q=0,找最短路徑,10,4,0 1,2,容量,費用,流量 7,1,0,1,4,2,費用 1,5,2,0,2,6,0,5,2,6,5,8,1,0,3,10,3,0,4,4,2,0,1,3,3,4,2,55,流量圖,費用賦權(quán)圖,OR:SM,OR:SM,第3步：求調(diào)整量，,Q=0 2,可均增加5，其他不變 2,10,4,0 1,5,2,5,7,1,5 7,1,0,1,4,1,5,2,0,2,6,0,5,2,6,5,8,1,0 8,1,5 3,10,3,0,4,4,

37、2,0,1,3,3,4,2,56,流量圖,費用賦權(quán)圖,OR:SM,OR:SM,第4步：重新構(gòu)造賦權(quán)有,Q=5 2,2,向圖,-1,10,4,0 1,7,1,5,1,4,1,5,2,5,2,6,0,5,-2,6,5,8,1,5,3,10,3,0,4,4,2,0,-1,1,3,3,4,2,57,流量圖,費用賦權(quán)圖,OR:SM,OR:SM,第5步：找最短路徑,Q=5 2,第6步：沿最短路徑調(diào)整 流量,可增加2 2,10,4,2 10,4,0,7,1,7 7,1,5,4,1,-1,1,1,5,2,5,2,6,0,5,-2,6,5,8,1,5,3,10,3,0,4,4,2,0,-1,1,3,3,4,2,

38、58,流量圖,費用賦權(quán)圖,OR:SM,OR:SM,Q=7,第7步：重新構(gòu)造賦權(quán)有 向圖，找最短路徑,2,-4,2,10,4,2 1,7,1,7,1,4,-1,5,2,5,2,6,0,5,-2,6,5,8,1,5,3,10,3,0,4,4,2,0,-1,1,3,3,4,2,59,流量圖,費用賦權(quán)圖,OR:SM,OR:SM,第8步：沿最短路徑調(diào)整,Q=7,流量,可增加3,2,-4,2,10,4,2 1,7,1,7,1,4,-1,5,2,5,2,6,0,5,-2,6,5,8,1,5 8,1,8,3,10,3,0 10,3,3,4,4,2,0 4,2,3,-1,1,3,3,4,2,60,流量圖,費用賦

39、權(quán)圖,OR:SM,OR:SM,Q=10,第9步：重新構(gòu)造賦權(quán)有 向圖，找最短路徑,2,-4,2,10,4,2 1,7,1,7,1,4,-1,5,2,5,2,6,0,5,-2,6,5,8,1,8,3,10,3,3,4,4,2,3,-1,3,3,4,2 -2,-3,61,流量圖,費用賦權(quán)圖,OR:SM,4,OR:SM,Q=10,第10步：沿最短路徑調(diào) 整流量,可增加1,10,4,2 10,4,3,2,7,1,7,-4,4,2,-1,1,1,8,1,8,3,5,2,5 5,2,4 10,3,3 10,3,4,2,6,0 4,2,3 4,2,4,5,-1,3,-2,3 -3,6 4,2 -2,5,62,流量圖,費用賦權(quán)圖,OR:SM,OR:SM,Q*=11,第11步：重新構(gòu)造賦權(quán) 有向圖，找最短路徑,10,4,3,2,7,1,7,-4,4,2,-1,1,1,-2,5,2,4,2,6,0,5,2,6,5,8,1,8,3,10,3,4,4,4,2,4,-1,3,3,4,-2,-3,63,流量圖,費用賦