運(yùn)籌學(xué)基礎(chǔ)圖論方法-資料下載頁
2025-04-30 12:05本頁面
【正文】 該鏈上增廣一單位流量，弧 (i,j) “增加” 的費(fèi)用。 第二步：重復(fù)第一步，一直到再也找不到增廣鏈為止 注：用標(biāo)號(hào)法的簡(jiǎn)單形式 ? 增廣鏈 ：是從發(fā)點(diǎn)到收點(diǎn)的一條鏈，該鏈上所有指向?yàn)?s→t的 前向弧 ，存在 f＜ c；所有指向?yàn)?t→s 的 后向弧 ，存在 f＞ 0，這樣的鏈叫增廣鏈。 ? 費(fèi)用： 弧 (i,j)為前向弧時(shí)， W(i,j)= bij； 弧 (i,j)為反向弧時(shí)， W(i,j)= bij 例 s 3 2 t 1 (4,9) 0 (8,4) 0 (10,9) 0 (3,2) 0 (2,5) 0 (8,7) 0 (5,8) 0 (cij , bij ) fij Θ=3 Θ=2 Θ=5 截止 最大流量＝ 8+4＝ 12 ∑W =14 333∑W =17 2 5∑W =20 ) 80,9) 5 5Θ=2 ∑W =21 最小流量費(fèi)用＝ ∑(q *∑W )=218 427s 1 3 t 8 2 4 5 3 8 s 1 t 8 9 2 4 s 2 3 t 7 9 4 8 10 5 s 2 1 t 7 5 9 3 2 2 s 2 3 1 7 9 2 1 5 3 又例 (cij , bij ) fij Θ=3 Θ=1 Θ=1 截止 最大流量＝ 4+5＝ 9 ∑W =6 ∑W =6 ∑W =7 Θ=3 ∑W =8 最小流量費(fèi)用＝ ∑(q *∑W )= 63 s 3 2 t 1 (7,6) 0 (5,2) 0 (6,1) 0 (2,3) 0 (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
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1