管理運(yùn)籌學(xué)圖與網(wǎng)絡(luò)模型課件

1、第7章 圖與網(wǎng)絡(luò)模型7/26/20221課件教學(xué)目標(biāo)與要求【教學(xué)目標(biāo)】通過對本章的學(xué)習(xí)，理解圖的基本概念；掌握最小支撐樹、最短路、最大流、中國郵路問題的求法；會利用相關(guān)模型解決合理組織人力、物力、財(cái)力的優(yōu)化問題。【知識結(jié)構(gòu)】7/26/20222課件導(dǎo)入案例七橋問題18世紀(jì)德國哥尼斯堡如圖（a）七座橋，能否不重復(fù)一次走完并回到出發(fā)地？（a）七橋問題示意圖（b）七橋問題簡單圖1736年，歐拉在圣彼得堡科學(xué)院作了一次學(xué)術(shù)報(bào)告。在報(bào)告中，他證明了鑒別任一圖形能否一筆畫出的準(zhǔn)則，即歐拉定理。7/26/20223課件導(dǎo)入案例四色問題“任何一張地圖只用四種顏色就能使有共同邊界的國家著上不同的顏色?！?185

2、2年，英國搞地圖著色工作的格思里，首先提出了四色問題。 1872年，英國數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會提出這個問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題。 美國數(shù)學(xué)教授哈肯和阿佩爾于1976年6月,使用伊利諾斯大學(xué)的電子計(jì)算機(jī)計(jì)算了1200個小時，作了100億個判斷，終于完成了四色定理的證明。 不過不少數(shù)學(xué)家認(rèn)為應(yīng)該有一種簡捷明快的書面證明方法。各省用點(diǎn)表示,有邊界接壤的用連線表示,則:這張地圖有幾種顏色?能區(qū)分各省的邊界嗎?7/26/20224課件導(dǎo)入案例運(yùn)籌學(xué)中把一些研究對象用節(jié)點(diǎn)表示，對象之間的關(guān)系用連線邊表示。用點(diǎn)、邊的集合構(gòu)成圖。圖論是研究有節(jié)點(diǎn)和邊所組成圖形的數(shù)學(xué)理論和方法。圖是網(wǎng)絡(luò)

3、分析的基礎(chǔ)，根據(jù)具體研究的網(wǎng)絡(luò)對象（如：鐵路網(wǎng)、電力網(wǎng)、通信網(wǎng)等），賦予圖中各邊某個具體的參數(shù)，如時間、流量、費(fèi)用、距離等，規(guī)定圖中各節(jié)點(diǎn)代表具體網(wǎng)絡(luò)中任何一種流動的起點(diǎn)，中轉(zhuǎn)點(diǎn)或終點(diǎn)，然后利用圖論方法來研究各類網(wǎng)絡(luò)結(jié)構(gòu)和流量的優(yōu)化分析。圖論廣泛地應(yīng)用于物理學(xué)、化學(xué)、信息論、科學(xué)管理、電子計(jì)算機(jī)等各個領(lǐng)域。如在管理中網(wǎng)絡(luò)合理架設(shè)、網(wǎng)絡(luò)承載能力分析、服務(wù)設(shè)施布點(diǎn)、匹配問題等。7/26/20225課件本章主要內(nèi)容 7.1 圖的基本概念7.2 樹圖及圖的最小支撐樹7.2.1 樹圖的基本性質(zhì)7.2.2 最小支撐樹的求法:避圈法和破圈法案例7-1 印第安那州公路規(guī)劃問題7.3 最短路問題7.3.1 兩點(diǎn)

