最大流量最小切割理论课件

第八章網路模式NetworkModels©

廖慶榮作業研究二版2009第八章網路模式©廖慶榮作業研究二版2009p.2/36章節大綱前言專有名詞最短路徑問題最小擴充樹問題最大流量問題最低成本流量問題網路單形法作業研究二版Ch.8網路模式p.2/36章節大綱前言作業研究二版Ch.8網路模式作業研究二版Ch.8網路模式p.3/368.2

專有名詞圖（graph）：一組節點（node）與一組弧（arc）的集合網路（network）：弧上具有流量的圖鏈（chain）：由弧所連接的一系列節點路徑（path）：所有弧之方向均相同的鏈迴路（circuit）：開始和結束在同一個節點的路徑循環（cycle）：開始和結束在同一個節點的鏈無循環網路（acyclicnetwork）：無迴路的網路連接圖（connectedgraph）：任意兩節點均存在相連之鏈的圖樹（tree）：無循環的連接圖擴充樹（spanningtree）：包含圖中所有節點的樹作業研究二版Ch.8網路模式p.3/368.2專作業研究二版Ch.8網路模式p.4/36專有名詞的圖示

作業研究二版Ch.8網路模式p.4/36專有名詞的圖作業研究二版Ch.8網路模式p.5/368.3

最短路徑問題最短路徑問題（shortest-pathproblem）找出由起始節點至終止節點的最短路徑應用電子地圖航空運輸網的設計消防車行經路線的規劃（弧可代表距離、成本、時間、機率等）作業研究二版Ch.8網路模式p.5/368.3最作業研究二版Ch.8網路模式p.6/36Dijkstra演算法Dijkstra演算法最短路徑演算法尤其適用於有迴路的網路定義：作業研究二版Ch.8網路模式p.6/36Dijkst作業研究二版Ch.8網路模式p.7/36Dijkstra演算法

作業研究二版Ch.8網路模式p.7/36Dijkst作業研究二版Ch.8網路模式p.8/36範例8.1若要開車由市中心（節點1）至該風景區（節點7），則最短路徑為何？作業研究二版Ch.8網路模式p.8/36範例8.1若作業研究二版Ch.8網路模式p.9/36範例8.1/最佳解

作業研究二版Ch.8網路模式p.9/36範例8.1作業研究二版Ch.8網路模式p.10/368.4

最小擴充樹問題最小擴充樹問題（minimalspanningtreeproblem）找出一個總長度最短的擴充樹，以使得圖中任意兩節點間存在一條路徑應用通訊網路的設計交通運輸系統的設計電力供應網路系統的設計水利灌溉工程的設計道路積雪的清除作業研究二版Ch.8網路模式p.10/368.4作業研究二版Ch.8網路模式p.11/368.4

最小擴充樹問題演算法步驟選擇長度最短的弧在所有尚未被連接的節點中，找出一個與目前連接圖距離最近的節點，並將其與連結圖相連若連接圖包含所有節點，則停止程序，否則返回步驟2作業研究二版Ch.8網路模式p.11/368.4作業研究二版Ch.8網路模式p.12/36範例8.2有線電視系統公司應如何選擇圖中的各弧，才能以最低的網路架設成本，提供對該郊區所有住戶的收視服務？作業研究二版Ch.8網路模式p.12/36範例8.2作業研究二版Ch.8網路模式p.13/36範例8.2最佳解作業研究二版Ch.8網路模式p.13/36範例8.2作業研究二版Ch.8網路模式p.14/368.5

最大流量問題最大流量問題（maximalflowproblem）決定由起始節點至終止節點的最大流量以及各弧的最佳流量應用顛峰時間的交通管制石油公司的管線輸送大型活動（如演唱會、集會遊行、運動比賽）前後的交通管制公司貨物的供應鏈系統設計作業研究二版Ch.8網路模式p.14/368.5作業研究二版Ch.8網路模式p.15/368.5

最大流量問題定義：LP模式：作業研究二版Ch.8網路模式p.15/368.5作業研究二版Ch.8網路模式p.16/368.5

最大流量問題演算法步驟：找出一條由起點至終點仍具有正剩餘流動容量（positiveremainingflowcapacity；PRFC）的路徑。若無此路徑，則程序停止。在此路徑上，選擇具最小PRFC的弧，並讓f等於此最小的PRFC。更新路徑上各弧的PRFC如下：對於與路徑方向相同的弧，將其容量減去f。對於與路徑方向相反的弧，將其容量加上f。返回步驟1。作業研究二版Ch.8網路模式p.16/368.5作業研究二版Ch.8網路模式p.17/36範例8.3 在下班的交通顛峰時間，各道路應如何管制交通，才能使得車輛得以儘速疏散？作業研究二版Ch.8網路模式p.17/36範例8.3作業研究二版Ch.8網路模式p.18/36範例8.3 /圖a.b

