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