4、間最短路的Dijkstra標(biāo)號算法7.3.3 各點(diǎn)間最短路的矩陣算法*案例7-2 設(shè)備更新問題7.4 中國郵遞員問題案例7-3 貨場巡視路線7.5 網(wǎng)絡(luò)最大流問題7.5.1 基本概念7.5.2 Ford-Fulkerson標(biāo)號算法案例7-4 航空公司的最大流量7.6 最小費(fèi)用流問題*7.6.1 最小費(fèi)用流的數(shù)學(xué)模型7.6.2 最小費(fèi)用最大流的標(biāo)號算法案例7-5 貨物配送問題本章小結(jié)7/26/20226課件7.1.1 圖的若干示例【例7.1】 有A、B、C、D、E5個球隊(duì)，已比賽過，就在這兩隊(duì)相應(yīng)的點(diǎn)之間連一條線.P1【例7.2】 8種化學(xué)藥品，不能存放在同一個庫房里的用連線表示。 【例7.3】

5、若在五支球隊(duì)比賽中，甲勝乙表示為“甲乙”，則右圖表明A三勝一負(fù)，B和E一勝一負(fù)，C和D一勝兩負(fù)。7/26/20227課件7.1.2 圖的基本概念圖（Graph）由點(diǎn)（Vertex）和點(diǎn)之間的連線所構(gòu)成的集合。不帶箭頭的連線稱為邊（Edge）；帶前頭的連線稱為?。ˋrc）。點(diǎn)和邊的集合稱為無向圖（Undirected graph），如圖7.5(a)，簡稱圖，用G=V，E表示；點(diǎn)和弧的集合稱為有向圖（Directed graph），如圖7.5(b)，用D=V，A表示。有向圖去掉箭頭所形成的無向圖稱為該有向圖的基礎(chǔ)圖（underlying graph）。端點(diǎn)，關(guān)聯(lián)邊，相鄰 若邊 e=u,vE，則稱

6、u,v是e 的端點(diǎn)，稱e 是點(diǎn)u或v的關(guān)聯(lián)邊。有公共關(guān)聯(lián)邊的點(diǎn)稱為點(diǎn)相鄰；公共端點(diǎn)的邊稱為邊相鄰。環(huán)，多重邊，簡單圖，多重圖 兩個端點(diǎn)重合的邊稱為環(huán)；若兩個點(diǎn)之間有多于一條的邊，稱為多重邊；一個無環(huán)、無多重邊的圖稱為簡單圖；一個無環(huán)，但允許有多重邊的圖稱為多重圖。圖7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6圖7.5(b)7/26/20228課件7.1.2 圖的基本概念次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)，懸掛點(diǎn)，懸掛邊 點(diǎn)的關(guān)聯(lián)邊的數(shù)目稱為的次(也稱度或線度)，記為d(v)(環(huán)在計(jì)算時算作兩次，稱為入次和出次)；次為奇數(shù)的點(diǎn)稱為奇點(diǎn)；次為偶數(shù)的點(diǎn)稱為偶點(diǎn)；次為0的點(diǎn)稱為

7、孤立點(diǎn)；次為1的點(diǎn)稱為懸掛點(diǎn)；與懸掛點(diǎn)相邊關(guān)聯(lián)的邊稱為懸掛邊。 【定理7.1】 圖中，所有頂點(diǎn)的次之和是邊數(shù)的2倍。【定理7.2】 任一個圖中，奇點(diǎn)的個數(shù)為偶數(shù)。鏈，圈，路，回路，連通圖 點(diǎn)和邊的交錯序列中，若邊各不相同稱為鏈；封閉的鏈稱為圈；在鏈中如果點(diǎn)也各不相同稱為路；起點(diǎn)與終點(diǎn)重合的路稱為回路；任意兩點(diǎn)之間至少能找到一條鏈的圖稱為連通圖。圖7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6圖7.5(b)7/26/20229課件7.1.2 圖的基本概念圖7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6圖7.5(b)完全圖，子圖，

