6.-5最小費用最大流問題

第五節(jié)

最小費用最大流問題6.-5最小費用最大流問題一、基本概念1、什么是最小費用最大流問題？對每一條弧都給出單位流量費用的容量網(wǎng)絡(luò)D=（V，A，B）（稱為費用容量網(wǎng)絡(luò)）中，求取最大流X，使輸送流量的總費用

C（X）=∑cijxij為最小的一類優(yōu)化問題。其中，bij表示?。╲i，vj）上的容量，xij表示?。╲i，vj）上的流量，cij表示?。╲i，vj）上通過單位流量所花費的費用。6.-5最小費用最大流問題2、最小費用流

對一費用容量網(wǎng)絡(luò)，具有相同流量f的可行流中，總費用最小的可行流稱為該費用容量網(wǎng)絡(luò)關(guān)于流量f的最小費用流，簡稱流量為f的最小費用流。6.-5最小費用最大流問題從上節(jié)可知，尋求最大流的方法是從某個可行流出發(fā)，找到關(guān)于這個流的一條增廣鏈μ。沿著μ調(diào)整f，對新的可行流試圖尋求關(guān)于它的增廣鏈，如此反復(fù)直至最大流?，F(xiàn)在，要尋求最小費用的最大流，我們首先考察一下，當(dāng)沿著一條關(guān)于可行流f的增廣鏈μ，以ε=1調(diào)整f，得到新的可行流f′（顯然v（f′）=v（f）+1）時，C（f′）比C（f）增加多少(輸送流量的總費用

)？6.-5最小費用最大流問題3、增廣鏈的費用當(dāng)沿著一條關(guān)于可行流X的增廣鏈（流量修正路線）μ，以修正量ε=1進(jìn)行調(diào)整，得到新的可行流，則稱C（）-C（X）為

增廣鏈μ的費用。6.-5最小費用最大流問題②增廣鏈μ的費用就是以單位調(diào)整量調(diào)整可行流時所付出的費用；③當(dāng)修正量ε=1時，此時，

①的流量f()=f(X)+1；C()-C(X)=6.-5最小費用最大流問題二、求解最小費用最大流問題的對偶法1、求解途徑：（1）始終保持網(wǎng)絡(luò)中的可行流是最小費用流，然后不斷調(diào)整，使流量逐步增大，最終成為最小費用的最大流；（2）始終保持可行流是最大流，通過不斷調(diào)整使費用逐步減小，最終成為最大流量的最小費用流。6.-5最小費用最大流問題2、算法原理（1）定理若X是流量為f(X)的最小費用流，μ是關(guān)于X的所有增廣鏈中費用最小的增廣鏈，那么沿著μ去調(diào)整X得到的新的可行流就是流量為f()的最小費用流。6.-5最小費用最大流問題（2）實現(xiàn)思路基于第一種求解途徑，根據(jù)上述定理，只要找到最小費用增廣鏈，在該鏈上調(diào)整流量，得到增加流量后的最小費用流。循環(huán)往復(fù)直至求出最小費用最大流。6.-5最小費用最大流問題對偶法原理和步驟求最大流Ford算法找從vs到vt的最短增廣鏈調(diào)整流量得費用最小的可行流將0流作為初始可行流Yes繪制擴展費用網(wǎng)絡(luò)No流量等于最大流?得最小費用最大流確保流量最大確保費用最小6.-5最小費用最大流問題

實施中的關(guān)鍵

構(gòu)造增廣費用網(wǎng)絡(luò)圖（即擴展費用網(wǎng)絡(luò)圖），借助最短路算法尋找最小費用增廣鏈。

為什么?理由:正向飽和弧不標(biāo)記,反向零流弧不標(biāo)記。

—不構(gòu)造增廣費用網(wǎng)絡(luò),就無法調(diào)整流量(1)飽和弧,流量無法減小;(2)非飽和弧,流量只能增加,不能減小;增廣鏈流量調(diào)整：正向弧增加流量，反向弧減少流量。6.-5最小費用最大流問題零流弧上

Wij=cij

原有?。髁靠梢栽黾樱藓蠹踊。髁坎荒茉贉p少）

飽和弧上wij=∞原有?。髁坎荒茉僭黾樱?/p>

