經(jīng)濟(jì)學(xué)Ch6網(wǎng)絡(luò)模型課件

1、 運(yùn) 籌 學(xué) Operations ResearchChapter 6 網(wǎng)絡(luò)模型Network Modeling6.1 最小(支撐)樹問題 Minimal (Spanning) Tree Problem6.2 最短路問題 Shortest Path Problem 6.3 最大流問題 Maximal Flow Problem5v1v2v3v4v5v6843752618圖61運(yùn)籌學(xué)中研究的圖具有下列特征：（1）用點(diǎn)表示研究對(duì)象，用邊（有方向或無方向）表示對(duì)象之間某種關(guān)系。（2）強(qiáng)調(diào)點(diǎn)與點(diǎn)之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀。（3）每條邊上都賦有一個(gè)權(quán)，其圖稱為賦權(quán)圖。實(shí)際中權(quán)可以代表兩點(diǎn)之間

2、的距離、費(fèi)用、利潤(rùn)、時(shí)間、容量等不同的含義。（4）建立一個(gè)網(wǎng)絡(luò)模型，求最大值或最小值。邊用vi,vj表示或簡(jiǎn)記為i，j，集合記為如圖61所示，點(diǎn)集合記為邊上的數(shù)字稱為權(quán)，記為wvi,vj、wi，j或wij，集合記為連通的賦權(quán)圖稱為網(wǎng)絡(luò)圖，記為 GV，E，W5v1v2v3v4v5v6843752618圖616.1 最小(支撐)樹問題 Minimal (Spanning)Tree Problem6.1.1樹的概念 一個(gè)無圈并且連通的無向圖稱為樹圖或簡(jiǎn)稱樹(Tree)。組織機(jī)構(gòu)、家譜、學(xué)科分支、因特網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)及高壓線路網(wǎng)絡(luò)等都能表達(dá)成一個(gè)樹圖 。 可以證明：（1）一棵樹的邊數(shù)等于點(diǎn)數(shù)減1；（2）

3、在樹中任意兩個(gè)點(diǎn)之間添加一條邊就形成圈；（3）在樹中去掉任意一條邊圖就變?yōu)椴贿B通。 在一個(gè)連通圖G中，取部分邊連接G的所有點(diǎn)組成的樹稱為G的部分樹或支撐樹(Spanning Tree )。圖62是圖61的部分樹。 v1v2v3v4v5v64321圖6276.1 最小樹問題 Minimal tree problem6.1.2 最小部分樹將網(wǎng)絡(luò)圖G邊上的權(quán)看作兩點(diǎn)間的長(zhǎng)度（距離、費(fèi)用、時(shí)間），定義G的部分樹T的長(zhǎng)度等于T中每條邊的長(zhǎng)度之和，記為C(T)。 G的所有部分樹中長(zhǎng)度最小的部分樹稱為最小部分樹，或簡(jiǎn)稱為最小樹。 最小部分樹可以直接用作圖的方法求解，常用的有破圈法和加邊法。破圈法：任取一圈，

4、去掉圈中最長(zhǎng)邊，直到無圈。6.1 最小樹問題 Minimal tree problem5v1v2v3v4v5v6843752618圖61【例6-1】用破圈法求圖61的最小樹。 圖64圖64就是圖61的最小部分樹，最小樹長(zhǎng)為 C(T)=4+3+5+2+1=15。當(dāng)一個(gè)圈中有多個(gè)相同的最長(zhǎng)邊時(shí)，不能同時(shí)都去掉，只能去掉其中任意一條邊。最小部分樹有可能不唯一，但最小樹的長(zhǎng)度相同 6.1 最小樹問題 Minimal tree problem加邊法：取圖G的n個(gè)孤立點(diǎn)v1，v2， vn作為一個(gè)支撐圖，從最短邊開始往支撐圖中添加，見圈回避，直到連通（有n1條邊） v1v2v3v4v5v643521圖65在

5、圖65中，如果添加邊v1, v2就形成圈v1, v2, v4，這時(shí)就應(yīng)避開添加邊v1, v2，添加下一條最短邊v3, v6。破圈法和加邊法得到樹的形狀可能不一樣，但最小樹的長(zhǎng)度相等 5v1v3v515v2v4v684375268Min C(T)=156.1 最小樹問題 Minimal tree problem【例6-2】用加邊法求圖61的最小樹圖61下一節(jié)：最短路問題1.樹、支撐樹、最小支撐樹的概念2.掌握求最小樹的方法： （1）破圈法 （2）加邊法6.1 最小樹問題 Minimal tree problem6.2 最短路問題 Shortest Path Problem最短路問題在實(shí)際中具有廣

