圖與網(wǎng)絡-西安電子科技大學經(jīng)濟管理學院(參考版)
2025-02-11 03:15本頁面
【正文】 綜合二者說明 p1不是 f1的可增容最短路（或說 p1是 f1的不可增容最短路）。表 20f是容量 為 v0的最小 費 用流p是關于 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已不可能再增容。 例 8 解 2：求解過程見表 19，表 19各最短路的增容過程見圖 18。（ ∵ 此中最短的含義即為路徑各弧的費用和最?。? 利用上述定理可得如下算法步驟?？稍鋈萘繛?δ 則沿 p增容 δ 后所得到的可行流 即為 的最小費用流。（二）求解算法（二）求解算法 算法原理：最小費用最大流之算法有多種，以下介紹一種比較易理解的算法。（一）基本概念（一）基本概念 例 8 某石油公司管道網(wǎng)，由于輸油管道的長短不一，故對于不同的地段（路徑）有不同的容量限制 cij之外，還有不同的單位流量費用 bij，該 cij的單位為萬加侖 /小時， bij的單位為百元 /萬加侖，管道網(wǎng)絡如圖 16所示，圖中括號內的數(shù)字表示（ cij， bij）。設 f是 N上的一個可行流（從 vs到 vt），稱 為可行流 f的費用。這就是最小費用最大流問題的研究。 圖 15 表 18 （例 7求解過程）l 可增路 pl 第二個 標 號 l（ vj）可 調 整量l（ vt） 標 號 圖 調 整 圖網(wǎng) 絡 流量 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（ v2）＝ 4， l（ v5）＝ 3l（ v7）＝ 33 （ g） （ h） 85 v1v4v3v6v7 l（ v4）＝ 3， l（ v3）＝ 3l（ v6）＝ 2， l（ v7）＝ 22 （ i） （ j） 10 已無可增路 END167。4．例 7（教材 P219） 某石油公司擁有一管道網(wǎng)絡，使用此管道網(wǎng)絡可將石油從采地 v1運往銷地 v7，由于各地的地質條件等不同，因而其管道直徑有所不同，從而使各弧的容量 cij（單位：萬加侖 /小時）不同，對于如圖 14所示的管道網(wǎng)絡 N＝（ V， A， C），問每小時從 v1往 v7能運送多少加侖石油？圖 14 解 1：若設?。?vi， vj）上的流量為 fij，網(wǎng)絡 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中各可增路及其流量調整過程見圖 15。 l＝ 1在 f中任取一可增路 pl利用標號規(guī)則與調整規(guī)則對沿著路 p的各弧作最大可能調整 是否對 N中所有 路均作調整打印經(jīng)調整后的最大流f*及最大流量 v（ f*）取 N的一條新可增路 pll＝ l＋ 1END 圖 12（二）
教學課件相關推薦
鄂ICP備17016276號-1