1、第五節(jié) 最小費(fèi)用最大流流問(wèn)題,在實(shí)際的網(wǎng)絡(luò)系統(tǒng)中，當(dāng)涉及到有關(guān)流的問(wèn)題的時(shí)候，我們往往不僅僅考慮的是流量，還經(jīng)常要考慮費(fèi)用的問(wèn)題。比如一個(gè)鐵路系統(tǒng)的運(yùn)輸網(wǎng)絡(luò)流，即要考慮網(wǎng)絡(luò)流的貨運(yùn)量最大，又要考慮總費(fèi)用最小。最小費(fèi)用最大流問(wèn)題就是要解決這一類(lèi)問(wèn)題。,最小費(fèi)用最大流問(wèn)題提法: 設(shè)一個(gè)網(wǎng)絡(luò)G=（V，E，C），對(duì)于每一個(gè)弧(vi ,vj )E ,給定容量cij外，還給出單位流量的費(fèi)用dij 0 ，網(wǎng)絡(luò)記為G=（V，E，C，d）。網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題，是指要尋求一個(gè)最大流 f ，使流量w(f)=v,且流的總費(fèi)用 達(dá)到最小。,如果要求f為最大流，問(wèn)題轉(zhuǎn)化為最小費(fèi)用最大流。 其算法有：原始算法和對(duì)

2、偶算法。,定義24：已知網(wǎng)絡(luò)G=（V，E，C，d），f是G上的一個(gè)可行流，u為從vs 到vt的可增廣鏈，d(u)為鏈u的費(fèi)用。,vs,v1,v2,vt,3,5,1,4,d(u)=(3+1+4)-(5)=3,我們將 叫做這條增廣鏈的費(fèi)用。,實(shí)際上在一個(gè)網(wǎng)絡(luò)G中，當(dāng)沿可行流 f 的一條增廣鏈，以調(diào)整量=1改進(jìn)f ，得到的新可行流 f 的流量，有 w(f )=w(f )+1，而此時(shí)總費(fèi)用b(f )比b(f)增加了,結(jié)論：如果可行流 f 在流量為w(f )的所有可行流中的費(fèi)用最小，并且 是關(guān)于f 的所有增廣鏈中的費(fèi)用最小的增廣鏈，那么沿增廣鏈調(diào)整可行流f，得到的新可行流f ，也是流量為w(f )的所有

3、可行流中的最小費(fèi)用流。依次類(lèi)推，當(dāng) f 是最大流時(shí)，就是所要求的最小費(fèi)用最大流。,對(duì)偶算法基本思路： 零流f =0是流量為0的最小費(fèi)用流。一般地，尋求最小費(fèi)用流，總可以從零流f =0開(kāi)始。下面的問(wèn)題是：如果已知f 是流量為w(f)的最小費(fèi)用流，那么就要去尋找關(guān)于f 的最小費(fèi)用增廣鏈，用最大流的方法將f(0)調(diào)整到f(1)，使f(1)流量為w(f(0)+，且保證f(1)在w(f(0)+流量下的最小費(fèi)用流，不斷進(jìn)行到w(f(k)=v為止。,定理12：如果f是流量為w(f)的最小費(fèi)用流，u是關(guān)于f的從vs到vt的一條最小費(fèi)用可增廣鏈，則f經(jīng)過(guò)u調(diào)整流量得到新可行流f(f=fu),一定是流量為w(f)

4、+可行流中的最小費(fèi)用流。,定義25：網(wǎng)絡(luò)G=（V，E，C，d），f是G上的一個(gè)可行流，保持原網(wǎng)絡(luò)各點(diǎn)，每一條邊 ( vi , vj )用兩條方向相反的邊（vi , vj）和(vj , vi)代替，各邊的權(quán)Lij為：,并且將權(quán)為+的邊去掉。,1、邊（vi , vj） E,2、邊（ vj , vi ）為原圖G中（vi,vj）的反向邊,這樣，在網(wǎng)絡(luò)G中尋找關(guān)于f 的最小費(fèi)用增廣鏈就等于價(jià)于在長(zhǎng)度網(wǎng)絡(luò)L(f )中尋求從vs 到vt 的最短路。 對(duì)偶算法基本步驟： （1）、取零流f (0) =0. （2）、如果在第K-1步得到最小費(fèi)用流f (K-1),流量w(f(k)v,則構(gòu)造長(zhǎng)度網(wǎng)絡(luò)L(f (k-1)

5、。 （3）、 在長(zhǎng)度網(wǎng)絡(luò)L(f (k-1)中，尋求從vs到vt的最短路。如果不存在最短路，則f (k-1)就是最小費(fèi)用最大流。如果存在最短路，則在原網(wǎng)絡(luò)G中得到相對(duì)應(yīng)的增廣鏈。,（4）、在G中與這條最短路相應(yīng)的可增廣鏈上，對(duì)f (k1)進(jìn)行調(diào)整， f(k) = f(k)u,取調(diào)整量,令：,得到一個(gè)新的可行流f(k)，其流量為w(f(k-1)+; 如果w(f(k-1)+=v，則停止；否則令f(k)代替f(k-1)返回2 。,例 求圖所示網(wǎng)絡(luò)中的流量為10的最小費(fèi)用流，弧旁的權(quán)是（ cij , dij ）.,解：（1）取初始可行流為零流f (0)=0,構(gòu)造賦權(quán)有向圖L(f(0),用Dijkstra

6、求出從vs到vt的最短路(vs ,v2 ,v1 ,vt),如圖b 中虛線(xiàn)所示。,圖 b,v1,vs,v2,v3,vt,f (0) =0,（2）在原網(wǎng)絡(luò)G中，與這條最短路相對(duì)應(yīng)的增廣鏈為=（vs ,v2 ,v1 ,vt ）。 （3）在上對(duì)f (0)=0進(jìn)行調(diào)整， =min8,5,7=5，得到新可行流f (1)，如圖b所示。,按照以上的算法，依次類(lèi)推，可以得到f (1)，f (2)，f( 3)，f (4)，流量分別為5，7，10，11，并且分別構(gòu)造相對(duì)應(yīng)的賦權(quán)有向圖L( f(1 ) , L(f (2) ) , L(f(3),L(f(4)。 由于在L(f(4)中已經(jīng)不存在從vs到vt的最短路，因此，可行流f (4)，v(f(1)=11是最小費(fèi)用最大流。,(5),(0),(0),(0),(5),(0),(5),圖 c,f(1),w( f (1)=5 d( f (1)=5*1+5*2+5*3,v1,vs,v2,v2,vt,L(f (1),圖 d,最短路：vs-v1-vt,L( f