運籌學第十章圖與網(wǎng)絡(luò)分析-文庫吧資料
2024-10-24 21:04本頁面
【正文】 (4)截集與截量 設(shè) S， T?V， S?T=?，我們把始點在 S，終點在 T中的 所有弧構(gòu)成的集合，記為（ S，T）。 最大流問題：求一流 {fij}滿足 0? fij?cij v(f) i=s ?fij–?fji= 0 i?s， t –v(f) i=t 且使 v(f)達到最大。 網(wǎng)絡(luò)的流：定義在弧集合 A上的一個函數(shù)f={f(vi,vj)}，稱 f(vi,vj)為弧 (vi,vj)上的流量。這樣的有向圖稱為網(wǎng)絡(luò)。 4 最大流問題 如下是一運輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡(luò)的最大流量是多少？ vs v2 v1 v3 v4 vt 4 3 2 3 1 2 2 3 4 基本概念和基本定理 (1) 網(wǎng)絡(luò)與流 定義 1 給定一個有向圖 D=(V,A),在 V中有一個發(fā)點 vs和一收點 vt，其余的點為中間點。這樣五年的總費用最少，為 78。于是，該問題就可歸結(jié)為從圖中找出一條從 v1到 v6的最短路問題。 例 設(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表示這一方案所需購置費和維護費之和。 例 求下圖所示有向圖中從 v1到各點的最短路。否則轉(zhuǎn) (1) 例 求節(jié)點 v1到節(jié)點 v5的最短距離及其路線 vS v1 v2 v3 v4 v5 1 2 2 2 3 3 3 4 4 [解 ] P(vs)=0 T(vj)=∞,j=1, … ,5 第一步： T(v1)=min{T(v1),P(vs)+ds1}=min{∞,0+4}=4 (1)與節(jié)點 vs直接相連的臨時標號的節(jié)點為 v1, v2，將這兩個節(jié)點的臨時標號改為 T(v2)=min{T(v2),P(vs)+ds2}=min{∞,0+3}=3 (2)在所有 T標號中，最小的為 T(v2)=3,于是令 P(v2)=3 第二步： (1)與節(jié)點 v2直接相連的臨時標號的節(jié)點為 v3和 v4，把這兩個節(jié)點的 T標號改為 T(v1)=min{T(v1),P(v2)+d21}=min{4,3+2}=4 T(v4)=min{T(v4),P(v2)+d24}=min{∞,3+2}=5 (2).在所有 T變化中， T(v1)=4最小，于是令 P(v1)=4 第三步： (1).與節(jié)點 v1相連的臨時標號的節(jié)點為v3,v4，把這兩個節(jié)點的 T標號改為 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→
教學課件相關(guān)推薦
鄂ICP備17016276號-1