8、支撐圖（部分圖） 一個簡單圖中若任意兩點(diǎn)之間均有邊相連，稱這樣的圖為完全圖，如圖7.5(b) ；圖如果滿足 的子圖；如果滿足 的一個支撐圖（或稱為部分圖）。如圖7.6(b)是圖(a)的子圖，并不是支撐圖，圖(c)是圖(a)的支撐圖。7/26/202210課件承【例7-2】這是一個染色問題,其方法: 找出次數(shù)最大的點(diǎn),將其與不相鄰的點(diǎn)組成新的點(diǎn)集;再從其余的子圖中找出次數(shù)最大的點(diǎn),將其與不相鄰的點(diǎn)組成新的點(diǎn)集,直到子圖的點(diǎn)集為空.v1v8v2v7v3v6v5v4 , , , , 7.1.2 圖的基本概念至少需要3個庫房7/26/202211課件7.2.1 樹圖的概念和性質(zhì)樹圖，簡稱樹，記作T(V

9、,E)：是一類簡單而十分有用的圖，其定義是無圈的聯(lián)通圖。現(xiàn)實(shí)生活中樹圖隨處可見，如管理組織機(jī)構(gòu)圖、決策樹圖、聚類分析的“龍骨圖”、磁盤文件存放路徑圖、家族族譜圖、經(jīng)濟(jì)管理中的因果分析圖（魚刺圖）等等，因其與大自然中的樹的特征相似而得名。 下面不加證明地給出樹的一些重要性質(zhì)。性質(zhì)1 任何樹圖必存在懸掛點(diǎn)。如圖7.8有3個懸掛點(diǎn)。性質(zhì)2 具有p個點(diǎn)的樹圖的邊數(shù)恰好為p-1條邊。如圖7.8有4個點(diǎn)、3條邊。性質(zhì)3 任何具有p個點(diǎn)條邊的聯(lián)通圖是樹圖。性質(zhì)4 樹圖中任意兩點(diǎn)之間恰有一條鏈。性質(zhì)5 樹圖中任意兩點(diǎn)之間添加一條邊正好構(gòu)成一個圈。如果圖T=(V,E)是圖G=(V,E)的支撐圖，又是樹圖，則稱T

10、是G的一個支撐樹（或稱為部分樹）。例如圖7.8是圖7.6(a)的一個支撐樹。7/26/202212課件7.2.1 樹圖的概念和性質(zhì)7/26/202213課件7.2.2 最小支撐樹的求法避圈法任選vi,使viV,其余點(diǎn)在 中從V與 的連線中找一條最小邊,使其包含在最小支撐樹內(nèi)所有點(diǎn)均在V中?結(jié)束是否ABCDEF872594631【例7.4】求下圖最小支撐樹 W(T*)=17 7/26/202214課件7.2.2 最小支撐樹的求法破圈法任取一個圈,從圈中去掉一條最大的邊(如果有兩條或兩條以上的邊都是權(quán)最大的邊,則任意去掉其中一條).在余下的圖中重復(fù)這個步驟,直到不含圈的圖為止,此時的圖便是最小樹.

11、ABDEF82594631C743取回路ABC，去掉最大邊A, B ；取回路BCE，去掉最大邊B, E ；取回路BCED，去掉最大邊D, E ；取回路BCEFD，去掉最大邊B, DW(T*)=177/26/202215課件案例7-1 印第安那州公路規(guī)劃問題(1)(2)(3)(4)(5)(1)Gary(2)Fort Wayne(3)Evansvile(4)Terre Haute(5)South Hend13221716458132290201792172901133031642011131965879303196因政治原因不能建造連接(1)和(2)的公路以及連接(3)和(5)的公路.如何建造可使

12、總施工長度最短?123452171645829020179196113W(T*)=414WinQSB演示Excel演示Lingo演示7/26/202216課件7.3.1 求兩點(diǎn)間最短路的Dijkstra標(biāo)號算法2444633223322ABCTDEFS02356789結(jié)論：最短路徑SADT，或SCFT；最短路長：9 【例7.6】7/26/202217課件7.3.1 求兩點(diǎn)間最短路的Dijkstra標(biāo)號算法【例7.7】 用Dijkstra方法求點(diǎn)S到點(diǎn)T的最短路及路長。056813最短路線:SACT 或:SAT最短路長:13(1)給S標(biāo)號0(2)V=S,補(bǔ)集CV=A,B,C,T,minLSS+D

