[教育]運(yùn)籌學(xué)ppt課件ch6網(wǎng)絡(luò)模型

1、運(yùn) 籌 學(xué)   Operations  Research,,,Chapter 6 網(wǎng)絡(luò)模型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,運(yùn)籌學(xué)中研究的圖具有下列特征：（1）用點(diǎn)表示研究對象，用邊（有方向或無方向）表示對象之間某種關(guān)系。（2）強(qiáng)調(diào)點(diǎn)與點(diǎn)之間的關(guān)聯(lián)關(guān)系，不

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

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樹的概念,一個(gè)無圈并且連通的無向圖稱為樹圖或簡稱樹(Tree)。組織機(jī)構(gòu)、家譜、學(xué)科分支、因特網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)及高壓線路網(wǎng)絡(luò)等都能表達(dá)成一個(gè)

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

6、、費(fèi)用、時(shí)間），定義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。當(dāng)一個(gè)圈中有多個(gè)相同的最長邊時(shí)，不能同時(shí)都去掉，只能去掉其中任意一條邊。最小部分樹有可能不唯一，但最小樹的長度相同,6.1 最小樹問題 Minimal tree problem,2024年3月27日星期三,加

8、邊法：取圖G的n個(gè)孤立點(diǎn)｛v1，v2，…， vn}作為一個(gè)支撐圖，從最短邊開始往支撐圖中添加，見圈回避，直到連通（有n－1條邊）,,,,,,,v1,v2,v3,v4,v5,v6,圖6－5,在圖6－5中，如果添加邊[v1, v2]就形成圈｛v1, v2, v4｝，這時(shí)就應(yīng)避開添加邊[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日星期三,最短路問題在實(shí)際中具有廣泛

10、的應(yīng)用，如管道鋪設(shè)、線路選擇等問題，還有些如設(shè)備更新、投資等問題也可以歸結(jié)為求最短路問題,求最短路有兩種算法： 一是求從某一點(diǎn)至其它各點(diǎn)之間最短離的狄克斯屈拉(Dijkstra)算法 另一種是求網(wǎng)絡(luò)圖上任意兩點(diǎn)之間最短路的Floyd(弗洛伊德)矩陣算法。,最短路問題，就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路,6.2.1最短路問題的網(wǎng)絡(luò)模型,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的距離（費(fèi)用、時(shí)間），從v1修一條公路或架設(shè)一條高壓線到v7，如何選擇一條路線使距離最短，建立該問題的網(wǎng)絡(luò)數(shù)學(xué)模型。,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,【解】 設(shè)xi

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

13、起點(diǎn)是vs ,終點(diǎn)是vt ,以vi為起點(diǎn)vj為終點(diǎn)的弧記為（i，j）,距離為cij,(2)找出所有vi已標(biāo)號vj未標(biāo)號的弧集合 B={(i，j)}，如果這樣的弧不存在或vt已標(biāo)號則計(jì)算結(jié)束；,(3)計(jì)算集合B中弧k(i，j)=b(i)+cij的標(biāo)號,(4)選一個(gè)點(diǎn)標(biāo)號 返回到第(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日星期三,從上例知，只要某點(diǎn)已標(biāo)號，說明已找到起點(diǎn)vs到該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號，求出vs到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)vj不能標(biāo)號，說明vs不可達(dá)vj 。,6.2.3 無向圖最短路的求法,無向圖最短路的求法只將上述步驟（2）改動(dòng)一下即可。,點(diǎn)標(biāo)號：b(i) —起點(diǎn)vs到點(diǎn)vj的最短路長；,邊標(biāo)號：k(i，j)=b(i)+cij，,步驟：(1)令起點(diǎn)的標(biāo)號；b(s)＝0。,(3)計(jì)算集合B中邊標(biāo)號：k[i

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

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

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

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

20、路問題。,【解】 (1)依據(jù)圖6-14,寫出任意兩點(diǎn)間一步到達(dá)距離表L1。見表6.1所示。本例n=8， ，因此計(jì)算到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,計(jì)算說明：L(2)ij等于表

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

22、意兩點(diǎn)間的最短距離。【解】圖6－15是一個(gè)混合圖，有3條邊的權(quán)是負(fù)數(shù),有兩條邊無方向。依據(jù)圖6－15,寫出任意兩點(diǎn)間一步到達(dá)距離表L1。表中第一列的點(diǎn)表示弧的起點(diǎn)，第一行的點(diǎn)表示弧的終點(diǎn)，無方向的邊表明可以互達(dá)，見表6-4所示。計(jì)算過程見表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一步到達(dá)距離表L1,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,表6-7 最短距離表L4,經(jīng)計(jì)算L4＝L5，L4是最優(yōu)表。表6-7不是對稱表，vi到vj與vj到vi的最短距離不一定相等。對于有負(fù)權(quán)圖情形，公式(6.3)失效。,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,6.2.4 最短路應(yīng)用

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

25、年的設(shè)備購置和維護(hù)總費(fèi)用最小。（1）第4年年末設(shè)備一定處理掉；（2）第4年年末設(shè)備不處理。,【解】畫網(wǎng)絡(luò)圖。用點(diǎn)(1,i,…,j)表示第1年年初購置設(shè)備使用到第i年年初更新，經(jīng)過若干次更新使用到第j年年初，第1年年初和第5年年初分別用①及⑤表示。使用過程用弧連接起來，弧上的權(quán)表示總費(fèi)用(購置費(fèi)＋維護(hù)費(fèi)－殘值)，如圖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)絡(luò)圖6－16說明：如圖中點(diǎn)(1,3)表示第1年購置設(shè)備使用兩年到第3年年初更新購置新設(shè)備，這時(shí)有2種更新方案，使用1年到第4年年初

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

28、，點(diǎn)(1,2,3)的殘值等于2(使用了一年)。點(diǎn)（1,3）到點(diǎn)（1,3,4）的總費(fèi)用為第三年的購置費(fèi)＋第一年的維護(hù)費(fèi)－設(shè)備使用兩年后的殘值＝2.8+0.3－1.6=1.5點(diǎn)（1,3）到點(diǎn)⑤的總費(fèi)用為第三年的購置費(fèi)＋第一年的維護(hù)費(fèi)＋第二年的維護(hù)費(fèi)－設(shè)備使用兩年后的殘值－第四年末的殘值＝2.8+0.3+0.8－1.6－1.6=0.7。,費(fèi)用表見教材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）第四年末不處理設(shè)備：將圖6－16第4年的數(shù)據(jù)換成表6-8

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

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

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

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

34、0，最佳服務(wù)點(diǎn)應(yīng)設(shè)置在v4。,6.2 最短路問題 Shortest Path Problem,2024年3月27日星期三,下一節(jié)：最大流問題,6.2 最短路問題 Shortest Path Problem,1.最短路的概念及應(yīng)用。2.有向圖、無向圖一點(diǎn)到各點(diǎn)最短路的Dijkstra算法3.任意兩點(diǎn)最短路的Floyd算法4.本節(jié)介紹了兩個(gè)應(yīng)用：設(shè)備更新問題和最佳服務(wù)點(diǎn)設(shè)置問題,作業(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)絡(luò)圖中定義了一個(gè)發(fā)點(diǎn)v1，稱為源(source，supply node），定義了一個(gè)收點(diǎn)v7，稱為匯（sink，demand node）

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

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

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

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

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

41、直到收點(diǎn)不能標(biāo)號為止,【定理6.1】 可行流f是最大流的充分必要條件是不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈,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ā)點(diǎn)v1到收點(diǎn)

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,第一輪標(biāo)號：,c12>f12,v2標(biāo)號2,增

43、廣鏈μ＝{(1,2)，(3,2)，(3,4)，(4,7) },μ+={(1,2)，(3,4)，(4,7)},μ－={(3，2)}，調(diào)整量為增廣鏈上點(diǎn)標(biā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,第二輪標(biāo)號：,增廣鏈μ＝μ＋＝{(

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,第三輪標(biāo)號：,增廣鏈μ＝μ＋＝{(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,第四輪標(biāo)號：,v7得不到標(biāo)號，不存在v1到 v7的增廣鏈，圖6-22所示的可行流是最大流，最大流量為 v＝f12+f13＝8+12=20,,4,6.3 最大

49、流問題Maximal Flow Problem,,2024年3月27日星期三,無向圖最大流標(biāo)號算法,無向圖不存在后向弧，可以理解為所有弧都是前向弧，對一端vi已標(biāo)號另一端vj未標(biāo)號的邊只要滿足 Cij－fij>0 則vj就可標(biāo)號（Cij－fij）,【例】求下圖v1到則v7標(biāo)的最大流,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）的點(diǎn)集分割成兩部分,稱為一個(gè)截集，截集中所有弧的容量之和稱為截集的截量。,,下圖所示的截集為,6.3 最大流問題Maximal Flow Proble

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

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

53、,,(1)制定一個(gè)總運(yùn)量等于15總運(yùn)費(fèi)最小的運(yùn)輸方案；屬于最小費(fèi)用流問題,(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)制定使運(yùn)量最大并且

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

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

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

57、在負(fù)權(quán)時(shí)用Floyd算法。（3）如果賦權(quán)圖D不存在從發(fā)點(diǎn)到收點(diǎn)的最短路，說明v(k－1)已是最大流量，不存在流量等于v的流，計(jì)算結(jié)束。,6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,【例6.11】對圖6－28，制定一個(gè)運(yùn)量v＝15及運(yùn)量最大總運(yùn)費(fèi)最小的運(yùn)輸方案?！窘狻苛钏谢〉牧髁康扔诹?，得到初始可行流f(0)＝{0}，流量v(0)＝0，總運(yùn)費(fèi)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,最小費(fèi)用增廣鏈μ1：s→①→④→⑥,見圖6－29(a),6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,調(diào)整量θ＝4，對f(0)＝{0}進(jìn)行調(diào)整得到f(1)，括號（ ）內(nèi)的數(shù)字為弧的流量，網(wǎng)絡(luò)流量v(1)＝4，總運(yùn)費(fèi) 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，沒有得到最小費(fèi)

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算法得到最小費(fèi)用增廣鏈μ2：s→②→④→⑥，調(diào)整量θ＝3，調(diào)整后得到最小費(fèi)用流f(2)，流量v(2)＝7，總運(yùn)費(fèi) 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，對最小費(fèi)用增廣鏈μ2上的弧進(jìn)行調(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算法得到最小費(fèi)用增廣鏈μ3：s→③→④→⑥，調(diào)整量θ＝1，調(diào)整后得到最小費(fèi)用流f

64、(3)，流量v(3)＝8，總運(yùn)費(fèi) 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),最小費(fèi)用增廣鏈μ4：s→③→⑤→⑥，調(diào)整量θ＝2，流量v(4)＝10。見圖6－29(h),6.3 最大流問題Maximal Flow Problem,2024年3月27日星期三,最小費(fèi)用增廣鏈μ5：s→①→⑤→⑥,調(diào)整量θ＝6，取θ＝5，流量v(5)＝v＝15得到滿

67、足，最小費(fèi)用流見圖6－29(j)，問題1計(jì)算結(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)求最小費(fèi)用最大流。對圖6－29(i)的最小費(fèi)用增廣鏈μ5，取調(diào)整量θ＝6對流量調(diào)整，得到圖6－30(a)及賦權(quán)圖6－30(b),,,,,,,(12,3),(3,5),(3,4),(1,6),(2,