资源描述：
《应用三：网络流问题培训讲学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、应用三：网络流问题把一种产品从产地通过铁路或公路网运往市场，交通网络中每一段的运输能力有一定限度，问如何安排，使得运输最快？这个问题在运输调度工作中是重要内容之一，同时也是运筹学许多问题的模型。产地市场中转站a中转站b中转站c中转站d44332224132基本概念定义1：称N=(V,E,c,X,Y)为一个网络，如果：（1）G=(V,E)是一个有向图；（2）c是E上的非负函数，称为容量函数，对每条边e，c(e)称为边e的容量（最大通过能力）；（3）X与Y是V的两个非空不交子集，分别称为G的发点集与收点集，
2、I=V(XUY)称为的中间点集。X的顶点称为发点或源，Y的顶点称为收点或汇，I的顶点称为中间点。若
3、X
4、>1，
5、Y
6、>1称为多源多汇网络；若
7、X
8、=1，
9、Y
10、=1称为单源单汇网络。下图所示就是一个网络流图：stabcd44332224132源点汇点容量中间点定义2：设网络N中任一条边e有流量f(e)（实际通过能力）,称集合f={f(e)}为网络N上的一个流.满足下述条件的流f称为可行流：①(容量限制条件)对每一边e,有0≤f(e)≤C(e);②(流量守衡条件)对于中间点v有流入该结点的流量和等于流出该
11、结点的流量和,其中：N+(v)表示v的所有出弧的集，N-(v)表示v的所有入弧的集。记f+(v)=流出点v的流量，f-(v)=流入点v的流量，则f+(v)=f-(v)stabcd(4,3)(4,3)(3,2)(3,0)(2,1)(2,2)(2,2)(4,4)(1,1)(3,2)(2,2)容量流量fat例：单源单汇网络和多元多汇网络。f(vi,vj)为弧(vi,vj)上的流量，简记为fij.如果f是可行流,则对收、发点vt、vs有∑fsi=∑fjt=Wf,即从vs点发出的物质总量=vt点输入的量.Wf称为
12、网络流f的总流量.上述概念可以这样来理解,如G是一个运输网络,则发点vs表示发送站,收点vt表示接收站,中间点vk表示中间转运站,可行流fij表示某条运输线上通过的运输量,容量Cij表示某条运输线能承担的最大运输量,Wf表示运输总量.可行流总是存在的.比如所有边的流量fij=0就是一个可行流(称为零流).定义3：设f是网络N的一个流，，则称f+(A)-f-(A)为流出A的净流量f-(A)-f+(A)为流入A的净流量。注：（1）流入、流出任何中间点的净流量为0；（2）流出发点集的净流量等于流入收点集的净流
13、量。定义4：设f是网络N的一个流，则f的流的价值Valf定义为即流的价值是发点集的流出量，也是收点集的流入量。即总流量=发点的净输出量=收点的净输入量注：任何一个多源多汇网络N=(V,E,c,X,Y)都等价与一个单源单汇网络N’=(V’,E’,c,X’,Y’)。在解决实际问题时，常把多源多汇网络转化为单源单汇网络。（1）,s,t分别是N’的发点与收点；（2）（3）sts’t’对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收点,并将其分别与各发点、收点连起来（见图），就可以转换为只含一个发点
14、和一个收点的网络。所以一般只研究具有一个发点和一个收点的网络总结：对于实际的网络系统上的流，有几个显著的特点：(1)发点的净流出量和收点的净流入量必相等。(2)每一个中间点的流入量与流出量的代数和等于零。(3)每一个弧上的流量不能超过它的最大通过能力（即容量）vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)最大流问题所谓最大流问题就是在容量网络中寻找流量最大的可行流。最大流问题实际上是一个线性规划问题。但利用它与图的密切关系，可以利用图直观简便地求解。最
15、大流问题最大流：设N=(V,E,c,X,Y)是一个网络，f是一个流，若不存在流f’，使Valf’>Valf,则称f为的最大流。割：给定网络N=(V,E,c,X,Y)，若点集V被划分为两个非空互补集合A和A，使s∈A，t∈A，记以A中的点为始点，A中的点为终点的弧集(A,A)称为（分离s和t的）割集（又称截集）。割集的容量：是割集中各弧的容量之和，记作：cap(A,A)最小割：容量最小的割割集的意义：若把某一割集的弧从网络中丢去，则从vs到vt便不存路，即割集是从vs到vt的必经之道！割集的容量为9+9=
16、18割集KKvsv1v3vtv2v48(8)7(5)9(4)5(5)6(1)2(0)5(4)10(8)9(9)这里(v3,v2)不属于此割集考虑割线的不同画法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)割集割集容量由于有限网络的割集只有有限多个，则割集容量的集合是有限的实数集合，令称割集容量为C0的割集为D的最小割集。（瓶颈）最大流与最小割的关系：（v1，v2）是饱和的2、如果0≤fij
