1、1,趙明霞 山西大學(xué)經(jīng)濟(jì)與管理學(xué)院,管理運(yùn)籌學(xué) 模型與方法,第8章網(wǎng)絡(luò)規(guī)劃,2,8.1圖 8.2最小樹問題 8.3最短路問題 8.4 最大流問題 8.5 最小費(fèi)用流問題,2,3,圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對象之間的關(guān)系。 例如：在一個人群中，對相互認(rèn)識這個關(guān)系我們可以用圖來表示，圖8-1就是一個表示這種關(guān)系的圖。,G = (V, E) 點(diǎn)集 V= v1,v2,v3,.,vm=1,2,3,m 邊集 E= eij=(vi,vj)= eij=(i, j),8.1圖,4,當(dāng)然圖論不僅僅是要描述對象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點(diǎn)的相對位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲

2、直，對于反映對象之間的關(guān)系并不是重要的，如對趙等七人的相互認(rèn)識關(guān)系我們也可以用圖8-2來表示，可見圖論中的圖與幾何圖、工程圖是不一樣的。,結(jié)（端）點(diǎn)：vi, vj 關(guān)聯(lián)邊，e3 點(diǎn)相鄰(同一條邊), v1,v3 邊相鄰(同一個端點(diǎn)), e1,e3 環(huán)，e2 多重邊, e3, e4 簡單圖：無環(huán)無多重邊,5,圖8-2,次：結(jié)點(diǎn)的關(guān)聯(lián)邊數(shù)目 d(v3)=4，偶點(diǎn) d(v4)=3，奇點(diǎn) d(v2)=5 d(v6)=0，孤立點(diǎn) d(v5)=1，懸掛邊,鏈： 閉鏈：v1 v2 v3 v1 開鏈：v1 v2 v3 邊不同，簡單鏈：v3 v1 v2 v3 v4 v5 邊不同且結(jié)點(diǎn)不同，初等鏈：v1 v2 v

3、3 v4 v5 圈：初等閉鏈，且至少有3個不同結(jié)點(diǎn)，v1 v2 v3 v1,6,圖8-2,7,如果我們把上面例子中的“相互認(rèn)識”關(guān)系改為“認(rèn)識” 的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個帶箭頭的聯(lián)線，稱為弧。圖8-3就是一個反映這七人“認(rèn)識”關(guān)系的圖。相互認(rèn)識用兩條反向的弧表示。,8,連通圖：若任何兩個不同的點(diǎn)之間，至少存在一條鏈，則G為連通圖。 若 ,則G是G的子圖，G是G的母圖 若 ,則G是G的真子圖， 若 ,則G是G的支撐圖。,無向圖：由點(diǎn)和邊構(gòu)成的圖，記作G =（V，E）。 有向圖：由點(diǎn)和弧構(gòu)成的圖，記作D =（V，A）。 無向圖是有向圖的基礎(chǔ)圖G(D

4、) 路：弧（邊）的方向與鏈的方向一致。 回路：若路的第一個點(diǎn)和最后一個點(diǎn)相同，則該路為回路。 開路 賦權(quán)圖：對一個圖的每一條邊（弧）(vi,vj)，相應(yīng)地有一個數(shù)wij，則稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。 網(wǎng)絡(luò)：賦權(quán)連通圖,9,2020/9/5,10,例8-3：柯尼斯堡七橋問題,歐拉回路：經(jīng)過每邊且僅一次 厄尼斯堡七橋問題、郵路問題 充要條件：圖中無奇點(diǎn) 哈密爾頓回路：經(jīng)過每點(diǎn)且僅一次 貨郎擔(dān)問題、快遞送貨問題,8個節(jié)目，首尾為A, H或H,A；10名演員，不連續(xù)出演。如何安排？,11,例8-4 節(jié)目排序問題,12,13,樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。,圖

5、8-4中，(a)就是一個樹，而(b)因為圖中有圈所以就不是樹， (c)因為不連通所以也不是樹。,8.2最小樹問題,14,給了一個無向圖G=(V,E)，我們保留G的所有點(diǎn)，而刪掉部分G的邊或者說保留一部分G的邊，所獲得的圖G，稱之為G的支撐(生成)圖。在圖8-4中，(b)和(c)都是(a)的支撐圖。 如果圖G的一個支撐圖還是一個樹，則稱這個支撐圖為支撐（生成）樹，在圖8-5中，(c)就是(a)的支撐樹。 最小支撐（生成）樹問題就是指在一個賦權(quán)的連通的無向圖G中找出一個支撐樹，并使得這個支撐樹的所有邊的權(quán)數(shù)之和為最小。,(a),(b),(c),樹的基本性質(zhì) 任意兩點(diǎn)間有且僅有一條鏈 不相鄰兩點(diǎn)間添

