圖與網(wǎng)絡(luò)-西安電子科技大學經(jīng)濟管理學院(文件)
【正文】 顯然若fij≥c ij則網(wǎng)絡(luò) N在 aij邊將發(fā)生堵塞現(xiàn)象，這是人們希望能避免的現(xiàn)象。若在路 P的一切順向弧（ vi， vj）上有 fij＜ cij，在路 P的一切逆向?。?vj， vi）上有 fji＞ 0，則稱路 P是一條關(guān)于 f的可增路。 圖 11 由上可知在 def11中可增路要求順向弧fij＜ cij之條件，實際上說明沿該?。?vi， vj）還可提高流量 △ ij＝ cij－ fij＞ 0，另一方面，為提高流量 v（ f）還要求該路的逆向弧降低流量，而fji＞ 0正說明了該逆向弧可降低 fji個單位。4．例 7（教材 P219） 某石油公司擁有一管道網(wǎng)絡(luò)，使用此管道網(wǎng)絡(luò)可將石油從采地 v1運往銷地 v7，由于各地的地質(zhì)條件等不同，因而其管道直徑有所不同，從而使各弧的容量 cij（單位：萬加侖 /小時）不同，對于如圖 14所示的管道網(wǎng)絡(luò) N＝（ V， A， C），問每小時從 v1往 v7能運送多少加侖石油？圖 14 解 1：若設(shè)?。?vi， vj）上的流量為 fij，網(wǎng)絡(luò) N上總流量為 F，則可建立如下 LP： max F ＝ f12 ＋ f14 f12 ＝ f23 ＋ f25 f14 ＝ f43 ＋ f46 ＋ f47 f23 ＋ f43 ＝ f35 ＋ f36 s． t f25 ＋ f35 ＝ f57 f36 ＋ f46 ＝ f67 f47 ＋ f57 ＋ f67 ＝ f12 ＋ f14 fij≤cij i＝ 1～ 6， j＝ 1～ 7 fij≥0 i＝ 1～ 6， j＝ 1～ 7v1 v2 v3 v4 v5 v6 v7v1v2v3v4v5v6v70 6 0 6 0 0 00 0 2 0 3 0 00 0 0 0 2 2 00 0 3 0 0 3 20 0 0 0 0 0 50 0 0 0 0 0 50 0 0 0 0 0 0C陣 利用單純形法可解得最大流： f*＝ {f12＝ 5， f14＝ 5， f23＝ 2， f25＝ 3， f43＝ 2， f46＝ 1， f47＝ 2， f35＝ 2， f36＝ 2， f57＝ 5， f67＝ 3， v（ f*）＝ 10} 解 2：（采用雙標號法求最大流） 求解中尋找了五條可增路，其標號過程與增流過程見表 18，表 18中各可增路及其流量調(diào)整過程見圖 15。這就是最小費用最大流問題的研究。（一）基本概念（一）基本概念 例 8 某石油公司管道網(wǎng)，由于輸油管道的長短不一，故對于不同的地段（路徑）有不同的容量限制 cij之外，還有不同的單位流量費用 bij，該 cij的單位為萬加侖 /小時， bij的單位為百元 /萬加侖，管道網(wǎng)絡(luò)如圖 16所示，圖中括號內(nèi)的數(shù)字表示（ cij， bij）。可增容量為 δ 則沿 p增容 δ 后所得到的可行流 即為 的最小費用流。 例 8 解 2：求解過程見表 19，表 19各最短路的增容過程見圖 18。綜合二者說明 p1不是 f1的可增容最短路（或說 p1是 f1的不可增容最短路）。表 20f是容量 為 v0的最小 費 用流p是關(guān)于 f的可增容（可增容量為 δ）最短路 則沿 p增容 δ后所得的可行流 為容量為 v0＋ δ 的最小 費 用f0是 0 p1 f0 1 p1 f1 1f1是 1 p2 f0 2 p2 f2 3f2是 2 p3 f0 2 p3 f3 5f3是 3 p4 f0 1 p4 f4 6f4是 4 p5 f0 3 p5 f5 9f5是 5 p6 f0 1 p6 f6 10 此中需要說明的是： p1是 f0的可增容最短路，為什么不是 f1的可增容最短路？這是由于 f1沿 p1已不可能再增容。（ ∵ 此中最短的含義即為路徑各弧的費用和最?。? 利用上述定理可得如下算法步驟。（二）求解算法（二）求解算法 算法原理：最小費用最大流之算法有多種，以下介紹一種比較易理解的算法。設(shè) f是 N上的一個可行流（從 vs到 vt），稱 為可行流 f的費用。 圖 15 表 18 （例 7求解過程）l 可增路 pl 第二個 標 號 l（ vj）可 調(diào) 整量l（ vt） 標 號 圖 調(diào) 整 圖網(wǎng) 絡(luò) 流量 v（ f）1 v1v4v7 l（ v4）＝ 6， l（ v7）＝ 2 2 （ a） （ b） 22 v1v2v3v5v7 l（ v2）＝ 6， l（ v3）＝ 2l（ v5）＝ 2， l（ v7）＝ 22 （ c） （ d） 43 v1v4v6v7 l（ v4）＝ 4， l（ v6）＝ 1l（ v7）＝ 21 （ e） （ f） 54 v1v2v5v7 l（
教學課件相關(guān)推薦
鄂ICP備17016276號-1