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

1、管理決策曹媛媛 .22022/7/15第七講 網(wǎng)絡(luò)分析圖論(Graph Theory) 是運(yùn)籌學(xué)的一個(gè)分支，已廣泛運(yùn)用在物理學(xué)、化學(xué)、控制論、信息論、科學(xué)管理、計(jì)算機(jī)等各個(gè)領(lǐng)域中。網(wǎng)絡(luò)分析Network Analysis 作為圖論的一個(gè)重要內(nèi)容，已成為對(duì)各種系統(tǒng)進(jìn)展分析、研討和管理的重要工具。本章主要引見運(yùn)輸問題、最短路問題、最小支撐樹問題、最大流問題，以及網(wǎng)絡(luò)方案評(píng)審與優(yōu)化問題。.第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的根本概念圖論中的圖，是反映現(xiàn)實(shí)世界中詳細(xì)事物及其相互關(guān)系的一種籠統(tǒng)工具,它比地圖、分子構(gòu)造圖、電路圖等更籠統(tǒng)。 圖的定義：簡單的說，一個(gè)圖是由一些點(diǎn)(

2、Vertices)及點(diǎn)間的連線(Edges)所組成的。點(diǎn)可以作為現(xiàn)實(shí)世界中事物的籠統(tǒng)，而點(diǎn)間的連線表示事物間的關(guān)系。無向圖：假設(shè)一個(gè)圖由點(diǎn)及邊所構(gòu)成，那么稱之為無向圖 ，記為G=(V，E)。其中，V是一個(gè)有限非空的點(diǎn)集合，稱為G的點(diǎn)集，普通表示為V=v1，v2，vn；E是一個(gè)邊集合，稱為G的邊集，一條銜接vi和vj的邊普通表示為一個(gè)無序?qū)=vi，vj。有向圖：假設(shè)一個(gè)圖由點(diǎn)及弧所構(gòu)成，那么稱之為有向圖，記為D(V，A)。其中，V是點(diǎn)的集合；A是弧的集合，一條從vi銜接到vj的弧普通表示為一個(gè)有序?qū)(vi，vj)。 .第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的根本概念 無向圖 例3-1 試用一個(gè)圖來表示大連

3、、北京、深圳、上海四城市之間的民航客機(jī)通航情況。 解： 設(shè)v1，v2，v3，v4分別表示大連、北京、深圳、上海四市，那么他們之間的通航情況可表示為一個(gè)無向圖：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四支籃球隊(duì)，進(jìn)展單循環(huán)競賽，競賽情況如表所示。試用一個(gè)圖表示各隊(duì)之間的勝負(fù)關(guān)系。 比賽球隊(duì)獲勝球隊(duì)ABAACAADDBCBBDDCDC解：設(shè)v1，v2，v3，v4分別表示球隊(duì)A、B

4、、C、D，其相互間的勝負(fù)關(guān)系可表示為一個(gè)有向圖： D=(V，A)，從vi銜接到vj的弧表示vi代表的球隊(duì)勝vj代表的球隊(duì)。其中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ò)的根本概念幾個(gè)根本概念 假設(shè)有e=vi，vj，那么稱vi，vj是e的端點(diǎn)，也稱點(diǎn)vi與vj相鄰，稱e是vi，vj的關(guān)聯(lián)邊。如圖中，v1與v4是e5的端點(diǎn)，點(diǎn)v2與v3相鄰，e6是v4與v5的關(guān)聯(lián)邊。 假設(shè)一條邊的兩個(gè)端點(diǎn)一樣，那么稱該邊為環(huán)。如e7。 假設(shè)兩個(gè)端點(diǎn)之間不止一條邊

