企業(yè)運籌學(xué)--圖與網(wǎng)絡(luò)理論講義(參考版)
2025-03-09 19:59本頁面
【正文】 福德－富克遜方法示例 ③ 在增廣鏈上調(diào)整流量 。 vt已經(jīng)標記 , 找到流量增廣鏈 。也表示增廣鏈可以從 V1延伸到 V1 vs 10 11 5 6 4 7 3 9 15 vt v5 v3 v4 v2 (4) (9) (3) (1) (5) (7) (5) (8) [, ∞] 福德－富克遜方法示例 ② 尋求增廣鏈 如果 vi是已經(jīng)標記的點 , vj是未標記的點 則當 (vi ,vj)是非飽和弧時 , vj可以標記 : [vi+,ej] ej=min{ei, bijxij} 當 (vj ,vi)是非零流弧時 , vj可以標記 : [vi,ej] ej=min{ei, xji} 如果 vt可以標記 ,則找到增廣鏈 , 否則繼續(xù) . 如果對于一切未標記的點 , 均不能再標記 , 則已經(jīng)是最優(yōu) . 福德－富克遜方法示例 ② 尋求增廣鏈 如圖 v1是已經(jīng)標記的點 , 其它點是未標記的點 (v1 ,v2)是非飽和弧 , v2可以標記 : [v1+,e2] e2=min{e1,b12x12} (v1 ,v3)是飽和弧 , 目前 v3和其它點暫時不能標記 ， 即暫時沒有從 v1 到 v3或其它點的增廣鏈 。 福德－富克遜方法示例 標記化算法的步驟 ： ① 為網(wǎng)絡(luò)分配初始流 xij標在圖中弧旁的 ( )內(nèi) vs 10 11 5 6 4 7 3 9 15 vt v5 v3 v4 v2 (4) (9) (3) (1) (5) (7) (5) (8) 福德－富克遜方法示例 ② 尋求增廣鏈 從 υs開始 ， 賦上標記 （ － ， ∞） ， 表示 υs是源點， 能夠得到任意多的量 。 從 υs開始 ， 逐個檢查每個點 υi， 看是否存在從υs到 υi的增廣鏈 。 重復(fù) ② 、 ③ 兩步 ， 直到最優(yōu) 。 2 增廣鏈上任一點到 Vt也有增廣鏈 。 ② 其上的逆向弧均為非零流弧 。 結(jié)論：若在可行流中 ， 存在從 υs到 υt的增廣鏈， 則該可行流不是最大流 ， 其流量可以增加；否則若不存在從 υs到 υt的增廣鏈 ， 則該可行流是最大流 。 福德－富克遜方法討論 流量增廣鏈 : 從 υs到 υt的某個初等鏈滿足 ① 其上的正向弧均為非飽和弧 。 ② 其上的逆向弧均為非零流弧 。 把這條鏈中的 υs到 υt方向相反的弧稱為 逆向弧 。 一條從 υs到 υt的初等鏈是由 υs開始的點 、 邊序列 ， 其中沒有相同的點 ， 也不考慮弧的方向 。 若弧 (vi,vj)上的流量 xij=0。 所謂可行流 ， 是指所有弧上流量滿足容量限制 ， 所有中間點滿足平衡條件的流； 若這一可行流的流量就是最大流量 ， 則問題已經(jīng)解決； 若不是最大流量 ， 則增加流量獲得流量更大的可行流 。 最大流－最小割集定理 流過網(wǎng)絡(luò)的最大流量等于最小割集的容量 。 最大流最小割集定理 2 網(wǎng)絡(luò)中的最大流量 fmax值大小是由網(wǎng)絡(luò)中最狹窄處瓶頸的容量所決定的 。 最大流－最小割集定理揭示了最小割集 （ 網(wǎng)絡(luò)中的瓶頸） 容量與最大流量的關(guān)系 ， 也提供了一個求最大流的方法 。 若以 bij表示由 υi到 υj的弧上允許流過的最大流量 ，以 xij表示實際流過該弧的流量 ， 則 0≤ xij ≤bij ④ 網(wǎng)絡(luò)中 ， 除起點 υs和終點 υt之外的任何頂點 ， 流入量總和應(yīng)該等于流出量的總和 。 }min{ )()1( ijkikj ldd ??? 福德算法 3 算法示例 }min{ )()1(ijkikj ldd ??? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L1jj ld ?)1( 福德算法 4 }min{)()1( ijkikj ldd ??? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ 福德算法 5 }min{ 1)1()2(1 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }min{ )()1( ijkikj ldd ??? 福德算法 6 }min{ 2)1()2(2 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }min{ )()1( ijkikj ldd ???2 福德算法 7 }min{ 3)1()2(3 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }min{ )()1( ijkikj ldd ???2 5② 福德算法 8 }min{ 4)1()2(4 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }min{ )()1( ijkikj ldd ???2 5② 10② 福德算法 9 }min{ 5)1()2(5 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }min{ )()1( ijkikj ldd ???2 5② 10② 9③ 福德算法 10 }min{ 6)1()2(6 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ??????????????????
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1