运筹学_最小费用流问题.ppt

《运筹学_最小费用流问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§5最小费用流问题已知容量网络G=(V,E,C),每条边(vi,vj)除了已给出容量cij外,还给出了单位流量的费用dij(≥0),记G=（V,E,C,d).求G的一个可行流f={fij},使得流量W(f)=v,且总费用最小.d(f)=∑dijfij(vi,vj)∈E特别地,当要求f为最大流时,此问题即为最小费用最大流问题。定义已知网络G=(V,E,C,d),f是G上的一个可行流,μμ+μ-为从vs到vt的(关于f的)可增广链,d(μ)=∑dij-∑dij称为链μ的费用。图中的可增广链μ中边上权为费用dijμ+:{(vs,

2、v1),(v2,v3),(v3,v4),(v5,vt),}μ-:{(v2,v1),(v5,v4)}若μ+是从vs到vt所有可增广链中费用最小的链,4vsvtv5v4v3v1v217653链μ的费用d(μ)=(3+4+1+6)-(5+7)=2则称μ+为最小费用增广链。对偶算法的基本思路:先找一个流量为W(f(0)

3、,在G中求关于f的最小费用可增广链等价于在长度网络L(f)中求从vs到vt的最短路.例图示运输网络,求流量v为10的最小费用流,L(vs→vt)=4边上括号为(cij,dij).(b)L(f(0))1vsvtv3v1v2136242(c)f(1)(7,5)vsvtv3v1v2(8,5)(10,0)(2,0)(5,5)(10,0)(0,0)-11-1(d)L(f(1))vsvtv3v1v2(10,3)(2,6)(－2)(10,4)(2,2)1L(vs→vt)=4W(f(1))=5d(f(1))=5×1+5×2+5×1=20(

4、7,1)vsvtv3v1v2(8,1)(10,3)(2,6)(5,2)(10,4)(4,2)(a)例16续7(e)f(2)vsvtv3v1v20(2,0)52(0,2)5L(vs→vt)=6W(f(2))=7d(f(2))=4×2+5×1+5×2+7×1=30f(3)即为所求v为10的最小费用流4-1(f)L(f(2))vsvtv3v1v236-221-1-427(g)f(3)vsvtv3v1v230538W(f(3))=10=vd(f(3))=2×4+8×1+5×2+3×3+3×2+7×1=30(7,1)vsvtv3v1

5、v2(8,1)(10,3)(2,6)(5,2)(10,4)(4,2)(a)对偶算法基本步骤:⑴取零流为初始可行流,即f(0)={0}.⑶在长度网络L(f(k-1))中求从vs到vt的最短路.若不存在否则令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))

6、中θ=min{min(cij-f(k-1)),minf(k-1)}μ-ij最短路,则f(k-1)已为最大流,不存在流量等于v的流,停止;否则转⑷.vs到vt的一条最小费用可增广链,则f经过μ调整流量θ得到新可行流f’(记为f’=fμθ),一定是流量为W(f)+θ的可行流中的最小费用流。定义对网络G=(V,E,C,d),有可行流f,保持原网络各点,1.当边(vi,vj)∈E,令lij=dij当fij

7、权为2.当边(vj,vi)为原来G中边(vi,vj)的反向边,-dij当fij>0+∞当fij=0令lij=每条边用两条方向相反的有向边代替,各边的权lij按如下规则：要花费很高的代价,实际无法实现,因此权为+∞的边可从网络中去掉.)+∞的边也可以去掉.)这样得到的网络L(f)称为长度网络(将费用看成长度).作业阅读p160-166p1746.12(c).