第三节最大流问题

1、精品课程运筹学,第三节 最大流问题,3.1 基本概念与定理,3.2 求解网络最大流的方法（标号法）,精品课程运筹学,第三节 最大流问题,流量问题在实际中是一种常见的问题。如公路系统中有车辆流量问题，供电系统中有电流量问题等等。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。,精品课程运筹学,3.1 基本概念与定理 设cij为弧（i，j）的容量，fij为弧（i，j）的流量。容量是弧（i，j）单位时间内的最大通过能力，流量是弧（i，j）单位时间内的实际通过量，流量的集合f=fij称为网络的流。发点到收点的总流量记为v=v(f)。 设D=(V,A)是一有

2、向图且对任意E均有容量cij =（vi，vj），记C=cij（vi，vj）A,此外,精品课程运筹学,D中只有一个源vs和汇vt( 即D中与vs相关联的弧只能以 vs为起点，与vt相关联的弧只能以 vt为终点)，则称D=(V,A,C, vs,vt)为一网络。 例6.3.1 图6-3-1给出了一张网络，其中：vs为源，vt为汇，弧旁的数字为该段弧的容量cij与流量fij，则显然有0fij cij 。,精品课程运筹学,最大流问题可以建立如下形式的线性规划数学模型。图6-3-1最大流问题的线性规划数学模型为 max v=fs1+fs2 所有弧(i,j) 由线性规划理论知，满足式上式的约束条件的解fij

3、称为可行解，在最大流问题中称为可行流。,精品课程运筹学,可行流满足下列三个条件： 条件（2）和条件（3）也称为流量守恒条件。,精品课程运筹学,在图D中，从发点到收点的一条路线称为链，从发点到收点的方向规定为链的方向。与链的方向相同的弧称为前向弧，前向弧集合记为u+ ，与链的方向相反的弧称为后向弧，后向弧集合记为u-。 设f是一个可行流，如果存在一条从发点vs到收点vt到的链u满足： （1）所有前向弧上fijcij (2)所有后向弧上fij0 则称链u为增广链.,精品课程运筹学,设S,TV,ST=,vsS,vtT则称（S，T）=（vi，vj）viS,vjT为图D的一个割集；称C（S，T）= 为割

4、集（S，T）的容量。 显然对任意可行流f及任意割集（S，T）总有V(f)=C(S,T).故有某个可行流f*及某一割集（S*，T*）使得V(f*)= C（S*，T*），则f*为D的最大流，（S*，T*）为最小容量割集。 定理6.3.1 图D上的可行流f*是最大流的充要条件是D上不存在关于f*的增广链。,精品课程运筹学,3.2 求解网络最大流的方法（标号法） 标号法是一种图上迭代计算方法，该算法首先给出一个初始可行流，通过标号找出一条增广链，然后调整增广链上的流量，得到更大的流量。再用标号找出一条新的增广链，再调整直到标号过程不能进行下去为止，这时的可行流就是最大流。,精品课程运筹学,标号法步骤如

5、下： 第一步 找出一个初始可行流fij(0),例如所有弧的流量fij(0) =0. 第二步 对点进行标号找出一条增广链。 （1） 起点标号（） （2）选一个点vi已标号且另一端未标号的弧沿着某条链向收点检查 （a）如果弧是前向弧且有fijcij，则vj标号 j=cijfij （b）如果弧是后向弧且有fij0，则vj标号j=fij,精品课程运筹学,当收点已得到标号时，说明已找到增广链，依据v的标号反向追踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束 第三步 调整流量 (1) 求增广链上点的vi标号的最小值，得到调整量号 = (2) 调整流量,精品课程运筹学,fij+ （vi，vj）u+ f1= fij （vi，vj)u- fij （vi，vj ) u 得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止。,精品课程运筹学,例6.3.2用标号法求网络最大流（图6-3-1），弧旁数字为（cij ，fij(0)）。 解 （1） 标号过程。见图6-3-2。 （2） 增广链为vs，v1，v2，v3，vt （注意（v2，v1），（v3，v2）u- ）。 （3）调整量=2调整后得图6-3-3。 （4）