[教育]運籌學ppt課件ch6網(wǎng)絡模型

1、運 籌 學   Operations  Research,,,Chapter 6 網(wǎng)絡模型Network Modeling,6.1 最小(支撐)樹問題 Minimal (Spanning)Tree Problem6.2 最短路問題 Shortest Path Problem 6.3 最大流問題 Maximal Flow Proble

2、m6.4 旅行售貨員與中國郵路問題 Traveling Salesman and China Carrier Problem,,2024年3月27日星期三,,,,5,,,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,圖6－1,運籌學中研究的圖具有下列特征：（1）用點表示研究對象，用邊（有方向或無方向）表示對象之間某種關(guān)系。（2）強調(diào)點與點之間的關(guān)聯(lián)關(guān)系，不

3、講究圖的比例大小與形狀。（3）每條邊上都賦有一個權(quán)，其圖稱為賦權(quán)圖。實際中權(quán)可以代表兩點之間的距離、費用、利潤、時間、容量等不同的含義。（4）建立一個網(wǎng)絡模型，求最大值或最小值。,2024年3月27日星期三,邊用[vi,vj]表示或簡記為[i，j]，集合記為,如圖6－1所示，點集合記為,邊上的數(shù)字稱為權(quán)，記為w[vi,vj]、w[i，j]或wij，集合記為,連通的賦權(quán)圖稱為網(wǎng)絡圖，記為

4、 G＝｛V，E，W｝,5,,,,,,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,圖6－1,,,6.1 最小(支撐)樹問題 Minimal (Spanning)Tree Problem,2024年3月27日星期三,6.1.1樹的概念,一個無圈并且連通的無向圖稱為樹圖或簡稱樹(Tree)。組織機構(gòu)、家譜、學科分支、因特網(wǎng)絡、通訊網(wǎng)絡及高壓線路網(wǎng)絡等都能表達成一個

5、樹圖 。,可以證明：（1）一棵樹的邊數(shù)等于點數(shù)減1；（2）在樹中任意兩個點之間添加一條邊就形成圈；（3）在樹中去掉任意一條邊圖就變?yōu)椴贿B通。,在一個連通圖G中，取部分邊連接G的所有點組成的樹稱為G的部分樹或支撐樹(Spanning Tree )。圖6－2是圖6－1的部分樹。,6.1 最小樹問題 Minimal tree problem,2024年3月27日星期三,6.1.2 最小部分樹,將網(wǎng)絡圖G邊上的權(quán)看作兩點間的長度（距離

6、、費用、時間），定義G的部分樹T的長度等于T中每條邊的長度之和，記為C(T)。 G的所有部分樹中長度最小的部分樹稱為最小部分樹，或簡稱為最小樹。,最小部分樹可以直接用作圖的方法求解，常用的有破圈法和加邊法。破圈法：任取一圈，去掉圈中最長邊，直到無圈。,6.1 最小樹問題 Minimal tree problem,2024年3月27日星期三,,,,5,,,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,8,4,3,7,5,

7、2,6,1,8,圖6－1,【例6.1】用破圈法求圖6－1的最小樹。,,,,,,圖6－4,圖6－4就是圖6－1的最小部分樹，最小樹長為 C(T)=4+3+5+2+1=15。當一個圈中有多個相同的最長邊時，不能同時都去掉，只能去掉其中任意一條邊。最小部分樹有可能不唯一，但最小樹的長度相同,6.1 最小樹問題 Minimal tree problem,2024年3月27日星期三,加

8、邊法：取圖G的n個孤立點｛v1，v2，…， vn}作為一個支撐圖，從最短邊開始往支撐圖中添加，見圈回避，直到連通（有n－1條邊）,,,,,,,v1,v2,v3,v4,v5,v6,圖6－5,在圖6－5中，如果添加邊[v1, v2]就形成圈｛v1, v2, v4｝，這時就應避開添加邊[v1, v2]，添加下一條最短邊[v3, v6]。破圈法和加邊法得到樹的形狀可能不一樣，但最小樹的長度相等,,×,Min C(T)=15,6.1