6、泛的應(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 Problem 610123214675811165圖669【例6-3】圖66中的權(quán)cij表示vi到vj的距離（費(fèi)用、時(shí)間），從v1修一條公路或架設(shè)一條高壓線到v7，如何選擇一條路線使距離

7、最短，建立該問題的網(wǎng)絡(luò)數(shù)學(xué)模型。6.2 最短路問題 Shortest Path Problem 【解】 設(shè)xij為選擇弧(i，j)的狀態(tài)變量，選擇弧(i，j)時(shí)xij1，不選擇弧(i，j)時(shí)xij0，得到最短路問題的網(wǎng)絡(luò)模型：6.2 最短路問題 Shortest Path Problem 6.2.2有向圖的狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法點(diǎn)標(biāo)號(hào)：b(j) 起點(diǎn)vs到點(diǎn)vj的最短路長(zhǎng)；邊標(biāo)號(hào)：k(i，j)=b(i)+cij，步驟：(1)令起點(diǎn)的標(biāo)號(hào)；b(s)0。先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點(diǎn)是vs ,終點(diǎn)是vt ,以vi為起點(diǎn)vj為終點(diǎn)的弧記為（i，j）,距離為cij (2)找出所有v

8、i已標(biāo)號(hào)vj未標(biāo)號(hào)的弧集合 B=(i，j)，如果這樣的弧不存在或vt已標(biāo)號(hào)則計(jì)算結(jié)束；(3)計(jì)算集合B中弧k(i，j)=b(i)+cij的標(biāo)號(hào)(4)選一個(gè)點(diǎn)標(biāo)號(hào) 返回到第(2)步。6.2 最短路問題 Shortest Path Problem 610123214675811165圖6690610129209186161217162432182929【例6-4】用Dijkstra算法求圖66 所示v1到v7的最短路及最短路長(zhǎng) v1 到v7的最短路為：p17=v1, v2, v3, v5, v7，最短路長(zhǎng)為L(zhǎng)17=29 6.2 最短路問題 Shortest Path Problem 14從上例知，

9、只要某點(diǎn)已標(biāo)號(hào)，說明已找到起點(diǎn)vs到該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號(hào)，求出vs到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)vj不能標(biāo)號(hào)，說明vs不可達(dá)vj 。6.2.3 無向圖最短路的求法無向圖最短路的求法只將上述步驟（2）改動(dòng)一下即可。點(diǎn)標(biāo)號(hào)：b(i) 起點(diǎn)vs到點(diǎn)vj的最短路長(zhǎng)；邊標(biāo)號(hào)：k(i，j)=b(i)+cij，步驟：(1)令起點(diǎn)的標(biāo)號(hào)；b(s)0。(3)計(jì)算集合B中邊標(biāo)號(hào)：ki，j=b(i)+cij(4)選一個(gè)點(diǎn)標(biāo)號(hào): 返回到第(2)步。 (2)找出所有一端vi已標(biāo)號(hào)另一端vj未標(biāo)號(hào)的邊集合 B=i，j如果這樣的邊不存在或vt已標(biāo)號(hào)則計(jì)算結(jié)束；6.2 最短路問題 Shortest

10、Path Problem 【例6-5】求圖6-10所示v1到各點(diǎn)的最短路及最短距離4526178393261216180452231039612641166188122482418所有點(diǎn)都已標(biāo)號(hào)，點(diǎn)上的標(biāo)號(hào)就是v1到該點(diǎn)的最短距離，最短路線就是紅色的鏈。圖6-106.2 最短路問題 Shortest Path Problem 6.2.4 最短路的Floyd算法 Floyd算法基本步驟 :(1)寫出vi一步到達(dá)vj 的距離矩陣 ，L1也是一步到達(dá)的最短距離矩陣。如果vi 與vj 之間沒有邊關(guān)聯(lián)，則令cij=+ (2)計(jì)算二步最短距離矩陣。設(shè)vi 到vj 經(jīng)過一個(gè)中間點(diǎn)vr 兩步到達(dá)vj，則vi到