5、，那么稱具有多重邊；一個(gè)無環(huán)也無多重邊的圖稱為簡單圖。.第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的根本概念幾個(gè)根本概念圖G=(V，E)中，設(shè) ； ； ；那么交替序列 稱為一條從 到 的鏈，簡記為假設(shè) 那么稱為閉鏈，否那么稱 為開鏈。假設(shè) 中的邊均不一樣，那么稱 為簡單鏈；假設(shè) 中一切結(jié)點(diǎn)也均不同，那么稱 為初等鏈。假設(shè)一條閉鏈 中，除 外，恣意兩點(diǎn)均不一樣，那么稱 為一個(gè)圈。假設(shè)圖G中，恣意兩點(diǎn)間至少存在一條鏈，那么稱圖G為連通圖，否那么稱為不連通圖。.第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的根本概念幾個(gè)根本概念如圖， v4v7v5v6v7v8是簡單鏈， v4v5v7v6v8是初等鏈， v4v5v6v8v7v4是一個(gè)圈，但

6、 v4v7v6v8v7v5v4僅為一條閉鏈，而不是圈。左圖是連通圖，而右圖是不連通圖，由于v1與v4之間不存在鏈。.第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的根本概念幾個(gè)根本概念設(shè)有圖G=(V，E)和圖G=(V，E)，假設(shè)VV，E E，那么稱G是G的一個(gè)支撐子圖或支撐圖。圖中 (a)，(b)，(c)均為(a)的支撐子圖，但(d)不是(a)的支撐子圖，由于(d)比(a)少一個(gè)點(diǎn)v1。.第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的根本概念幾個(gè)根本概念假設(shè)把一個(gè)有向圖D中一切弧的方向去掉，即每一條弧都用相應(yīng)的無向邊替代，所得到一個(gè)無向圖稱為該有向圖D的根底圖，記為G(D)。如圖中(b)為(a)的根底圖。.第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的根

7、本概念幾個(gè)根本概念假設(shè)交替序列 是有向圖D(V，A)的一條鏈，并且有： ；那么稱 是圖D的一條從 到 的路，簡記為： ，假設(shè) ，那么稱是圖D的一條回路，否那么稱為開路。對(duì)無向圖G而言，鏈和路(閉鏈和回路)這兩個(gè)概念是一致的。如圖， v2v4v1v3是一條開路， v4v1v3v4是一條回路；但 v2v1v4v3 和 v2v4v1v2雖然分別是G(D)的開路和回路，卻不是D的路，而僅是D的鏈和圈。.第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的根本概念幾個(gè)根本概念 假設(shè)給一個(gè)圖中的每一條邊或弧都賦予一個(gè)實(shí)數(shù) = (vi，vj)，所得的圖稱為一個(gè)賦權(quán)網(wǎng)絡(luò)圖。賦權(quán)無向圖和賦權(quán)有向圖統(tǒng)稱為網(wǎng)絡(luò)，記為N。這里， 稱為邊(vi

8、，vj)的權(quán)數(shù)或權(quán)。 普通來講，圖論中所討論的圖，特別是在運(yùn)用圖論中所討論的圖多數(shù)是網(wǎng)絡(luò)。.第七講 網(wǎng)絡(luò)分析運(yùn)輸問題 運(yùn)輸問題普通描畫為：一種物資有m個(gè)產(chǎn)地 ，其產(chǎn)量分別為ai，有n個(gè)銷地 ，其銷量分別為bj；從Ai至Bj的運(yùn)價(jià)為cij，問如何設(shè)計(jì)調(diào)運(yùn)方案才干使總運(yùn)費(fèi)最少？產(chǎn)銷平衡問題 當(dāng)總產(chǎn)量等于總銷量，即： 時(shí)，稱為產(chǎn)銷平衡的運(yùn)輸問題，簡稱平衡問題。產(chǎn)銷不平衡問題 當(dāng)總產(chǎn)量大于總銷量，即 時(shí)，稱為產(chǎn)大于銷的運(yùn)輸問題；當(dāng)總產(chǎn)量小于總銷量，即 時(shí)，稱為產(chǎn)小于銷的運(yùn)輸問題。產(chǎn)大于銷的運(yùn)輸問題和產(chǎn)小于銷的運(yùn)輸問題統(tǒng)稱為產(chǎn)銷不平衡問題。 .第七講 網(wǎng)絡(luò)分析運(yùn)輸問題產(chǎn)銷平衡問題 例3-3 有A1，A2