13、SB,LSS+DSA=0+5,0+6=5給B標(biāo)號5,S,B加粗(2)V=S,B,CV=A,C,T,minLSS+DSA,LSB+DBC=0+6,5+8=6給A標(biāo)號6,S,A加粗(3)V=S,B,A,CV=C,T,minLSA+DAC,LSA+DAT,LSB+DBC=6+2,6+7,5+6=8給C標(biāo)號8,A,C加粗(3)V=S,B,A,C,CV=T,minLSA+DAT,LSC+DCT=6+7,8+5=13給T標(biāo)號13,A,C或A,T加粗WinQSB演示Excel演示Lingo演示7/26/202218課件7.3.3 求網(wǎng)絡(luò)各點(diǎn)之間最短路的矩陣計(jì)算法*【例7.9】 求各點(diǎn)間最短路矩陣 解 (1)

14、構(gòu)造鄰接矩陣 (2)計(jì)算經(jīng)過1個中間點(diǎn)的可達(dá)矩陣一般地(3)利用遞推公式計(jì)算經(jīng)過1個中間點(diǎn)的可達(dá)矩陣自編軟件ExcelORM所見即所得.7/26/202219課件案例7-2 設(shè)備更新問題設(shè)備在各年年初的價格第1年第2年第3年第4年第5年1012131415使用不同時間（年）的設(shè)備所需要的維修費(fèi)用使用年數(shù)0-11-22-33-44-5維修費(fèi)用4691219v1 v2 v3 v4 v5 v6202941602231432332241416171819求費(fèi)用最小的設(shè)備更新計(jì)劃.Dijkstra標(biāo)號算法：先給v1標(biāo)號“0”給v2標(biāo)號“14”給v3標(biāo)號“20”014給v4標(biāo)號“29”給v5標(biāo)號“41”給

15、v6標(biāo)號“52”202941最優(yōu)路線：V1V3V6即第1年初購置，第3年初更新，第5年末結(jié)束。總費(fèi)用：52527/26/202220課件7.4 中國郵遞員問題抽象為圖的語言，就是給定一個連通圖，在每邊上賦予一個非負(fù)的權(quán)，要求一個圈，過每邊至少一次，并使圈的總權(quán)最小。 我國管梅谷教授在1962年首先提出的，因此在國際上通稱為中國郵遞員問題。結(jié)論1：若網(wǎng)絡(luò)圖上的所有點(diǎn)均為偶點(diǎn)，則郵遞員可以走遍所有街道，做到每條街道只走一次而不重復(fù)。結(jié)論2：最短的投遞路線具有這樣的性質(zhì)：有奇點(diǎn)連線的邊最多重復(fù)一次；在該網(wǎng)絡(luò)圖的每個回路上，有重復(fù)的邊的長度不超過回路總長的一半。 【例7.10】 解 (1)找出奇點(diǎn)(4

16、個)(2)連接不超過回路長一半的邊組成兩對(虛線)(3)虛線重復(fù)一次,其余邊只走一次(有多種走法)7/26/202221課件案例7-3 貨場巡視路線解 (1)找出奇點(diǎn)(6個)(2)連接不超過回路長一半的邊組成兩對(虛線)(3)虛線重復(fù)一次,其余邊只走一次(有多種走法)7/26/202222課件7.5 網(wǎng)絡(luò)最大流問題7/26/202223課件7.5.1 基本概念1. 容量網(wǎng)絡(luò)、弧的容量與流量容量網(wǎng)絡(luò)是指對網(wǎng)絡(luò)上的每條弧都給定一個最大通過能力。從vi到vj的最大通過能力，記為c(vi,vj)或cij，稱為弧vi,vj的容量。在容量網(wǎng)絡(luò)中規(guī)定一個發(fā)點(diǎn)s和一個收點(diǎn)t,其余點(diǎn)稱為中間點(diǎn)。在網(wǎng)絡(luò)中給弧加載

