330管理運籌學(xué)第十一章圖與網(wǎng)絡(luò)模型§1§2§3§4§5圖與網(wǎng)絡(luò)的基本概念最短路問題最小生成樹問題最大流問題最小費用最大流問題331管理運籌學(xué)§1圖與網(wǎng)絡(luò)的基本概念

圖論中圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系。 例如：在一個人群中，對相互認識這個關(guān)系我們可以用圖來表示，圖11-1就是一個表示這種關(guān)系的圖。

圖11-1332管理運籌學(xué)§1圖與網(wǎng)絡(luò)的基本概念

當然圖論不僅僅是要描述對象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點的相對位置如何、點與點之間連線的長短曲直，對于反映對象之間的關(guān)系并不是重要的，如對趙、錢、孫、李、周、吳、陳等七人的相互認識關(guān)系我們也可以用圖11-2來表示，可見圖論中的圖與幾何圖、工程圖是不一樣的。

圖11-2333管理運籌學(xué)§1圖與網(wǎng)絡(luò)的基本概念

如果我們把上面例子中的“相互認識”關(guān)系改為“認識”的關(guān)系，那么只用兩點之間的連線就很難刻畫他們之間的關(guān)系了，這是我們引入一個帶箭頭的連線，稱為弧。圖11-3就是一個反映這七人“認識”關(guān)系的圖。相互認識用兩條反向的弧表示。

圖11-3334管理運籌學(xué)§1圖與網(wǎng)絡(luò)的基本概念

無向圖：

由點和邊構(gòu)成的圖，記作G=(V,E)。

有向圖：

由點和弧構(gòu)成的圖，記作D=(V,A)。

連通圖：

對無向圖G，若任何兩個不同的點之間，至少存在一條鏈，則G為連通圖。

回路：

若路的第一個點和最后一個點相同，則該路為回路。

賦權(quán)圖：

對一個無向圖G的每一條邊(vi,vj)，相應(yīng)地有一個數(shù)wij，則稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。

網(wǎng)絡(luò)：

在賦權(quán)的有向圖D中指定一點，稱為發(fā)點(記為vs)，指定另一點稱為收點(記為vt)，其他點稱為中間點，并把D中的每一條弧的賦權(quán)數(shù)cij稱為弧(vi,vj)的容量，這樣的賦權(quán)有向圖D就稱為網(wǎng)絡(luò)。335管理運籌學(xué)§2最短路問題??

最短路問題：對一個賦權(quán)的有向圖D中的指定的兩個點vs和vt找到一條從vS到

vt的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從vs到vt的最 短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從vs到vt的距離。求解最短路的Dijkstra算法（雙標號法）

步驟：

1．給出點v1以標號（0,s）

2．找出已標號的點的集合I，沒標號的點的集合J以及弧的集合

{(vi,vj)|vi∈I,vj∈J} 3．如果上述弧的集合是空集，則計算結(jié)束。如果vt已標號(lt,kt)，則vs到vt的距離為lt，而從vs到vt的最短路徑，則可以從vt反向追蹤到起點vs而得到。如果vt未標號，則可以斷言不存在從vs到vt的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。

4．對上述弧的集合中的每一條弧，計算sij=li+cij。在所有的sij中，找到其值為最小的弧。不妨設(shè)此弧為(Vc,Vd)，則給此弧的終點以雙標號(scd,c)，返回步驟2。336管理運籌學(xué)§2最短路問題例1求圖11-4中v1到v6的最短路解：采用Dijkstra算法，可解得最短路徑為v1→v3→v4→v6各點的標號圖如圖11-5所示。圖11-4圖11-5→→→337管理運籌學(xué)§2最短路問題

求解過程如下。 （1）給定起始點v1標以(0，s)，表示從v1到v1的距離為0，v1為起始點。 （2）這時已標定點集合I={v1}，未標定點的集合J={v2,v3,v4,v5,v6}，弧集合{(vi,vj)vi∈I,vj∈J}={(v1,v2),(v1,v3),(v1,v4)},則有min(s12,s13,s14)=s13=2，這樣，給弧(v1,v3)的終點v3標以（2，1），表示從v1到v3的距離為2.

