1、第八章第八章網路模式網路模式 Network Models 廖慶榮作業研究 二版 2009p.2/36章節大綱章節大綱1.前言2.專有名詞3.最短路徑問題4.最小擴充樹問題5.最大流量問題6.最低成本流量問題7.網路單形法作業研究作業研究 二版二版 Ch.8 網路模式網路模式作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.3/368.2 專有名詞專有名詞o 圖圖（graph）：一組節點（node）與一組弧（arc）的集合o 網路網路（network）：弧上具有流量的圖o 鏈鏈（chain）：由弧所連接的一系列節點o 路徑路徑（path）：所有弧之方向均相同的鏈o 迴路迴路（circu
2、it）：開始和結束在同一個節點的路徑o 循環循環（cycle）：開始和結束在同一個節點的鏈o 無循環網路無循環網路（acyclic network）：無迴路的網路o 連接圖連接圖（connected graph）：任意兩節點均存在相連之鏈的圖o 樹樹（tree）：無循環的連接圖o 擴充樹擴充樹（spanning tree）：包含圖中所有節點的樹作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.4/36專有名詞的圖示專有名詞的圖示 作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.5/368.3 最短路徑問題最短路徑問題o 最短路徑問題最短路徑問題（shortest-path p
3、roblem）n 找出由起始節點至終止節點的最短路徑o 應用應用n 電子地圖n 航空運輸網的設計n 消防車行經路線的規劃n（弧可代表距離、成本、時間、機率等）作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.6/36Dijkstra演算法演算法o Dijkstra演算法n 最短路徑演算法n 尤其適用於有迴路的網路o 定義：定義：作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.7/36Dijkstra演算法演算法 作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.8/36範例範例8.1o 若要開車由市中心（節點1）至該風景區（節點7），則最短路徑為何？作業研究作業研究
4、二版二版 Ch.8 網路模式網路模式p.9/36範例範例8.1/最佳解最佳解 (5,3)(3,1)1 3 5 5 3 2 1 6 3 2 1 3 4 2 6 7 5 4(4,1)(2,1)(3,3)(6,2)(5,4)(4,4)(9,6)(0,)作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.10/368.4 最小擴充樹問題最小擴充樹問題o 最小擴充樹問題（最小擴充樹問題（minimal spanning tree problem）n 找出一個總長度最短的擴充樹，以使得圖中任意兩節點間存在一條路徑o 應用應用n 通訊網路的設計n 交通運輸系統的設計n 電力供應網路系統的設計n 水利灌
5、溉工程的設計n 道路積雪的清除作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.11/368.4 最小擴充樹問題最小擴充樹問題o 演算法步驟演算法步驟1.選擇長度最短的弧2.在所有尚未被連接的節點中，找出一個與目前連接圖距離最近的節點，並將其與連結圖相連3.若連接圖包含所有節點，則停止程序，否則返回步驟2作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.12/36範例範例8.2o 有線電視系統公司應如何選擇圖中的各弧，才能以最低的網路架設成本，提供對該郊區所有住戶的收視服務？作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.13/36範例範例8.2o 最佳解最佳解作業研
6、究作業研究 二版二版 Ch.8 網路模式網路模式p.14/368.5 最大流量問題最大流量問題o 最大流量問題最大流量問題（maximal flow problem）n 決定由起始節點至終止節點的最大流量以及各弧的最佳流量o 應用應用n 顛峰時間的交通管制n 石油公司的管線輸送n 大型活動（如演唱會、集會遊行、運動比賽）前後的交通管制n 公司貨物的供應鏈系統設計作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.15/368.5 最大流量問題最大流量問題o 定義：定義：o LP模式：模式：111111102,3,10Max s.t.nnijjijjnnijjijjnnijjijjijij
7、fxxfixxfinxxinxu 作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.16/368.5 最大流量問題最大流量問題o 演算法步驟：演算法步驟：1.找出一條由起點至終點仍具有正剩餘流動容量（positive remaining flow capacity；PRFC）的路徑。若無此路徑，則程序停止。2.在此路徑上，選擇具最小PRFC的弧，並讓f等於此最小的PRFC。3.更新路徑上各弧的PRFC如下：a.對於與路徑方向相同的弧，將其容量減去f。b.對於與路徑方向相反的弧，將其容量加上f。4.返回步驟1。作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.17/36範例範例8
8、.3o 在下班的交通顛峰時間，各道路應如何管制交通，才能使得車輛得以儘速疏散？作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.18/36範例範例8.3/圖圖a.b 10 10 10 10 10 20 20 10 15 0 10 0 0 5 25 0 0 0 30 0 0 10 0 20 1 3 4 2 6 7 5 10 10 10 10 20 10 20 20 10 15 0 0 0 10 5 15 0 0 10 20 0 0 10 0 20 1 3 4 2 6 7 5 10 作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.19/36範例範例8.3/圖圖c.d 10 10
9、10 10 20 10 0 20 10 15 0 0 0 10 5 15 20 0 30 0 0 20 10 0 0 1 3 4 2 6 7 5 10 20 20 10 10 10 5 20 15 0 20 5 15 0 0 0 15 0 10 20 0 30 0 5 20 10 5 0 1 3 4 2 6 7 5 10 20 20 5 5 作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.20/36範例範例8.3/最佳解最佳解 30 10 10 20 20 10 45 45 1 3 4 2 6 7 5 15 5 5 15 作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.21
10、/36最大流量最小切割理論最大流量最小切割理論o 切割切割（cut）n 一組有向弧（directed arc）所成的集合，此集合包含所有由起點至終點的路徑中，至少其中一個弧o 切割值切割值（cut value）n 集合內所有弧之流動容量的總和o 最大流量最小切割理論最大流量最小切割理論（max-flow min-cut theorem）n 最小切割值則等於最大流量作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.22/36最大流量最小切割理論最大流量最小切割理論o 以範例8.3為例，其中三條切割：n 切割1：55/切割2：45/切割3：50 切割 2 10 0 20 20 20 5 1
11、0 10 0 0 5 25 0 10 0 30 0 0 0 10 20 1 3 4 2 6 7 5 0 切割 1 切割 3 作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.23/36最大流量最小切割理論最大流量最小切割理論o 此切割內所有弧的流動容量均為零，故為最佳解 10 10 10 5 20 15 0 20 5 15 0 0 0 15 0 10 20 0 30 0 5 20 10 5 0 1 3 4 2 6 7 5 10 20 20 5 5 作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.24/368.6 最低成本流量問題最低成本流量問題o 最低成本流量問題最低成本流量
12、問題（minimum cost flow problem）n 以最低總成本將供給經由網路運送至所需的節點o 應用應用n 石油管線運送n 大多數網路問題均是最低成本流量問題的特例o LP模式模式：11111,2,0(,)Max s.t.nnijijijnnijjiijjijijc xxxbinxui j作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.25/36流量下限限制的調整流量下限限制的調整作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.26/36範例範例8.4o 最低成本流量問題的網路表達方式：n 必要條件：淨流量的總和必須為零，即 2 4 3 1 5 40 30 0
13、50 20(15)$2(25)$4$3(20)$5$8$1$2$1 10niib作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.27/36特殊情況特殊情況o 運輸問題：運輸問題：當符合以下條件時：1.無轉運節點2.各弧無容量限制o 指派問題：指派問題：除運輸問題的兩項條件外，尚需：n 供給節點的淨流量=1，需求節點的淨流量=-1o 轉運問題轉運問題n 當各弧無容量限制時作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.28/36特殊情況特殊情況o 最短路徑問題：最短路徑問題：當符合以下三項條件時：1.供給及需求節點各僅有一個，其餘均為轉運節點2.供給節點的淨流量=1，需求節點
14、的淨流量=-13.各弧無容量限制o 最大流量問題：最大流量問題：當符合以下條件時：1.供給及需求節點各僅有一個，其餘均為轉運節點2.供給節點的 ，需求節點的 ，其中 是任意指定的一個最大流量上限值3.加上弧(1,n)，並讓其容量限制為無限大4.所有 ，惟 1bfnbf f0ijc 1ncM作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.29/368.7 網路單形法網路單形法o 網路單形法網路單形法（network simplex method）n結合運輸問題單形法運輸問題單形法以及單形法上限技巧單形法上限技巧兩個方法，應用在網路問題，而形成的一個有效率的方法o 四個重要部分：四個重要
15、部分：1.可行解的表達方式2.測試最佳性及決定進入變數3.決定離開變數4.建立下一個可行基解作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.30/361.可行解的表達方式可行解的表達方式o 若指定一個擴充樹，即可找出（如果存在的話）此擴充樹所代表的可行基解o 範例範例8.5(Z=490)2 4 3 1 5 40 30 0 50 20 30 30 40 50 作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.31/362.測試最佳性及決定進入變數測試最佳性及決定進入變數 2 4 3 1 5 40 30 0 50 20$2$4$3$5$8$1$2$1 30 30 40 50 作業
16、研究作業研究 二版二版 Ch.8 網路模式網路模式p.32/363.&4.決定離開變數並建立決定離開變數並建立BFSo 說明說明n 由於弧上有容量的限制，所以決定離開變數的方式須依4.5節上限技巧的方式處理n 在此循環中，最先降為零或最先達到上限的弧即為離開變數n 讓f為此離開變數的變化量，則將所有與循環方向相同的弧加上f，與循環方向相反的弧減去f，即可得到下一個BFS作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.33/363.&4.決定離開變數並建立決定離開變數並建立BFSo 為進一步簡化計算過程，當變數 到達上限而以 取代時，僅需調整如下：ijxijy作業研究作業研究 二版二版
17、 Ch.8 網路模式網路模式p.34/36範例範例8.6/圖圖(a)&(b)2 4 3 1 5 40 30 0 50 20$2$4$3$5$8$1$2$1 30 30 40 50(15)(20)(25)$2$2 2 4 3 1 5 25 0 50 20$4$3$5$8$1$2$1 45 45 25 50(15)*(20)(25)作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.35/36範例範例8.6/圖圖(c)&(d)$5$2$2 2 4 3 1 5 5 45 20 50 20$4$3$8$1$2$1 45 65 5 50(15)*(20)*(25)$4$5$2$2 2 4 3 1 5 5 20 20 25 20$3$8$1$2$1 20 40 5 25(15)*(20)*(25)*作業研究作業研究 二版二版 Ch.8 網路模式網路模式p.36/36範例範例8.6/最佳解最佳解$2 2 4 3 1 5 40 30 0 50 20$3$8$1$2$1 20 40 5 25 15 20 25$5$4 395Z