11、vj的最短距離為最短距離矩陣記為 (3)計(jì)算k步最短距離矩陣。設(shè) vi經(jīng)過中間點(diǎn)vr 到達(dá)vj，vi 經(jīng)過k1步到達(dá)點(diǎn)vr 的最短距離為 ，vr 經(jīng)過k1步到達(dá)點(diǎn)vj 的最短距離為 ，則 vi 經(jīng)k步 到達(dá)vj 的最短距離為(6-1)6.2 最短路問題 Shortest Path Problem 最短距離矩陣記為 (4)比較矩陣Lk與Lk1，當(dāng)LkLk1時(shí)得到任意兩點(diǎn)間的最短距離矩陣Lk。設(shè)圖的點(diǎn)數(shù)為n并且cij0，迭代次數(shù)k由式(6-3) 估計(jì)得到。 (6-2)(6-3)6.2 最短路問題 Shortest Path Problem 6345212789326121610【例6-6】圖6-1

12、4是一張8個(gè)城市的鐵路交通圖，鐵路部門要制作一張兩兩城市間的距離表。這個(gè)問題實(shí)際就是求任意兩點(diǎn)間的最短路問題?！窘狻?(1)依據(jù)圖6-14,寫出任意兩點(diǎn)間一步到達(dá)距離表L1。見表6-1所示。本例n=8， ，因此計(jì)算到L3 圖6-146.2 最短路問題 Shortest Path Problem v1v2v3v4v5v6v7v8v10654v260328v330716v45209123v58790106v641202v73102012v8166120表6-1 最短距離表 L16.2 最短路問題 Shortest Path Problem 表6-2 最短距離表L2v1v2v3v4v5v6v7v8v

13、106951446v26032810514v3930571713v4525095315v514879012106v64105120214v765173102012v8141315614120計(jì)算說明：L(2)ij等于表6-1中第i行與第j列對(duì)應(yīng)元素相加取最小值。如 6.2 最短路問題 Shortest Path Problem 表6-3計(jì)算示例: 等于表6-2中第i行與第j列對(duì)應(yīng)元素相加取最小值。例如，v3經(jīng)過三步（最多三個(gè)中間點(diǎn)4條邊）到達(dá)v6的最短距離是表6-3 最短距離表L3v1v2v3v4v5v6v7v8v10695144618v2603287514v39305710813v45250

14、95315v514879012106v647105120214v76583102012v8181413156141206.2 最短路問題 Shortest Path Problem 【例6-7】求圖615中任意兩點(diǎn)間的最短距離。【解】圖615是一個(gè)混合圖，有3條邊的權(quán)是負(fù)數(shù),有兩條邊無方向。依據(jù)圖615,寫出任意兩點(diǎn)間一步到達(dá)距離表L1。表中第一列的點(diǎn)表示弧的起點(diǎn)，第一行的點(diǎn)表示弧的終點(diǎn)，無方向的邊表明可以互達(dá)，見表6-4所示。計(jì)算過程見表6-56-7。445743271028圖615156.2 最短路問題 Shortest Path Problem 表6-4一步到達(dá)距離表L1v1v2v3v4

15、v5v6v7v105 4v2042v34072v440107v5103v6508v7206.2 最短路問題 Shortest Path Problem 表6-7 最短距離表L4v1v2v3v4v5v6v7v10593419v2204-2635v364021072v44990857v5-14720-35v69141051308v786241290經(jīng)計(jì)算L4L5，L4是最優(yōu)表。表6-7不是對(duì)稱表，vi到vj與vj到vi的最短距離不一定相等。對(duì)于有負(fù)權(quán)圖情形，公式(6-3)失效。 6.2 最短路問題 Shortest Path Problem 6.2.4 最短路應(yīng)用舉例6.2 最短路問題 Short

16、est Path Problem 【例6-8】設(shè)備更新問題。企業(yè)在使用某設(shè)備時(shí)，每年年初可購(gòu)置新設(shè)備，也可以使用一年或幾年后賣掉重新購(gòu)置新設(shè)備。已知4年年初購(gòu)置新設(shè)備的價(jià)格分別為2.5、2.6、2.8和3.1萬元。設(shè)備使用了14年后設(shè)備的殘值分別為2、1.6、1.3和1.1萬元，使用時(shí)間在14年內(nèi)的維修保養(yǎng)費(fèi)用分別為0.3、0.8、1.5和2.0萬元。試確定一個(gè)設(shè)備更新策略，在下例兩種情形下使4年的設(shè)備購(gòu)置和維護(hù)總費(fèi)用最小。（1）第4年年末設(shè)備一定處理掉；（2）第4年年末設(shè)備不處理。 【解】畫網(wǎng)絡(luò)圖。用點(diǎn)(1,i,j)表示第1年年初購(gòu)置設(shè)備使用到第i年年初更新，經(jīng)過若干次更新使用到第j年年初，

