【文章內(nèi)容簡介】 設(shè)備使用兩年后的殘值 ＝ +－ = 點(diǎn)（ 1,3）到點(diǎn)⑤的總費(fèi)用為 第三年的購置費(fèi)＋第一年的維護(hù)費(fèi)＋第二年的維護(hù)費(fèi)－設(shè)備使用兩年后的殘值－第四年末的殘值 ＝ ++－ － =。 費(fèi)用表見教材表 68。 Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 30 2022年 2月 16日星期三 ① ⑤ 6 圖 6－ 16 (1,2,3) (1,4) (1,3,4) (1,2,4) (1,2,3,4) (1,2) (1,3) 第一年 第二年 第三年 第四年 Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 31 2022年 2月 16日星期三 最短路問題 Shortest Path Problem （ 2）第四年末不處理設(shè)備： 將圖 6－ 16第 4年的數(shù)據(jù)換成表 68最后一列，求點(diǎn)①到點(diǎn)⑤的最短路。最短路線為： ① → (1,2)→(1,2,3)→ ⑤ ，最短路長為 ，即總費(fèi)用為 。更新方案與第一種情形相同。 （ 1）第四年末處理設(shè)備： 求點(diǎn)①到點(diǎn)⑤的最短路。用 Dijkstra算法得到最短路線為： ① → (1,2)→(1,2,3)→ ⑤ ，最短路長為 4。 4年總費(fèi)用最小的設(shè)備更新方案是：第 1年購置設(shè)備使用 1年，第 2年更新設(shè)備使用 1年后賣掉，第 3年購置設(shè)備使用 2年到第 4年年末， 4年的總費(fèi)用為 4萬元。 Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 32 2022年 2月 16日星期三 【 例 69】 服務(wù)網(wǎng)點(diǎn)設(shè)置問題。以圖 6－ 14為例，現(xiàn)提出這樣一個(gè)問題，在交通網(wǎng)絡(luò)中建立一個(gè)快速反應(yīng)中心，應(yīng)選擇哪一個(gè)城市最好。類似地，在一個(gè)網(wǎng)絡(luò)中設(shè)置一所學(xué)校、醫(yī)院、消防站、購物中心，還有廠址選擇、總部選址、公司銷售中心選址等問題都屬于最佳服務(wù)網(wǎng)點(diǎn)設(shè)置問題。 【 解 】 對(duì)于不同的問題，尋求最佳服務(wù)點(diǎn)有不同的標(biāo)準(zhǔn)。像圖 6－ 14只有兩點(diǎn)間的距離，可以采用“ 使最大服務(wù)距離達(dá)到最小 ”為標(biāo)準(zhǔn)，計(jì)算步驟如下。 第一步：利用 Floyd算法求出任意兩點(diǎn)之間的最短距離表（表 6－ 3）。 第二步：計(jì)算最短距離表中每行的最大距離的最小值，即 ? ?ijji LL maxm i n? 最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 33 2022年 2月 16日星期三 引用例 66計(jì)算的結(jié)果，對(duì)表 6－ 3每行取最大值再取最小值，見表 6－ 9倒數(shù)第二列。 v1 v2 v3 v4 v5 v6 v7 v8 Max Lij 總運(yùn)量 v1 0 6 9 5 14 4 6 18 18 3220 v2 6 0 3 2 8 7 5 14 14 2465 v3 9 3 0 5 7 10 8 13 13 2955 v4 5 2 5 0 9 5 3 15 15 2450 v5 14 8 7 9 0 12 10 6 14 3780 v6 4 7 10 5 12 0 2 14 14 2960 v7 6 5 8 3 10 2 0 12 12 2560 v8 18 14 13 15 6 14 12 0 18 5040 產(chǎn)量 80 50 70 40 30 35 60 65 表 6－ 9 表 6－ 9中倒數(shù)第二列最小值為 12，位于第 7行，則 v7為網(wǎng)絡(luò)的中心，最佳服務(wù)點(diǎn)應(yīng)設(shè)置在 v7。 最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 34 2022年 2月 16日星期三 如果每個(gè)點(diǎn)還有一個(gè)權(quán)數(shù)，例如一個(gè)網(wǎng)點(diǎn)的人數(shù)、需要運(yùn)送的物質(zhì)數(shù)量、產(chǎn)量等，這時(shí)采用“ 使總運(yùn)量最小 ”為標(biāo)準(zhǔn)，計(jì)算方法是將上述第二步的最大距離改為總運(yùn)量，總運(yùn)量的最小值對(duì)應(yīng)的點(diǎn)就是最佳服務(wù)點(diǎn)。 表 6－ 9中最后一行是點(diǎn) vj的產(chǎn)量，將各行的最小距離分別乘以產(chǎn)量求和得到總運(yùn)量，例如， 0 80＋ 6 50＋ … ＋ 18 65＝3220，見表 6－ 9最后一列，最小運(yùn)量為 2450，最佳服務(wù)點(diǎn)應(yīng)設(shè)置在 v4。 最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 35 2022年 2月 16日星期三 下一節(jié)：最大流問題 最短路問題 Shortest Path Problem 。 、無向圖一點(diǎn)到各點(diǎn)最短路的 Dijkstra算法 Floyd算法 ：設(shè)備更新問題和最佳服務(wù)點(diǎn)設(shè)置問題 作業(yè)：教材習(xí)題 , , , , 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 37 2022年 2月 16日星期三 最大流問題 Maximal Flow Problem 基本概念 ① ② ③ ④ ⑤ ⑥ 8 14 5 6 3 3 8 10 7 6 ⑦ 3 圖 6－ 18 4 圖 6－ 18所示的網(wǎng)絡(luò)圖中定義了一個(gè) 發(fā)點(diǎn) v1，稱為源 (source， supply node），定義了一個(gè) 收點(diǎn) v7，稱為匯（ sink， demand node），其余點(diǎn) v2， v3， … ， v6為 中間點(diǎn) ，稱為 轉(zhuǎn)運(yùn)點(diǎn) (transshipment nodes)。如果有多個(gè)發(fā)點(diǎn)和收點(diǎn)，則虛設(shè)發(fā)點(diǎn)和收點(diǎn)轉(zhuǎn)化成一個(gè)發(fā)點(diǎn)和收點(diǎn)。圖中的權(quán)是該弧在單位時(shí)間內(nèi)的最大通過能力，稱為弧的 容量 (capacity)。最大流問題是在單位時(shí)間內(nèi)安排一個(gè)運(yùn)送方案，將發(fā)點(diǎn)的物質(zhì)沿著弧的方向運(yùn)送到收點(diǎn)，使總運(yùn)輸量最大。 Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 38 2022年 2月 16日星期三 設(shè) cij為?。?i， j）的容量， fij為?。?i， j）的流量。 容量是?。?i， j）單位時(shí)間內(nèi)的 最大通過能力 ，流量是弧（ i， j）單位時(shí)間內(nèi)的 實(shí)際通過量 ，流量的集合 f={fij}稱為網(wǎng)絡(luò)的流。發(fā)點(diǎn)到收點(diǎn)的總流量記為 v=val(f)， v也是網(wǎng)絡(luò)的 流量 。 圖 6－ 18最大流問題的線性規(guī)劃數(shù)學(xué)模型為 ????????????????????),(000m a x67475713121312jicfvfffffffffvijijmvmjvimmm所有弧所有中間點(diǎn) 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 39 2022年 2月 16日星期三 滿足下例 3個(gè)條件的流 fij 的集合 f ={ fij }稱為可行流 1 ) 0 ( , )ij ijf c i j??（ 所 有 弧( 3 )sts j i tvvv f f????發(fā)點(diǎn) vs流出的總流量等于流入收點(diǎn) vt的總流量 ( 2 ) mmi m m j mvvf f v??? 所 有 中 間 點(diǎn) 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 40 2022年 2月 16日星期三 鏈： 從發(fā)點(diǎn)到收點(diǎn)的一條路線（弧的方向不一定都同向）稱為鏈。從發(fā)點(diǎn)到收點(diǎn)的方向規(guī)定為鏈的方向。 前向?。?與鏈的方向相同的弧稱為前向弧。 后向?。?與鏈的方向相反的弧稱為后向弧。 增廣鏈 : 設(shè) f 是一個(gè)可行流，如果存在一條從 vs到 vt的鏈，滿足： fijCij fij0 則該鏈稱為增廣鏈 ① ② ③ ④ ⑤ ⑥ 前向弧 后向弧 容量 流量 這是一條增廣鏈 8 4 4 6 9 （ 5） (2) (3) (4) (6) 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 41 2022年 2月 16日星期三 步驟如下： 第二步：對(duì)點(diǎn)進(jìn)行標(biāo)號(hào)找一條增廣鏈。 （ 1）發(fā)點(diǎn)標(biāo)號(hào) （ ∞） （ 2）選一個(gè)點(diǎn) vi 已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查： A．如果弧的方向向前（前向?。┎⑶矣?fijcij，則 vj標(biāo)號(hào) : θj＝ cij－ fij B． 如果弧的方向指向 vi（后向弧）并且有 fji0，則 vj標(biāo)號(hào) : θj＝ fji 當(dāng)收點(diǎn)已得到標(biāo)號(hào)時(shí)，說明已找到增廣鏈，依據(jù) vi 的標(biāo)號(hào)反向跟蹤得到一條增廣鏈。當(dāng)收點(diǎn)不能得到標(biāo)號(hào)時(shí)，說明不存在增廣鏈，計(jì)算結(jié)束。 第一步： 找出第一個(gè)可行流，例如所有弧的流量 fij =0 FordFulkerson標(biāo)號(hào)算法 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 42 2022年 2月 16日星期三 第三步：調(diào)整流量 （ 1）求增廣鏈上點(diǎn) vi 的標(biāo)號(hào)的最小值，得到調(diào)整量 ? ?m in jj???（ 2）調(diào)整流量 ????????????????????),(),(),(1jifjifjiffijijij得到新的可行流 f1，去掉所有標(biāo)號(hào)，返回到第二步從發(fā)點(diǎn)重新標(biāo)號(hào)尋找增廣鏈，直到收點(diǎn)不能標(biāo)號(hào)為止 【 定理 】 可行流 f是最大流的充分必要條件是不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 43 2022年 2月 16日星期三 ① ② ③ ④ ⑤ ⑥ 8 14 5 6 3 3 8 10 7 6 ⑦ 3 圖 6－ 19 (10) (6) (3) (6) (3) (7) (0) (6) (1) 4 (3) (1) (7) 【 例 610】 求圖 6－ 18發(fā)點(diǎn) v1到收點(diǎn) v7的最大流及最大流量 【 解 】 給定初始可行流，見圖 619 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 44 2022年 2月 16日星期三 ① ② ③ ④ ⑤ ⑥ 8 14 5 6 3 3 8 10 7 6 ⑦ 3 圖 6－ 20(b) (10) (6) (3) (6) (3) (7) (0) (6) (1) 4 (3) (1) (7) ∞ 2 3 3 7 第一輪標(biāo)號(hào)： c12f12,v2標(biāo)號(hào) 2