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