17、第1年年初和第5年年初分別用及表示。使用過程用弧連接起來，弧上的權(quán)表示總費(fèi)用(購(gòu)置費(fèi)維護(hù)費(fèi)殘值)，如圖616所示 6.2 最短路問題 Shortest Path Problem 6圖616(1,2,3)(1,4)(1,3,4)(1,2,4)(1,2,3,4)(1,2)(1,3)第一年第二年第三年第四年5.10.91.50.73.62.81.7-0.21.91.12.10.3-0.6-0.6網(wǎng)絡(luò)圖616說明：如圖中點(diǎn)(1,3)表示第1年購(gòu)置設(shè)備使用兩年到第3年年初更新購(gòu)置新設(shè)備，這時(shí)有2種更新方案，使用1年到第4年年初、使用2年到第5年年初,更新方案用弧表示，點(diǎn)（1,2,3）表示第1年購(gòu)置設(shè)備使

18、用一年到第二年年初又更新，使用一年到第三年初再更新，這時(shí)仍然有2種更新方案，使用1年到第4年年初和使用2年到第5年年初。6.2 最短路問題 Shortest Path Problem 點(diǎn)（1,3）和點(diǎn)（1,2,3）不能合并成一個(gè)點(diǎn)，雖然都是第三年年初購(gòu)置新設(shè)備，購(gòu)置費(fèi)用相同，但殘值不同。點(diǎn)(1,3)的殘值等于1.6(使用了兩年)，點(diǎn)(1,2,3)的殘值等于2(使用了一年)。點(diǎn)（1,3）到點(diǎn)（1,3,4）的總費(fèi)用為第三年的購(gòu)置費(fèi)第一年的維護(hù)費(fèi)設(shè)備使用兩年后的殘值2.8+0.31.6=1.5點(diǎn)（1,3）到點(diǎn)的總費(fèi)用為第三年的購(gòu)置費(fèi)第一年的維護(hù)費(fèi)第二年的維護(hù)費(fèi)設(shè)備使用兩年后的殘值第四年末的殘值2.8

19、+0.3+0.81.61.6=0.7。費(fèi)用表見教材表6-8。6圖616(1,2,3)(1,4)(1,3,4)(1,2,4)(1,2,3,4)(1,2)(1,3)第一年第二年第三年第四年5.10.91.50.73.62.81.7-0.21.91.12.10.3-0.6-0.66.2 最短路問題 Shortest Path Problem （2）第四年末不處理設(shè)備：將圖616第4年的數(shù)據(jù)換成表6-8最后一列，求點(diǎn)到點(diǎn)的最短路。最短路線為：(1,2)(1,2,3)，最短路長(zhǎng)為5.6，即總費(fèi)用為5.6萬元。更新方案與第一種情形相同。 （1）第四年末處理設(shè)備：求點(diǎn)到點(diǎn)的最短路。用Dijkstra算法得到

20、最短路線為：(1,2)(1,2,3)，最短路長(zhǎng)為4。 4年總費(fèi)用最小的設(shè)備更新方案是：第1年購(gòu)置設(shè)備使用1年，第2年更新設(shè)備使用1年后賣掉，第3年購(gòu)置設(shè)備使用2年到第4年年末，4年的總費(fèi)用為4萬元。 【例6-9】服務(wù)網(wǎng)點(diǎn)設(shè)置問題。以圖614為例，現(xiàn)提出這樣一個(gè)問題，在交通網(wǎng)絡(luò)中建立一個(gè)快速反應(yīng)中心，應(yīng)選擇哪一個(gè)城市最好。類似地，在一個(gè)網(wǎng)絡(luò)中設(shè)置一所學(xué)校、醫(yī)院、消防站、購(gòu)物中心，還有廠址選擇、總部選址、公司銷售中心選址等問題都屬于最佳服務(wù)網(wǎng)點(diǎn)設(shè)置問題。 【解】 對(duì)于不同的問題，尋求最佳服務(wù)點(diǎn)有不同的標(biāo)準(zhǔn)。像圖614只有兩點(diǎn)間的距離，可以采用“使最大服務(wù)距離達(dá)到最小”為標(biāo)準(zhǔn)，計(jì)算步驟如下。 第一步