（3）這時I={v1,v3},J={v2,v4,v5,v6}，則有min(s12,s14,s34)=s12=s34=3。給弧(v1,v2)的終點v2標以(3，1)，表示從v1到v2的距離為3；我們給弧(v3,v4)的終點v4標以(3,3)，表示從v1到v4的距離為3.

（4）這時I={v1,v2,v3,v4},J={v5,v6}，則有min(s26,s46)=s46=8,這樣給點v6標以(8,4)，表示從v1到v6的距離是8.

（5）這時I={v1,v2,v3,v4,v6},J={v5}，而弧集合為空，也即v5還未標號，說明從v1到v5沒有有向路.

（6）得到一組最優(yōu)結(jié)果。從終點v6的標號倒推到起點v1，得到此最短路徑為v1v3v4v6.338管理運籌學(xué)§2最短路問題

例2．電信公司準備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。

圖11-6

解：這是一個求無向圖的最短路的問題。可以把無向圖的每一邊（vi,vj）都用方向相反的兩條?。╲i,vj）和（vj,vi）代替，就化為有向圖，即可用Dijkstra算法來求解。也可直接在無向圖中用Dijkstra算法來求解。只要在算法中把從已標號的點到未標號的點的弧的集合改成已標號的點到未標號的點的邊的集合即可。339管理運籌學(xué)§2最短路問題

例2求解過程如下。 （1）給起始點v1，標號為（0,s）。 （2）I={v1},J={v2,v3,v4,v5,v6,v7}。邊的集合為{[v1,v2],[v1,v3]}，則有s12=15,s13=10,min(s12,s13)=s13=10。給邊[v1,v3]中的未標號的點v3標以（10，1）表示從v1到v3的距離為10。 （3）這時I={v1,v3},J={v2,v3,v4,v5,v6,v7}。邊集合為{[v1,v2],[v3,v2],[v3,v5]}，則有min(s12,s32,s35)=s32=13。給邊[v3,v2]中未標號的點v2標以（13,3）。 （4）這時I={v1,v3,v2},J={v4,v5,v6,v7}.邊集合為{[v3,v5],[v2,v4],[v2,v7]}，則有min（s35,s24,s27）=s35=14。給邊[v3,v5]中未標號的點v5標以(14,3)。 （5）這時I={v1,v2,v3,v5},J={v4,v6,v7}.邊集合為{[v2,v4],[v5,v4],[v2,v7],[v5,v6]},則有min(s24,s54,s27,s56)=s56=16。給邊[v5,v6]中未標號的點v6標以(16,5)。 （6）這時I={v1,v2,v3,v5,v6},J={v4,v7}。邊集合為{[v2,v4],[v2,v7],[v5,v4],[v6,v7]}，則有min(s24,s27,s54,s67)=s54=18。給邊[v5,v4]中未標號的點v4標以(18,5)。340管理運籌學(xué)§2最短路問題

（7）這時I={v1,v2,v3,v4,v5,v6},J={v7}。邊集合為{[v2,v7],[v4,v7],[v6,v7]}，并有min(s27,s47,s67)=s67=22。給邊[v6,v7]中未標號的點v7標以（22，6）。 （8）此時I={v1,v2,v3,v4,v5,v6,v7},J為空集，計算結(jié)束。 （9）得到最短路。 最短路徑v1→v3→v5→v6→v7，每點的標號如圖11-7所示。

圖11-7341理運籌§2最短路問題例3設(shè)備更新問題。某公司使用一臺設(shè)備，在每年年初，公司就要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費，當然新設(shè)備的維修費用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費，但維修費用就高了。請設(shè)計一個五年之內(nèi)的更新設(shè)備的計劃，使得五年內(nèi)購置費用和維修費用總的支付費用最小。 已知：設(shè)備每年年初的價格如表11-1所示。

表11-1

年份年初價格

111

211

312

412

513設(shè)備維修費如表11-2所示。

