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

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

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

3、情況。 解： 設(shè)v1，v2，v3，v4分別表示大連、北京、深圳、上海四市，則他們之間的通航情況可表示為一個(gè)無(wú)向圖：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ì)獲勝球隊(duì)獲勝球隊(duì)A AB BA AA AC CA AA AD DD DB BC CB BB BD DD DC CD DC

4、C解：設(shè)v1，v2，v3，v4分別表示球隊(duì)A、B、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è)基本概念 若有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)邊。 若一條邊的兩個(gè)端點(diǎn)相同，則稱該邊

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

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

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

8、avav,.,2110),(1tttiijvva),2, 1(kt0ivkivkiiivvv1034120ivkiv第七講 網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念幾個(gè)基本概念 若給一個(gè)圖中的每一條邊（或弧）都賦予一個(gè)實(shí)數(shù) = (vi，vj)，所得的圖稱為一個(gè)賦權(quán)網(wǎng)絡(luò)圖。賦權(quán)無(wú)向圖和賦權(quán)有向圖統(tǒng)稱為網(wǎng)絡(luò)，記為N。這里， 稱為邊(vi，vj)的權(quán)數(shù)（或權(quán)）。 一般來(lái)講，圖論中所討論的圖，特別是在應(yīng)用圖論中所討論的圖多數(shù)是網(wǎng)絡(luò)。ijij第七講 網(wǎng)絡(luò)分析運(yùn)輸問(wèn)題 運(yùn)輸問(wèn)題一般描述為：一種物資有m個(gè)產(chǎn)地 ，其產(chǎn)量分別為ai，有n個(gè)銷地 ，其銷量分別為bj；從Ai至Bj的運(yùn)價(jià)為cij，問(wèn)如何設(shè)計(jì)調(diào)運(yùn)方案才能使總運(yùn)費(fèi)最

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

10、（元運(yùn)價(jià)（元/噸）（噸）（cij）產(chǎn)量（產(chǎn)量（ai）B1B2A112015011A214513015A31351409銷量（銷量（bj）1421 解：因?yàn)?=11+15+9=35， = 14+21=35， 所以這是一個(gè)產(chǎn)銷平衡問(wèn)題。miia1njjb1njjmiiba11目標(biāo)函數(shù)為： 其中xij為Ai至 Bj的運(yùn)量，因?yàn)槟钞a(chǎn)地運(yùn)往各銷地的運(yùn)量之和應(yīng)等于該產(chǎn)地的產(chǎn)量，所以有 : 。 又因各產(chǎn)地運(yùn)往某銷地的運(yùn)量之和應(yīng)等于該銷地的銷量（需求量），所以有: miijnjijxcz11min), 2 , 1( ,1miaxinjij), 2 , 1( ,1njbxjmiij第七講 網(wǎng)絡(luò)分析運(yùn)輸問(wèn)題產(chǎn)銷平

11、衡問(wèn)題產(chǎn)銷平衡運(yùn)輸問(wèn)題的一般模型為：應(yīng)用到本例中的實(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元。 ), 2 , 1, 2 , 1(0), 2 , 1(), 2 , 1(. t . smin1111njmixnjbxmiaxxczijjmiijinjijmiijnjijK?KKK)2 , 13 , 2 , 1(0211491511. t . s140135130145150120min322212312111323122211211323122211211jix

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

13、為Ai至 Bj的運(yùn)量，因?yàn)槟钞a(chǎn)地運(yùn)往各銷地的運(yùn)量之和應(yīng)不大于該產(chǎn)地的產(chǎn)量，所以有 : 。 又因各產(chǎn)地運(yùn)往某銷地的運(yùn)量之和應(yīng)等于該銷地的銷量（需求量），所以有: miijnjijxcz11min), 2 , 1( ,1miaxinjijK), 2 , 1( ,1njbxjmiij第七講 網(wǎng)絡(luò)分析運(yùn)輸問(wèn)題產(chǎn)銷不平衡問(wèn)題產(chǎn)大于銷運(yùn)輸問(wèn)題的一般模型為：應(yīng)用到本例中的實(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元。 ), 2 , 1, 2 , 1(0), 2 , 1()

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

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

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

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

18、46353425241514xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzTX)10,14,11,0,9 ,0,15,0,0,11(*5306*z第七講 網(wǎng)絡(luò)分析運(yùn)輸問(wèn)題轉(zhuǎn)運(yùn)問(wèn)題歸納出轉(zhuǎn)運(yùn)問(wè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的銷量（需求量）。jiijjijijijijiijijijijxbxxxxaxxxcz和對(duì)于所有的銷地節(jié)點(diǎn)轉(zhuǎn)運(yùn)節(jié)點(diǎn)起點(diǎn)節(jié)點(diǎn)運(yùn)出弧運(yùn)入弧運(yùn)入弧運(yùn)出弧運(yùn)入弧運(yùn)出弧所有弧0)(0)(. t . smin第七講 網(wǎng)絡(luò)分析最短路問(wèn)題 最短路問(wèn)題一般描述為：在一網(wǎng)絡(luò)中，

19、給定兩個(gè)點(diǎn)vs和vt，找到一條從vs到vt的路，使這條路上所有弧的權(quán)數(shù)之和最小，這條路就是vs到vt的最短路。這條路上所有弧的權(quán)數(shù)之和稱為vs到vt的距離。 最短路線問(wèn)題可以采用標(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的銷量（需求量）。例 某電信公司計(jì)劃在甲、乙兩地鋪設(shè)通信電纜，圖是甲、乙兩地間的交通圖，圖中 v1，v2，v3，v4，v5，v6表示6個(gè)地名點(diǎn)，其中v1 表示甲地，v6表示乙地，點(diǎn)之間的連線（邊）表示兩地公路，邊上的數(shù)值表示兩地間公路的長(zhǎng)度（單位：千米），問(wèn)如何鋪設(shè)能

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

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

22、：萬(wàn)元）。問(wèn)應(yīng)如何設(shè)計(jì)該通訊線路？ 經(jīng)求解，結(jié)果如圖所示，鋪設(shè)總成本最小，為4+5+4+3+4+3=23（萬(wàn)元）。練習(xí)：最小支撐樹(shù)為節(jié)約成本，請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)系統(tǒng)，使得城市1與鄉(xiāng)鎮(zhèn)2-10之間都有光纖連通，且鋪設(shè)總長(zhǎng)度最少。地點(diǎn)地點(diǎn)2 23 34 45 56 67 78 89 910101949151511161622281612810191420369117121115441611815175712614136103715779108111299第七講 網(wǎng)絡(luò)分析最大流問(wèn)題 現(xiàn)實(shí)生活中，許多系統(tǒng)中都存在流量問(wèn)題。如公路系統(tǒng)中存在車輛流，電力系統(tǒng)中存在電流，供水系統(tǒng)中存在水流，信息系統(tǒng)中存在信息流，金融系統(tǒng)中存在現(xiàn)金流等。例 迅達(dá)通訊公司使用光纜網(wǎng)絡(luò)在不同地方傳遞 和其他信息。信息通過(guò)光纜線和轉(zhuǎn)換點(diǎn)傳遞。該公司的傳送網(wǎng)絡(luò)如圖所示。一個(gè)圓圈代表一個(gè)轉(zhuǎn)換點(diǎn)，轉(zhuǎn)換點(diǎn)之間的連線上的數(shù)字表示該條光纜線的最大信息傳遞能力。求該通訊網(wǎng)絡(luò)的最大傳輸能力。 第七講 網(wǎng)絡(luò)分析最大流問(wèn)題 (1) 容量網(wǎng)絡(luò)與網(wǎng)絡(luò)流 滿足如下規(guī)定的網(wǎng)絡(luò)稱之為容量網(wǎng)絡(luò)。 對(duì)于一個(gè)有向網(wǎng)絡(luò)N(V，A)，各弧的方向就是流量通過(guò)的方向； 對(duì)網(wǎng)絡(luò)中的每一?。╲i，vj）A，都