21、：利用Floyd算法求出任意兩點(diǎn)之間的最短距離表（表63）。 第二步：計(jì)算最短距離表中每行的最大距離的最小值，即 6.2 最短路問題 Shortest Path Problem 引用例6-6計(jì)算的結(jié)果，對(duì)表63每行取最大值再取最小值，見表69倒數(shù)第二列。v1v2v3v4v5v6v7v8Max Lij總運(yùn)量v10695144618183220v2603287514142465v39305710813132955v4525095315152450v514879012106143780v647105120214142960v76583102012122560v81814131561412018504

22、0產(chǎn)量8050704030356065表69表69中倒數(shù)第二列最小值為12，位于第7行，則v7為網(wǎng)絡(luò)的中心，最佳服務(wù)點(diǎn)應(yīng)設(shè)置在v7。 6.2 最短路問題 Shortest Path Problem 如果每個(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)量的最小值對(duì)應(yīng)的點(diǎn)就是最佳服務(wù)點(diǎn)。表69中最后一行是點(diǎn)vj的產(chǎn)量，將各行的最小距離分別乘以產(chǎn)量求和得到總運(yùn)量，例如，08065018653220，見表69最后一列，最小運(yùn)量為2450，最佳服務(wù)點(diǎn)應(yīng)設(shè)置在v4。 6.2 最短路問題 Shortest P

