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

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

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

3、0-7最短路徑解法一：貼標(biāo)籤法(2/2)0-8最短路徑解法一：貼標(biāo)籤法(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最短路徑活用範(fàn)例一

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

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

6、可能地增加此路徑上的流量。0-17最大流量問(wèn)題 最大流量問(wèn)題 ：0-17最大流量範(fàn)例 題目請(qǐng)參考課本p2580-18最大流量範(fàn)例 題目請(qǐng)參考課本p2580-18最大流量解法一(1/7)最大流量解法一解法過(guò)程0-19最大流量解法一(1/7)最大流量解法一解法過(guò)程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