资源描述：
《运输网络最大流问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运输网络最大流问题本节内容的安排基本概念与基本定理寻求最大流的标号法一、引言1.应用背景在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题,控制系统中的信息流问题，常见的人流，物流，水流，气流，电流，现金流等。在一定条件下,求解给定系统的最大流量,就是网络最大流问题.2.问题描述连通网络G(V,A)中有m个节点,n条弧,弧eij上的流量上界为cij,求从起始节点vs到终点vt的最大流量的问题就是最大流问题。引例：如下输水网络，南水北调工程，从v1到v6送水，弧
2、旁数字为管道容量，问应当如何输水使得流量最大？v2v451v1v6v3v5108533171131、网络与流设一个赋权有向图D=（V,A）,在V-----图中的节点，中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于A-----图中的弧，D中的每一个弧（vi,vj）∈A,都有一个非负数cij,叫做弧的容量---cij。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，A，C）。弧的容量：是对网络上的每条弧(vi,vj)都给出一个最大的通过能力，记为c(vi,vj)或简写为cij。二、基本概念s
3、ts’t’对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收点,并将其分别与各发点、收点连起来（见图），就可以转换为只含一个发点和一个收点的网络。所以一般只研究具有一个发点和一个收点的网络流：加在网络各条弧上的一组负载量,即弧线上的流量f(vi,vj)：加在弧(vi,vj)上的负载量简记为fij，fij>=0.网络上的流：是指定义在弧集合上的一个函数f={f(vi,vj)},注意：弧的流量f(vi,vj)：表示弧(vi,vj)上每单位时间内的实际通过能力弧的容量c(vi,vj)：表示弧（vi,vj
4、)上每单位时间内的最大通过能力零流：网络上所有的fij=0例如下图表示的就是这个网络上的一个流（运输方案），每一个弧上的流量fij就是运输量。例如：f12=1,f13=2,f24=3等等。v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvtv3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt对于实际的网络系统上的流，有几个显著的特点：(1)发点的净流出量和收点的净流入量必相等。(2)每一个中间点的流入量与流出量的代数和等于零。(3)每
5、一个弧上的流量不能超过它的最大通过能力（即容量）称满足下列条件的流为可行流：（1）容量限制条件：对于每一个弧（vi,vj）∈A有0f(vi,vj)c(vi,vj)（简记为0fijcij）2、可行流与最大流（2）平衡条件：总流量v(f)=发点的净输出量v(f)=收点的净输入量-v(f)容量网络的可行流总是存在的，如当所有弧的流均取零，即对所有的i,j,有f(vi,vj)=0就是一个可行流可行流中fij＝cij的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。fij＞0的弧为非零流弧，fij＝0的弧叫做零流
6、弧。13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)图中谁是零流弧，谁是饱和弧？就是要求一个流{fij},使其流量v(f)达到最大,并且满足0fijcij网络的最大流:求网络的最大流，即是指满足容量限制条件和平衡条件的条件下，使v(f)值达到最大.容量网络D，若给μ定向为从vs到vt，图上的弧分为两类：凡与μ方向相同的称为前向弧，凡与μ方向相反的称为后向弧，其集合分别用μ+和μ-表示。链的方向：若µ是联结vs和vt的一条链，定义链的方向是从vs到vt。3
7、、增广链stf10f3>0增广链：一条链中的可行流，如果满足：中的每一条弧都是非饱和弧中的每一条弧都是非零流弧则称μ为从vs到vt的关于f的一条增广链。stf10f3>0v2v53-34-18-3v3v1v4v65-110-511-66-317-23-25-2µ=(v1,v2,v3,v4,v5,v6)µ+={(v1,v2),(v2,v3),(v3,v4),(v5,v6)}µ-={(v5,v4)}后向弧13(5)9(3)4(1)5(3)6(3)5(
8、2)5(2)5(0)4(2)4(1)9(5)10(1)是一个增广链显然图中增广链不止一条4、截集与截量我们在图中画一条线，使所有始点属于Vs，而终点属于Vt，v2v53(3)4（1）8(3）v3v1v4v65（1）10（5)11(66（3017(2)3（2）5（2）=(v1,v2,v3)V11=(v4,v5,v6)=(v1,v2,v3)V11=(v4,v5,v6)截集为所有被割断的弧线，黄色弧集：v
