管理決策 第七講 網(wǎng)絡(luò)分析及應(yīng)用

1、管理決策曹媛媛曹媛媛 22022-2-10第七講 網(wǎng)絡(luò)分析圖論(Graph Theory) 是運籌學(xué)的一個分支，已廣泛應(yīng)用在物理學(xué)、化學(xué)、控制論、信息論、科學(xué)管理、計算機等各個領(lǐng)域中。網(wǎng)絡(luò)分析（Network Analysis） 作為圖論的一個重要內(nèi)容，已成為對各種系統(tǒng)進行分析、研究和管理的重要工具。本章主要介紹運輸問題、最短路問題、最小支撐樹問題、最大流問題，以及網(wǎng)絡(luò)計劃評審與優(yōu)化問題。第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念圖論中的圖，是反映現(xiàn)實世界中具體事物及其相互關(guān)系的一種抽象工具,它比地圖、分子結(jié)構(gòu)圖、電路圖等更抽象。 圖的定義：圖的定義：簡單的說，一個圖是由一些點(Vertices)及點

2、間的連線(Edges)所組成的。點可以作為現(xiàn)實世界中事物的抽象，而點間的連線表示事物間的關(guān)系。無向圖：如果一個圖由點及邊所構(gòu)成，則稱之為無向圖 ，記為G=(V，E)。其中，V是一個有限非空的點集合，稱為G的點集，一般表示為V=v1，v2，vn；E是一個邊集合，稱為G的邊集，一條連接vi和vj的邊一般表示為一個無序?qū)=（vi，vj）。有向圖：如果一個圖由點及弧所構(gòu)成，則稱之為有向圖，記為D(V，A)。其中，V是點的集合；A是弧的集合，一條從vi連接到vj的弧一般表示為一個有序?qū)(vi，vj)。 第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念 無向圖無向圖 例3-1 試用一個圖來表示大連、北京、深圳、上海

3、四城市之間的民航客機通航情況。 解： 設(shè)v1，v2，v3，v4分別表示大連、北京、深圳、上海四市，則他們之間的通航情況可表示為一個無向圖：G=(V，E) 。 V=v1，v2，v3，v4E=e1，e2，e3，e4，e5，e6e1=v1，v2，e2=v1，v3，e3=v1，v4，e4=v2，v3，e5=v2，v4，e6=v3，v4第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念 有向圖有向圖 例3-2 有A、B、C、D四支籃球隊，進行單循環(huán)比賽，比賽情況如表所示。試用一個圖表示各隊之間的勝負關(guān)系。 比賽球隊比賽球隊獲勝球隊獲勝球隊A AB BA AA AC CA AA AD DD DB BC CB BB BD

4、DD DC CD DC C解：設(shè)v1，v2，v3，v4分別表示球隊A、B、C、D，其相互間的勝負關(guān)系可表示為一個有向圖： D=(V，A)，從vi連接到vj的弧表示vi代表的球隊勝vj代表的球隊。其中V=v1，v2，v3，v4A=a1，a2，a3，a4，a5，a6a1=v1，v2，a2=v1，v3，a3=v4，v1，a4=v2，v3，a5=v4，v2，a6=v3，v4第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念幾個基本概念 若有e=（vi，vj），則稱vi，vj是e的端點，也稱點vi與vj相鄰，稱e是vi，vj的關(guān)聯(lián)邊。如圖中，v1與v4是e5的端點，點v2與v3相鄰，e6是v4與v5的關(guān)聯(lián)邊。 若一條邊