9、，A3三個(gè)水泥廠，每天要把消費(fèi)的水泥運(yùn)往B1，B2兩地。各廠的產(chǎn)量、各地的需求量銷量以及各廠地間的運(yùn)價(jià)見表3-2。問如何設(shè)計(jì)調(diào)運(yùn)方案才干使總運(yùn)費(fèi)最少？運(yùn)價(jià)（元/噸）（cij）產(chǎn)量（ai）B1B2A112015011A214513015A31351409銷量（bj）1421 解：由于 =11+15+9=35， = 14+21=35， 所以這是一個(gè)產(chǎn)銷平衡問題。目的函數(shù)為： 其中xij為Ai至 Bj的運(yùn)量，由于某產(chǎn)地運(yùn)往各銷地的運(yùn)量之和應(yīng)等于該產(chǎn)地的產(chǎn)量，所以有 : 。 又因各產(chǎn)地運(yùn)往某銷地的運(yùn)量之和應(yīng)等于該銷地的銷量需求量，所以有:.第七講 網(wǎng)絡(luò)分析運(yùn)輸問題產(chǎn)銷平衡問題產(chǎn)銷平衡運(yùn)輸問題的普通模型

10、為：運(yùn)用到本例中的實(shí)例模型為：經(jīng)求解，最優(yōu)解： ，可知，由A1運(yùn)往 B1地11噸，A2運(yùn)往 B2 地15噸，A3運(yùn)往 B1 地3噸，A3運(yùn)往 B2 地6噸，這樣安排總運(yùn)費(fèi)最少，最少總運(yùn)費(fèi)為4515元。 .第七講 網(wǎng)絡(luò)分析運(yùn)輸問題產(chǎn)銷不平衡問題 例3-4 有A1，A2，A3三個(gè)水泥廠，每天要把消費(fèi)的水泥運(yùn)往B1，B2兩地。各廠的產(chǎn)量、各地的需求量銷量以及各廠地間的運(yùn)價(jià)見表。問如何設(shè)計(jì)調(diào)運(yùn)方案才干使總運(yùn)費(fèi)最少？運(yùn)價(jià)（元/噸）（cij）產(chǎn)量（ai）B1B2A112015011A214513015A31351409銷量（bj）1320 解：由于 =11+15+9=35， = 13+20=33， 所以這

11、是一個(gè)產(chǎn)大于銷的問題。目的函數(shù)為： 其中xij為Ai至 Bj的運(yùn)量，由于某產(chǎn)地運(yùn)往各銷地的運(yùn)量之和應(yīng)不大于該產(chǎn)地的產(chǎn)量，所以有 : 。 又因各產(chǎn)地運(yùn)往某銷地的運(yùn)量之和應(yīng)等于該銷地的銷量需求量，所以有:.第七講 網(wǎng)絡(luò)分析運(yùn)輸問題產(chǎn)銷不平衡問題產(chǎn)大于銷運(yùn)輸問題的普通模型為：運(yùn)用到本例中的實(shí)例模型為：經(jīng)求解，最優(yōu)解： ，可知，由A1運(yùn)往 B1 地11噸，A2運(yùn)往 B2 地15噸，A3運(yùn)往 B1 地2噸，A3運(yùn)往 B2 地5噸，這樣安排總運(yùn)費(fèi)最少，最少總運(yùn)費(fèi)為4240元。 .第七講 網(wǎng)絡(luò)分析運(yùn)輸問題轉(zhuǎn)運(yùn)問題 前面引見的運(yùn)輸問題，都是將物資直接由產(chǎn)地運(yùn)往銷地，但是，實(shí)踐中很多的運(yùn)輸問題是先將物資由產(chǎn)地運(yùn)

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

