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

第7章圖與網(wǎng)絡(luò)模型2/6/20231課件教學(xué)目標(biāo)與要求【教學(xué)目標(biāo)】通過對本章的學(xué)習(xí)，理解圖的基本概念；掌握最小支撐樹、最短路、最大流、中國郵路問題的求法；會利用相關(guān)模型解決合理組織人力、物力、財(cái)力的優(yōu)化問題?！局R結(jié)構(gòu)】2/6/20232課件導(dǎo)入案例——七橋問題18世紀(jì)德國哥尼斯堡如圖（a）七座橋，能否不重復(fù)一次走完并回到出發(fā)地？（a）七橋問題示意圖（b）七橋問題簡單圖1736年，歐拉在圣彼得堡科學(xué)院作了一次學(xué)術(shù)報(bào)告。在報(bào)告中，他證明了鑒別任一圖形能否一筆畫出的準(zhǔn)則，即歐拉定理。2/6/20233課件導(dǎo)入案例運(yùn)籌學(xué)中把一些研究對象用節(jié)點(diǎn)表示，對象之間的關(guān)系用連線邊表示。用點(diǎn)、邊的集合構(gòu)成圖。圖論是研究有節(jié)點(diǎn)和邊所組成圖形的數(shù)學(xué)理論和方法。圖是網(wǎng)絡(luò)分析的基礎(chǔ)，根據(jù)具體研究的網(wǎng)絡(luò)對象（如：鐵路網(wǎng)、電力網(wǎng)、通信網(wǎng)等），賦予圖中各邊某個具體的參數(shù)，如時(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)、匹配問題等。2/6/20235課件本章主要內(nèi)容7.1圖的基本概念7.2樹圖及圖的最小支撐樹7.2.1樹圖的基本性質(zhì)7.2.2最小支撐樹的求法:避圈法和破圈法案例7-1印第安那州公路規(guī)劃問題7.3最短路問題7.3.1兩點(diǎn)間最短路的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.2Ford-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é)2/6/20236課件7.1.1圖的若干示例【例7.1】

有A、B、C、D、E5個球隊(duì)，已比賽過，就在這兩隊(duì)相應(yīng)的點(diǎn)之間連一條線.

[P1]【例7.2】8種化學(xué)藥品，不能存放在同一個庫房里的用連線表示?！纠?.3】若在五支球隊(duì)比賽中，甲勝乙表示為“甲→乙”，則右圖表明A三勝一負(fù)，B和E一勝一負(fù)，C和D一勝兩負(fù)。2/6/20237課件7.1.2圖的基本概念次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)，懸掛點(diǎn)，懸掛邊點(diǎn)的關(guān)聯(lián)邊的數(shù)目稱為的次(也稱度或線度)，記為d(v)(環(huán)在計(jì)算時(shí)算作兩次，稱為入次和出次)；次為奇數(shù)的點(diǎn)稱為奇點(diǎn)；次為偶數(shù)的點(diǎn)稱為偶點(diǎn)；次為0的點(diǎn)稱為孤立點(diǎn)；次為1的點(diǎn)稱為懸掛點(diǎn)；與懸掛點(diǎn)相邊關(guān)聯(lián)的邊稱為懸掛邊?！径ɡ?.1】圖中，所有頂點(diǎn)的次之和是邊數(shù)的2倍?！径ɡ?.2】任一個圖中，奇點(diǎn)的個數(shù)為偶數(shù)。鏈，圈，路，回路，連通圖點(diǎn)和邊的交錯序列中，若邊各不相同稱為鏈；封閉的鏈稱為圈；在鏈中如果點(diǎn)也各不相同稱為路；起點(diǎn)與終點(diǎn)重合的路稱為回路；任意兩點(diǎn)之間至少能找到一條鏈的圖稱為連通圖。圖7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6圖7.5(b)2/6/20239課件7.1.2圖的基本概念圖7.5(a)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6圖7.5(b)完全圖，子圖，支撐圖（部分圖）一個簡單圖中若任意兩點(diǎn)之間均有邊相連，稱這樣的圖為完全圖，如圖7.5(b)；圖

如果滿足的子圖；如果滿足的一個支撐圖（或稱為部分圖）。如圖7.6(b)是圖(a)的子圖，并不是支撐圖，圖(c)是圖(a)的支撐圖。2/6/202310課件承【例7-2】這是一個染色問題,其方法:找出次數(shù)最大的點(diǎn),將其與不相鄰的點(diǎn)組成新的點(diǎn)集;再從其余的子圖中找出次數(shù)最大的點(diǎn),將其與不相鄰的點(diǎn)組成新的點(diǎn)集,直到子圖的點(diǎn)集為空.v1v8v2v7v3v6v5v4{,}{,}{,,}{}7.1.2圖的基本概念至少需要3個庫房2/6/202311課件7.2.1樹圖的概念和性質(zhì)2/6/202313課件7.2.2最小支撐樹的求法——避圈法任選vi,使vi∈V,

其余點(diǎn)在中從V與的連線中找一條最小邊,