9、最小樹問題 Minimal tree problem,2024年3月27日星期三,下一節(jié)：最短路問題,1.樹、支撐樹、最小支撐樹的概念2.掌握求最小樹的方法： （1）破圈法 （2）加邊法,作業(yè)：P149 T 1，4，5,6.1 最小樹問題 Minimal tree problem,,,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,最短路問題在實際中具有廣泛

10、的應用，如管道鋪設、線路選擇等問題，還有些如設備更新、投資等問題也可以歸結(jié)為求最短路問題,求最短路有兩種算法： 一是求從某一點至其它各點之間最短離的狄克斯屈拉(Dijkstra)算法 另一種是求網(wǎng)絡圖上任意兩點之間最短路的Floyd(弗洛伊德)矩陣算法。,最短路問題，就是從給定的網(wǎng)絡圖中找出一點到各點或任意兩點之間距離最短的一條路,6.2.1最短路問題的網(wǎng)絡模型,6.2 最短路問題 Shortest Path Probl

11、em,2024年3月27日星期三,①,②,③,④,⑤,⑥,⑦,,,,,,,,,,,,,6,10,12,,3,2,14,6,7,5,8,11,16,,5,圖6－6,,9,【例6.3】圖6－6中的權(quán)cij表示vi到vj的距離（費用、時間），從v1修一條公路或架設一條高壓線到v7，如何選擇一條路線使距離最短，建立該問題的網(wǎng)絡數(shù)學模型。,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,【解】 設xi

12、j為選擇弧(i，j)的狀態(tài)變量，選擇弧(i，j)時xij＝1，不選擇弧(i，j)時xij＝0，得到最短路問題的網(wǎng)絡模型：,,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,6.2.2有向圖的狄克斯屈拉(Dijkstra)標號算法,點標號：b(j) —起點vs到點vj的最短路長；,邊標號：k(i，j)=b(i)+cij，,步驟：(1)令起點的標號；b(s)＝0。,先求有向圖的最短路，設網(wǎng)絡圖的

13、起點是vs ,終點是vt ,以vi為起點vj為終點的弧記為（i，j）,距離為cij,(2)找出所有vi已標號vj未標號的弧集合 B={(i，j)}，如果這樣的弧不存在或vt已標號則計算結(jié)束；,(3)計算集合B中弧k(i，j)=b(i)+cij的標號,(4)選一個點標號 返回到第(2)步。,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,②,③,④,⑤,⑥,⑦,,,,,,,,,,,,,6

14、,10,12,,3,2,14,6,7,5,8,11,16,,5,圖6－6,,9,0,6,10,12,9,20,9,18,6,①,16,12,17,16,24,32,18,29,29,【例6.4】用Dijkstra算法求圖6－6 所示v1到v7的最短路及最短路長,v1 到v7的最短路為：p17=｛v1, v2, v3, v5, v7｝，最短路長為L17=29,6.2 最短路問題 Shortest Path Problem,14,2024

15、年3月27日星期三,從上例知，只要某點已標號，說明已找到起點vs到該點的最短路線及最短距離，因此可以將每個點標號，求出vs到任意點的最短路線，如果某個點vj不能標號，說明vs不可達vj 。,6.2.3 無向圖最短路的求法,無向圖最短路的求法只將上述步驟（2）改動一下即可。,點標號：b(i) —起點vs到點vj的最短路長；,邊標號：k(i，j)=b(i)+cij，,步驟：(1)令起點的標號；b(s)＝0。,(3)計算集合B中邊標號：k[i

16、，j]=b(i)+cij,(4)選一個點標號: 返回到第(2)步。,(2)找出所有一端vi已標號另一端vj未標號的邊集合 B={[i，j]}如果這樣的邊不存在或vt已標號則計算結(jié)束；,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,【例6.5】求圖6-10所示v1到各點的最短路及最短距離,0,4,5,2,,2,3,10,,3,9,6,12,6,,4,11,,6,,6,18,8,12,24

17、,,8,24,,18,所有點都已標號，點上的標號就是v1到該點的最短距離，最短路線就是紅色的鏈。,圖6-10,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,6.2.4 最短路的Floyd算法,Floyd算法基本步驟 :,(1)寫出vi一步到達vj 的距離矩陣 ，L1也是一步到達的最短距離矩陣。如果vi 與vj 之間沒有邊關(guān)聯(lián)，則令cij=+∞,(2)計算

