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