网络系统的最小费用最大流问题.ppt

《网络系统的最小费用最大流问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、网络中的最小费用最大流问题二、基本概念与基本定理三、寻求最大流的标号法四、最小费用最大流问题一、引言网络系统的最大流问题一、引言在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。网络系统的最大流问题图8.23是一个网络vtv3v2v1v4vs1735108611453Cij每一个弧旁边的权就是对应的容量（即最大通过能力）。要求指定一个运输方案，使得从vs到vt的货运量最大，这

2、是寻求网络系统的最大流问题。网络系统的最大流问题二、基本概念与基本定理定义8.5设一个赋权有向图D=（V,A）,在v中指定一个发点（或源点）vs和一个收点（或汇点）vt,其他的点叫做中间点。对于D中的每一个弧（vi,vj）∈A,都有一个权cij叫做弧的容量。我们把这样的图D叫做一个网络系统，简称网络，记做D=（V，A，C）。网络D上的流，是指定义在弧集合A上的一个函数f={f(vi,vj)}={fij}f(vi,vj)=fij叫做弧在(vi,vj)上的流量。网络系统的最大流问题v3v2v1v4vs（2）（3）（2）（5）（3）（3）

3、（6）（1）（1）（2）fij图8.24网络上的一个流（运输方案）每一个弧上的流量fij就是运输量例如fs1=5,fs2=3,f13=2等等vt网络系统的最大流问题网络系统上流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的流入量与流出量的代数和等于零；(3)每一个弧上的流量不能超过它的最大通过能力（即容量）。网络系统的最大流问题定义8.6网络上的一个流f叫做可行流，如果f满足以下条件（1）容量限制条件：对每一弧（vi,vj）∈A,有0fijcij.（2）平衡条件：对于发点vs，有∑fsj-∑fjs=v

4、(f)对于收点vt，有∑ftj-∑fjt=-v(f)对于中间点，有∑fij-∑fji=0式中v(f)叫做这个可行流的流量，即发点的净输出量（或收点的净输入量）网络系统的最大流问题任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。网络系统中最大流问题就是在给定的网络上寻求一个可行流f,使其流量v(f)达到最大值。设流f={fij}是网络D上的一个可行流，我们把D中fij=cij的弧叫做饱和弧，fij0的弧为非零流弧，fij=0的弧叫做零流弧。网络系统的最大流问题设μ

5、是网络D中连接发点νs和收点vt的一条链。定义链的方向是从vs到vt，于是链μ上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做μ+。二是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做μ-。在下图（图8.23与8.24合并图）中，(v4,v3)是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。v3v2v1v4vs（17,2）（3,3）（5,2）（10,5）（8,3）（6,3）（11,6）（4,1）（5,1）（3,2）fij如图，在链（vs,v1,v2,v3,v4,vt)中，μ+={(vs,v1),(v1,

6、v2),(v2,v3),(v4,vt)},μ-={(v4,v3)}.vt网络系统的最大流问题网络系统的最大流问题增广链，如果链μ满足以下条件：1．在弧（vi,vj）∈μ+上，有0≤fij

7、1,V1）叫做是分离vs和vt的截集。定义8.9设一个截集（V1,V1），将截集（V1,V1）中所有的弧的容量的和叫做截集的截量，记做c(V1,V1),亦即c(V1,V1)=∑cij,(vi,vj)∈(V1,V1)设图D=(V，A，C)，点集S,TV,S∩T=ф中，将起点在S，终点在T的所有弧构成的集合，记做（S，T）。网络系统的最大流问题下面的事实是显然的：一个网络D中，任何一个可行流f的流量v(f)都小于或等于这个网络中任何一个截集(V1,V1)的截量。并且，如果网络上的一个可行流f*和网络中的一个截集（V1*,V1*），满足

8、条件v*(f*)=c(V1*,V1*),那么f*一定是D上的最大流，而（V1*,V1*）一定是D的所有的截集中截量最小的一个（即最小截集）。网络系统的最大流问题定理8.8网络中的一个可行流f*是最大流的充要条件是不存在关于f*的增广链