18、二步最短距離矩陣。設vi 到vj 經(jīng)過一個中間點vr 兩步到達vj，則vi到vj的最短距離為,,最短距離矩陣記為,,(3)計算k步最短距離矩陣。設 vi經(jīng)過中間點vr 到達vj，vi 經(jīng)過k－1步到達點vr 的最短距離為 ，vr 經(jīng)過k－1步到達點vj 的最短距離為 ，則 vi 經(jīng)k步 到達vj 的最短距離為,,,(6.1),6.2 最短路問題 Shortest Path Problem,202

19、4年3月27日星期三,,最短距離矩陣記為,,(4)比較矩陣Lk與Lk－1，當Lk＝Lk－1時得到任意兩點間的最短距離矩陣Lk。設圖的點數(shù)為n并且cij≥0，迭代次數(shù)k由式(6.3) 估計得到。,(6.2),,,(6.3),6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,【例6.6】圖6-14是一張8個城市的鐵路交通圖，鐵路部門要制作一張兩兩城市間的距離表。這個問題實際就是求任意兩點間的最短

20、路問題。,【解】 (1)依據(jù)圖6-14,寫出任意兩點間一步到達距離表L1。見表6.1所示。本例n=8， ，因此計算到L3,圖6-14,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,表6-1 最短距離表 L1,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,表6-2 最短距離表L2,計算說明：L(2)ij等于表

21、6-1中第i行與第j列對應元素相加取最小值。如,,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,表6-3計算示例: 等于表6-2中第i行與第j列對應元素相加取最小值。例如，v3經(jīng)過三步（最多三個中間點4條邊）到達v6的最短距離是,表6-3 最短距離表L3,,,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,【例6.7】求圖6－15中任

22、意兩點間的最短距離?！窘狻繄D6－15是一個混合圖，有3條邊的權(quán)是負數(shù),有兩條邊無方向。依據(jù)圖6－15,寫出任意兩點間一步到達距離表L1。表中第一列的點表示弧的起點，第一行的點表示弧的終點，無方向的邊表明可以互達，見表6-4所示。計算過程見表6-5～6-7。,①,②,③,④,⑤,⑥,⑦,4,4,5,7,4,－3,－2,7,10,2,8,圖6－15,,,,,,,,,,,,,,－1,5,6.2 最短路問題 Shortest Path Pr

23、oblem,2024年3月27日星期三,表6-4一步到達距離表L1,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,表6-7 最短距離表L4,經(jīng)計算L4＝L5，L4是最優(yōu)表。表6-7不是對稱表，vi到vj與vj到vi的最短距離不一定相等。對于有負權(quán)圖情形，公式(6.3)失效。,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,6.2.4 最短路應用

24、舉例,6.2 最短路問題 Shortest Path Problem,【例6.8】設備更新問題。企業(yè)在使用某設備時，每年年初可購置新設備，也可以使用一年或幾年后賣掉重新購置新設備。已知4年年初購置新設備的價格分別為2.5、2.6、2.8和3.1萬元。設備使用了1～4年后設備的殘值分別為2、1.6、1.3和1.1萬元，使用時間在1～4年內(nèi)的維修保養(yǎng)費用分別為0.3、0.8、1.5和2.0萬元。試確定一個設備更新策略，在下例兩種情形下使4

25、年的設備購置和維護總費用最小。（1）第4年年末設備一定處理掉；（2）第4年年末設備不處理。,【解】畫網(wǎng)絡圖。用點(1,i,…,j)表示第1年年初購置設備使用到第i年年初更新，經(jīng)過若干次更新使用到第j年年初，第1年年初和第5年年初分別用①及⑤表示。使用過程用弧連接起來，弧上的權(quán)表示總費用(購置費＋維護費－殘值)，如圖6－16所示,2024年3月27日星期三,6.2 最短路問題 Shortest Path Problem,①,⑤,6,