23、ath Problem 下一節(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è)置問題6.3 最大流問題Maximal Flow Problem6.3 最大流問題Maximal Flow Problem6.3.1 基本概念8145633810763圖6184圖618所示的網(wǎng)絡(luò)圖中定義了一個(gè)發(fā)點(diǎn)v1，稱為源(source，supply node），定義了一個(gè)收點(diǎn)v7，稱為匯（sink，demand node）

24、，其余點(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)輸量最大。 設(shè)cij為?。╥，j）的容量，fij為?。╥，j）的流量。容量是弧（i，j）單位時(shí)間內(nèi)的最大通過能力，流量是?。╥，j）單位時(shí)間內(nèi)的實(shí)際通過量，流量的集合f=fij稱為網(wǎng)絡(luò)的流。發(fā)點(diǎn)到收點(diǎn)的總流量記為v=val(f)，v也是網(wǎng)絡(luò)的流量。 圖618最大流問題的線性規(guī)劃數(shù)學(xué)模型為6.

25、3 最大流問題Maximal Flow Problem滿足下例3個(gè)條件的流fij 的集合 f = fij 稱為可行流 發(fā)點(diǎn)vs流出的總流量等于流入收點(diǎn)vt的總流量6.3 最大流問題Maximal Flow Problem鏈：從發(fā)點(diǎn)到收點(diǎn)的一條路線（弧的方向不一定都同向）稱為鏈。從發(fā)點(diǎn)到收點(diǎn)的方向規(guī)定為鏈的方向。前向?。号c鏈的方向相同的弧稱為前向弧。后向弧：與鏈的方向相反的弧稱為后向弧。增廣鏈: 設(shè) f 是一個(gè)可行流，如果存在一條從vs到vt的鏈，滿足：1.所有前向弧上fij0則該鏈稱為增廣鏈前向弧后向弧容量流量這是一條增廣鏈84469（5）(2)(3)(4)(6)6.3 最大流問題Maxima

26、l Flow Problem步驟如下：第二步：對(duì)點(diǎn)進(jìn)行標(biāo)號(hào)找一條增廣鏈。（1）發(fā)點(diǎn)標(biāo)號(hào)（）（2）選一個(gè)點(diǎn) vi 已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查： A如果弧的方向向前（前向?。┎⑶矣衒ij0，則vj標(biāo)號(hào): jfji當(dāng)收點(diǎn)已得到標(biāo)號(hào)時(shí)，說明已找到增廣鏈，依據(jù)vi 的標(biāo)號(hào)反向跟蹤得到一條增廣鏈。當(dāng)收點(diǎn)不能得到標(biāo)號(hào)時(shí)，說明不存在增廣鏈，計(jì)算結(jié)束。第一步： 找出第一個(gè)可行流，例如所有弧的流量fij =06.3.2 Ford-Fulkerson標(biāo)號(hào)算法6.3 最大流問題Maximal Flow Problem第三步：調(diào)整流量（1）求增廣鏈上點(diǎn)vi 的標(biāo)號(hào)的最小值，得到調(diào)整量 （2）調(diào)整流量

27、得到新的可行流f1，去掉所有標(biāo)號(hào)，返回到第二步從發(fā)點(diǎn)重新標(biāo)號(hào)尋找增廣鏈，直到收點(diǎn)不能標(biāo)號(hào)為止 【定理6.1】 可行流f是最大流的充分必要條件是不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈 6.3 最大流問題Maximal Flow Problem8145633810763圖619(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)【例6-10】求圖618發(fā)點(diǎn)v1到收點(diǎn)v7的最大流及最大流量【解】給定初始可行流，見圖6-196.3 最大流問題Maximal Flow Problem8145633810763圖620(b)(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(

28、7)2337第一輪標(biāo)號(hào)：c12f12,v2標(biāo)號(hào)2cij=fij，v4、v5不能標(biāo)號(hào)后向弧f320,v3標(biāo)號(hào)3=f32增廣鏈(1,2)，(3,2)，(3,4)，(4,7) ,+=(1,2)，(3,4)，(4,7),=(3，2)，調(diào)整量為增廣鏈上點(diǎn)標(biāo)號(hào)的最小值min，2，3，3，726.3 最大流問題Maximal Flow Problem8145633810763圖621(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)調(diào)整后的可行流：6.3 最大流問題Maximal Flow Problem8145633810763圖622(10)(8)(1)(6)(3)(7)(2)

29、(6)(1)4(5)(1)(7)4415第二輪標(biāo)號(hào)：Cij=fij，v4、v5不能標(biāo)號(hào)，返回到v3增廣鏈(1,3)，(3,4)，(4,7) ，調(diào)整量為 min，4，1，516.3 最大流問題Maximal Flow Problem8145633810763圖623(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)調(diào)整后得到可行流：6.3 最大流問題Maximal Flow Problem8145633810763圖622(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)314第三輪標(biāo)號(hào)：增廣鏈(1,3)，(3,6)，(6,4)，(4,7) ，

30、調(diào)整量為 min，3，1，2，4126.3 最大流問題Maximal Flow Problem8145633810763圖625(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)調(diào)整后得到可行流：6.3 最大流問題Maximal Flow Problem8145633810763圖622(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)2第四輪標(biāo)號(hào)：v7得不到標(biāo)號(hào)，不存在v1到 v7的增廣鏈，圖6-22所示的可行流是最大流，最大流量為 vf12+f138+12=20Cij=fij，v4、v5不能標(biāo)號(hào)Cij=fij，v4、v6不能標(biāo)號(hào)46.3

31、最大流問題Maximal Flow Problem無向圖最大流標(biāo)號(hào)算法無向圖不存在后向弧，可以理解為所有弧都是前向弧，對(duì)一端vi已標(biāo)號(hào)另一端vj未標(biāo)號(hào)的邊只要滿足 Cijfij0 則vj就可標(biāo)號(hào)（Cijfij）【例】求下圖v1到則v7標(biāo)的最大流71292085148691316(10)(6)(10)(8)(2)(3)(7)(6)(5)(13)(0)(13)239936.3 最大流問題Maximal Flow Problem71292085148691316(12)(6)(10)(8)(4)(3)(7)(6)(7)(13)(2)(15)377171292085148691316(12)(7)(1

32、0)(8)(4)(3)(7)(6)(8)(13)(3)(16)V=29105666.3 最大流問題Maximal Flow Problem1截集 將圖G（V，E）的點(diǎn)集分割成兩部分稱為一個(gè)截集，截集中所有弧的容量之和稱為截集的截量。68441226796411322306下圖所示的截集為6.3 最大流問題Maximal Flow Problem68441226796401322106又如下圖所示的截集為上圖所示的截集為所有截量中此截量最小且等于最大流量，此截集稱為最小截集?！径ɡ怼孔畲罅髁康扔谧钚〗丶慕亓俊?.3 最大流問題Maximal Flow Problem6.3.4 最小費(fèi)用流滿足流

33、量達(dá)到一個(gè)固定數(shù)使總費(fèi)用最小，就是最小費(fèi)用流問題。另一個(gè)問題是滿足流量到達(dá)最大使總費(fèi)用最小，稱為最小費(fèi)用最大流問題。圖627是一個(gè)運(yùn)輸網(wǎng)絡(luò)圖，將工廠v1，v2及v3的物質(zhì)(數(shù)量不限)運(yùn)往v6，v4和v5是中轉(zhuǎn)點(diǎn)，弧上的數(shù)字為（cij，dij)。設(shè)?。╥,j）的單位流量費(fèi)用為dij0，弧的容量為cij0 設(shè)可行流f的一條增廣鏈為，稱 為增廣鏈的費(fèi)用。第一個(gè)求和式是增廣鏈中前向弧的費(fèi)用之和，第二個(gè)求和式是增廣鏈中后向弧的費(fèi)用之和。d()最小的增廣鏈稱為最小費(fèi)用增廣鏈。6.3 最大流問題Maximal Flow Problem (1)制定一個(gè)總運(yùn)量等于15總運(yùn)費(fèi)最小的運(yùn)輸方案；屬于最小費(fèi)用流問題(3

34、,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)圖627圖628(12,3) (2)制定使運(yùn)量最大并且總運(yùn)費(fèi)最小的運(yùn)輸方案，屬于最小費(fèi)用最大流問題6.3 最大流問題Maximal Flow Problem設(shè)給定的流量為v。最小費(fèi)用流的標(biāo)號(hà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)整流量的方法與前

35、面最大流算法一樣，前向弧上令jcijfij，后向弧上令jfij，調(diào)整量為=minj。調(diào)整后得到最小費(fèi)用流f(k) ，流量為v(k) v(k1)，當(dāng)v(k)v時(shí)計(jì)算結(jié)束，否則轉(zhuǎn)第3步繼續(xù)計(jì)算。第3步：作賦權(quán)圖D并尋找最小費(fèi)用增廣鏈。6.3 最大流問題Maximal Flow Problem(1) 對(duì)可行流f(k1)的最小費(fèi)用增廣鏈上的?。╥，j）作如下變動(dòng) 第一種情形：當(dāng)?。╥，j）上的流量滿足0fijcij時(shí)，在點(diǎn)vi與vj之間添加一條方向相反的弧（j，i），權(quán)為（dij）。第二種情形：當(dāng)?。╥，j）上的流量滿足fijcij時(shí)將?。╥，j）反向變?yōu)椋╦，i）, 權(quán)為（bij）。不在最小費(fèi)用增廣