-cij

后加?。髁靠梢詼p少）

非飽和且非零流

(0<xij<bij)弧上

cij

原有?。髁靠梢栽黾樱?/p>

-cij

后加?。髁靠梢詼p少）

Wij=增廣費用網(wǎng)絡(luò)圖的構(gòu)造方法將網(wǎng)絡(luò)中的每一條弧（vi,vj）都變成一對方向相反的弧，以形成四通八達(dá)的“路”，權(quán)數(shù)定義如下：

6.-5最小費用最大流問題將上述思想加以簡化，出現(xiàn)∞處相應(yīng)的弧不畫，按下面的方法具體構(gòu)造增廣費用網(wǎng)絡(luò)圖：

零流弧上，保持原弧不變，將單位費用作為權(quán)數(shù)，即wij=cij:

Vi

Vj原網(wǎng)絡(luò)

Vi

Vj增廣費用網(wǎng)絡(luò)6.-5最小費用最大流問題非飽和弧上，原有弧以單位費用作權(quán)數(shù)，后加弧（虛線?。┮詥挝毁M用的負(fù)數(shù)作權(quán)數(shù)：ViVj原網(wǎng)絡(luò)ViVj增廣費用網(wǎng)絡(luò)6.-5最小費用最大流問題飽和弧上,去掉原有弧,添上后加弧(虛線弧),權(quán)數(shù)為單位費用的負(fù)數(shù)：ViVj原網(wǎng)絡(luò)ViVj(bij,-cij)增廣費用網(wǎng)絡(luò)6.-5最小費用最大流問題

于是，在容量網(wǎng)絡(luò)中尋找最小費用增廣鏈就相當(dāng)于在增廣費用網(wǎng)絡(luò)圖（擴展費用網(wǎng)絡(luò)圖）中尋找從發(fā)點到收點的最短路。注意將找到的最短路還原到原網(wǎng)絡(luò)圖中（虛線弧改成原圖中的反向?。?。6.-5最小費用最大流問題3、步驟：第一步---用Ford-Fukerson算法求出該容量網(wǎng)絡(luò)的最大流量fmax；（本步驟的作用是什么？）第二步---取初始可行流為零流，其必為流量為0的最小費用流（為什么？）6.-5最小費用最大流問題

第三步---一般為第k-1次迭代，得一最小費用流X(k-1)

，對當(dāng)前可行流構(gòu)造增廣費用網(wǎng)絡(luò)圖W(X(k-1))，用最短路算法求出從發(fā)點到收點的最短路。

若不存在最短路，則X(k-1)即最小費用最大流，停止迭代；

否則，轉(zhuǎn)下一步。

6.-5最小費用最大流問題

第四步---將最短路還原成原網(wǎng)絡(luò)圖中的最小費用增廣鏈μ，在μ上對可行流X(k-1)進(jìn)行調(diào)整，得到新的可行流圖，若其流量等于fmax,迭代結(jié)束。否則轉(zhuǎn)入第一步，進(jìn)入下一次迭代過程。6.-5最小費用最大流問題4、舉例增廣費用網(wǎng)絡(luò)圖(容量費用圖(bij,cij))

可行流圖

(流量網(wǎng)絡(luò)(bij,cij,xij))vsvtv2v3v1(10,7)(7,7)(8,4)(10,4)(4,4)(5,0)(2,0)最大流圖fmax=11(未標(biāo)費用)第0次迭代6.-5最小費用最大流問題vsvtv2v3v1(10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)(5,2,5)(7,1,5)vsvtv2v3v1(10,4,0)(8,1,5)(10,3,0)(4,2,0)(2,6,0)第1次迭代①原圖全部是零流弧,保持原邊不變,單位費用為權(quán)；②所有的權(quán)均大于零，可用D氏標(biāo)號法求出最短路：恰也是最小費用增廣鏈。

①流量調(diào)整量ε1=min{8-0,5-0,7-0}=5

總流量f1=5②最小費用增廣鏈的費用∑cij=1+2+1=4③總費用C1=4×5=20

