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