《运筹学：第2章 图与网络分析 第4节 最大流》由会员分享，可在线阅读，更多相关《运筹学：第2章 图与网络分析 第4节 最大流（30页珍藏版）》请在金锄头文库上搜索。
1、 第四节 最大流问题例：下图为v1到v6的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从v1到v6的产品数量最多1、一般提法设有网络G=（V，E，C），其中C=cij，cij为弧（vi ,vj）上的容量，现在上要通过一个流f=fij， fij为弧（vi ,vj）上的流量问题：如何安排fij，可使网络上的总流量最大。称满足约束条件的流f为可行流：可行流中 fijcij 的弧叫做饱和弧，fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧，fij0 的弧叫做零流弧。（2）平衡条件：对于发点vs，有对于收点vt ，有对于中间点，有（1）容量限制条件：对于每一条弧（vi ,vj）E 有
2、0 fij cij 。 、最大流问题的模型可行流中: fijcij 的弧叫做饱和弧，fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧，fij0 的弧叫做零流弧。 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1) 图中 为零流弧，其余为非零流弧。3、f为一个可行流，若u为从vs到vt的一条链，给u定向为从vs到vt。 u上的弧：凡与u方向相同的称为正向弧；凡与u方向相反的称为反向弧；其集合分别用u+和u-表示。f 是一个可行流，如果满足： 则称 u为从vs到vt 的关于f 的一条增广链。 推论 可行流f 是最大流的充
3、分必要条件是： 即+中的每一条弧都是非饱和弧即-中的每一条弧都是非零流弧不存在从vs到vt 的关于f 的一条可增广链。 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)是一个可增广链显然图中可增广链不止一条 4、容量网络D =（V，A，C），vs为始点，vt为终点。如果把V分成两个非空集合 使 ，则所有始点属于 ，而终点属于 的弧的集合，称为D的截集,记作 。截集 中所有弧的容量之和，称为这个截集的截量，记为 。 vsv1v2v4v3vt374556378 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5
4、(2)5 (0)4 (2)4 (1)9 (5)10 (1)设 ，则截集为截量为24 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)设 ，则截集为截量为20流量与截量的关系任一可行流的流量都不会超过任一截集的截量。 定理 最大流-最小截定理 任何一个网络G中，从vs到vt的最大流的流量等于最小截量。例：如图所示的网络中，弧旁数字为（ cij ，fij ） (1)确定所有的截集 (2)求最小截集的流量 (3)证明图中的流为最大流例：如图所示的网络中，弧旁数字为（ cij ，fij ） (1) 所有的截集例：如图所示的网络中
5、，弧旁数字为（ cij ，fij ） (2)最小截量 (3) 是最大流三、 求最大流的标号法理论依据：可行流是最大流不存在关于的增广链思路：从始点开始标号，寻找是否存在增广链。给vj标号为j, vi，其中j为调整量， vi为前一结点。求最大流的标号法 标号过程：1 给vs 标号（+，vs ），选与vs关联的流出未饱和弧（vs，vj ），给vj标号j, vs，其中j=csj-fsj。2 把节点集V分成VA ：已标号点集 VB ：未标号点集3考虑所有这样的弧(vi ，vj) 或(vj，vi ) ，其中 ，若该弧为（1）流出未饱弧，那么给vj标号(j, vi) ，其中： j=cij-fij（2）流入
6、非零弧，那么给vj标号(j, -vi) ，其中： j=fij 4重复步骤2，3，直到vt被标号或标号过程无法进行下去，则标号结束。(1) 若vt被标号，则存在一条可增广链，转调整过程；(2)若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流，此时的截集为最小截。调整过程取1令 2去掉所有标号，回到第1步，对可行流重新标号。vsv5v2v4v1v3v6vt(3 , 3)(4 ,2)(2 , 2)(2 , 2)(5 , 2)(3 , 0)(5 , 4)(3 , 3)(4 , 2)(3 , 2)(5 ,5)+ ,vs2,vs3,v21,vs3,-v53,v12,v4vsv5v2v4v1v
7、3v6vt(3 , 3)(4 ,2)(2 , 2)(2 , 2)(5 , 2)(3 , 0)(5 , 4)(3 , 3)(4 , 2)(3 , 2)(5 ,5)+ , vs2,vs3,v21,vs3,-v52,v12,v4vsv5v2v4v1v3v6vt(3 , 3)(4 ,2)(2 , 2)(2 , 2)(5 , 2)(3 , 0)(5 , 4)(3 , 3)(4 , 2)(3 , 2)(5 ,5)+,vs2,vs3,v21,vs3,-v53,v12,v4+2+2+2+2-2vsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(
8、5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5)vsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5)+ ,vs1,vsvsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5)+ , vs1,vsvsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4
9、)(3 , 3)(4 , 4)(3 , 2)(5 ,5)+ ,vs1,vsvsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5)+ ,vs1,vsvsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5) ,+ +vs,1已经标号点集合：未标号点集合：截集为：截量为： 求下图所示网络中的最大流，弧旁数为(1 ,1)v2v1v4v3vsvt(3
10、 , 3)(5 , 1)(1 , 1)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,1)+ ,vs 1,-v14,vs 1,-v2 1,v21, v3 (1 ,1)v2v1v4v3vsvt(3 , 3)(5 , 1)(1 , 1)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,1)+ ,vs 1,-v14, vs1, -v2 1 , v22, v3 (1 ,0v2v1v4v3vsvt(3 , 3)(5 , 2)(1 , 0)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,2)(1 ,0)v2v1v4v3vsvt(3 , 3)(5 , 2)(1 , 0)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,2)+ , vs3,vs 当前的可行流为最大流最小截集
