最大流量最小切割理論課件

第八章網(wǎng)路模式NetworkModels?

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

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

作業(yè)研究二版Ch.8網(wǎng)路模式p.4/36專有名詞的圖作業(yè)研究二版Ch.8網(wǎng)路模式p.5/368.3

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

作業(yè)研究二版Ch.8網(wǎng)路模式p.7/36Dijkst作業(yè)研究二版Ch.8網(wǎng)路模式p.8/36範(fàn)例8.1若要開車由市中心（節(jié)點(diǎn)1）至該風(fēng)景區(qū)（節(jié)點(diǎn)7），則最短路徑為何？作業(yè)研究二版Ch.8網(wǎng)路模式p.8/36範(fàn)例8.1若作業(yè)研究二版Ch.8網(wǎng)路模式p.9/36範(fàn)例8.1/最佳解

作業(yè)研究二版Ch.8網(wǎng)路模式p.9/36範(fàn)例8.1作業(yè)研究二版Ch.8網(wǎng)路模式p.10/368.4

最小擴(kuò)充樹問題最小擴(kuò)充樹問題（minimalspanningtreeproblem）找出一個(gè)總長(zhǎng)度最短的擴(kuò)充樹，以使得圖中任意兩節(jié)點(diǎn)間存在一條路徑應(yīng)用通訊網(wǎng)路的設(shè)計(jì)交通運(yùn)輸系統(tǒng)的設(shè)計(jì)電力供應(yīng)網(wǎng)路系統(tǒng)的設(shè)計(jì)水利灌溉工程的設(shè)計(jì)道路積雪的清除作業(yè)研究二版Ch.8網(wǎng)路模式p.10/368.4作業(yè)研究二版Ch.8網(wǎng)路模式p.11/368.4

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

最大流量問題最大流量問題（maximalflowproblem）決定由起始節(jié)點(diǎn)至終止節(jié)點(diǎn)的最大流量以及各弧的最佳流量應(yīng)用顛峰時(shí)間的交通管制石油公司的管線輸送大型活動(dòng)（如演唱會(huì)、集會(huì)遊行、運(yùn)動(dòng)比賽）前後的交通管制公司貨物的供應(yīng)鏈系統(tǒng)設(shè)計(jì)作業(yè)研究二版Ch.8網(wǎng)路模式p.14/368.5作業(yè)研究二版Ch.8網(wǎng)路模式p.15/368.5

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

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

作業(yè)研究二版Ch.8網(wǎng)路模式p.18/36範(fàn)例8.3作業(yè)研究二版Ch.8網(wǎng)路模式p.19/36範(fàn)例8.3 /圖c.d

作業(yè)研究二版Ch.8網(wǎng)路模式p.19/36範(fàn)例8.3作業(yè)研究二版Ch.8網(wǎng)路模式p.20/36範(fàn)例8.3/最佳解

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

此切割內(nèi)所有弧的流動(dòng)容量均為零，故為最佳解作業(yè)研究二版Ch.8網(wǎng)路模式p.23/36最大流量最作業(yè)研究二版Ch.8網(wǎng)路模式p.24/368.6

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

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

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

測(cè)試最佳性及決定進(jìn)入變數(shù)

作業(yè)研究二版Ch.8網(wǎng)路模式p.31/362.測(cè)試作業(yè)研究二版Ch.8網(wǎng)路模式p.32/363.&4.

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

決定離開變數(shù)並建立BFS為進(jìn)一步簡(jiǎn)化計(jì)算過程，當(dāng)變數(shù)到達(dá)上限而以取代時(shí)，僅需調(diào)整如下：作業(yè)研究二版Ch.8網(wǎng)路模式p.33/363.&4.作業(yè)研究二