本章結構 網路簡介 最短路徑問題 最小展開樹問題 最大流量問題 10-1.

Presentation on theme: "本章結構 網路簡介 最短路徑問題 最小展開樹問題 最大流量問題 10-1."— Presentation transcript:

1 本章結構 網路簡介 最短路徑問題 最小展開樹問題 最大流量問題 10-1

2 網路名詞介紹(1/2) 網路(network)： 路徑(path)： 循環(loop或cycle)：
由無數個節點(nodes)與弧(arcs)所構成的；通常節點是用來代表某一實際的地點，而弧則是用來表示連接兩個點。 路徑(path)： 連接兩個節點的一系列的弧所組成的。 循環(loop或cycle)： 一路徑的起點與終點重疊。 10-2

3 網路名詞介紹(2/2) 展開樹(spanning tree)： 樹(tree)：
網路將一些弧刪除後形成樹，而且連接網路的任何一節點之子網路。 樹(tree)： 不具有任何的循環的網路。 10-3

4 最短路徑演算法(1/2) 貼標籤法: 每一個標上標籤的結點，包含一對數字，分別表示從起點(節點1)到此節點的最短距離與最短路徑上的前一節點編號 。 10-4

5 最短路徑演算法(2/2) 重覆執行下列步驟 : 辨識候選未貼標籤節點 。 候選未貼標籤節點中，挑選一節點，使得起始節點到此節點的距離最短 。
10-5

6 最短路徑問題範例 題目請參考課本p248 10-6

7 最短路徑解法一：貼標籤法(1/2) 10-7

8 最短路徑解法一：貼標籤法(2/2) 10-8

9 最短路徑解法二：線性/整數規劃 Min 20X12+16X13+6(X23+X32)+12(X24+X42)+15X35+8(X45+X54)+25X27+11X47+5X56+18X67 St. X12+X13 = 1 X12+X32+X42 = X23+X24+X25 X13+X23 = X32+X35 X24+X54 = X42+X45+X47 X35+X45 = X54+X56 X56=X67 X27+X47+X67=1 Xij=0/1 10-9

10 最短路徑活用範例一 設備租賃問題（題目請參考課本p248 範例10.1 ） 10-10

11 設備租賃問題的解法 根據表10.6之成本分析，本題可用圖10.5的網路圖來進行分析 10-11

12 最短路徑活用範例二 最安全路徑問題（題目請參考課本p254 範例10.2 ） 10-12

13 最安全路徑問題的解法 10-13

14 最小展開樹問題 最小展開樹 ： 最小展開樹演算法 尋找一個能夠連接各個結點而且弧的總長度最小的樹。
步驟一：從任何的一節點開始進行，然後將它連到網路上最近的節點。 步驟二：在未連接節點中，挑選與已連接節點最近的節點，並連接之。重覆執行本步驟，直到所有的節點都已經連接為止。 10-14

15 最小展開樹範例 最小展開樹問題（題目請參考課本p255 ） 10-15

16 最小展開樹問題的解法 10-16

17 最大流量問題 最大流量問題 ： 最大流量演算法 給定一個網路，尋找從起始節點到目的節點的最大流量。
尋找從任何起點至終點的路徑，條件是此路徑上的每一弧上的最大流量必須都大於零。 儘可能地增加此路徑上的流量。 持續尋找任何流量大於零的路徑；然後儘可能地增加此路徑上的流量。 10-17

18 最大流量範例 題目請參考課本p258 10-18

19 最大流量解法一(1/7) 最大流量解法一解法過程 10-19

20 最大流量解法一(2/7) 10-20

21 最大流量解法一(3/7) 10-21

22 最大流量解法一(4/7) 10-22

23 最大流量解法一(5/7) 10-23

24 最大流量解法一(6/7) 10-24

25 最大流量解法一(7/7) 10-25

26 最大流量解法二：線性/整數規劃 Max X71 St. X71 = X12+X13+X14 X12+X32=X23+X25
10-26