管理運籌學第7章圖與網(wǎng)絡模型課件

第7章圖與網(wǎng)絡模型2/6/20231課件教學目標與要求【教學目標】通過對本章的學習，理解圖的基本概念；掌握最小支撐樹、最短路、最大流、中國郵路問題的求法；會利用相關模型解決合理組織人力、物力、財力的優(yōu)化問題?！局R結(jié)構(gòu)】2/6/20232課件導入案例——七橋問題18世紀德國哥尼斯堡如圖（a）七座橋，能否不重復一次走完并回到出發(fā)地？（a）七橋問題示意圖（b）七橋問題簡單圖1736年，歐拉在圣彼得堡科學院作了一次學術報告。在報告中，他證明了鑒別任一圖形能否一筆畫出的準則，即歐拉定理。2/6/20233課件導入案例運籌學中把一些研究對象用節(jié)點表示，對象之間的關系用連線邊表示。用點、邊的集合構(gòu)成圖。圖論是研究有節(jié)點和邊所組成圖形的數(shù)學理論和方法。圖是網(wǎng)絡分析的基礎，根據(jù)具體研究的網(wǎng)絡對象（如：鐵路網(wǎng)、電力網(wǎng)、通信網(wǎng)等），賦予圖中各邊某個具體的參數(shù)，如時間、流量、費用、距離等，規(guī)定圖中各節(jié)點代表具體網(wǎng)絡中任何一種流動的起點，中轉(zhuǎn)點或終點，然后利用圖論方法來研究各類網(wǎng)絡結(jié)構(gòu)和流量的優(yōu)化分析。圖論廣泛地應用于物理學、化學、信息論、科學管理、電子計算機等各個領域。如在管理中網(wǎng)絡合理架設、網(wǎng)絡承載能力分析、服務設施布點、匹配問題等。2/6/20235課件本章主要內(nèi)容7.1圖的基本概念7.2樹圖及圖的最小支撐樹7.2.1樹圖的基本性質(zhì)7.2.2最小支撐樹的求法:避圈法和破圈法案例7-1印第安那州公路規(guī)劃問題7.3最短路問題7.3.1兩點間最短路的Dijkstra標號算法7.3.3各點間最短路的矩陣算法*案例7-2設備更新問題7.4中國郵遞員問題案例7-3貨場巡視路線7.5網(wǎng)絡最大流問題7.5.1基本概念7.5.2Ford-Fulkerson標號算法案例7-4航空公司的最大流量7.6最小費用流問題*7.6.1最小費用流的數(shù)學模型7.6.2最小費用最大流的標號算法案例7-5貨物配送問題本章小結(jié)2/6/20236課件7.1.1圖的若干示例【例7.1】

有A、B、C、D、E5個球隊，已比賽過，就在這兩隊相應的點之間連一條線.

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

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

其余點在中從V與的連線中找一條最小邊,

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

【例7.6】2/6/202317課件7.3.1求兩點間最短路的Dijkstra標號算法【例7.7】用Dijkstra方法求點S到點T的最短路及路長。056813最短路線:SACT

或:SAT最短路長:13(1)給S標號0(2)V={S},補集CV={A,B,C,T},min{LSS+DSB,LSS+DSA}={0+5,0+6}=5

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

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

給T標號13,[A,C]或[A,T]加粗WinQSB演示Excel演示Lingo演示2/6/202318課件7.3.3求網(wǎng)絡各點之間最短路的矩陣計算法*【例7.9】求各點間最短路矩陣解(1)構(gòu)造鄰接矩陣(2)計算經(jīng)過1個中間點的可達矩陣一般地(3)利用遞推公式計算經(jīng)過1個中間點的可達矩陣自編軟件ExcelORM所見即所得.2/6/202319課件7.4中國郵遞員問題抽象為圖的語言，就是給定一個連通圖，在每邊上賦予一個非負的權(quán)，要求一個圈，過每邊至少一次，并使圈的總權(quán)最小。我國管梅谷教授在1962年首先提出的，因此在國際上通稱為中國郵遞員問題。結(jié)論1：若網(wǎng)絡圖上的所有點均為偶點，則郵遞員可以走遍所有街道，做到每條街道只走一次而不重復。結(jié)論2：最短的投遞路線具有這樣的性質(zhì)：①有奇點連線的邊最多重復一次；②在該網(wǎng)絡圖的每個回路上，有重復的邊的長度不超過回路總長的一半。【例7.10】