26、圖6－16,,(1,2,3),,(1,4),(1,3,4),(1,2,4),,,(1,2,3,4),,,(1,2),(1,3),,,,,,第一年,第二年,第三年,第四年,,,,5.1,0.9,1.5,0.7,3.6,2.8,,1.7,-0.2,1.9,,,,,1.1,,,2.1,0.3,-0.6,-0.6,網(wǎng)絡圖6－16說明：如圖中點(1,3)表示第1年購置設備使用兩年到第3年年初更新購置新設備，這時有2種更新方案，使用1年到第4年年初

27、、使用2年到第5年年初,更新方案用弧表示，點（1,2,3）表示第1年購置設備使用一年到第二年年初又更新，使用一年到第三年初再更新，這時仍然有2種更新方案，使用1年到第4年年初和使用2年到第5年年初。,2024年3月27日星期三,6.2 最短路問題 Shortest Path Problem,點（1,3）和點（1,2,3）不能合并成一個點，雖然都是第三年年初購置新設備，購置費用相同，但殘值不同。點(1,3)的殘值等于1.6(使用了兩年)

28、，點(1,2,3)的殘值等于2(使用了一年)。點（1,3）到點（1,3,4）的總費用為第三年的購置費＋第一年的維護費－設備使用兩年后的殘值＝2.8+0.3－1.6=1.5點（1,3）到點⑤的總費用為第三年的購置費＋第一年的維護費＋第二年的維護費－設備使用兩年后的殘值－第四年末的殘值＝2.8+0.3+0.8－1.6－1.6=0.7。,費用表見教材P135表6-8。,2024年3月27日星期三,①,⑤,6,圖6－16,,(1,2,

29、3),,(1,4),(1,3,4),(1,2,4),,,(1,2,3,4),,,(1,2),(1,3),,,,,,第一年,第二年,第三年,第四年,,,,5.1,0.9,1.5,0.7,3.6,2.8,,1.7,-0.2,1.9,,,,,1.1,,,2.1,0.3,-0.6,-0.6,2024年3月27日星期三,6.2 最短路問題 Shortest Path Problem,（2）第四年末不處理設備：將圖6－16第4年的數(shù)據(jù)換成表6-8

30、最后一列，求點①到點⑤的最短路。最短路線為：①→(1,2)→(1,2,3)→⑤，最短路長為5.6，即總費用為5.6萬元。更新方案與第一種情形相同。,（1）第四年末處理設備：求點①到點⑤的最短路。用Dijkstra算法得到最短路線為：①→(1,2)→(1,2,3)→⑤，最短路長為4。 4年總費用最小的設備更新方案是：第1年購置設備使用1年，第2年更新設備使用1年后賣掉，第3年購置設備使用2年到第4年年末，4年的總費用為4萬元。

31、,2024年3月27日星期三,【例6.9】服務網(wǎng)點設置問題。以圖6－14為例，現(xiàn)提出這樣一個問題，在交通網(wǎng)絡中建立一個快速反應中心，應選擇哪一個城市最好。類似地，在一個網(wǎng)絡中設置一所學校、醫(yī)院、消防站、購物中心，還有廠址選擇、總部選址、公司銷售中心選址等問題都屬于最佳服務網(wǎng)點設置問題。,【解】 對于不同的問題，尋求最佳服務點有不同的標準。像圖6－14只有兩點間的距離，可以采用“使最大服務距離達到最小”為標準，計算步驟如下。 第一

32、步：利用Floyd算法求出任意兩點之間的最短距離表（表6－3）。 第二步：計算最短距離表中每行的最大距離的最小值，即,,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,引用例6.6計算的結(jié)果，對表3－3每行取最大值再取最小值，見表6－9倒數(shù)第二列。,表6－9,表6－9中倒數(shù)第二列最小值為12，位于第7行，則v7為網(wǎng)絡的中心，最佳服務點應設置在v7。,6.2 最短路問題 Shorte

33、st Path Problem,2024年3月27日星期三,如果每個點還有一個權(quán)數(shù)，例如一個網(wǎng)點的人數(shù)、需要運送的物質(zhì)數(shù)量、產(chǎn)量等，這時采用“使總運量最小”為標準，計算方法是將上述第二步的最大距離改為總運量，總運量的最小值對應的點就是最佳服務點。表6－9中最后一行是點vj的產(chǎn)量，將各行的最小距離分別乘以產(chǎn)量得到總運量，例如，0×80＋6×50＋…＋18×65＝3220，見表6－9最后一列，最小運量為245