6、加一條邊，有且僅有一個圈 任意去掉一條邊，得不連通圖 存在懸掛點(diǎn) 邊數(shù)+1=結(jié)點(diǎn)數(shù),15,最小樹的基本性質(zhì) 定理8-1：任意結(jié)點(diǎn)i的最小關(guān)聯(lián)邊（i, k）必在最小樹中。 定理8-2：點(diǎn)集V的非空子集 ,連結(jié)兩子集的最小邊（i, k）必在最小樹中。,16,17,1、破圈算法 步驟： （1）在給定的賦權(quán)的連通圖上任找一個圈。 （2）在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。 （3）如果所余下的圖已不包含圈，則計算結(jié)束，所余下的圖即為最小樹，否則返回第1步。,18,例8-5,2、避圈算法 步驟： （1）任找一個點(diǎn)S，其余各點(diǎn)就是 。 （2）在連

7、接S與 的所有邊中，選擇權(quán)數(shù)最小的邊(i, k)； （3）將最小邊(i, k)的另一個端點(diǎn)移入S； （4）若 則停止，否則返回（2）。,19,20,例8-5,21,最短路問題： 對一個網(wǎng)絡(luò)中的指定的兩個點(diǎn)Vs(起點(diǎn))和Vt（終點(diǎn)）找到一條從 Vs 到 Vt 的路，使得這條路上所有弧（邊）的權(quán)數(shù)總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有?。罚┑臋?quán)數(shù)總和被稱為從Vs到Vt的距離。,8.3最短路問題,22,適用于：每條?。ㄟ叄┑馁x權(quán)數(shù)wij 0 優(yōu)點(diǎn)：能夠求出某點(diǎn)至各點(diǎn)的最短路 基本思想： P(j)從始點(diǎn)s到j(luò)點(diǎn)的最短路長，稱為固定標(biāo)號； T(j)從始點(diǎn)s到j(luò)點(diǎn)的最短路長上界，稱為

8、臨時標(biāo)號。 基本步驟,1、狄氏標(biāo)號法（Dijkstra）,23,例8-6,24,例8-7 設(shè)備更新問題。某廠擬于明年購置一臺設(shè)備，以后每年年初都要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費(fèi)，但維修費(fèi)用就高了。請設(shè)計一個今后五年之內(nèi)的更新設(shè)備的計劃，使得五年內(nèi)購置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。,25,解： 將問題轉(zhuǎn)化為最短路問題，如下圖： 用vi表示“第i年年初購進(jìn)一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進(jìn)的設(shè)備一直使用到第j年年初。,26,把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。,2

9、7,適用于：每條弧的賦權(quán)數(shù)wij- 優(yōu)點(diǎn)：通用有效方法 （直接）距離矩陣,2、矩陣摹乘法,例8-8,各點(diǎn)至某點(diǎn)的最短路 求和取小,28,29,例8-8（各點(diǎn)至5的最短路）,某點(diǎn)至各點(diǎn)的最短路 求和取小,30,31,例8-8（1至各點(diǎn)的最短路）,各點(diǎn)間的最短距離,32,例8-9 （求各村間的最短距離）,33,直接距離矩陣,34,網(wǎng)絡(luò)中心（r點(diǎn)） 網(wǎng)絡(luò)重心（r點(diǎn)）,35,36,例8-10 （1） 商店建在哪個村，使各村都離他較近？ （2）小學(xué)應(yīng)建在哪個村，使各村小學(xué)生走路總里程最少？,37,（1）,38,（2）,39,8.4最大流問題,最大流問題：給一個帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在

10、不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。 一、最大流的數(shù)學(xué)模型 例8.1 某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點(diǎn)，這個網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（vi,vj）的流量cij（容量）也是不一樣的。cij的單位為萬加侖/小時。如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷地 v7運(yùn)送石油，問每小時能運(yùn)送多少加侖石油？,40,我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型： 設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上的總的流量為F，則有：,41,在這個線性規(guī)劃模型中，其 約束條件中的前6個方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點(diǎn)的流出量必

11、須等于收點(diǎn)的總流入量； 其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量必須等于總流出量。 后面幾個約束條件表示對每一條弧(vi,vj)的流量fij要滿足流量的可行條件，應(yīng)小于等于弧(vi,vj)的容量cij，并大于等于零，即0fij cij。 我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流 fij稱之為可行流（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。,42,二、最大流問題網(wǎng)絡(luò)圖論的解法 對網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方向，如下圖: (a)和 (b)、(c)和(d)的意義相同。 用以上方法對例6的圖的容量標(biāo)號作改進(jìn)，得下圖,vi,vj

12、,vi,vj,cij,0,（a）,（b）,cij,cij,vi,vj,（cji）,（c）,vi,vj,cij,cji,（d）,43,求最大流的基本算法 （1）找出一條從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。 （2）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf。 （3）在這條路上，減少每一條弧的順流容量pf ，同時增加這些弧的逆流容量pf，返回步驟（1）。,44,用此方法對例8.1求解： 第一次迭代：選擇路為v1 v4 v7 ?；。?v4 , v7 ）的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：,4

