圖與網(wǎng)絡(luò)分析

1、 圖與網(wǎng)絡(luò)分析 (Graph Theory and Network Analysis)1 圖論是運(yùn)籌學(xué)的一個(gè)重要分支，它是建立和處理離散類數(shù)學(xué)模型的一個(gè)重要工具。用圖論的方法往往能幫助人們解決一些用其它方法難于解決的問題。圖論的發(fā)展可以追溯到1736年歐拉所發(fā)表的一篇關(guān)于解決著名的“哥尼斯堡七橋問題”的論文。由于這種數(shù)學(xué)模型和方法直觀形象，富有啟發(fā)性和趣味性，深受人們的青睞。到目前為止，已被廣泛地應(yīng)用于系統(tǒng)工程、通訊工程、計(jì)算機(jī)科學(xué)及經(jīng)濟(jì)領(lǐng)域。傳統(tǒng)的物理、化學(xué)、生命科學(xué)也越來越廣泛地使用了圖論模型方法。2圖與網(wǎng)絡(luò)分析 (Graph Theory and Network Analysis)圖的基

2、本知識最短路問題 樹及最小生成樹最大流問題最小費(fèi)用最大流問題3第五節(jié) 最小費(fèi)用最大流問題在考慮一個(gè)運(yùn)輸系統(tǒng)中的運(yùn)輸量的同時(shí)，往往還要考慮運(yùn)輸費(fèi)用，希望給出從發(fā)貨站到收貨站的運(yùn)輸量最大、費(fèi)用最小的運(yùn)輸方案。這就是最小費(fèi)用最大流問題。一、最小費(fèi)用最大流的基本概念1、單位流量費(fèi)用設(shè) 是一個(gè)網(wǎng)絡(luò)，對于每一條弧 ，除容量 外，還給定一個(gè)數(shù) ，稱作弧 上的單位流量費(fèi)用。2、帶費(fèi)用的網(wǎng)絡(luò)4 規(guī)定了費(fèi)用的網(wǎng)絡(luò)稱作帶費(fèi)用的網(wǎng)絡(luò)，記作 ，其中 是頂點(diǎn)集合， 是弧集合， 是容量集合， 是費(fèi)用函數(shù)， 為發(fā)點(diǎn)， 為收點(diǎn)。設(shè) 是 上的可行流，稱 為可行流 的費(fèi)用。 3、可行流 的費(fèi)用 4、流量為v 的最小費(fèi)用流 把D上所

3、有流量等于v 的可行流中費(fèi)用最小的可行流稱作流量為v 的最小費(fèi)用流。55、最小費(fèi)用最大流 當(dāng) 是 中最大流的流量時(shí)，流量為 的最小費(fèi)用流稱作最小費(fèi)用最大流。所謂最小費(fèi)用最大流問題（minimal costmaximal flow problem）是求給定帶費(fèi)用的網(wǎng)絡(luò)上的最小費(fèi)用最大流。二、最小費(fèi)用最大流的求法1、由圖編寫程序2、由lingo8.0軟件求最小費(fèi)用最大流6例11 現(xiàn)需要將城市s 的石油通過管道運(yùn)送到城市t,中間有4個(gè)中轉(zhuǎn)站v1,v2,v3 和v4。由于輸油管道的長短不一或地質(zhì)等原因，使每條管道上運(yùn)輸費(fèi)用也不相同。城市與中轉(zhuǎn)站的連接以及管道的容量、單位運(yùn)費(fèi)如下圖所示，求從城市s 到城

4、市t 的最小費(fèi)最大流。(2,1)(9,2) (5,5)v1v2v3v4 s t( 8,2) (7,8)(9,3)(6,4) (5,6) (10,7)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 #n

5、e#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);END8Global 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.00

6、0000 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)9例12 求下圖帶費(fèi)用的網(wǎng)絡(luò)D 中VS 到VT 的最小費(fèi)用最大流。圖中弧旁的數(shù)字是bij,cij。解1、先求其最大流10MODEL:se

7、ts: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

8、 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.000000112、再求其最小費(fèi)用MODEL:sets:no

9、des/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(

10、1);for(arcs:bnd(0,f,c);END12 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)

11、 10.00000 -2.00000013例 13 某貿(mào)易公司在每個(gè)月的月初訂購貨物，訂購后能及時(shí)到貨、進(jìn)庫并供應(yīng)市場。貨物與當(dāng)月售出，則不必付存貯費(fèi)。當(dāng)月未出售的貨物，盤點(diǎn)后轉(zhuǎn)入下月，每件要付庫存費(fèi)6個(gè)單位。庫存的最大貯量是120件。預(yù)測1月到6月的訂購價(jià)格和需求量如下：月份 1 2 3 4 5 6需求量50 55 50 45 40 30價(jià)格70 67 65 80 84 88假設(shè)1月初的庫存量為零，要求6月底的庫存量也為零，不允許缺貨。試做出6個(gè)月的訂貨計(jì)劃，使成本最低。14解： 用 表示第 個(gè)月初進(jìn)貨后的狀態(tài)， 。 表示進(jìn)貨， 表示銷售。于是，可用網(wǎng)絡(luò)來描述這個(gè)問題。但是在這個(gè)網(wǎng)絡(luò)中，頂點(diǎn) 具有容量，即倉庫的最大存貯量。如圖7-22所示，15弧旁的數(shù)字是 ，其中 是單位成本（訂購價(jià)格或庫存費(fèi)）， 是貨物的最大流通量（訂購、銷售或轉(zhuǎn)入下月）。頂點(diǎn)內(nèi)的數(shù)字是它的容量（最大庫存量）。于是，我們的問題是要求這個(gè)網(wǎng)絡(luò)的最小費(fèi)用的最大流。這個(gè)網(wǎng)絡(luò)可以化成與它等價(jià)的不帶頂點(diǎn)容量的網(wǎng)絡(luò)，如圖7-23所示。它的最小費(fèi)用最大流（在圖7-23中用帶括號的數(shù)字標(biāo)在弧旁）就給出了所需的最優(yōu)訂購方案：1月至6月的訂購量分別