34、0，最佳服務點應設置在v4。,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,下一節(jié)：最大流問題,6.2 最短路問題 Shortest Path Problem,1.最短路的概念及應用。2.有向圖、無向圖一點到各點最短路的Dijkstra算法3.任意兩點最短路的Floyd算法4.本節(jié)介紹了兩個應用：設備更新問題和最佳服務點設置問題,作業(yè)：P149 T 2,6,7,8,9,,,6.

35、3 最大流問題Maximal Flow Problem,2024年3月27日星期三,6.3 最大流問題Maximal Flow Problem,6.3.1 基本概念,①,②,③,④,⑤,⑥,,,,,,,,,8,14,5,6,3,3,8,10,7,6,,⑦,,,3,圖6－18,4,圖6－18所示的網(wǎng)絡圖中定義了一個發(fā)點v1，稱為源(source，supply node），定義了一個收點v7，稱為匯（sink，demand node）

36、，其余點v2，v3，…，v6為中間點，稱為轉(zhuǎn)運點(transshipment nodes)。如果有多個發(fā)點和收點，則虛設發(fā)點和收點轉(zhuǎn)化成一個發(fā)點和收點。圖中的權(quán)是該弧在單位時間內(nèi)的最大通過能力，稱為弧的容量(capacity)。最大流問題是在單位時間內(nèi)安排一個運送方案，將發(fā)點的物質(zhì)沿著弧的方向運送到收點，使總運輸量最大。,,2024年3月27日星期三,設cij為?。╥，j）的容量，fij為?。╥，j）的流量。容量是?。╥，j）單位時間

37、內(nèi)的最大通過能力，流量是弧（i，j）單位時間內(nèi)的實際通過量，流量的集合f={fij}稱為網(wǎng)絡的流。發(fā)點到收點的總流量記為v=val(f)，v也是網(wǎng)絡的流量。,圖6－18最大流問題的線性規(guī)劃數(shù)學模型為,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,滿足下例3個條件的流fij 的集合 f ={ fij }稱為可行流,發(fā)點vs流出的總流量等于流入收點vt的總流量,6.3 最大流問題Maximal

38、Flow Problem,2024年3月27日星期三,鏈：從發(fā)點到收點的一條路線（弧的方向不一定都同向）稱為鏈。從發(fā)點到收點的方向規(guī)定為鏈的方向。,前向?。号c鏈的方向相同的弧稱為前向弧。,后向?。号c鏈的方向相反的弧稱為后向弧。,增廣鏈: 設 f 是一個可行流，如果存在一條從vs到vt的鏈，滿足：,1.所有前向弧上fij<Cij,2.所有后向弧上fij>0,則該鏈稱為增廣鏈,①,②,③,④,⑤,⑥,,,,,,容量,流量,6.

39、3 最大流問題Maximal Flow Problem,2024年3月27日星期三,步驟如下：,第二步：對點進行標號找一條增廣鏈。（1）發(fā)點標號（∞）（2）選一個點 vi 已標號并且另一端未標號的弧沿著某條鏈向收點檢查： A．如果弧的方向向前（前向?。┎⑶矣衒ij0，則vj標號: θj＝fji當收點已得到標號時，說明已找到增廣鏈，依據(jù)vi

40、的標號反向跟蹤得到一條增廣鏈。當收點不能得到標號時，說明不存在增廣鏈，計算結(jié)束。,第一步： 找出第一個可行流，例如所有弧的流量fij =0,6.3.2 Ford-Fulkerson標號算法,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,第三步：調(diào)整流量（1）求增廣鏈上點vi 的標號的最小值，得到調(diào)整量,（2）調(diào)整流量,,得到新的可行流f1，去掉所有標號，返回到第二步從發(fā)點重新標號尋找增廣鏈，

41、直到收點不能標號為止,【定理6.1】 可行流f是最大流的充分必要條件是不存在發(fā)點到收點的增廣鏈,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,①,②,③,④,⑤,⑥,,,,,,,,,,8,14,5,6,3,3,8,10,7,6,,⑦,,,3,圖6－19,(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),【例6.10】求圖6－18發(fā)點v1到收點

42、v7的最大流及最大流量,【解】給定初始可行流，見圖6-19,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,①,②,③,④,⑤,⑥,,,,,,,,,,8,14,5,6,3,3,8,10,7,6,,⑦,,,3,圖6－20(b),(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),∞,2,3,3,7,第一輪標號：,c12>f12,v2標號2,增

43、廣鏈μ＝{(1,2)，(3,2)，(3,4)，(4,7) },μ+={(1,2)，(3,4)，(4,7)},μ－={(3，2)}，調(diào)整量為增廣鏈上點標號的最小值θ＝min{∞，2，3，3，7}＝2,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,①,②,③,④,⑤,⑥,,,,,,,,,,8,14,5,6,3,3,8,10,7,6,,⑦,,,3,圖6－21,(10),(8),(1),(6),(3

44、),(7),(2),(6),(1),4,(5),(1),(7),調(diào)整后的可行流：,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,①,②,③,④,⑤,⑥,,,,,,,,,,8,14,5,6,3,3,8,10,7,6,,⑦,,,3,圖6－22,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),∞,4,4,1,5,第二輪標號：,增廣鏈μ＝μ＋＝{(

45、1,3)，(3,4)，(4,7) }，調(diào)整量為 θ＝min{∞，4，1，5}＝1,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,①,②,③,④,⑤,⑥,,,,,,,,,,8,14,5,6,3,3,8,10,7,6,,⑦,,,3,圖6－23,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),調(diào)整后得到可行流：