13、5,第二次迭代：選擇路為v1 v2 v5 v7 ?；。?v2 , v5 ）的順流容量為3，決定了pf=3，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：,46,第三次迭代：選擇路為v1 v4 v6 v7 。?。?v4 , v6 ）的順流容量為1，決定了pf=1，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：,47,第四次迭代：選擇路為v1 v4 v3 v6 v7 。?。?v3 , v6 ）的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：,48,第五次迭代：選擇路為v1 v2 v3 v5 v7 ?；。?v2 , v3 ）的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：,49,經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點(diǎn)到收點(diǎn)的一

14、條路，路上的每一條弧順流容量都大于零，運(yùn)算停止。得到最大流量為10。 最大流量圖如下圖：,例8-11、8-12,50,51,最小費(fèi)用最大流問題：給了一個帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對每一條?。╲i,vj），除了給出容量cij外，還給出了這條弧的單位流量的費(fèi)用bij，要求一個最大流F，并使得總運(yùn)送費(fèi)用最小。,8.5最小費(fèi)用（最大）流問題,52,一、最小費(fèi)用最大流的數(shù)學(xué)模型 例8.2 由于輸油管道的長短不一，所以在例8.1中每段管道（ vi,vj ）除了有不同的流量限制cij外，還有不同的單位流量的費(fèi)用bij ，cij的單位為萬加侖/小時， bij的單位為百元/萬加侖。如圖。從采地 v1向銷地 v7運(yùn)送石油，

15、怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最小？求出最大流量和最小費(fèi)用。,(6,6),(3,4),(5,7),(2,5),(2,4),（2,3）,(4,4),(1,3),(2,8),（3,2）,v1,v2,v5,v7,v4,v3,v6,(6,3),53,這個最小費(fèi)用最大流問題也是一個線性規(guī)劃的問題。 解：我們用線性規(guī)劃來求解此題，可以分兩步走。 第一步，先求出此網(wǎng)絡(luò)圖中的最大流量F，這已在例6中建立了線性規(guī)劃的模型，通過管理運(yùn)籌學(xué)軟件已經(jīng)獲得結(jié)果。 第二步，在最大流量F的所有解中，找出一個最小費(fèi)用的解，我們來建立第二步中的線性規(guī)劃模型如下： 仍然設(shè)弧（vi,vj）上的流量為fij，這時已知網(wǎng)

16、絡(luò)中最大流量為F，只要在例6的約束條件上，再加上總流量必須等于F的約束條件：f12+f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標(biāo)函數(shù)顯然是求其流量的最小費(fèi)用: 由此得到線性規(guī)劃模型如下：,54,55,如果我們把例8.2的問題改為： 每小時運(yùn)送6萬加侖的石油從采地v1到銷地v7最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了一個最小費(fèi)用流的問題。 一般來說，所謂最小費(fèi)用流的問題就是：在給定了收點(diǎn)和發(fā)點(diǎn)并對每條弧(vi,vj)賦權(quán)以容量cij及單位費(fèi)用bij的網(wǎng)絡(luò)中，求一個給定值f的流量的最小費(fèi)用，這個給定值f的流量應(yīng)小于等于最大流量F，否則無解。 求最小費(fèi)用流的問題的線性規(guī)劃的模型只要把最小費(fèi)用

17、最大流模型中的約束條件中的發(fā)點(diǎn)流量F改為f即可。 在例8.1中只要把f12+f14=F改為f12+f14=f=6得到了最小費(fèi)用流的線性規(guī)劃的模型了。,56,二、最小費(fèi)用最大流的網(wǎng)絡(luò)圖論解法 對網(wǎng)絡(luò)上?。╲i,vj）的（cij,bij）的表示作如下改動，用(b)來表示(a)。 用上述方法對例8.2中的圖形進(jìn)行改進(jìn)，得圖如下頁：,vi,vj,vi,vj,（cij,bij ）,（0,-bij ）,（a）,（b）,（cij,bij ）,（cij,bij ）,vi,vj,（cji,bji ）,（cij,bij ）,vi,vj,（cji,bji ）,（0,-bji),（0,-bji),（c）,（d）,57

18、,求最小費(fèi)用最大流的基本算法 在對弧的標(biāo)號作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費(fèi)用最大流的基本算法與求最大流的基本算法完全一樣，不同的只是在步驟（1）中要選擇一條總的單位費(fèi)用最小的路，而不是包含邊數(shù)最小的路。,58,用上述方法對例8.2求解： 第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后總流量為1，總費(fèi)用10。,v5,59,第二次迭代：找到最短路v1 v4 v7。第二次迭代后總流量為3，總費(fèi)用32。,60,第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后總流量為5，總費(fèi)用56。,61,第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后總流量為6，總費(fèi)用72。,62,第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后總流量為9，總費(fèi)用123。,63,第六次迭代：找到最短路v1 v2 v3 v5 v7 。第六次迭代后總流量為10，總費(fèi)用145。已經(jīng)找不到從v1