36、鏈上的弧不作任何變動(dòng)，得到一個(gè)賦權(quán)網(wǎng)絡(luò)圖D。（2）求賦權(quán)圖D從發(fā)點(diǎn)的收點(diǎn)的最短路，如果最短路存在，則這條最短路就是f(k1)的最小費(fèi)用增廣鏈，轉(zhuǎn)第2步。賦權(quán)圖D的所有權(quán)非負(fù)時(shí)，可用Dijkstra算法求最短路，存在負(fù)權(quán)時(shí)用Floyd算法。（3）如果賦權(quán)圖D不存在從發(fā)點(diǎn)到收點(diǎn)的最短路，說明v(k1)已是最大流量，不存在流量等于v的流，計(jì)算結(jié)束。6.3 最大流問題Maximal Flow Problem【例6-11】對(duì)圖628，制定一個(gè)運(yùn)量v15及運(yùn)量最大總運(yùn)費(fèi)最小的運(yùn)輸方案?！窘狻苛钏谢〉牧髁康扔诹?，得到初始可行流f(0)0，流量v(0)0，總運(yùn)費(fèi)d(f(0)=0。354246312圖629s

37、000(a) f (0)，賦權(quán)圖D0最小費(fèi)用增廣鏈1：s,見圖629(a) 6.3 最大流問題Maximal Flow Problem 調(diào)整量4，對(duì)f(0)0進(jìn)行調(diào)整得到f(1)，括號(hào)（ ）內(nèi)的數(shù)字為弧的流量，網(wǎng)絡(luò)流量v(1)4，總運(yùn)費(fèi) d(f(1)04243420如圖629(b)。圖629(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)s(10,0)(6,0)(3,0)(b) f (1)(4)(4)(4)(6,4)(4,2)圖中：（cij，dij) ( fij )6.3 最大流問題Maximal Flow Problem354246312圖629s000(c) f (1)，賦

38、權(quán)圖D13(3) v(1)415，沒有得到最小費(fèi)用流。在圖629(b)中，弧(s,1)和(4,6)滿足條件0fijcij，添加兩條邊(1,s)和(6,4)，權(quán)分別為“0”和“3”，邊(1,s)可以去掉，弧(1,4)上有fijcij說明已飽和，將弧(1,4)反向變?yōu)?4,1)，權(quán)為“2”，如圖629(c)。 6.3 最大流問題Maximal Flow Problem(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖629s(10,0)(6,0)(3,0)(d) f (2)(4)(4)(7)(6,4)(4,2)(3)(3)圖中：（cij，dij) ( fij )用Floyd算法得到

