運籌學(xué)第十章圖與網(wǎng)絡(luò)分析(編輯修改稿)
2024-11-14 21:04 本頁面
【文章內(nèi)容簡介】 為 T(v3)=min{T(v3),P(v1)+d13}=min{∞,4+3}=7 T(v4)=min{T(v4),P(v1)+d14}=min{5,4+1}=5 (2).在 T標號中， T(v4)=5最小，令 P(v4)=5 第四步： (1).與節(jié)點 v4相連的 T標號有 v3,v5把這兩個節(jié)點的 T標號改為 T(v3)=min{T(v3),P(v4)+d43}=min{7,5+2}=7 T(v5)=min{T(v5),P(v5)+d45}=min{∞,5+4}=9 (2).T(v3)最小 ,P(v3)=7 第五步： (1).與 v3相連的臨時標號有 v5 T(v5)=min{T(v5),P(v3)+d35}=min{9,7+3}=9 (2).P(v5)=9 最短路線： vs→ v1→ v4→ v5 vs→ v2→ v4→ v5 下面介紹當賦權(quán)有向圖中，存在具負權(quán)的弧時，求最短路的方法。 令 d(1)(vs,vj)=wsj 對 t=2,3,…, d(t)(vs,vj)=min{d(t1)(vs,vi)+wij} (j=1,2, …, p) 若進行到某一步 ,例如第 k步 ,對所有 j=1, 2, …,p, 有 d(k)(vs,vj)=d(k1)(vs,vj) i 則 {d(k)(vs,vj)}j=1,2,…,p 即為到各點的最短路的權(quán)。 例 求下圖所示有向圖中從 v1到各點的最短路。 v1 v4 v2 v3 v5 v6 v7 v8 2 5 3 4 6 7 4 2 3 1 3 4 2 wij d(t)(v1,vj) v1 v2 v3 v4 v5 v6 v7 v8 v1 v2 v3 v4 v5 v6 v7 v8 0 2 5 3 0 2 4 0 6 4 0 0 3 0 7 2 0 3 2 0 t=1 t=2 t=3 t=4 t=5 t=6 0 2 5 3 0 2 0 3 6 11 0 2 0 3 6 6 15 0 2 0 3 3 6 14 10 0 2 0 3 3 6 9 10 0 2 0 3 3 6 9 10 說明：表中空格處為 +?。 例 設(shè)備更新問題 制訂一設(shè)備更新問題，使得總費用最小 第 1年 第 2年 第 3年 第 4年 第 5年 購買費 13 14 16 19 24 使用年數(shù) 01 12 23 34 45 維修費 8 10 13 18 27 [解 ]設(shè)以 vi(i=1,2,3,4,5)表示“第 i年初購進一臺新設(shè)備”這種狀態(tài)，以 v6表示“第 5年末”這種狀態(tài)；以弧 (vi, vj)表示“第 i年初購置的一臺設(shè)備一直使用到第 j年初”這一方案，以 wij表示這一方案所需購置費和維護費之和。 這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問題就可歸結(jié)為從圖中找出一條從 v1到 v6的最短路問題。 用 Dijkstra標號法，求得最短路為 v1?v3?v6 即第一年初購置的設(shè)備使用到第三年初予以更新，然后一直使用到第五年末。這樣五年的總費用最少，為 78。 v1 v2 v3 v5 v6 v4 21 44 32 22 89 62 31 63 45 24 47 34 27 37 32 (0) (21) (31) (44) (62) (78) 167。 4 最大流問題 如下是一運輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡(luò)的最
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1