第八章 網路模式 Network Models 作業研究 二版 2009 © 廖慶榮.

Presentation on theme: "第八章 網路模式 Network Models 作業研究 二版 2009 © 廖慶榮."— Presentation transcript:

1 第八章 網路模式 Network Models 作業研究 二版 2009 © 廖慶榮

2 章節大綱 前言 專有名詞 最短路徑問題 最小擴充樹問題 最大流量問題 最低成本流量問題 網路單形法 作業研究 二版 Ch.8 網路模式

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

4 專有名詞的圖示 作業研究 二版 Ch.8 網路模式

5 8.3 最短路徑問題 最短路徑問題（shortest-path problem） 應用 找出由起始節點至終止節點的最短路徑 電子地圖
8.3 最短路徑問題 最短路徑問題（shortest-path problem） 找出由起始節點至終止節點的最短路徑 應用 電子地圖 航空運輸網的設計 消防車行經路線的規劃 （弧可代表距離、成本、時間、機率等） 作業研究 二版 Ch.8 網路模式

6 Dijkstra演算法 Dijkstra演算法 最短路徑演算法 尤其適用於有迴路的網路 定義： 作業研究 二版 Ch.8 網路模式

7 Dijkstra演算法 作業研究 二版 Ch.8 網路模式

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

9 範例8.1 /最佳解 作業研究 二版 Ch.8 網路模式

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

11 8.4 最小擴充樹問題 演算法步驟 選擇長度最短的弧 在所有尚未被連接的節點中，找出一個與目前連接圖距離最近的節點，並將其與連結圖相連
8.4 最小擴充樹問題 演算法步驟 選擇長度最短的弧 在所有尚未被連接的節點中，找出一個與目前連接圖距離最近的節點，並將其與連結圖相連 若連接圖包含所有節點，則停止程序，否則返回步驟2 作業研究 二版 Ch.8 網路模式

12 範例8.2 有線電視系統公司應如何選擇圖中的各弧，才能以最低 的網路架設成本，提供對該郊區所有住戶的收視服務？
作業研究 二版 Ch.8 網路模式

13 範例8.2 最佳解 作業研究 二版 Ch.8 網路模式

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

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

16 8.5 最大流量問題 演算法步驟： 找出一條由起點至終點仍具有正剩餘流動容量（positive remaining flow capacity；PRFC）的路徑。若無此路徑，則程序停止。 在此路徑上，選擇具最小PRFC的弧，並讓f等於此最小的PRFC。 更新路徑上各弧的PRFC如下： 對於與路徑方向相同的弧，將其容量減去f。 對於與路徑方向相反的弧，將其容量加上f。 返回步驟1。 作業研究 二版 Ch.8 網路模式

17 範例8.3 在下班的交通顛峰時間，各道路應如何管制交通， 才能使得車輛得以儘速疏散？ 作業研究 二版 Ch.8 網路模式

18 範例8.3 /圖a.b 作業研究 二版 Ch.8 網路模式

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

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

21 最大流量最小切割理論 切割（cut） 切割值（cut value） 最大流量最小切割理論（max-flow min-cut theorem）
一組有向弧（directed arc）所成的集合，此集合包含所有由起點至終點的路徑中，至少其中一個弧 切割值（cut value） 集合內所有弧之流動容量的總和 最大流量最小切割理論（max-flow min-cut theorem） 最小切割值則等於最大流量 作業研究 二版 Ch.8 網路模式

22 最大流量最小切割理論 以範例8.3為例，其中三條切割： 切割1：55 /切割2：45 /切割3：50 作業研究 二版 Ch.8 網路模式

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

24 8.6 最低成本流量問題 應用 最低成本流量問題（minimum cost flow problem）
8.6 最低成本流量問題 最低成本流量問題（minimum cost flow problem） 以最低總成本將供給經由網路運送至所需的節點 應用 石油管線運送 大多數網路問題均是最低成本流量問題的特例 LP模式： 作業研究 二版 Ch.8 網路模式

25 流量下限限制的調整 作業研究 二版 Ch.8 網路模式

26 範例8.4 最低成本流量問題的網路表達方式： 必要條件：淨流量的總和必須為零，即 作業研究 二版 Ch.8 網路模式

27 特殊情況 運輸問題：當符合以下條件時： 指派問題：除運輸問題的兩項條件外，尚需： 轉運問題 無轉運節點 各弧無容量限制
供給節點的淨流量=1，需求節點的淨流量= -1 轉運問題 當各弧無容量限制時 作業研究 二版 Ch.8 網路模式

28 特殊情況 最短路徑問題：當符合以下三項條件時： 最大流量問題：當符合以下條件時： 供給及需求節點各僅有一個，其餘均為轉運節點
供給節點的淨流量=1，需求節點的淨流量= -1 各弧無容量限制 最大流量問題：當符合以下條件時： 供給節點的 ，需求節點的 ，其中 是任意指定的一個最大流量上限值 加上弧(1,n)，並讓其容量限制為無限大 所有 ，惟 作業研究 二版 Ch.8 網路模式

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

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

31 2. 測試最佳性及決定進入變數 作業研究 二版 Ch.8 網路模式

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

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

34 範例8.6 /圖(a)&(b) 作業研究 二版 Ch.8 網路模式

35 範例8.6 /圖(c)&(d) 作業研究 二版 Ch.8 網路模式

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