作業研究二版Ch.8網路模式p.18/36範例8.3作業研究二版Ch.8網路模式p.19/36範例8.3 /圖c.d

作業研究二版Ch.8網路模式p.19/36範例8.3作業研究二版Ch.8網路模式p.20/36範例8.3/最佳解

作業研究二版Ch.8網路模式p.20/36範例8.3作業研究二版Ch.8網路模式p.21/36最大流量最小切割理論切割（cut）一組有向弧（directedarc）所成的集合，此集合包含所有由起點至終點的路徑中，至少其中一個弧切割值（cutvalue）集合內所有弧之流動容量的總和最大流量最小切割理論（max-flowmin-cuttheorem）最小切割值則等於最大流量作業研究二版Ch.8網路模式p.21/36最大流量最作業研究二版Ch.8網路模式p.22/36最大流量最小切割理論以範例8.3為例，其中三條切割：切割1：55/切割2：45/切割3：50作業研究二版Ch.8網路模式p.22/36最大流量最作業研究二版Ch.8網路模式p.23/36最大流量最小切割理論

此切割內所有弧的流動容量均為零，故為最佳解作業研究二版Ch.8網路模式p.23/36最大流量最作業研究二版Ch.8網路模式p.24/368.6

最低成本流量問題最低成本流量問題（minimumcostflowproblem）以最低總成本將供給經由網路運送至所需的節點應用石油管線運送大多數網路問題均是最低成本流量問題的特例LP模式：作業研究二版Ch.8網路模式p.24/368.6作業研究二版Ch.8網路模式p.25/36流量下限限制的調整作業研究二版Ch.8網路模式p.25/36流量下限限作業研究二版Ch.8網路模式p.26/36範例8.4最低成本流量問題的網路表達方式：必要條件：淨流量的總和必須為零，即作業研究二版Ch.8網路模式p.26/36範例8.4作業研究二版Ch.8網路模式p.27/36特殊情況運輸問題：當符合以下條件時：無轉運節點各弧無容量限制指派問題：除運輸問題的兩項條件外，尚需：供給節點的淨流量=1，需求節點的淨流量=-1轉運問題當各弧無容量限制時作業研究二版Ch.8網路模式p.27/36特殊情況運作業研究二版Ch.8網路模式p.28/36特殊情況最短路徑問題：當符合以下三項條件時：供給及需求節點各僅有一個，其餘均為轉運節點供給節點的淨流量=1，需求節點的淨流量=-1各弧無容量限制最大流量問題：當符合以下條件時：供給及需求節點各僅有一個，其餘均為轉運節點供給節點的，需求節點的，其中是任意指定的一個最大流量上限值加上弧(1,n)，並讓其容量限制為無限大所有，惟作業研究二版Ch.8網路模式p.28/36特殊情況最作業研究二版Ch.8網路模式p.29/368.7

網路單形法網路單形法（networksimplexmethod）結合運輸問題單形法以及單形法上限技巧兩個方法，應用在網路問題，而形成的一個有效率的方法四個重要部分：可行解的表達方式測試最佳性及決定進入變數決定離開變數建立下一個可行基解作業研究二版Ch.8網路模式p.29/368.7作業研究二版Ch.8網路模式p.30/361.

可行解的表達方式若指定一個擴充樹，即可找出（如果存在的話）此擴充樹所代表的可行基解範例8.5(Z=490)作業研究二版Ch.8網路模式p.30/361.可行作業研究二版Ch.8網路模式p.31/362.

測試最佳性及決定進入變數

作業研究二版Ch.8網路模式p.31/362.測試作業研究二版Ch.8網路模式p.32/363.&4.

決定離開變數並建立BFS說明由於弧上有容量的限制，所以決定離開變數的方式須依4.5節上限技巧的方式處理在此循環中，最先降為零或最先達到上限的弧即為離開變數讓f為此離開變數的變化量，則將所有與循環方向相同的弧加上f，與循環方向相反的弧減去f，即可得到下一個BFS作業研究二版Ch.8網路模式p.32/363.&4.作業研究二版Ch.8網路模式p.33/363.&4.

決定離開變數並建立BFS為進一步簡化計算過程，當變數到達上限而以取代時，僅需調整如下：作業研究二版Ch.8網路模式p.33/363.&4.作業研究二