圖與網(wǎng)絡分析 最小費用最大流

圖與網(wǎng)絡分析圖與網(wǎng)絡分析 (Graph Theory and Network Analysis)圖論是運籌學的一個重要分支，它是建立圖論是運籌學的一個重要分支，它是建立和處理和處理離散類離散類數(shù)學模型的一個重要工具數(shù)學模型的一個重要工具。用圖。用圖論的方法往往能幫助人們解決一些用其它方法論的方法往往能幫助人們解決一些用其它方法難于解決的問題。圖論的發(fā)展可以追溯到難于解決的問題。圖論的發(fā)展可以追溯到1736年歐拉所發(fā)表的一篇關于解決著名的年歐拉所發(fā)表的一篇關于解決著名的“哥尼斯哥尼斯堡七橋問題堡七橋問題”的論文。由于的論文。由于這種數(shù)學模型和方這種數(shù)學模型和方法直觀形象，富有啟發(fā)性和趣味性，法直觀形象，富有啟發(fā)性和趣味性，深受人們深受人們的青睞。到目前為止，已被廣泛地應用于系統(tǒng)的青睞。到目前為止，已被廣泛地應用于系統(tǒng)工程、通訊工程、計算機科學及經(jīng)濟領域。傳工程、通訊工程、計算機科學及經(jīng)濟領域。傳統(tǒng)的物理、化學、生命科學也越來越廣泛地使統(tǒng)的物理、化學、生命科學也越來越廣泛地使用了圖論模型方法。用了圖論模型方法。圖與網(wǎng)絡分析圖與網(wǎng)絡分析(Graph Theory and Network Analysis)圖的基本知識圖的基本知識最短路問題最短路問題 樹及最小生成樹樹及最小生成樹最大流問題最大流問題最小費用最大流問題最小費用最大流問題第五節(jié)第五節(jié) 最小費用最大流問題最小費用最大流問題在考慮一個運輸系統(tǒng)中的運輸量的同時，往往還要在考慮一個運輸系統(tǒng)中的運輸量的同時，往往還要考慮運輸費用，希望給出從發(fā)貨站到收貨站的運輸考慮運輸費用，希望給出從發(fā)貨站到收貨站的運輸量最大、費用最小的運輸方案。這就是最小費用最量最大、費用最小的運輸方案。這就是最小費用最大流問題。大流問題。一、最小費用最大流的基本概念一、最小費用最大流的基本概念1 1、單位流量費用、單位流量費用設設 是一個網(wǎng)絡，對于每一條弧是一個網(wǎng)絡，對于每一條弧 ，除容量，除容量 外，還給定一個數(shù)外，還給定一個數(shù) ，稱作弧，稱作弧 上的單位流上的單位流量費用。量費用。DAa )(ac0)(aba2 2、帶費用的網(wǎng)絡、帶費用的網(wǎng)絡 規(guī)定了費用的網(wǎng)絡稱作規(guī)定了費用的網(wǎng)絡稱作帶費用的網(wǎng)絡帶費用的網(wǎng)絡，記作記作 ，其中，其中 是頂點集合，是頂點集合，是弧集合，是弧集合，是容量集合，是容量集合，是費用函數(shù)，是費用函數(shù)，為發(fā)為發(fā)點，點，為收點。為收點。,tsvvbcAVD VAcbsvtv設設 是是 上的可行流，稱上的可行流，稱 為可為可行流行流 的費用。的費用。D Aaafabfb)()()(ff3 3、可行流、可行流 的費用的費用 f4 4、流量為流量為v v 的最小費用流的最小費用流 把把D上所有流量等于上所有流量等于v 的可行流中費用最小的可行的可行流中費用最小的可行流稱作流稱作流量為流量為v 的最小費用流的最小費用流。5 5、最小費用最大流、最小費用最大流 當當 是是 中最大流的流量時，流量為中最大流的流量時，流量為 的最小的最小費用流稱作最小費用最大流。所謂最小費用最大費用流稱作最小費用最大流。所謂最小費用最大流問題（流問題（minimal costmaximal flow minimal costmaximal flow problemproblem）是求給定帶費用的網(wǎng)絡上的最小費用）是求給定帶費用的網(wǎng)絡上的最小費用最大流。最大流。*vD*v二、最小費用最大流的求法二、最小費用最大流的求法1 1、由圖編寫程序、由圖編寫程序2 2、由、由lingo8.0lingo8.0軟件求最小費用最大流軟件求最小費用最大流例例11 11 現(xiàn)需要將城市現(xiàn)需要將城市s s 的石油通過管道運送到城市的石油通過管道運送到城市t t,中間有中間有4 4個中轉站個中轉站v v1,1,v v2,2,v v3 3 和和v v4 4。由于輸油管道。由于輸油管道的長短不一或地質等原因，使每條管道上運輸費用的長短不一或地質等原因，使每條管道上運輸費用也不相同。城市與中轉站的連接以及管道的容量、也不相同。城市與中轉站的連接以及管道的容量、單位運費如下圖所示，求從城市單位運費如下圖所示，求從城市s s 到城市到城市t t 的最小的最小費最大流。費最大流。(2,1)(9,2)(5,5)v1v2v3v4 s t(8,2)(7,8)(9,3)(6,4)(5,6)(10,7)附程序附程序MODEL:sets:nodes/s,1,2,3,4,t/:d;arcs(nodes,nodes)/s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/:b,c,f;endsetsdata:d=14 0 0 0 0-14;b=2 8 5 2 3 1 6 4 7;c=8 7 5 9 9 2 5 6 10;enddatamin=sum(arcs:b*f);for(nodes(i)|i#ne#1#and#i#ne#size(nodes):sum(arcs(i,j):f(i,j)-sum(arcs(j,i):f(j,i)=d(i);sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);for(arcs:bnd(0,f,c);END s,ti,tivsi,vdAi,j,cfdfffbffiijijiAj,iVjjiAi,jVjijAi,jijij 0,)(0 t.smin)()()(其中其中Global optimal solution found at iteration:3 Objective value:205.0000 Variable Value Reduced Cost F(S,1)8.000000 -1.000000 F(S,2)6.000000 0.000000 F(1,2)1.000000 0.000000 F(1,3)7.000000 0.000000 F(2,4)9.000000 0.000000 F(3,2)2.000000 -2.000000 F(3,T)5.000000 -7.000000 F(4,3)0.000000 10.00000 F(4,T)9.000000 0.000000 (2,2)(9,7)(5,1)v1v2v3v4 s t(8,8)(7,6)(9,9)(6,0)(5,5)(10,9)例例12 12 求下圖帶費用的網(wǎng)絡求下圖帶費用的網(wǎng)絡D D 中中V VS S 到到V VT T 的最小費用的最小費用最大流。圖中弧旁的數(shù)字是最大流。圖中弧旁的數(shù)字是b bijij,c,cijij。解解1、先求其最大流、先求其最大流MODEL:sets:nodes/s,1,2,3,t/;arcs(nodes,nodes)/s,1 s,2 s,3 1,t 2,1 2,t 2,3 3,t/:c,f;endsetsdata:c=15 15 10 10 5 10 10 10;enddatamax=flow;for(nodes(i)|i#ne#1#and#i#ne#size(nodes):sum(arcs(i,j):f(i,j)-sum(arcs(j,i):f(j,i)=0);sum(arcs(i,j)|i#eq#1:f(i,j)=flow;for(arcs:bnd(0,f,c);ENDGlobal optimal solution found at iteration:4 Objective value:30.00000 F(S,1)10.00000 0.000000 F(S,2)10.00000 0.000000 F(S,3)10.00000 0.000000 F(1,T)10.00000 -1.000000 F(2,1)0.000000 0.000000 F(2,T)10.00000 -1.000000 F(2,3)0.000000 0.000000 F(3,T)10.00000 -1.00000030)(*fv2 2、再求其最小費用、再求其最小費用MODEL:sets:nodes/s,1,2,3,t/:d;arcs(nodes,nodes)/s,1 s,2 s,3 1,t 2,1 2,t 2,3 3,t/:b,c,f;endsetsdata:d=30 0 0 0 -30;b=4 2 6 5 5 8 1 5;c=15 15 10 10 5 10 10 10;enddatamin=sum(arcs:b*f);for(nodes(i)|i#ne#1#and#i#ne#size(nodes):sum(arcs(i,j):f(i,j)-sum(arcs(j,i):f(j,i)=d(i);sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);for(arcs:bnd(0,f,c);END Global optimal solution found at iteration:6 Objective value:285.0000 F(S,1)10.00000 0.000000 F(S,2)15.00000 -3.000000 F(S,3)5.000000 0.000000 F(1,T)10.00000 -4.000000 F(2,1)0.000000 6.000000 F(2,T)10.00000 0.000000 F(2,3)5.000000 0.000000 F(3,T)10.00000 -2.00000030)(*fv285)(*fb例例 1313 某貿易公司在每個月的月初訂購貨物，訂購某貿易公司在每個月的月初訂購貨物，訂購后能及時到貨、進庫并供應市場。貨物與當月售出后能及時到貨、進庫并供應市場。貨物與當月售出，則不必付存貯費。當月未出售的貨物，盤點后轉，則不必付存貯費。當月未出售的貨物，盤點后轉入下月，每件要付庫存費入下月，每件要付庫存費6 6個單位。庫存的最大貯量個單位。庫存的最大貯量是是120120件。預測件。預測1 1月到月到6 6月的訂購價格和需求量如下：月的訂購價格和需求量如下：月份月份 1 2 3 4 5 6 1 2 3 4 5 6需求量需求量50 55 50 45 40 3050 55 50 45 40 30價格價格70 67 65 80 84 8870 67 65 80 84 88假設假設1 1月初的庫存量為零，要求月初的庫存量為零，要求6 6月底的庫存量也為月底的庫存量也為零，不允許缺貨。試做出零，不允許缺貨。試做出6 6個月的訂貨計劃，使成個月的訂貨計劃，使成本最低。本最低。解：解：用用 表示第表示第 個月初進貨后的狀態(tài)，個月初進貨后的狀態(tài)，。表示進貨，表示進貨，表示銷售。于是，可用網(wǎng)絡來描表示銷售。于是，可用網(wǎng)絡來描述這個問題。但是在這個網(wǎng)絡中，頂點述這個問題。但是在這個網(wǎng)絡中，頂點 具有容量具有容量，即倉庫的最大存貯量。如圖，即倉庫的最大存貯量。如圖7-227-22所示，所示，ivi61 isvtviv弧旁的數(shù)字是弧旁的數(shù)字是 ，其中，其中 是單位成本（是單位成本（訂購價格或庫存費），訂購價格或庫存費），是貨物的最大流通是貨物的最大流通量（訂購、銷售或轉入下月）。頂點內的數(shù)字量（訂購、銷售或轉入下月）。頂點內的數(shù)字是它的容量（最大庫存量）。是它的容量（最大庫存量）。于是，我們的問于是，我們的問題是要求這個網(wǎng)絡的最小費用的最大流。題是要求這個網(wǎng)絡的最小費用的最大流。這個這個網(wǎng)絡可以化成與它等價的不帶頂點容量的網(wǎng)絡網(wǎng)絡可以化成與它等價的不帶頂點容量的網(wǎng)絡，如圖，如圖7-237-23所示。所示。它的最小費用最大流（在圖它的最小費用最大流（在圖7-237-23中用帶括號的數(shù)字標在弧旁）就給出了所中用帶括號的數(shù)字標在弧旁）就給出了所需的最優(yōu)訂購方案：需的最優(yōu)訂購方案：1 1月至月至6 6月的訂購量分別是月的訂購量分別是5050，5555，120120，0 0，1515，3030。（見下頁附圖）（見下頁附圖）ijijbc,ijbijc練習練習求下列網(wǎng)絡的最小費用最大流及其流量和費求下列網(wǎng)絡的最小費用最大流及其流量和費用。圖中弧旁的數(shù)字是用。圖中弧旁的數(shù)字是 。ijijcb,附答案：附答案：5)(fv37)(fba a 流量流量,費用費用 18)(fv171)(fbb b 流量流量,費用費用 總總 結結1 1、賦權圖賦權圖 最小生成樹最小生成樹避圈法避圈法。最短路最短路matlabmatlab。2 2、賦權有向圖賦權有向圖 最短路最短路matlabmatlab。3 3、網(wǎng)絡網(wǎng)絡 最大流最大流lingo8.0lingo8.04 4、帶費用的網(wǎng)絡帶費用的網(wǎng)絡 最小費用最大流最小費用最大流lingo8.0lingo8.0),(EVG ),(AVD )v,vc,(ts，AVD ,tsvvbcAVD Thanks