实用管理科学解读ppt课件

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,1,0-,實用管理科學陳明德、陳武林 著,前程文化,Ch10,網路分析,本章結構,網路簡介,最短路徑問題,最小展開樹問題,最大流量問題,1,0-,網路名詞介紹,(1/2),網路,(network),：,由無數個節點,(nodes),與弧,(arcs),所構成的；通常節點是用來代表某一實際的地點，而弧則是用來表示連接兩個點。,路徑,(path),：,連接兩個節點的一系列的弧所組成的。,循環,(loop,或,cycle),：,一路徑的起點與終點重疊。,1,0-,網路名詞介紹,(2/2),展開樹,(spanning tree),：,網路將一些弧刪除後形成樹，而且連接網路的任何一節點之子網路。,樹,(tree),：,不具有任何的循環的網路。,1,0-,最短路徑演算法,(1/2),貼標籤法,:,每一個標上標籤的結點，,包含一對數字，分別表示從起點,(,節點,1),到此節點的最短距離與最短路徑上的前一節點編號。,1,0-,最短路徑演算法,(2/2),重覆執行下列步驟,:,辨識,候選未貼標籤節點,。,候選未貼標籤節點中，挑選一節點，使得起始節點到此節點的距離最短。,1,0-,最短路徑問題範例,題目請參考課本,p248,1,0-,最短路徑解法一：貼標籤法,(1/2),1,0-,最短路徑解法一：貼標籤法,(2/2),1,0-,最短路徑解法二：線性,/,整數規劃,Min,20X12+16X13+6(X23+X32)+12(X24+X42)+15X35+8(X45+X54)+25X27+11X47+5X56+18X67,St.,X12+X13=1,X12+X32+X42=X23+X24+X25,X13+X23=X32+X35,X24+X54=X42+X45+X47,X35+X45=X54+X56,X56=X67,X27+X47+X67=1,Xij,=0/1,1,0-,最短路徑活用範例一,設備租賃問題,（題目請參考課本,p248,範例,10.1,）,1,0-,設備租賃問題的解法,根據表,10.6,之成本分析，本題可用圖,10.5,的網路圖來進行分析,1,0-,最短路徑活用範例二,最安全路徑問題,（題目請參考課本,p254,範例,10.2,）,1,0-,最安全路徑問題的解法,1,0-,最小展開樹問題,最小展開樹,：,尋找一個能夠連接各個結點而且弧的總長度最小的樹。,最小展開樹演算法,步驟一,：從任何的一節點開始進行，然後將它連到網路上最近的節點。,步驟二,：在未連接節點中，挑選與已連接節點最近的節點，並連接之。重覆執行本步驟，直到所有的節點都已經連接為止。,1,0-,最小展開樹範例,最小展開樹問題,（題目請參考課本,p255,）,1,0-,最小展開樹問題的解法,1,0-,最大流量問題,最大流量問題：,給定一個網路，尋找從起始節點到目的節點的最大流量。,最大流量演算法,尋找從任何起點至終點的路徑，條件是此路徑上的每一弧上的最大流量必須都大於零。,儘可能地增加此路徑上的流量。,持續尋找任何流量大於零的路徑；然後儘可能地增加此路徑上的流量。,1,0-,最大流量範例,題目請參考課本,p258,1,0-,最大流量解法一,(1/7),最大流量解法一解法過程,1,0-,最大流量解法一,(2/7),1,0-,最大流量解法一,(3/7),1,0-,最大流量解法一,(4/7),1,0-,最大流量解法一,(5/7),1,0-,最大流量解法一,(6/7),1,0-,最大流量解法一,(7/7),1,0-,最大流量解法二：,線性,/,整數規劃,Max,X71,St.,X71=X12+X13+X14,X12+X32=X23+X25,X13+X23=X32+X34+X35+X36,X14+X34=X46,X25+X35+X65=X56+X57,X36+X46+X56=X65+X67,X57+X67=X71,X12=5,（等）,1,0-,