運籌學——圖與網(wǎng)絡-資料下載頁
2025-08-01 15:24本頁面
【正文】 第三節(jié) 網(wǎng)絡最大流問題 增廣鏈 若給一個可行流 f={fij}，我們把網(wǎng)絡中使 fij=cij的弧稱為 飽和弧 ，使 fijcij的弧稱為 非飽和弧 。把 fij=0的弧稱為 零流弧 ， fij0的弧稱為 非零流弧 。 若 u是網(wǎng)絡中聯(lián)結(jié)發(fā)點 vs和收點 vt的一條鏈。我們定義鏈的方向是從 vs到 vt，則鏈上的弧被分為兩類：一類是弧的方向與鏈的方向一致，叫作 前向弧 。前向弧的全體記為 u+。另一類弧與鏈的方向相反，稱為 后向弧 。后向弧的全體記為 u。 定義 3： 設 f是一個可行流， u是從 vs到 vt的一條鏈，若 u滿足下述條件，稱之為 (關于可行流 f的 )一條增廣鏈。 在弧 (vi,vj)∈ u+上， 0≤fij≤cij，即 u+中每一弧是非飽和鏈。 在弧 (vi,vj)∈ u上， 0fij≤cij，即 u中每一弧是非零流鏈。 (4,3) (2,2) (1,1) (3,0) vs v1 v2 v3 v4 vt 定理 1：可行流 f*是最大流，當且僅當不存在關于 f*的增廣鏈。 第三節(jié) 網(wǎng)絡最大流問題 四、求最大流的標號法 在這個過程中，網(wǎng)絡中的點或者是標號點（又分為已檢查和未檢查兩種），或者是未標號點。每個標號點的標號包含兩部分：第一個標號表明它的標號是從哪一點得到的，以便找出增廣鏈；第二個標號是為確定增廣鏈的調(diào)整量用的。 第三節(jié) 網(wǎng)絡最大流問題 (4,3) (2,2) (1,1) (3,0) vs v1 v2 v3 v4 vt 例：用標號法求下圖所示網(wǎng)絡的最大流?；∨缘臄?shù)是（ cij,fij） 第三節(jié) 網(wǎng)絡最大流問題 （ 1）標號過程 標號過程開始，先給 vs標上 (0， +∞)，這時 vs是標號而未檢查的點，其余都是未標號點。一般地，取一個標號而未檢查的點 vi，對一切未標號點 vj： GO (vi， vj)上， fijcij，則給 vj標號 (vi,l(vj))。這里 l(vj)=min[l(vi),cijfij]。這時點 vj成為標號而未檢查的點。 (vj,vi)上， fij0，則給 vj標號 (vi,l(vj))，這里l(vj)=min[l(vi),fij]。這時點 vj成為標號而未檢查的點。 于是 vi成為標號而已檢查過的點。重復上述步驟，一旦 vt被標上號，表明得到一條從 vs到 vt的增廣鏈 u，轉(zhuǎn)入調(diào)整過程。 若所有標號都是已檢查過，而標號過程進行不下去時，由算法結(jié)束，這時的可行流就是最大流 第三節(jié) 網(wǎng)絡最大流問題 (2)調(diào)整過程 GO 首先按 vt及其它點的第一個標號，利用 “ 反向追蹤 ”的辦法，找出增廣鏈 u。令調(diào)整量 θ是 l(vt)，即 vt的第二個標號。 ????????????????????)v,(v f)v,(v f)v,(v ffjiijjiijjiij39。ij令 去掉所有的標號，對新的可行流 f’={fij’}，重新進入標號過程。 (4,3) (2,2) (1,1) (3,0) vs v1 v2 v3 v4 vt (0,+∞) 解： 標號過程： (1)首先給 vs標上 (0,+∞) (2)檢查 vs，在弧 (vs,v2)上， fs2=cs2=3，不滿足標號條件?；?(vs,v1)上， fs1=1， cs1=5， fs1cs1，則 v1的標號為(vs,l(v1))其中 l(v1)=min[l(vs),(cs1fs1)]=[+∞,51]=4 (3)檢查 v1 (vs,4) (v1,1) (4)檢查 v2 (5)在 v3， v4中任選一個進行檢查 調(diào)整過程： 按點的第一標號找到一條增廣鏈。 即： vt→v 3→v 2→v 1→v s 調(diào)整量 θ=1 (4,3) (2,2) (1,1) (3,0) vs v1 v2 v3 v4 vt (0,+∞) (vs,4) (v1,1) (v2,1) (v2,1) (v3,1) (1,0) (vs,3) ∵ 標號進行不下去 ∴ 當前可行流是最大流。 最大流 W=5。 第三節(jié) 網(wǎng)絡最大流問題 練習： 用標號法求下圖所示網(wǎng)絡的最大流。 Vs、 Vt分別為發(fā)點和收點，弧旁數(shù)字為 (cij,fij)。（ 哈工程 2022年考研真題 ） 第三節(jié) 網(wǎng)絡最大流問題 s1 s2 v1 v2 t1 t2 3 7 2 2 4 4 3 7 7 6 練習： 如下圖所示，發(fā)點 s1， s2分別可供應 10和 15個單位，收點 t1， t2可以接收 10和 25個單位，求最大流，弧旁數(shù)字為 cij。 s t 10 15 10 25 第四節(jié) 應用舉例 例．某工廠使用一臺設備，每年年初工廠都要作出決定，如果繼續(xù)使用舊的，要付維修費；若購買一臺新設備，要付購買費．試制定一個５年更新計劃，使總支出最少．若已知設備在各年的購買費，及不同機器役齡時的殘值與維修費如下表５－１所示． 項目 第 1年 第 2年 第 3年 第 4年 第５年 購買費 11 12 13 14 14 機器役齡 01 12 23 34 45 維修費 5 6 8 11 18 殘值 4 3 2 1 0 表５－１ 第四節(jié) 應用舉例 例．設有５位待業(yè)者，５項工作，他們各自能勝任工作情況如圖所示，要求，設計一個就業(yè)方案，使盡量多的人能就業(yè)． x1 x2 x3 x4 x5 y1 y2 y3 y4 y5
研究報告相關推薦
鄂ICP備17016276號-1