表11-2

使用年數(shù)每年維修費用0～1 51～2 6

管2～3 8

學(xué)3～4 114～5 18342管理運籌學(xué)§2最短路問題

例3的解： 將問題轉(zhuǎn)化為最短路問題，如圖11-8所示。 用vi表示“第i年年初購進一臺新設(shè)備”，?。╲i,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。

圖11-8

把所有弧的權(quán)數(shù)計算如下表。

表11-31

216

32216123

4302217

5413023

6594131172318456343管理運籌學(xué)§2最短路問題

（繼上頁）把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。

圖11-9

求解過程如下。 （1）給定起始點v1標以（0，s)。 （2）這時I={v1},J={v2,v3,v4,v5,v6}。 弧集合為{(v1,v2),(v1,v3),(v1,v4),(v1,v5),(v1,v6)}，則有min(s12,s13,s14,s15,s16)=s12=16，給弧（v1,v2）的終點v2標以（16，1）。 （3）這時I={v1,v2},J={v3,v4,v5,v6}。 弧集合為{(v1,v3),(v1,v4),(v1,v5),(v1,v6),(v2,v3),(v2,v4),(v2,v5),(v2,v6)}，則有min(s13,s14,s15,s16,s23,s24,s25,s26)=s13=22，給弧(v1,v3)的終點v3標以（22，1）。344管理運籌學(xué)§2最短路問題

（4）這時I={v1,v2,v3},J={v4,v5,v6}。則有

min(s14,s15,s16,s24,s25,s26,s34,s35,s36)=s14=30。 給?。╲1,v4）的終點v4標以（30，1）。 （5）這時I={v1,v2,v3,v4},J={v5,v6}。則有

min(s15,s16,s25,s26,s35,s36,s45,s46)=s15=41。 給?。╲1,v5）的終點v5標以（41，1）。 （6）這時I={v1,v2,v3,v4,v5},J={v6}。則有

min(s16,s26,s36,s46,s56)=s36=s46=53。 給?。╲3,v6）和（v4,v6）的終點標以（53,3）和（53,4），最終得到圖11-10，可知，v1到v6的距離是53，最短路徑有兩條：v1→v3→v6和v1→v4→v6。

圖11-10345管理運籌學(xué)§3最小生成樹問題?樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。

圖11-11

圖11-11中，（a）就是一個樹，而（b）因為圖中有圈所以就不是樹，（c）因為不連通所以也不是樹。346管理運籌學(xué)§3最小生成樹問題

給了一個無向圖G=(V,E)，我們保留G的所有點，而刪掉部分G的邊或者說保留一部分G的邊，所獲得的圖G，稱之為G的生成子圖。在圖11-12中，（b）和（c）都是（a）的生成子圖。 如果圖G的一個生成子圖還是一個樹，則稱這個生成子圖為生成樹，在圖11-12中，（c）就是（a）的生成樹。

最小生成樹問題就是指在一個賦權(quán)的連通的無向圖G中找出一個生成樹，并使得這個生成樹的所有邊的權(quán)數(shù)之和為最小。

圖11-12347管理運籌學(xué)§3最小生成樹問題·求解最小生成樹的破圈算法

算法的步驟如下。 （1）在給定的賦權(quán)的連通圖上任找一個圈。 （2）在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。 （3）如果所余下的圖已不包含圈，則計算結(jié)束，所余下的圖即為最小生成樹，否則返回第（1）步。348管理運籌學(xué)§3最小生成樹問題例4．用破圈算法求圖（a）中的一個最小生成樹。

圖11-13349管理運籌學(xué)§3最小生成樹問題

例5．某大學(xué)準備對其所屬的7個學(xué)院辦公室進行計算機聯(lián)網(wǎng)，這個網(wǎng)絡(luò)可能聯(lián)通的途徑如圖11-14所示，圖中v1,…,v7表示7個學(xué)院辦公室，請設(shè)計一個網(wǎng)絡(luò)能聯(lián)通7個學(xué)院辦公室，并使總的線路長度最短。

圖11-14