5、的兩個端點相同，則稱該邊為環(huán)。如e7。 若兩個端點之間不止一條邊，則稱具有多重邊；一個無環(huán)也無多重邊的圖稱為簡單圖。第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念幾個基本概念圖G=(V，E)中，設(shè) ； ； ；則交替序列 稱為一條從 到 的鏈，簡記為若 則稱為閉鏈，否則稱 為開鏈。若 中的邊均不相同，則稱 為簡單鏈；若 中所有結(jié)點也均不同，則稱 為初等鏈。若一條閉鏈 中，除 外，任意兩點均不相同，則稱 為一個圈。若圖G中，任意兩點間至少存在一條鏈，則稱圖G為連通圖，否則稱為不連通圖。Vvvvkiii.,10Eeeekjjj.,10),(1tttiijvve), 2 , 1(ktkkijjijiveevev,

6、21100ivkivkiiivvvL100ivkivkiv0iv第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念幾個基本概念如圖， v4v7v5v6v7v8是簡單鏈， v4v5v7v6v8是初等鏈， v4v5v6v8v7v4是一個圈，但 v4v7v6v8v7v5v4僅為一條閉鏈，而不是圈。左圖是連通圖，而右圖是不連通圖，因為v1與v4之間不存在鏈。1423第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念幾個基本概念設(shè)有圖G=(V，E)和圖G=(V，E)，若VV，E E，則稱G是G的一個支撐子圖或支撐圖。圖中 (a)，(b)，(c)均為(a)的支撐子圖，但(d)不是(a)的支撐子圖，因為(d)比(a)少一個點v1。第七講

7、網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念幾個基本概念若把一個有向圖D中所有弧的方向去掉，即每一條弧都用相應(yīng)的無向邊代替，所得到一個無向圖稱為該有向圖D的基礎(chǔ)圖，記為G(D)。如圖中(b)為(a)的基礎(chǔ)圖。第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念幾個基本概念若交替序列 是有向圖D(V，A)的一條鏈，并且有： ；則稱 是圖D的一條從 到 的路，簡記為： ，若 ，則稱是圖D的一條回路，否則稱為開路。對無向圖G而言，鏈和路(閉鏈和回路)這兩個概念是一致的。如圖， v2v4v1v3是一條開路， v4v1v3v4是一條回路；但 v2v1v4v3 和 v2v4v1v2雖然分別是G(D)的開路和回路，卻不是D的路，而僅是D的鏈和

8、圈。kkijjijivaavav,.,2110),(1tttiijvva),2, 1(kt0ivkivkiiivvv1034120ivkiv第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念幾個基本概念 若給一個圖中的每一條邊（或?。┒假x予一個實數(shù) = (vi，vj)，所得的圖稱為一個賦權(quán)網(wǎng)絡(luò)圖。賦權(quán)無向圖和賦權(quán)有向圖統(tǒng)稱為網(wǎng)絡(luò)，記為N。這里， 稱為邊(vi，vj)的權(quán)數(shù)（或權(quán)）。 一般來講，圖論中所討論的圖，特別是在應(yīng)用圖論中所討論的圖多數(shù)是網(wǎng)絡(luò)。ijij第七講 網(wǎng)絡(luò)分析運輸問題 運輸問題一般描述為：一種物資有m個產(chǎn)地 ，其產(chǎn)量分別為ai，有n個銷地 ，其銷量分別為bj；從Ai至Bj的運價為cij，問如何設(shè)

9、計調(diào)運方案才能使總運費最少？產(chǎn)銷平衡問題 當(dāng)總產(chǎn)量等于總銷量，即： 時，稱為產(chǎn)銷平衡的運輸問題，簡稱平衡問題。產(chǎn)銷不平衡問題 當(dāng)總產(chǎn)量大于總銷量，即 時，稱為產(chǎn)大于銷的運輸問題；當(dāng)總產(chǎn)量小于總銷量，即 時，稱為產(chǎn)小于銷的運輸問題。產(chǎn)大于銷的運輸問題和產(chǎn)小于銷的運輸問題統(tǒng)稱為產(chǎn)銷不平衡問題。 ), 2 , 1(miAi), 2 , 1(njBjKnjjmiiba11njjmiiba11njjmiiba11第七講 網(wǎng)絡(luò)分析運輸問題產(chǎn)銷平衡問題 例3-3 有A1，A2，A3三個水泥廠，每天要把生產(chǎn)的水泥運往B1，B2兩地。各廠的產(chǎn)量、各地的需求量（銷量）以及各廠地間的運價見表3-2。問如何設(shè)計調(diào)運方

10、案才能使總運費最少？運價（元運價（元/噸）（噸）（cij）產(chǎn)量（產(chǎn)量（ai）B1B2A112015011A214513015A31351409銷量（銷量（bj）1421 解：因為 =11+15+9=35， = 14+21=35， 所以這是一個產(chǎn)銷平衡問題。miia1njjb1njjmiiba11目標函數(shù)為： 其中xij為Ai至 Bj的運量，因為某產(chǎn)地運往各銷地的運量之和應(yīng)等于該產(chǎn)地的產(chǎn)量，所以有 : 。 又因各產(chǎn)地運往某銷地的運量之和應(yīng)等于該銷地的銷量（需求量），所以有: miijnjijxcz11min), 2 , 1( ,1miaxinjij), 2 , 1( ,1njbxjmiij第七講

11、 網(wǎng)絡(luò)分析運輸問題產(chǎn)銷平衡問題產(chǎn)銷平衡運輸問題的一般模型為：應(yīng)用到本例中的實例模型為：經(jīng)求解，最優(yōu)解： ，可知，由A1運往 B1地11噸，A2運往 B2 地15噸，A3運往 B1 地3噸，A3運往 B2 地6噸，這樣安排總運費最少，最少總運費為4515元。 ), 2 , 1, 2 , 1(0), 2 , 1(), 2 , 1(. t . smin1111njmixnjbxmiaxxczijjmiijinjijmiijnjijK?KKK)2 , 13 , 2 , 1(0211491511. t . s140135130145150120min322212312111323122211211323

12、122211211jixxxxxxxxxxxxxxxxxxxzij；TX) 6 , 3 ,15, 0 , 0 ,11(*4515*z第七講 網(wǎng)絡(luò)分析運輸問題產(chǎn)銷不平衡問題 例3-4 有A1，A2，A3三個水泥廠，每天要把生產(chǎn)的水泥運往B1，B2兩地。各廠的產(chǎn)量、各地的需求量（銷量）以及各廠地間的運價見表。問如何設(shè)計調(diào)運方案才能使總運費最少？運價（元運價（元/噸）（噸）（cij）產(chǎn)量（產(chǎn)量（ai）B1B2A112015011A214513015A31351409銷量（銷量（bj）1320 解：因為 =11+15+9=35， = 13+20=33， 所以這是一個產(chǎn)大于銷的問題。miia1njjb1

13、目標函數(shù)為： 其中xij為Ai至 Bj的運量，因為某產(chǎn)地運往各銷地的運量之和應(yīng)不大于該產(chǎn)地的產(chǎn)量，所以有 : 。 又因各產(chǎn)地運往某銷地的運量之和應(yīng)等于該銷地的銷量（需求量），所以有: miijnjijxcz11min), 2 , 1( ,1miaxinjijK), 2 , 1( ,1njbxjmiij第七講 網(wǎng)絡(luò)分析運輸問題產(chǎn)銷不平衡問題產(chǎn)大于銷運輸問題的一般模型為：應(yīng)用到本例中的實例模型為：經(jīng)求解，最優(yōu)解： ，可知，由A1運往 B1 地11噸，A2運往 B2 地15噸，A3運往 B1 地2噸，A3運往 B2 地5噸，這樣安排總運費最少，最少總運費為4240元。 ), 2 , 1, 2 , 1

