资源描述:
《运筹学最小费用流问题.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称为链μ的费用。图中的可增广链μ中边上权为费
2、用dijμ+:{(vs,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、))=v为止。使f(1)流量为W(f(0))+θ,在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→v
4、t)=4W(f(1))=5d(f(1))=5×1+5×2+5×1=20(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=
5、vd(f(3))=2×4+8×1+5×2+3×3+3×2+7×1=30(7,1)vsvtv3v1v2(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、))7、=dij当fij0+∞当fij=0令lij=每条边用两条方向相反的有向边代替,各边的权lij按如下规则:要花费很高的代价,实际无法实现,因此权为+∞的边可从网络中去掉.)+∞的边也可以去掉.)这样得到的网络L(f)称为长度网络(将费用看成长度).作业阅读p160-166p1746.12(c).