解：此問題實際上是求圖11-14的最小生成樹，這在例4中已經(jīng)求得，也即按照圖11-13的（f）設(shè)計，可使此網(wǎng)絡(luò)的總的線路長度為最短，為19。 管理運籌學(xué)軟件有專門的子程序可以解決最小生成樹問題。350管理運籌學(xué)§4最大流問題?最大流問題：給一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱為容量，在不超過每條

弧的容量的前提下，求出從發(fā)點到收點的最大流量。一、最大流的數(shù)學(xué)模型 例6．某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運送到一些銷售點，這個網(wǎng)絡(luò)的一部分如圖11-15所示。由于管道的直徑的變化，它的各段管道（vi,vj）的流量cij（容量）也是不一樣的。cij的單位為萬加侖/小時。如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地v1向銷地v7運送石油，問每小時能運送多少加侖石油？

圖11-15351管理運籌學(xué)§4最大流問題我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型：設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上的總的流量為F，則有7)7)F=f12+f14,6;j=1,2,目標函數(shù)：max約束條件：f12=f23+f25

f14=f43+f46+f47

f23+f43=f35+f36

f25+f35=f57

f36+f46=f67f57+f67+f47=f12+f14fij≤cij,(i=1,2,,6;j=1,2,fij≥0,(i=1,2,352管理運籌學(xué)§4最大流問題

在這個線性規(guī)劃模型中，其約束條件中的前6個方程表示了網(wǎng)絡(luò)中的 流量必須滿足守恒條件，發(fā)點的流出量必須等于收點的總流入量；其余的 點稱之為中間點，它的總流入量必須等于總流出量。其后面幾個約束條件 表示對每一條弧（vi,vj）的流量fij要滿足流量的可行條件，應(yīng)小于等于?。╲i,vj）的容量cij，并大于等于零，即0≤fij≤cij。我們把滿足守恒條件及 流量可行條件的一組網(wǎng)絡(luò)流{fij}稱之為可行流，（即線性規(guī)劃的可行解）， 可行流中一組流量最大（也即發(fā)出點總流出量最大）的稱之為最大流（即 線性規(guī)劃的最優(yōu)解）。 我們把例6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運籌學(xué)軟件”運 算，馬上得到以下的結(jié)果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，

f35=2，f36=2，f57=5，f67=3。最優(yōu)值（最大流量）=10。353管理運籌學(xué)§4最大流問題二、最大流問題網(wǎng)絡(luò)圖論的解法 對網(wǎng)絡(luò)上弧的容量的表示作改進。對一條?。╲i,vj）的容量我們用一對數(shù)cij,0標在?。╲i,vj）上，cij靠近vi點，0靠近vj點，表示從vi到vj容許通過的容量為cij，而從vj到vi容許通過的容量為0，這樣我們可以省去弧的方向了。如圖11-16所示，（a）和（b）、（c）和（d）的意義相同。用以上方法對例6的圖的容量標號作改進，得到圖11-17。

圖11-17圖11-16354管理運籌學(xué)§4最大流問題

求最大流的基本算法 （1）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。 （2）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf。 （3）在這條路上，減少每一條弧的順流容量pf，同時增加這些弧的逆流容量pf，返回步驟（1）。 當然由于在步驟（1）中選擇的路不一樣，計算過程也不一樣，但最終所求得的最大流量應(yīng)該是一樣的，為了使算法更快捷有效，我們一般在步驟（1）中盡量選擇包含弧數(shù)最少的路。 用此方法對例6求解： 第一次迭代：選擇路為v1→v4→v7?；。╲4,v7）的順流容量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如圖11-18所示。

圖11-18355管理運籌學(xué)§4最大流問題

第二次迭代：選擇路為v1→v2→v5→v7?；。╲2,v5）的順流容量為3，決定了pf=3，改進的網(wǎng)絡(luò)流量圖如圖11-19所示。

圖11-19356管理運籌學(xué)§4最大流問題

第三次迭代：選擇路為v1→v4→v6→v7。?。╲4,v6）的順流容量為1，決定了pf=1，改進的網(wǎng)絡(luò)流量圖如圖11-20所示。

圖11-20357管理運籌學(xué)§4最大流問題

第四次迭代：選擇路為v1→v4→v3→v6→v7?；。╲3,v6）的順流容量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如圖11-21所示。

圖11-21358管理運籌學(xué)§4最大流問題

第五次迭代：選擇路為v1→v2→v3→v5→v7?；。╲2,v3）的順流容量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如圖11-22所示。

圖11-22359管理運籌學(xué)§4最大流問題

經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點的一條路，路上的每一條弧順流容量都大于零，運算停止。得到最大流量為10。 最大流量圖如圖11-23所示。

圖11-23

管理運籌學(xué)軟件中還有專門的子程序用于解決最大流問題。360管理運籌學(xué)§5最小費用最大流問題?最小費用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，對每一條?。╲i,vj），除了給

出容量cij外，還給出了這條弧的單位流量的費用bij，要求一個最大流F，并使得 總運送費用最小。一、最小費用最大流的數(shù)學(xué)模型 例7．由于輸油管道的長短不一，所以在例6中每段管道（vi,vj）除了有不同的流量限制cij外，還有不同的單位流量的費用bij，cij的單位為萬加侖/小時，bij的單位為百元/萬加侖。如圖11-24所示。從采地v1向銷地v7運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最??？求出最大流量的最小費用。

圖11-24361管理運籌學(xué)§5最小費用最大流問題

這個最小費用最大流問題也是一個線性規(guī)劃問題。 解：我們用線性規(guī)劃來求解此題，可以分兩步走。 第一步，先求出此網(wǎng)絡(luò)圖中的最大流量F，這已在例6中建立了線性規(guī)劃的模型，通過“管理運籌學(xué)”軟件已經(jīng)獲得結(jié)果。 第二步，在最大流量F的所有解中，找出一個最小費用的解，我們來建立第二步中的線性規(guī)劃模型如下。 仍然設(shè)?。╲i,vj）上的流量為fij，這時已知網(wǎng)絡(luò)中最大流量為F，只要在例6的約束條件上，再加上總流量必須等于F的約束條件：f12+f14=F，即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標函數(shù)顯然是求其流量的最小費用∑fij×bij。

(vi,vj)∈A

由此得到線性規(guī)劃模型如下。362管理運籌學(xué)§5最小費用最大流問題(vi,vj)∈A

4f35+7f57+3f36+3f46+8f47+4f67s.t.

f12+f14=F=10,

f12=f23+f25,

f14=f43+f46+f47,

f23+f43=f35+f36,

f25+f35=f57,

f36+f46=f67,

f57+f67+f47=f12+f14,

,7),,7),