解(1)找出奇點(4個)(2)連接不超過回路長一半的邊組成兩對(虛線)(3)虛線重復一次,其余邊只走一次(有多種走法)2/6/202321課件案例7-3貨場巡視路線解(1)找出奇點(6個)(2)連接不超過回路長一半的邊組成兩對(虛線)(3)虛線重復一次,其余邊只走一次(有多種走法)2/6/202322課件7.5網(wǎng)絡最大流問題2/6/202323課件7.5.1基本概念2/6/202325課件7.5.1基本概念2/6/202326課件7.5.2最大流問題Ford-Fulkerson標號算法【例7.12】用標號法求網(wǎng)絡的最大流。解給v1標號（0，+∞）[v1,v3]非飽和弧，給v3標號，標號值min{+∞,9-5}=4，即v3標號（v1,4）[v3,v6]非飽和弧，給v6標號，標號值min{4,5-0}=4，即v6標號（v3,4）[v6,v7]非飽和弧，給v7標號，標號值min{4,10-3}=4，即v7標號（v6,4）逆向追蹤找到增廣鏈v1v3v6v7,最大可調(diào)整流量ε(t)=4增廣鏈上所有的弧均為前向弧，流量+4。2/6/202329課件案例7-4航空公司的最大流量3(0)2(0)1(0)3(0)2(0)洛杉磯JSDeDL朱諾西雅圖丹佛達拉斯解先繪制容量網(wǎng)絡圖再用Ford-Fulkerson標號算法3(2)2(2)3(2)(J,1)(S,1)(L,1)1(1)2(1)3(3)最小割2/6/202330課件7.6.1最小費用流的數(shù)學模型2/6/202331課件7.6.2最小費用最大流的標號算法2/6/202332課件7.6.2最小費用最大流的標號算法承【例7.15】，用標號算法求從節(jié)點1到節(jié)點5的最小費用最大流。解賦初始流0流,構(gòu)造容量網(wǎng)絡由費用構(gòu)造加權(quán)網(wǎng)絡(零流弧以bij加權(quán),飽和弧構(gòu)造反向弧以-bij反向加權(quán),非飽和且非零流以bij和-bij雙向加權(quán)).并求最短路即增廣鏈.在增廣鏈上調(diào)整流量2/6/202333課件案例7-5貨物配送問題三個供應商運往每個倉庫最大運輸量為6;兩個倉庫運往每個工廠的最大運輸量為6;單位費用=商品價格+單位運價;倉庫到工廠的運輸單價為已知數(shù);700200500400v1v3v4v2v5v6v7供應商倉庫工廠(6,)(6,)(6,)(6,)(6,)(6,)234402296023000232002315023200(6,)(6,)(6,)(6,)供應商商品價格單位運價倉庫1倉庫2123225002270022300300+4×運送路程200+5×運送路程500+2×運送路程300+4×160=940200+5×50=450500+2×200=900300+4×40=460200+5×60=500500+2×100=700設fij表示從節(jié)點i到j的流量,則有:fij<=6;目標總費用最小:min=∑bijfij;供應能力限制:f14+f15<=10;f24+f25<=10;f34+f35<=10;工廠需求限制:f46+f56=10;f47+f57=6;中間點平衡: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;!總費用最小;f14+f15<=10;!產(chǎn)大于銷，運出貨物不超過各供貨商供應能力;f24