运筹学 最小费用流问题

1、5,最小费用流问题,已知容量网络,G,(V,E,C,每条边,v,i,v,j,除了已给出,容量,c,ij,外,还给出了单位流量的,费用,d,ij,0,记,G,V,E,C,d,求,G,的一个可行流,f,f,ij,使得流量,W,f,v,且总费用最小,d,f,=,d,i,j,f,i,j,v,i,v,j,E,特别地,当要求,f,为,最大流,时,此问题即为,最小费用最大流,问题,定义,已知网络,G,V,E,C,d,f,是,G,上的一个,可行流,为从,v,s,到,v,t,的,关于,f,的,可增广链,d,d i j,d i j,称为,链,的费用,图中的可增广链,中,边上权为费用,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,所有可增广链中费用最小的链,4,v,s,v,t,v,5,v,4,v,3,v,1,v,2,1,7,6,5,3,链,的费用,d,= (3+4+1+6),5+7) = 2,则称,为,最小费用增广链,对偶算法的基本思路,先找一个流量为,W,f,0,v,的最小费用流,f,0,再找从,v,s,到,v,t,可增广链,且保证,f,1,是在,W,f,0,流量下的最小费用流,用最大流法将,f,0,调整到,f,1,不断进行到,W,f,k,v,为止,使,f,1,流量为,W,f,0,在,G,中求关于,f,的,最小

3、费用可增广链,等价于,在长度网络,L,f,中求,从,v,s,到,v,t,的,最短路,例,图示运输网络,求流量,v,为,10,的最小费用流,L,v,s,v,t,4,边上括号为,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,续,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,的,最小费用流,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,对偶算法基本步骤,取,零流,为,初始可行流,即,f,0,0,在长度网络,L,f,k,1,中求从,v,s,到,v,t,的最短路,若不存在,否,则,令,f,k,代替,f,k,1,返回,此时,f,k,的流量为,W,f,k,1,若,W,f,k,1,v,则,停,定理,若,f,是流量为,W,f,的最小费用流,是关于,f,的从,若有,f,k,1,流量为,W,f,k,1,v,构造,长度网络,L,f,k-1,在,G,中与这条最短路相应的,可增广链,上,做,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,的流,停止,否则,转,v,s,到,v,t,的一条最小费用可增广链,则,f,经过,调整流量,得,到,新可行流,f,记为,f,f,一定是,流量为,W,f,的可行流中的,最小费用流,定义,对网络,G,V,E,C,d,有可行流,f,保持原网络各点,1,当边,v,i,v,j,E,令,l,ij,d,ij,当,f,ij,c,ij,当,f,ij,0,其中,的意义是,这条边,已饱和,不能再增大流量,否则,其中,的意义是此边,流量已减少到,0,不能再减少,权为,2,当边,v,j,v,i,为原来,G,中边,v,i,v,j,的反向边,d,ij,当,f,ij,0,当,f,ij,0,令,l,ij,每条边用两条方向相反的有向边代替,各边的权,l,ij,按如下,