运筹学最小费用流问题.pptx

5最小最小费用流用流问题已知容量网络已知容量网络G=(V,E,C),每条边每条边(vi,vj)除了已给出除了已给出容量容量cij外外,还给出了单位流量的还给出了单位流量的费用费用dij(0),记记G=（V,E,C,d).求求G的一个可行流的一个可行流 f=fij,使得流量使得流量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 jd i j 称为链链的费用的费用。图中的可增广中的可增广链中中 边上权为费用d i j +:(vs,v1),(v2,v3),(v3,v4),(v5,vt),-:(v2,v1),(v5,v4)若若+是从是从vs到到vt所有可增广链中费用最小的链所有可增广链中费用最小的链,4v sv tv5v4v3v1v217653链 的费用 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 的最小费用可增广链最小费用可增广链等价于等价于在长度网络L(f)中求 从从 v s 到到 v t 的的最短路最短路.例例 图示运示运输网网络,求流量求流量v为1010的最小的最小费用流用流,L(vs vt)=4边上括号为边上括号为 (c i j,d i j).(b)L(f (0)1vsvtv3v1v2136242(c)f (1)(7,5)vsvtv3v1v2(85)(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)=51+52+51=20(7,1)vsvtv3v1v2(8,1)(10,3)(2,6)(5,2)(10,4)(4,2)(a)例例1616续7(e)f (2)vsvtv3v1v20(2,0)52(0,2)5L(vs vt)=6W(f (2)=7d(f(2)=42+51+52+71=30f(3)即为所求即为所求v为为10的的最小费用流最小费用流4-1(f)L(f (2)vsvtv3v1v236-221-1-427(g)f (3)vsvtv3v1v230538W(f(3)=10=vd(f(3)=24+81+52+33+32+71=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)v,构造长度网络长度网络L(f(k-1).在G中与这条最短路相应的可增广链可增广链上,做 f(k)=f(k-1)+i j其中=minmin(cij-f(k-1),min f(k-1)-i j最短路,则 f(k-1)已为最大流,不存在流量等于v的流,停止;否则转转.vs到vt的一条最小费用可增广链,则f 经过调整流量 得到新可行流新可行流 f(记为 f =f),一定是一定是流量为W(f)+的可行流中的最小费用流最小费用流。定义对网络G=(V,E,C,d),有可行流 f,保持原网络各点,1.当边(vi,vj)E,令令 lij=dij 当 f ij 0+当 f ij=0令令 lij=每条边用两条方向相反的有向边代替,各边的权lij按如下规则：要花费很高的代价,实际无法实现,因此权为+的边可从网络中去掉.)+的边也可以去掉.)这样得到的网络 L(f)称为长度网络长度网络(将费用看成长度).作 业阅读阅读 p160-166 p174 6.12(c).