46、,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,①,②,③,④,⑤,⑥,,,,,,,,,8,14,5,6,3,3,8,10,7,6,,⑦,,,3,圖6－22,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),∞,3,1,4,第三輪標號：,增廣鏈μ＝μ＋＝{(1,3)，(3,6)，(6,4)，(4,7) }，調(diào)整量為

47、 θ＝min{∞，3，1，2，4}＝1,2,,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,①,②,③,④,⑤,⑥,,,,,,,,,8,14,5,6,3,3,8,10,7,6,,⑦,,,3,圖6－25,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),,調(diào)整后得到可行流：,6.3 最大流問題Maximal Flow Problem,

48、2024年3月27日星期三,①,②,③,④,⑤,⑥,,,,,,,,,8,14,5,6,3,3,8,10,7,6,,⑦,,,3,圖6－22,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),∞,2,第四輪標號：,v7得不到標號，不存在v1到 v7的增廣鏈，圖6-22所示的可行流是最大流，最大流量為 v＝f12+f13＝8+12=20,,4,6.3 最大

49、流問題Maximal Flow Problem,,2024年3月27日星期三,無向圖最大流標號算法,無向圖不存在后向弧，可以理解為所有弧都是前向弧，對一端vi已標號另一端vj未標號的邊只要滿足 Cij－fij>0 則vj就可標號（Cij－fij）,【例】求下圖v1到則v7標的最大流,7,(10),(6),(10),(8),(2),(3),(7),(6),(5),(13),(0),(13),∞,2,3,9,9,3,,,

50、,,,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,∞,3,7,7,1,,,,,V=29,,∞,,10,5,,6,,6,,6.3 最大流問題Maximal Flow Problem,1,,2024年3月27日星期三,截集 將圖G＝（V，E）的點集分割成兩部分,稱為一個截集，截集中所有弧的容量之和稱為截集的截量。,,下圖所示的截集為,6.3 最大流問題Maximal Flow Proble

51、m,2024年3月27日星期三,又如下圖所示的截集為,,,上圖所示的截集為,所有截量中此截量最小且等于最大流量，此截集稱為最小截集。,【定理】最大流量等于最小截集的截量。,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,6.3.4 最小費用流,滿足流量達到一個固定數(shù)使總費用最小，就是最小費用流問題。另一個問題是滿足流量到達最大使總費用最小，稱為最小費用最大流問題。,圖6－27是一個運輸網(wǎng)絡圖，

