运筹学课件4.6 最大流问题.ppt

《运筹学课件4.6 最大流问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四节最大流问题网络流的基本概念求解网络最大流的基本原理寻找网络最大流的标号法确定网络中最大流的方法一、网络流的基本概念流量与容量流量：表示某时间内通过弧（vivj）的物质数量，记为fij。网络中的总流量用v(f)表示。容量：弧的最大允许通过量，一般用cij表示。一、网络流的基本概念可行流：节点和边的限制条件1)容量限制条件：对于每一个弧{vivj}∈A，A为弧集，0≤fij≤cij2）节点限制条件始点vs终点vs中间顶点i一、网络流的基本概念饱和弧和非饱和弧正向弧：与链的走向一致的弧。反向弧：与链的走向相反的

2、弧。一、网络流的基本概念增广链：对于一可行流，网络的一条链满足可增加的流量：二、求解网络最大流的基本原理数学模型二、求解网络最大流的基本原理给出一初始可行流，例如。寻找增广链，若存在，则通过该增广链调整、增加网络流。若不存在增广链，则网络流不可再增加。求得最大流。定理：可行流f为最大流的充分必要条件是当且仅当网络不存在增广链。三、寻找网络最大流的标号法Ford-Fulkson标号算法，给每个节点以一对标号，第一个标号表示箭尾节点，第二个标号表示可调整量，若终点有了标号，则找到一条增广链。否则不存在增广链。标号过

3、程中，从任意顶点i出发都要确定标号的方向。根据增广链的定义，有下面两种情况：1）从已标号的顶点vi出发的弧是正向弧到顶点vj为止的增广链可以增加流量的大小是：2）从已标号的顶点vi出发的弧是反向弧三、寻找网络最大流的标号法调整过程：在增广链上，正向弧加上调整量，反向弧减去调整量。经过调整网络流v(f)增加一个调整量：例4-2：第一次迭代第二次迭代第三次迭代：最优解四、确定网络中最大流的方法最大流时始节点的净流出量最大流时终节点的净流入量最小割集的容量割集：某连通图G上的一个边的集合。割集容量：指割集中所有边的容

4、量之和。最小割集：割集中容量最小的割集。最小割集最大流定理：网络最大流等于所有割集中的最小割量。标号法求得最小割集一个简单的例子再看例4-2习题第一版：P.266，习题4，图9-5（1）、（2）。第二版：P.285，习题7，图9-5（1）、（2）。