,6;j=2,3,,6;j=2,3,fij≤cij,(i=1,2,fij≥0,(i=1,2,363管理運籌學(xué)§5最小費用最大流問題

用管理運籌學(xué)軟件，可求得如下結(jié)果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最優(yōu)值（最小費用）為145。對照前面例6的結(jié)果，可對最小費用最大流的概念有一個深刻的理解。 如果我們把例7的問題改為：每小時運送6萬加侖的石油從采地v1到銷地v7最小費用是多少？應(yīng)怎樣運送？這就變成了一個最小費用流的問題。一般來說，所謂最小費用流的問題就是在給定了收點和發(fā)點并對每條?。╲i,vj）賦權(quán)以容量cij及單位費用bij的網(wǎng)絡(luò)中，求一個給定值f的流量的最小費用，這個給定值f的流量應(yīng)小于等于最大流量F，否則無解。求最小費用流的問題的線性規(guī)劃模型只要把最小費用最大流模型中的約束條件中的發(fā)點流量F改為f即可。在例6中只要把f12+f14=F改為f12+f14=f=6，就可得到最小費用流的線性規(guī)劃模型了。364管理運籌學(xué)§5最小費用最大流問題二、最小費用最大流的網(wǎng)絡(luò)圖論解法 對網(wǎng)絡(luò)上?。?/p>