52、將工廠v1，v2及v3的物質(zhì)(數(shù)量不限)運往v6，v4和v5是中轉(zhuǎn)點，弧上的數(shù)字為（cij，dij)。,設弧（i,j）的單位流量費用為dij≥0，弧的容量為cij≥0,設可行流f的一條增廣鏈為μ，稱,,為增廣鏈μ的費用。第一個求和式是增廣鏈中前向弧的費用之和，第二個求和式是增廣鏈中后向弧的費用之和。d(μ)最小的增廣鏈稱為最小費用增廣鏈。,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,,,,,

53、,,(1)制定一個總運量等于15總運費最小的運輸方案；屬于最小費用流問題,(3,5),(6,4),(4,2),(3,4),(1,6),(2,3),(9,12),①,②,③,④,⑤,⑥,,,,,,,,,(12,3),(3,5),(6,4),(4,2),(3,4),(1,6),(2,3),(9,12),①,②,③,④,⑤,⑥,,,s,,,,(10,0),(6,0),(3,0),,圖6－27,圖6－28,(12,3),(2)制定使運量最大并且

54、總運費最小的運輸方案，屬于最小費用最大流問題,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,設給定的流量為v。最小費用流的標號算法步驟如下。第1步：取初始流量為零的可行流f(0)＝{0}，令網(wǎng)絡中所有弧的權(quán)等于dij得到一個賦權(quán)圖D，用Dijkstra算法求出最短路，這條最短路就是初始最小費用增廣鏈μ。,第2步：調(diào)整流量。在最小費用增廣鏈上調(diào)整流量的方法與前面最大流算法一樣，前向弧上令θj

55、＝cij－fij，后向弧上令θj＝fij，調(diào)整量為θ=min{θj}。調(diào)整后得到最小費用流f(k) ，流量為v(k)＝ v(k－1)＋θ，當v(k)＝v時計算結(jié)束，否則轉(zhuǎn)第3步繼續(xù)計算。,第3步：作賦權(quán)圖D并尋找最小費用增廣鏈。,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,(1) 對可行流f(k－1)的最小費用增廣鏈上的?。╥，j）作如下變動,,,第一種情形：當?。╥，j）上的流量滿足0&l

56、t;fij<cij時，在點vi與vj之間添加一條方向相反的?。╦，i），權(quán)為（－dij）。第二種情形：當?。╥，j）上的流量滿足fij＝cij時將?。╥，j）反向變?yōu)椋╦，i）, 權(quán)為（－bij）。不在最小費用增廣鏈上的弧不作任何變動，得到一個賦權(quán)網(wǎng)絡圖D。（2）求賦權(quán)圖D從發(fā)點的收點的最短路，如果最短路存在，則這條最短路就是f(k－1)的最小費用增廣鏈，轉(zhuǎn)第2步。賦權(quán)圖D的所有權(quán)非負時，可用Dijkstra算法求最短路，存

57、在負權(quán)時用Floyd算法。（3）如果賦權(quán)圖D不存在從發(fā)點到收點的最短路，說明v(k－1)已是最大流量，不存在流量等于v的流，計算結(jié)束。,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,【例6.11】對圖6－28，制定一個運量v＝15及運量最大總運費最小的運輸方案?！窘狻苛钏谢〉牧髁康扔诹?，得到初始可行流f(0)＝{0}，流量v(0)＝0，總運費d(f(0))=0。,,,,,,,3,5,4,

58、2,4,6,3,12,圖6－29,①,②,③,④,⑤,⑥,,,s,,,,0,0,0,(a) f (0)，賦權(quán)圖D0,最小費用增廣鏈μ1：s→①→④→⑥,見圖6－29(a),6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,調(diào)整量θ＝4，對f(0)＝{0}進行調(diào)整得到f(1)，括號（ ）內(nèi)的數(shù)字為弧的流量，網(wǎng)絡流量v(1)＝4，總運費 d

59、(f(1))＝0×4＋2×4＋3×4＝20如圖6－29(b)。,圖6－29,圖中：（cij，dij) ( fij ),6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,,,,,,,3,5,4,－2,4,6,3,12,圖6－29,①,②,③,④,⑤,⑥,,,s,,,,0,0,0,(c) f (1)，賦權(quán)圖D1,,－3,(3) v(1)＝4<15，沒有得到最小費

