運(yùn)籌學(xué)基礎(chǔ)圖論方法-全文預(yù)覽
【正文】 (3,2) 0 (8,4) 0 (4,1) 0 33,2) 3 3414) 5413 ) 4 Θ=1 ∑W =8 45) 5s 1 3 t 1 1 2 2 2 4 3 6 5 s 1 3 t 1 3 2 1 2 2 s 2 3 t 4 1 2 8 3 1 s 2 1 t 4 2 6 7 3 7 s 2 1 t 4 3 6 3 1 4 2 1 4 s 2 3 4 1 3 1 （六）利用 EXCEL求 網(wǎng)絡(luò)最大流量 第一步：建立各結(jié)點(diǎn)間的流量矩陣和單位費(fèi)用矩陣 s32t1(7,6 ) 0 (5,2 ) 0(6,1 ) 0(2,3 ) 0(3,2 ) 0(8,4 ) 0(4,1 ) 0各結(jié)點(diǎn)間的流量矩陣vs v1 v2 v3 vtvs 4 8v1 3 2 7v2 6v3 5vt各結(jié)點(diǎn)間的單位費(fèi)用矩陣vs v1 v2 v3 vtvs 1 4v1 2 3 6v2 1v3 2vt利用 EXCEL求起點(diǎn)到終點(diǎn)的最短路徑 第二步：定義最大流量方案 vs v1 v2 v3 vt 流出vs =SUM(B17:F17)v1 =SUM(B18:F18)v2 =SUM(B19:F19)v3 =SUM(B20:F20)vt =SUM(B21:F21)流入 =SUM(B17:B21) =SUM(C17:C21) =SUM(D17:D21) =SUM(E17:E21) =SUM(F17:F21) =SUMPRODUCT(B17:F21,I5:M9)最大流量計(jì)算表vs v1 v2 v3 vt 流出vs 0v1 0v2 0v3 0vt 0流入 0 0 0 0 0 0 第三步：利用規(guī)劃求解 各結(jié)點(diǎn)間的流量矩陣vs v1 v2 v3 vtvs 4 8v1 3 2 7v2 6v3 5vt vs v1 v2 v3 vt 流出vs 0 4 5 0 0 9v1 0 0 0 0 4 4v2 0 0 0 5 0 5v3 0 0 0 0 5 5vt 0 0 0 0 0 0流入 0 4 5 5 9 63結(jié)點(diǎn)流 9 0 0 0 9結(jié)點(diǎn)流限制 0 0 0最大流量計(jì)算表vs v1 v2 v3 vt 流出vs 0v1 0v2 0v3 0vt 0流入 0 0 0 0 0 0。 求最小費(fèi)用流的步驟 第一步：從零流 f0開始，找一條使 總費(fèi)用最小 的 增廣鏈 ? 該鏈上的總費(fèi)用為 ： q ∑W(i,j)； 其中， q是該鏈上增加的流量， W(i,j)是該鏈上增廣一單位流量，弧 (i,j) “增加” 的費(fèi)用。 若在最小費(fèi)用流問題中，將單位流量通過弧的 費(fèi)用 當(dāng)成是距離 ，則求從發(fā)點(diǎn)至收點(diǎn)調(diào)運(yùn)一單位流量的最小費(fèi)用，也就等價(jià)于求該兩點(diǎn)之間的最短距離。ij=fij –θ s t 5 2 4 1 3(2) 2(0) 5(4) 3(3) 3(3) 6(4) 5(5) 6(6) 8(6) 3 2(0) 4(4) 2(2) 3(3)5(5)3(2)6(5)8(7)2(1)（四）應(yīng)用舉例 ［例］某河流中有幾個(gè)島嶼，從兩岸至各島嶼及島嶼之間的橋梁如圖。ij=fij –θ,增廣后仍是可行流 ????? ?? 后向弧 前向弧ijijijij ffcq欲求增廣量 找最小截集的標(biāo)號法步驟 第一步：標(biāo)號過程，找一條增廣鏈 給源點(diǎn) s 標(biāo)號 [s+,q(s)=?]，表示從 s 點(diǎn)有無限流出潛力 找出與 已標(biāo)號節(jié)點(diǎn) i 相鄰 的所有未標(biāo)號 節(jié)點(diǎn) j，若 (1) (i, j)是前向弧且 飽和 ， 則節(jié)點(diǎn) j 不標(biāo)號 （即此路不通） ； (2) (i, j)是前向弧且未飽和，則節(jié)點(diǎn) j 標(biāo)號為 [i+,θ(j)]，表示從節(jié)點(diǎn) i 正向 流出，可增廣 θ(j)=min[θ(i), cij?fij] ； (3) (j, i)是后向弧，若 fji=0， 則節(jié)點(diǎn) j
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1