13、0條運(yùn)輸?shù)缆罚謩e是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，那么這十條運(yùn)輸?shù)缆飞系倪\(yùn)量可分別用x14，x15，x24，x25，x34，x35，x46，x47，x56，x57來表示。.第七講 網(wǎng)絡(luò)分析運(yùn)輸問題轉(zhuǎn)運(yùn)問題目的函數(shù)為： minz=90 x14+100 x15+105x24+92x25+102x34 +83x35+72x46+67x47+58x56+64x57由于這是一個(gè)產(chǎn)銷平和問題，對(duì)于產(chǎn)地，物資的運(yùn)出量應(yīng)等于產(chǎn)地的產(chǎn)量

14、，因此 ，對(duì)A1有： 對(duì)A2有： 對(duì)A3有： 對(duì)于轉(zhuǎn)運(yùn)站倉庫，物資的運(yùn)入量應(yīng)等于運(yùn)出量，因此: 對(duì)C1有： 對(duì)C2有：對(duì)于銷地，物資的運(yùn)入量應(yīng)等于銷地的需求量，因此: 對(duì)B1有： 對(duì)B2有：.第七講 網(wǎng)絡(luò)分析運(yùn)輸問題轉(zhuǎn)運(yùn)問題綜上，建立此例的數(shù)學(xué)模型為：經(jīng)求解，最優(yōu)解如下：.第七講 網(wǎng)絡(luò)分析運(yùn)輸問題轉(zhuǎn)運(yùn)問題歸納出轉(zhuǎn)運(yùn)問題的普通線性規(guī)劃模型這里xij表示從節(jié)點(diǎn)i到j(luò)的運(yùn)量，cij表示從i到j(luò)的運(yùn)價(jià)，ai表示產(chǎn)地i的產(chǎn)量，bj表示銷地j的銷量需求量。.第七講 網(wǎng)絡(luò)分析最短路問題 最短路問題普通描畫為：在一網(wǎng)絡(luò)中，給定兩個(gè)點(diǎn)vs和vt，找到一條從vs到vt的路，使這條路上一切弧的權(quán)數(shù)之和最小，這條路就

15、是vs到vt的最短路。這條路上一切弧的權(quán)數(shù)之和稱為vs到vt的間隔。 最短道路問題可以采用標(biāo)號(hào)法等方法進(jìn)展求解，也可借助相關(guān)的運(yùn)籌學(xué)軟件包進(jìn)展求解。這里xij表示從節(jié)點(diǎn)i到j(luò)的運(yùn)量，cij表示從i到j(luò)的運(yùn)價(jià)，ai表示產(chǎn)地i的產(chǎn)量，bj表示銷地j的銷量需求量。例 某電信公司方案在甲、乙兩地鋪設(shè)通訊電纜，圖是甲、乙兩地間的交通圖，圖中 v1，v2，v3，v4，v5，v6表示6個(gè)地名點(diǎn)，其中v1 表示甲地，v6表示乙地，點(diǎn)之間的連線邊表示兩地公路，邊上的數(shù)值表示兩地間公路的長度單位：千米，問如何鋪設(shè)能使甲、乙兩地的電纜長度最短？ . 經(jīng)標(biāo)號(hào)法求解最短路是v1-v2-v6，最短間隔是7+12=19千米

16、，所以應(yīng)在v1-v2，v2-v6間鋪設(shè)線路。(0)14(14)7819(7)(8)(19)11(11).練習(xí)：最短路為提高運(yùn)輸效率，請找出公司節(jié)點(diǎn)1到零售店節(jié)點(diǎn)11之間的最短途徑。.第七講 網(wǎng)絡(luò)分析最小支撐樹問題 一個(gè)連通無圈簡單圖稱為樹。假設(shè)圖G的一個(gè)支撐圖T是樹，那么稱T是圖G的一棵支撐樹。 如圖示出了一個(gè)圖G及其支撐樹T1，T2，T3。 .第七講 網(wǎng)絡(luò)分析最小支撐樹問題 設(shè)TkV，Ek是網(wǎng)絡(luò)N(G， )的一個(gè)棵支撐樹，那么Tk的邊集Ek中一切邊的權(quán)數(shù)之和稱為樹Tk的權(quán)，記為 。 即： 假設(shè)支撐樹T*的權(quán) 是N的一切支撐樹的權(quán)中最小者，那么稱T*為網(wǎng)絡(luò)N的最小支撐樹，簡稱最小樹。 即： 如