14、(0), 2 , 1(), 2 , 1(. t . smin1111njmixnjbxmiaxxczijjmiijinjijmiijnjijK?KKK)2 , 13 , 2 , 1(0201391511. t . s140135130145150120min322212312111323122211211323122211211jixxxxxxxxxxxxxxxxxxxzij；TX)5 , 2 ,15, 0 , 0 ,11(*4240*z第七講 網(wǎng)絡(luò)分析運輸問題轉(zhuǎn)運問題 前面介紹的運輸問題，都是將物資直接由產(chǎn)地運往銷地，但是，實際中很多的運輸問題是先將物資由產(chǎn)地運往某個或某些轉(zhuǎn)運站（轉(zhuǎn)運站在現(xiàn)

15、實情況中往往表現(xiàn)為倉庫），再由轉(zhuǎn)運站運往銷地，這類運輸問題不僅要求總運費最少，而且要同時選出最優(yōu)運輸路線，這就是轉(zhuǎn)運問題。 第七講 網(wǎng)絡(luò)分析運輸問題轉(zhuǎn)運問題例3-5 有A1，A2，A3三個水泥廠，每天要把生產(chǎn)的水泥先運往C1，C2兩個倉庫，再由倉庫運往B1，B2兩地。各廠至各倉庫、各倉庫至各銷地的運價（單位：元/噸）見表3-4，每個產(chǎn)地的產(chǎn)量（單位：噸/天）和每個銷地的銷量（單位：噸/天）分別在左側(cè)和右側(cè)做了標注。問如何設(shè)計調(diào)運方案才能使總運費最少？ C1C211 A19010015 A2105929 A310283B1 14B2 21C17267C25864 解：該例中共有10條運輸路線，分

16、別是A1- C1，A1- C2，A2- C1，A2- C2，A3- C1，A3- C2，C1- B1，C1- B2，C2- B1，C2- B2，我們分別用數(shù)字17來表示A1、A2、A3、C1、C2 、B1、B2，則這十條運輸路線上的運量可分別用x14，x15，x24，x25，x34，x35，x46，x47，x56，x57來表示。第七講 網(wǎng)絡(luò)分析運輸問題轉(zhuǎn)運問題目標函數(shù)為： minz=90 x14+100 x15+105x24+92x25+102x34 +83x35+72x46+67x47+58x56+64x57由于這是一個產(chǎn)銷平和問題，對于產(chǎn)地，物資的運出量應(yīng)等于產(chǎn)地的產(chǎn)量，因此 ，對A1有：

17、 對A2有： 對A3有： 對于轉(zhuǎn)運站（倉庫），物資的運入量應(yīng)等于運出量，因此: 對C1有： 對C2有：對于銷地，物資的運入量應(yīng)等于銷地的需求量，因此: 對B1有： 對B2有：111514 xx152524 xx93534 xx4746342414xxxxx5756352515xxxxx145646xx215747xx第七講 網(wǎng)絡(luò)分析運輸問題轉(zhuǎn)運問題綜上，建立此例的數(shù)學(xué)模型為：經(jīng)求解，最優(yōu)解如下：0,211491511. t . s645867728310292105100 90 min 575647463534252415145747564657563525154746342414353425

18、24151457564746353425241514xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzTX)10,14,11,0,9 ,0,15,0,0,11(*5306*z第七講 網(wǎng)絡(luò)分析運輸問題轉(zhuǎn)運問題歸納出轉(zhuǎn)運問題的一般線性規(guī)劃模型這里xij表示從節(jié)點i到j(luò)的運量，cij表示從i到j(luò)的運價，ai表示產(chǎn)地i的產(chǎn)量，bj表示銷地j的銷量（需求量）。jiijjijijijijiijijijijxbxxxxaxxxcz和對于所有的銷地節(jié)點轉(zhuǎn)運節(jié)點起點節(jié)點運出弧運入弧運入弧運出弧運入弧運出弧所有弧0)(0)(. t . smin第七講 網(wǎng)絡(luò)分析最短路問題 最短路問題

19、一般描述為：在一網(wǎng)絡(luò)中，給定兩個點vs和vt，找到一條從vs到vt的路，使這條路上所有弧的權(quán)數(shù)之和最小，這條路就是vs到vt的最短路。這條路上所有弧的權(quán)數(shù)之和稱為vs到vt的距離。 最短路線問題可以采用標號法等方法進行求解，也可借助相關(guān)的運籌學(xué)軟件包進行求解。這里xij表示從節(jié)點i到j(luò)的運量，cij表示從i到j(luò)的運價，ai表示產(chǎn)地i的產(chǎn)量，bj表示銷地j的銷量（需求量）。例 某電信公司計劃在甲、乙兩地鋪設(shè)通信電纜，圖是甲、乙兩地間的交通圖，圖中 v1，v2，v3，v4，v5，v6表示6個地名點，其中v1 表示甲地，v6表示乙地，點之間的連線（邊）表示兩地公路，邊上的數(shù)值表示兩地間公路的長度（單

20、位：千米），問如何鋪設(shè)能使甲、乙兩地的電纜長度最短？ 經(jīng)標號法求解最短路是v1-v2-v6，最短距離是7+12=19千米，所以應(yīng)在v1-v2，v2-v6間鋪設(shè)線路。(0)14(14)7819(7)(8)(19)11(11)練習(xí)：最短路為提高運輸效率，請找出公司（節(jié)點1）到零售店（節(jié)點11）之間的最短路徑。第七講 網(wǎng)絡(luò)分析最小支撐樹問題 一個連通無圈簡單圖稱為樹。若圖G的一個支撐圖T是樹，則稱T是圖G的一棵支撐樹。 如圖示出了一個圖G及其支撐樹T1，T2，T3。 第七講 網(wǎng)絡(luò)分析最小支撐樹問題 設(shè)Tk（V，Ek）是網(wǎng)絡(luò)N(G， )的一個棵支撐樹，則Tk的邊集Ek中所有邊的權(quán)數(shù)之和稱為樹Tk的權(quán)，

21、記為 。 即： 若支撐樹T*的權(quán) 是N的所有支撐樹的權(quán)中最小者，則稱T*為網(wǎng)絡(luò)N的最小支撐樹，簡稱最小樹。 即： 如何找出網(wǎng)絡(luò)的最小樹就是最小支撐樹問題。最小支撐樹問題可以采用避圈法和破圈法等方法進行求解，也可借助相關(guān)的運籌學(xué)軟件包進行求解。kTkEeekT)( *T)(min)(*kTTTTk第七講 網(wǎng)絡(luò)分析最小支撐樹問題 例某自然景區(qū)內(nèi)設(shè)有6個服務(wù)站和一個網(wǎng)絡(luò)中心，景區(qū)的管理部門決定鋪設(shè)光纖網(wǎng)絡(luò)，為各服務(wù)站點提供通信線路。管理部門希望這個通信線路的建設(shè)成本盡可能低。圖表示了服務(wù)站和網(wǎng)絡(luò)中心的分布情況，一個圓圈表示一個服務(wù)站（或網(wǎng)絡(luò)中心），圓圈之間連線上的數(shù)字表示兩個站點（或站點與網(wǎng)絡(luò)中心）

22、之間鋪設(shè)電纜的成本（單位：萬元）。問應(yīng)如何設(shè)計該通訊線路？ 經(jīng)求解，結(jié)果如圖所示，鋪設(shè)總成本最小，為4+5+4+3+4+3=23（萬元）。練習(xí)：最小支撐樹為節(jié)約成本，請設(shè)計一個網(wǎng)絡(luò)系統(tǒng)，使得城市1與鄉(xiāng)鎮(zhèn)2-10之間都有光纖連通，且鋪設(shè)總長度最少。地點地點2 23 34 45 56 67 78 89 910101949151511161622281612810191420369117121115441611815175712614136103715779108111299第七講 網(wǎng)絡(luò)分析最大流問題 現(xiàn)實生活中，許多系統(tǒng)中都存在流量問題。如公路系統(tǒng)中存在車輛流，電力系統(tǒng)中存在電流，供水系統(tǒng)中存在水

23、流，信息系統(tǒng)中存在信息流，金融系統(tǒng)中存在現(xiàn)金流等。例 迅達通訊公司使用光纜網(wǎng)絡(luò)在不同地方傳遞電話和其他信息。信息通過光纜線和轉(zhuǎn)換點傳遞。該公司的傳送網(wǎng)絡(luò)如圖所示。一個圓圈代表一個轉(zhuǎn)換點，轉(zhuǎn)換點之間的連線上的數(shù)字表示該條光纜線的最大信息傳遞能力。求該通訊網(wǎng)絡(luò)的最大傳輸能力。 第七講 網(wǎng)絡(luò)分析最大流問題 (1) 容量網(wǎng)絡(luò)與網(wǎng)絡(luò)流 滿足如下規(guī)定的網(wǎng)絡(luò)稱之為容量網(wǎng)絡(luò)。 對于一個有向網(wǎng)絡(luò)N(V，A)，各弧的方向就是流量通過的方向； 對網(wǎng)絡(luò)中的每一?。╲i，vj）A，都賦予一個容量r（vi，vj）rij 0，表示容許通過該弧的最大流量； 網(wǎng)絡(luò)有一個始點vs和一個終點vt。除vs和vt外的其余點稱之為中間點。 所謂網(wǎng)絡(luò)流，指某種流在網(wǎng)絡(luò)中各弧上的流量的集合。即： 其