使其包含在最小支撐樹內(nèi)所有點(diǎn)均在V中?結(jié)束是否ABCDEF872594631【例7.4】求下圖最小支撐樹W(T*)=172/6/202314課件7.2.2最小支撐樹的求法——破圈法任取一個圈,從圈中去掉一條最大的邊(如果有兩條或兩條以上的邊都是權(quán)最大的邊,則任意去掉其中一條).在余下的圖中重復(fù)這個步驟,直到不含圈的圖為止,此時(shí)的圖便是最小樹.ABDEF82594631C743取回路ABC，去掉最大邊[A,B]；取回路BCE，去掉最大邊[B,E]；取回路BCED，去掉最大邊[D,E]；取回路BCEFD，去掉最大邊[B,D]W(T*)=172/6/202315課件7.3.1求兩點(diǎn)間最短路的Dijkstra標(biāo)號算法2444633223322ABCTDEFS02356789結(jié)論：最短路徑SADT，或SCFT；最短路長：9

【例7.6】2/6/202317課件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},min{LSS+DSB,LSS+DSA}={0+5,0+6}=5

給B標(biāo)號5,[S,B]加粗(2)V={S,B},CV={A,C,T},min{LSS+DSA,LSB+DBC}={0+6,5+8}=6

給A標(biāo)號6,[S,A]加粗(3)V={S,B,A},CV={C,T},min{LSA+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},min{LSA+DAT,LSC+DCT}={6+7,8+5}=13

給T標(biāo)號13,[A,C]或[A,T]加粗WinQSB演示Excel演示Lingo演示2/6/202318課件7.3.3求網(wǎng)絡(luò)各點(diǎn)之間最短路的矩陣計(jì)算法*【例7.9】求各點(diǎn)間最短路矩陣解(1)構(gòu)造鄰接矩陣(2)計(jì)算經(jīng)過1個中間點(diǎn)的可達(dá)矩陣一般地(3)利用遞推公式計(jì)算經(jīng)過1個中間點(diǎn)的可達(dá)矩陣自編軟件ExcelORM所見即所得.2/6/202319課件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ù)的邊的長度不超過回路總長的一半?！纠?.10】

解(1)找出奇點(diǎn)(4個)(2)連接不超過回路長一半的邊組成兩對(虛線)(3)虛線重復(fù)一次,其余邊只走一次(有多種走法)2/6/202321課件案例7-3貨場巡視路線解(1)找出奇點(diǎn)(6個)(2)連接不超過回路長一半的邊組成兩對(虛線)(3)虛線重復(fù)一次,其余邊只走一次(有多種走法)2/6/202322課件7.5網(wǎng)絡(luò)最大流問題2/6/202323課件7.5.1基本概念2/6/202325課件7.5.1基本概念2/6/202326課件7.5.2最大流問題Ford-Fulkerson標(biāo)號算法【例7.12】用標(biāo)號法求網(wǎng)絡(luò)的最大流。解給v1標(biāo)號（0，+∞）[v1,v3]非飽和弧，給v3標(biāo)號，標(biāo)號值min{+∞,9-5}=4，即v3標(biāo)號（v1,4）[v3,v6]非飽和弧，給v6標(biāo)號，標(biāo)號值min{4,5-0}=4，即v6標(biāo)號（v3,4）[v6,v7]非飽和弧，給v7標(biāo)號，標(biāo)號值min{4,10-3}=4，即v7標(biāo)號（v6,4）逆向追蹤找到增廣鏈v1v3v6v7,最大可調(diào)整流量ε(t)=4增廣鏈上所有的弧均為前向弧，流量+4。2/6/202329課件案例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)2(1)3(3)最小割2/6/202330課件7.6.1最小費(fèi)用流的數(shù)學(xué)模型2/6/202331課件7.6.2最小費(fèi)用最大流的標(biāo)號算法2/6/202332課件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)整流量2/6/202333課件案例7-5貨物配送問題三個供應(yīng)商運(yùn)往每個倉庫最大運(yùn)輸量為6;兩個倉庫運(yùn)往每個工廠的最大運(yùn)輸量為6;單位費(fèi)用=商品價(jià)格+單位運(yùn)價(jià);倉庫到工廠的運(yùn)輸單價(jià)為已知數(shù);700200500400v1v3v4v2v5v6v7供應(yīng)商倉庫工廠(6,)(6,)(6,)(6,)(6,)(6,)234402296023000232002315023200(6,)(6,)(6,)(6,)供應(yīng)商商品價(jià)格單位運(yùn)價(jià)倉庫1倉庫2123225002270022300300+4×運(yùn)送路程200+5×運(yùn)送路程500+2×運(yùn)送路程300+4×160=940200+5×50=450500+2×200=900300+4×40=460200+5×60=500500+2×100=700設(shè)fij表示從節(jié)點(diǎn)i到j(luò)的流量,則有:fij<=6;目標(biāo)總費(fèi)用最小:min=∑bijfij;供應(yīng)能力限制:f14+f15<=10;f24+f25<=10;f34+f35<=10;工廠需求限制:f46+f56=10;f47+f57=6;中間點(diǎn)平衡:f14+f24+f34=f46+f47;f15+f25+f35=f56+f57;2/6/202334課件案例7-5貨物配送問題有如下Lingo模型：min=23440*f14+22960*f15+23150*f24+23200*f25+23200*f34+23000*f35+200*f46+700*f47+400*f56+500*f57;!總費(fèi)用最小;f14+f15<=10;!產(chǎn)大于銷，運(yùn)出貨物不超過各供貨商供應(yīng)能力;f24