17、的負(fù)載量稱為弧的流量，記為f(vi,vj)或fij。網(wǎng)絡(luò)的最大流是指網(wǎng)絡(luò)中從發(fā)點(diǎn)s到收點(diǎn)t之間允許通過的最大流量。下圖為引例的最大流，v1為發(fā)點(diǎn)，v7為收點(diǎn)，其他為中間點(diǎn)，圖中各弧旁邊的數(shù)字表示為“容量(流量)”。7/26/202224課件7.5.1 基本概念7/26/202225課件7.5.1 基本概念7/26/202226課件7.5.1 基本概念7/26/202227課件7.5.2 最大流問題Ford-Fulkerson標(biāo)號算法7/26/202228課件7.5.2 最大流問題Ford-Fulkerson標(biāo)號算法【例7.12】 用標(biāo)號法求網(wǎng)絡(luò)的最大流。解 給v1標(biāo)號（0，+）v1,v3非飽和

18、弧，給v3標(biāo)號，標(biāo)號值min+ ,9-5=4，即v3標(biāo)號（v1,4）v3,v6非飽和弧，給v6標(biāo)號，標(biāo)號值min4 ,5-0=4，即v6標(biāo)號（v3,4）v6,v7非飽和弧，給v7標(biāo)號，標(biāo)號值min4 ,10-3=4，即v7標(biāo)號（v6,4）逆向追蹤找到增廣鏈v1v3v6v7,最大可調(diào)整流量(t)=4增廣鏈上所有的弧均為前向弧，流量+4。7/26/202229課件案例7-4 航空公司的最大流量3(0)2(0)1(0)3(0)2(0)洛杉磯JSDeDL朱諾 西雅圖 丹佛 達(dá)拉斯解 先繪制容量網(wǎng)絡(luò)圖 再用Ford-Fulkerson標(biāo)號算法3(2)2(2)3(2)(J,1)(S,1)(L,1)1(1)

19、2(1)3(3)最小割7/26/202230課件7.6.1 最小費(fèi)用流的數(shù)學(xué)模型7/26/202231課件7.6.2 最小費(fèi)用最大流的標(biāo)號算法7/26/202232課件7.6.2 最小費(fèi)用最大流的標(biāo)號算法承【例7.15】，用標(biāo)號算法求從節(jié)點(diǎn)1到節(jié)點(diǎn)5的最小費(fèi)用最大流。解 賦初始流0流,構(gòu)造容量網(wǎng)絡(luò)由費(fèi)用構(gòu)造加權(quán)網(wǎng)絡(luò)(零流弧以bij加權(quán),飽和弧構(gòu)造反向弧以-bij反向加權(quán),非飽和且非零流以bij和-bij雙向加權(quán)).并求最短路即增廣鏈.在增廣鏈上調(diào)整流量7/26/202233課件案例7-5 貨物配送問題三個供應(yīng)商運(yùn)往每個倉庫最大運(yùn)輸量為6;兩個倉庫運(yùn)往每個工廠的最大運(yùn)輸量為6;單位費(fèi)用=商品價格

20、+單位運(yùn)價;倉庫到工廠的運(yùn)輸單價為已知數(shù);700200500400v1v3v4v2v5v6v7供應(yīng)商 倉庫 工廠(6, )(6, )(6, )(6, )(6, )(6, )234402296023000232002315023200(6, )(6, )(6, )(6, )供應(yīng)商商品價格單位運(yùn)價倉庫1倉庫2123225002270022300300+4運(yùn)送路程200+5運(yùn)送路程500+2運(yùn)送路程300+4160=940200+550=450500+2200=900300+440=460200+560=500500+2100=700設(shè)fij表示從節(jié)點(diǎn)i到j(luò)的流量,則有:fij=6;目標(biāo)總費(fèi)用最小:min=bij