60、用流。在圖6－29(b)中，弧(s,1)和(4,6)滿足條件0<fij<cij，添加兩條邊(1,s)和(6,4)，權(quán)分別為“0”和“－3”，邊(1,s)可以去掉，弧(1,4)上有fij＝cij說明已飽和，將弧(1,4)反向變?yōu)?4,1)，權(quán)為“－2”，如圖6－29(c)。,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,,,,,,,(12,3),(3,5),(3,4),(1,6),(

61、2,3),(9,12),圖6－29,①,②,③,④,⑤,⑥,,,s,,,,(10,0),(6,0),(3,0),(d) f (2),(4),(4),(7),(6,4),(4,2),(3),(3),圖中：（cij，dij) ( fij ),用Floyd算法得到最小費用增廣鏈μ2：s→②→④→⑥，調(diào)整量θ＝3，調(diào)整后得到最小費用流f(2)，流量v(2)＝7，總運費 d(f(2))＝

62、2×4＋3×7＋5×3＝44如圖6－29(d)。,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,(4) v(2)＝7<15，對最小費用增廣鏈μ2上的弧進行調(diào)整，在圖6－29(c)中，弧(s,2)和(4,6)滿足條件0<fij<cij，添加兩條邊(2,s)和(6,4)，權(quán)分別為“0”和“－3”，邊(2,s)可以去掉，弧(6,4)已經(jīng)存在，弧(2,

63、4)上有fij＝cij說明已飽和，將弧(2,4)反向變?yōu)?4,2)，權(quán)為“－5”，如圖6－29(e)。,,,,,,,3,－5,4,－2,4,6,3,12,圖6－29,①,②,③,④,⑤,⑥,,,s,,,,0,0,0,(e) f (2)，賦權(quán)圖D2,,－3,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,用Floyd算法得到最小費用增廣鏈μ3：s→③→④→⑥，調(diào)整量θ＝1，調(diào)整后得到最小費用流f

64、(3)，流量v(3)＝8，總運費 d(f(3))＝2×4＋3×8＋5×3＋6×1＝53如圖6－29(f)。,,,,,,,(12,3),(3,5),(3,4),(1,6),(2,3),(9,12),圖6－29,①,②,③,④,⑤,⑥,,,s,,,,(10,0),(6,0),(3,0),(f) f (3),(4),(4),(8),(6,4),(4,2)

65、,(3),(3),(1),(1),6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,(5)類似地，得到圖6－29(g),,,,,,,3,－5,4,－2,4,－6,3,12,圖6－29,①,②,③,④,⑤,⑥,,,s,,,,0,0,0,(g) f (3)，賦權(quán)圖D3,,－3,,,,,,,(12,3),(3,5),(3,4),(1,6),(2,3),(9,12),圖6－29,①,②,③,④,⑤,⑥,

66、,,s,,,,(10,0),(6,0),(3,0),(h) f (4),(4),(4),(8),(6,4),(4,2),(3),(3),(3),(1),(2),(2),最小費用增廣鏈μ4：s→③→⑤→⑥，調(diào)整量θ＝2，流量v(4)＝10。見圖6－29(h),6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,最小費用增廣鏈μ5：s→①→⑤→⑥,調(diào)整量θ＝6，取θ＝5，流量v(5)＝v＝15得到滿

67、足，最小費用流見圖6－29(j)，問題1計算結(jié)束。,,,,,,,3,－5,4,－2,4,－6,－3,12,圖6－29,①,②,③,④,⑤,⑥,,,s,,,,0,0,0,(i) f (4)，賦權(quán)圖D4,,－3,,－12,,,,,,,(12,3),(3,5),(3,4),(1,6),(2,3),(9,12),圖6－29,①,②,③,④,⑤,⑥,,,s,,,,(10,0),(6,0),(3,0),(j) f (5),(9),(4),(8

68、),(6,4),(4,2),(3),(3),(3),(1),(2),(7),(5),(6)由圖6－29(g)及(h),得到圖 6－29(i),,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,(7)求最小費用最大流。對圖6－29(i)的最小費用增廣鏈μ5，取調(diào)整量θ＝6對流量調(diào)整，得到圖6－30(a)及賦權(quán)圖6－30(b),,,,,,,(12,3),(3,5),(3,4),(1,6),(2,