实用管理科学解读课件.ppt

1、實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析本章結構網路簡介 最短路徑問題 最小展開樹問題 最大流量問題 0-1實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析網路名詞介紹(1/2)網路(network)：由無數個節點(nodes)與弧(arcs)所構成的；通常節點是用來代表某一實際的地點，而弧則是用來表示連接兩個點。路徑(path)：連接兩個節點的一系列的弧所組成的。循環(loop或cycle)：一路徑的起點與終點重疊。0-2實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前

2、程文化前程文化Ch10 網路分析網路分析網路名詞介紹(2/2)展開樹(spanning tree)：網路將一些弧刪除後形成樹，而且連接網路的任何一節點之子網路。樹(tree)：不具有任何的循環的網路。0-3實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最短路徑演算法(1/2)貼標籤法貼標籤法:每一個標上標籤的結點，包含一對數字，分別表示從起點(節點1)到此節點的最短距離與最短路徑上的前一節點編號。0-4實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最短路徑演算法(2/2)重覆執行下列步驟

3、:辨識候選未貼標籤節點候選未貼標籤節點。候選未貼標籤節點中，挑選一節點，使得起始節點到此節點的距離最短。0-5實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最短路徑問題範例 題目請參考課本p2480-6實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最短路徑解法一：貼標籤法(1/2)0-7實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最短路徑解法一：貼標籤法(2/2)0-8實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文

4、化前程文化Ch10 網路分析網路分析最短路徑解法二：線性/整數規劃Min 20X12+16X13+6(X23+X32)+12(X24+X42)+15X35+8(X45+X54)+25X27+11X47+5X56+18X67St.X12+X13=1 X12+X32+X42=X23+X24+X25X13+X23=X32+X35X24+X54=X42+X45+X47X35+X45=X54+X56X56=X67X27+X47+X67=1Xij=0/10-9實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最短路徑活用範例一設備租賃問題（題目請參考課本p

5、248 範例10.1）0-10實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析設備租賃問題的解法根據表10.6之成本分析，本題可用圖10.5的網路圖來進行分析0-11實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最短路徑活用範例二最安全路徑問題（題目請參考課本p254 範例10.2）0-12實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最安全路徑問題的解法kkpppp211kkkppppppplogloglog)log(log21211

6、0-13實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最小展開樹問題 最小展開樹：尋找一個能夠連接各個結點而且弧的總長度最小的樹。最小展開樹演算法最小展開樹演算法 步驟一步驟一：從任何的一節點開始進行，然後將它連到網路上最近的節點。步驟二步驟二：在未連接節點中，挑選與已連接節點最近的節點，並連接之。重覆執行本步驟，直到所有的節點都已經連接為止。0-14實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最小展開樹範例最小展開樹問題（題目請參考課本p255）0-15實用管理科學實用管理科學陳明德

7、、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最小展開樹問題的解法0-16實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最大流量問題 最大流量問題：給定一個網路，尋找從起始節點到目的節點的最大流量。最大流量演算法最大流量演算法 尋找從任何起點至終點的路徑，條件是此路徑上的每一弧上的最大流量必須都大於零。儘可能地增加此路徑上的流量。持續尋找任何流量大於零的路徑；然後儘可能地增加此路徑上的流量。0-17實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最大流量範例 題目請

8、參考課本p2580-18實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最大流量解法一(1/7)最大流量解法一解法過程0-19實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最大流量解法一(2/7)0-20實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最大流量解法一(3/7)0-21實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最大流量解法一(4/7)0-22實用管理科學實用管理科學陳

9、明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最大流量解法一(5/7)0-23實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最大流量解法一(6/7)0-24實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最大流量解法一(7/7)0-25實用管理科學實用管理科學陳明德、陳武林陳明德、陳武林 著著前程文化前程文化Ch10 網路分析網路分析最大流量解法二：線性/整數規劃 Max X71 St.X71=X12+X13+X14X12+X32=X23+X25X13+X23=X32+X34+X35+X36X14+X34=X46X25+X35+X65=X56+X57X36+X46+X56=X65+X67X57+X67=X71X12=5（等）0-26