17、何找出網(wǎng)絡(luò)的最小樹就是最小支撐樹問題。最小支撐樹問題可以采用避圈法和破圈法等方法進(jìn)展求解，也可借助相關(guān)的運(yùn)籌學(xué)軟件包進(jìn)展求解。.第七講 網(wǎng)絡(luò)分析最小支撐樹問題 例某自然景區(qū)內(nèi)設(shè)有6個(gè)效力站和一個(gè)網(wǎng)絡(luò)中心，景區(qū)的管理部門決議鋪設(shè)光纖網(wǎng)絡(luò)，為各效力站點(diǎn)提供通訊線路。管理部門希望這個(gè)通訊線路的建立本錢盡能夠低。圖表示了效力站和網(wǎng)絡(luò)中心的分布情況，一個(gè)圓圈表示一個(gè)效力站或網(wǎng)絡(luò)中心，圓圈之間連線上的數(shù)字表示兩個(gè)站點(diǎn)或站點(diǎn)與網(wǎng)絡(luò)中心之間鋪設(shè)電纜的本錢單位：萬元。問應(yīng)如何設(shè)計(jì)該通訊線路？ 經(jīng)求解，結(jié)果如下圖，鋪設(shè)總本錢最小，為4+5+4+3+4+3=23萬元。.練習(xí)：最小支撐樹為節(jié)約本錢，請?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)系統(tǒng)

18、，使得城市1與鄉(xiāng)鎮(zhèn)2-10之間都有光纖連通，且鋪設(shè)總長度最少。地點(diǎn)23456789101949151511161622281612810191420369117121115441611815175712614136103715779108111299.第七講 網(wǎng)絡(luò)分析最大流問題 現(xiàn)實(shí)生活中，許多系統(tǒng)中都存在流量問題。如公路系統(tǒng)中存在車輛流，電力系統(tǒng)中存在電流，供水系統(tǒng)中存在水流，信息系統(tǒng)中存在信息流，金融系統(tǒng)中存在現(xiàn)金流等。例 迅達(dá)通訊公司運(yùn)用光纜網(wǎng)絡(luò)在不同地方傳送和其他信息。信息經(jīng)過光纜線和轉(zhuǎn)換點(diǎn)傳送。該公司的傳送網(wǎng)絡(luò)如下圖。一個(gè)圓圈代表一個(gè)轉(zhuǎn)換點(diǎn)，轉(zhuǎn)換點(diǎn)之間的連線上的數(shù)字表示該條光纜線的最大信息傳送才干。求該通訊網(wǎng)絡(luò)的最大傳輸才干。 .第七講 網(wǎng)絡(luò)分析最大流問題 (1) 容量網(wǎng)絡(luò)與網(wǎng)絡(luò)流 滿足如下規(guī)定的網(wǎng)絡(luò)稱之為容量網(wǎng)絡(luò)。 對(duì)于一個(gè)有向網(wǎng)絡(luò)N(V，A)，各弧的方向就是流量經(jīng)過的方向； 對(duì)網(wǎng)絡(luò)中的每一弧vi，vjA，都賦予一個(gè)容量rvi，vjrij 0，表示允許經(jīng)過該弧的最大流量； 網(wǎng)絡(luò)有一個(gè)始點(diǎn)vs和一個(gè)終點(diǎn)vt。除vs和vt外的其他點(diǎn)稱之為中間點(diǎn)。 所謂網(wǎng)絡(luò)流，指某種流在網(wǎng)絡(luò)