運(yùn)籌學(xué) 最小費(fèi)用流問題

1、5,最小費(fèi)用流問題,已知容量網(wǎng)絡(luò),G,(V,E,C,每條邊,v,i,v,j,除了已給出,容量,c,ij,外,還給出了單位流量的,費(fèi)用,d,ij,0,記,G,V,E,C,d,求,G,的一個(gè)可行流,f,f,ij,使得流量,W,f,v,且總費(fèi)用最小,d,f,=,d,i,j,f,i,j,v,i,v,j,E,特別地,當(dāng)要求,f,為,最大流,時(shí),此問題即為,最小費(fèi)用最大流,問題,定義,已知網(wǎng)絡(luò),G,V,E,C,d,f,是,G,上的一個(gè),可行流,為從,v,s,到,v,t,的,關(guān)于,f,的,可增廣鏈,d,d i j,d i j,稱為,鏈,的費(fèi)用,圖中的可增廣鏈,中,邊上權(quán)為費(fèi)用,d,i j,v,s,v,1,v

2、,2,v,3,v,3,v,4,v,5,v,t,v,2,v,1,v,5,v,4,若,是從,v,s,到,v,t,所有可增廣鏈中費(fèi)用最小的鏈,4,v,s,v,t,v,5,v,4,v,3,v,1,v,2,1,7,6,5,3,鏈,的費(fèi)用,d,= (3+4+1+6),5+7) = 2,則稱,為,最小費(fèi)用增廣鏈,對(duì)偶算法的基本思路,先找一個(gè)流量為,W,f,0,v,的最小費(fèi)用流,f,0,再找從,v,s,到,v,t,可增廣鏈,且保證,f,1,是在,W,f,0,流量下的最小費(fèi)用流,用最大流法將,f,0,調(diào)整到,f,1,不斷進(jìn)行到,W,f,k,v,為止,使,f,1,流量為,W,f,0,在,G,中求關(guān)于,f,的,最小

3、費(fèi)用可增廣鏈,等價(jià)于,在長(zhǎng)度網(wǎng)絡(luò),L,f,中求,從,v,s,到,v,t,的,最短路,例,圖示運(yùn)輸網(wǎng)絡(luò),求流量,v,為,10,的最小費(fèi)用流,L,v,s,v,t,4,邊上括號(hào)為,c,i j,d,i j,b,L,f,0,1,v,s,v,t,v,3,v,1,v,2,1,3,6,2,4,2,c,f,1,7,5,v,s,v,t,v,3,v,1,v,2,8,5,10,0,2,0,5,5,10,0,0,0,1,1,1,d,L,f,1,v,s,v,t,v,3,v,1,v,2,10,3,2,6,2,10,4,2,2,1,L,v,s,v,t,4,W,f,1,5,d,f,1,= 5,1,5,2,5,1,20,7,1,

4、v,s,v,t,v,3,v,1,v,2,8,1,10,3,2,6,5,2,10,4,4,2,a,例,16,續(xù),7,e,f,2,v,s,v,t,v,3,v,1,v,2,0,2,0,5,2,0,2,5,L,v,s,v,t,6,W,f,2,7,d,f,2,4,2,5,1,5,2+7,1,30,f,3,即為所求,v,為,10,的,最小費(fèi)用流,4,1,f,L,f,2,v,s,v,t,v,3,v,1,v,2,3,6,2,2,1,1,4,2,7,g,f,3,v,s,v,t,v,3,v,1,v,2,3,0,5,3,8,W,f,3,10,v,d,f,3,2,4,8,1,5,2+3,3,3,2+7,1,30,7,

5、1,v,s,v,t,v,3,v,1,v,2,8,1,10,3,2,6,5,2,10,4,4,2,a,對(duì)偶算法基本步驟,取,零流,為,初始可行流,即,f,0,0,在長(zhǎng)度網(wǎng)絡(luò),L,f,k,1,中求從,v,s,到,v,t,的最短路,若不存在,否,則,令,f,k,代替,f,k,1,返回,此時(shí),f,k,的流量為,W,f,k,1,若,W,f,k,1,v,則,停,定理,若,f,是流量為,W,f,的最小費(fèi)用流,是關(guān)于,f,的從,若有,f,k,1,流量為,W,f,k,1,v,構(gòu)造,長(zhǎng)度網(wǎng)絡(luò),L,f,k-1,在,G,中與這條最短路相應(yīng)的,可增廣鏈,上,做,f,k,f,k,1,i j,其中,min,min,c,ij

6、,f,k,1,min,f,k,1,i j,最短路,則,f,k,1,已為最大流,不存在流量等于,v,的流,停止,否則,轉(zhuǎn),v,s,到,v,t,的一條最小費(fèi)用可增廣鏈,則,f,經(jīng)過,調(diào)整流量,得,到,新可行流,f,記為,f,f,一定是,流量為,W,f,的可行流中的,最小費(fèi)用流,定義,對(duì)網(wǎng)絡(luò),G,V,E,C,d,有可行流,f,保持原網(wǎng)絡(luò)各點(diǎn),1,當(dāng)邊,v,i,v,j,E,令,l,ij,d,ij,當(dāng),f,ij,c,ij,當(dāng),f,ij,0,其中,的意義是,這條邊,已飽和,不能再增大流量,否則,其中,的意義是此邊,流量已減少到,0,不能再減少,權(quán)為,2,當(dāng)邊,v,j,v,i,為原來,G,中邊,v,i,v,j,的反向邊,d,ij,當(dāng),f,ij,0,當(dāng),f,ij,0,令,l,ij,每條邊用兩條方向相反的有向邊代替,各邊的權(quán),l,ij,按如下,