實用管理科學(xué)解讀課件

1、本章結(jié)構(gòu)網(wǎng)路簡介 最短路徑問題 最小展開樹問題 最大流量問題 0-1本章結(jié)構(gòu)網(wǎng)路簡介 0-1網(wǎng)路名詞介紹(1/2)網(wǎng)路(network)：由無數(shù)個節(jié)點(nodes)與弧(arcs)所構(gòu)成的；通常節(jié)點是用來代表某一實際的地點，而弧則是用來表示連接兩個點。 路徑(path)：連接兩個節(jié)點的一系列的弧所組成的。 循環(huán)(loop或cycle)：一路徑的起點與終點重疊。 0-2網(wǎng)路名詞介紹(1/2)網(wǎng)路(network)：0-2網(wǎng)路名詞介紹(2/2)展開樹(spanning tree)：網(wǎng)路將一些弧刪除後形成樹，而且連接網(wǎng)路的任何一節(jié)點之子網(wǎng)路。 樹(tree)：不具有任何的循環(huán)的網(wǎng)路。 0-3網(wǎng)路名詞

2、介紹(2/2)展開樹(spanning tree)：最短路徑演算法(1/2) 貼標籤法:每一個標上標籤的結(jié)點，包含一對數(shù)字，分別表示從起點(節(jié)點1)到此節(jié)點的最短距離與最短路徑上的前一節(jié)點編號 。0-4最短路徑演算法(1/2) 貼標籤法:0-4最短路徑演算法(2/2)重覆執(zhí)行下列步驟 :辨識候選未貼標籤節(jié)點 。候選未貼標籤節(jié)點中，挑選一節(jié)點，使得起始節(jié)點到此節(jié)點的距離最短 。0-5最短路徑演算法(2/2)重覆執(zhí)行下列步驟 :0-5最短路徑問題範例 題目請參考課本p2480-6最短路徑問題範例 題目請參考課本p2480-6最短路徑解法一：貼標籤法(1/2)0-7最短路徑解法一：貼標籤法(1/2)

3、0-7最短路徑解法一：貼標籤法(2/2)0-8最短路徑解法一：貼標籤法(2/2)0-8最短路徑解法二：線性/整數(shù)規(guī)劃Min 20X12+16X13+6(X23+X32)+12(X24+X42)+15X35+8(X45+X54)+25X27+11X47+5X56+18X67St.X12+X13 = 1 X12+X32+X42 = X23+X24+X25X13+X23 = X32+X35X24+X54 = X42+X45+X47X35+X45 = X54+X56X56=X67X27+X47+X67=1Xij=0/10-9最短路徑解法二：線性/整數(shù)規(guī)劃Min 20X12+16X13最短路徑活用範例一

4、設(shè)備租賃問題（題目請參考課本p248 範例10.1 ）0-10最短路徑活用範例一設(shè)備租賃問題（題目請參考課本p248 範例設(shè)備租賃問題的解法根據(jù)表10.6之成本分析，本題可用圖10.5的網(wǎng)路圖來進行分析0-11設(shè)備租賃問題的解法根據(jù)表10.6之成本分析，本題可用圖10.最短路徑活用範例二最安全路徑問題（題目請參考課本p254 範例10.2 ）0-12最短路徑活用範例二最安全路徑問題（題目請參考課本p254 範最安全路徑問題的解法0-13最安全路徑問題的解法0-13最小展開樹問題 最小展開樹 ：尋找一個能夠連接各個結(jié)點而且弧的總長度最小的樹。最小展開樹演算法 步驟一：從任何的一節(jié)點開始進行，然後

5、將它連到網(wǎng)路上最近的節(jié)點。步驟二：在未連接節(jié)點中，挑選與已連接節(jié)點最近的節(jié)點，並連接之。重覆執(zhí)行本步驟，直到所有的節(jié)點都已經(jīng)連接為止。 0-14最小展開樹問題 最小展開樹 ：0-14最小展開樹範例最小展開樹問題（題目請參考課本p255 ）0-15最小展開樹範例最小展開樹問題（題目請參考課本p255 ）0-最小展開樹問題的解法0-16最小展開樹問題的解法0-16最大流量問題 最大流量問題 ：給定一個網(wǎng)路，尋找從起始節(jié)點到目的節(jié)點的最大流量。 最大流量演算法 尋找從任何起點至終點的路徑，條件是此路徑上的每一弧上的最大流量必須都大於零。儘可能地增加此路徑上的流量。持續(xù)尋找任何流量大於零的路徑；然後儘

6、可能地增加此路徑上的流量。0-17最大流量問題 最大流量問題 ：0-17最大流量範例 題目請參考課本p2580-18最大流量範例 題目請參考課本p2580-18最大流量解法一(1/7)最大流量解法一解法過程0-19最大流量解法一(1/7)最大流量解法一解法過程0-19最大流量解法一(2/7)0-20最大流量解法一(2/7)0-20最大流量解法一(3/7)0-21最大流量解法一(3/7)0-21最大流量解法一(4/7)0-22最大流量解法一(4/7)0-22最大流量解法一(5/7)0-23最大流量解法一(5/7)0-23最大流量解法一(6/7)0-24最大流量解法一(6/7)0-24最大流量解法一(7/7)0-25最大流量解法一(7/7)0-25最大流量解法二：線性/整數(shù)規(guī)劃 Max X71 St.X71 = X12+X13+X14X12+X32=X23+X25X13+X23=X32+X34+X35+X3