6.-5最小費用最大流問題第2次迭代(3,1)v1vt(5,-2)(2,6)v2v3(10,4)(5,-1)(10,3)(4,2)（2,1）vs（5，-1）(7,1,7)vsvtv2v3v1(10,4,2)(8,1,5)(10,3,0)(4,2,0)(2,6,0)(5,2,5)①零流弧保持原邊,非飽和非零流弧(vs,v2)和(v1,vt)增添后加弧,飽和弧(v2,v1)去掉原弧增添后加??；②用列表法求出最短路:恰也是最小費用增廣鏈。①流量調(diào)整量ε2=min{10-0,2-0(7-5)}=2，總流量=原流量+新增流量

=5+2=7；②最小費用增廣鏈的費用∑cij=4+1=5③總費用C2=原費用+新增費用=20+5×2=306.-5最小費用最大流問題vsvtv2v3v1(8,4)（2,-4）(5,-1)(7,-1)(10,3)(4,2)(2,6)(5,-2)(3,1)①零流弧保持原邊，此外的非飽和弧增添后加弧，飽和弧去掉原邊增添反向虛線弧②用列表法求得最短路恰也是最小費用增廣鏈。①流量調(diào)整量ε3=min{3，10,4}=3，總流量=原流量+新增流量

=7+3=10；②最小費用增廣鏈的費用∑cij=1+3+2=6③總費用C2=原費用+新增費用=30+6×3=48第3次迭代(7,1,7)vsvtv2v3v1(10,4,2)(8,1,8)(10,3,3)(4,2,3)(2,6,0)(5,2,5)6.-5最小費用最大流問題(2,6)(7,3)(8,4)vsvtv2v3v1(3,-3)(7,-1,)(8,-1)(3,-2)（1,2）(2,-4)（5,-2）①零流弧保持原邊，此外的非飽和弧增添后加弧，飽和弧去掉原邊增添反向虛線??；②用列表法求得最短路

③對應(yīng)的最小費用增廣鏈?zhǔn)洽倭髁空{(diào)整量ε4=min{8,5,7,1}=1，總流量=原流量+新增流量=10+1=11；②最小費用增廣鏈的費用∑cij=4-2+3+2=7③總費用C2=原費用+新增費用

=48+7×1=55。由于總流量11已達(dá)到最大流量，故停止迭代，當(dāng)前的可行流圖即最大流圖。第4次迭代(7,1,7)vsvtv2v3v1(10,4,3)(8,1,8)(10,3,4)(4,2,4)(2,6,0)(5,2,4)6.-5最小費用最大流問題舉例—求最小費用-最大流問題求下圖中網(wǎng)絡(luò)從到的最小費用最大流，圖中弧上的數(shù)字為。vsv2v3v4v5vt6.-5最小費用最大流問題vsv2v3v4v5vt(0)求網(wǎng)絡(luò)的最大流量由前面計算知，。將0流作為初始可行流。①擴展費用網(wǎng)絡(luò)與原網(wǎng)絡(luò)相同(1)第一次迭代：②用Ford算法求最短增廣鏈，路線是vs—v3—v5—vt6.-5最小費用最大流問題vsv2v3v4v5vt③調(diào)整流量：在增廣鏈上有：在初始可行流的基礎(chǔ)上調(diào)整流量④得到新的可行流，刷新網(wǎng)絡(luò)圖（bij,cij,xij）6.-5最小費用最大流問題(2)第二次迭代①擴展費用網(wǎng)絡(luò)vsv2v3v4v5vt飽和弧—只能減小流量，單位費用減少3（1）流量還可增加3，單位費用6；（2）流量也可減小，當(dāng)前流量為6，每減單位流量，費用節(jié)省6。（1）流量還可增加4，單位費用1；（2）流量也可減小，當(dāng)前流量為6，每減單位流量，費用節(jié)省1。6.-5最小費用最大流問題②用Ford算法求最短增廣鏈，路線是vs—v2—v5—vtvsv2v3v4v5vt在原可行流基礎(chǔ)上調(diào)整流量④得到新的可行流，刷新網(wǎng)絡(luò)圖6.-5最小費用最大流問題(3)第三次迭代①擴展費用網(wǎng)絡(luò)vsv2v3v4v5vt②用Ford算法求最短增廣鏈，路線是vs—v2—v4—vt6.-5最小費用最大流問題③調(diào)整流量：在增廣鏈上有：在初始可行