39、最小費(fèi)用增廣鏈2：s，調(diào)整量3，調(diào)整后得到最小費(fèi)用流f(2)，流量v(2)7，總運(yùn)費(fèi) d(f(2)24375344如圖629(d)。6.3 最大流問題Maximal Flow Problem(4) v(2)715，對(duì)最小費(fèi)用增廣鏈2上的弧進(jìn)行調(diào)整，在圖629(c)中，弧(s,2)和(4,6)滿足條件0fijcij，添加兩條邊(2,s)和(6,4)，權(quán)分別為“0”和“3”，邊(2,s)可以去掉，弧(6,4)已經(jīng)存在，弧(2,4)上有fijcij說明已飽和，將弧(2,4)反向變?yōu)?4,2)，權(quán)為“5”，如圖629(e)。 354246312圖629s000(e) f (2)，賦權(quán)圖D236.3 最

40、大流問題Maximal Flow Problem用Floyd算法得到最小費(fèi)用增廣鏈3：s，調(diào)整量1，調(diào)整后得到最小費(fèi)用流f(3)，流量v(3)8，總運(yùn)費(fèi) d(f(3)2438536153如圖629(f)。 (12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖629s(10,0)(6,0)(3,0)(f) f (3)(4)(4)(8)(6,4)(4,2)(3)(3)(1)(1)6.3 最大流問題Maximal Flow Problem(5)類似地，得到圖629(g)354246312圖629s000(g) f (3)，賦權(quán)圖D33(12,3)(3,5)(3,4)(1,6)(2,3)

41、(9,12)圖629s(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。見圖629(h) 6.3 最大流問題Maximal Flow Problem最小費(fèi)用增廣鏈5：s,調(diào)整量6，取5，流量v(5)v15得到滿足，最小費(fèi)用流見圖629(j)，問題1計(jì)算結(jié)束。 354246312圖629s000(i) f (4)，賦權(quán)圖D4312(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖629s(10,0)(6,0)(3,0)(j) f (5)(9)(4)(8)(6

42、,4)(4,2)(3)(3)(3)(1)(2)(7)(5)(6)由圖629(g)及(h),得到圖 629(i), 6.3 最大流問題Maximal Flow Problem(7)求最小費(fèi)用最大流。對(duì)圖629(i)的最小費(fèi)用增廣鏈5，取調(diào)整量6對(duì)流量調(diào)整，得到圖630(a)及賦權(quán)圖630(b) (12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖630s(10,0)(6,0)(3,0)(a) f (5)(10)(4)(8)(6,4)(4,2)(3)(3)(3)(1)(2)(8)(6)6.3 最大流問題Maximal Flow Problem354246312圖630s000(b)

43、f (5)，賦權(quán)圖D5312(8)圖630(b)的最小費(fèi)用增廣鏈6：s，6.3 最大流問題Maximal Flow Problem(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖630s(10,0)(6,0)(3,0)(c) f (6)(10)(4)(8)(6,4)(4,2)(4)(3)(3)(1)(2)(9)(6)(1)調(diào)整量1，流量v(6)17，最小費(fèi)用流為f(6)，見圖630(c)。6.3 最大流問題Maximal Flow Problem賦權(quán)圖見圖630（d）。圖630(d)不存在從vs發(fā)點(diǎn)到v6的最短路，則圖630(c)的流就是最小費(fèi)用最大流，最大流量v=17，最小的總運(yùn)費(fèi)為d(f)=24465341613238129195354246312圖630s000(d) f (6)，賦權(quán)圖