算法创新与实践论文

最大流问题的算法及其应用

目录

1 绪论.............................................................. 1 2 最大流问题简述.................................................... 2 3 最大流问题的算法.................................................. 3

3.1 割集矩阵算法................................................. 3 3.2 图单纯形算法................................................. 3 3.3 表格算法..................................................... 4 3.4 数值算法..................................................... 5 3.5“构造式”算法................................................ 6 3.6 一种改进算法（断路法）....................................... 7 4 最大流问题的应用.................................................. 8

4.1 实例1 求网络图1 的最大流.................................... 8 4.2 实例2 求网络图2 的最大流.................................... 9 5 结论............................................................. 10 参考文献........................................................... 11

1

算法创新与实践论文

1 绪论

最大流问题是运筹学的一个重要分支，是指在满足容量限制条件和中间点平衡条件的要求下求取流量值达到最大的可行流的一类优化问题。 网络最大流问题的算法是一个传统的研究课题。 早在20世纪50~70年代，许多学者就提出了很多算法，目前许多方法被广泛应用于实际问题的解决中。 基于实际问题的需求及网络最大流算法的不断发展，本文对最大流问题的算法进行了研究，介绍了最大流问题的六种算法：割集矩阵算法、图单纯形算法、表格算法、数值算法,“构造式”算法以及一种改进算法（断路法）

1

算法创新与实践论文

2 最大流问题简述

给定一个网络图D=（V，A），设???? 为D 的一个点集，若对于????中的每一个顶点 ????都是D 中弧的发点，称????为D 的发点集；????为D 的另一个点集，若对于????中的每一个顶点????都是D 中弧的收点，称????为D 的收点集；M 为D 的一个点集，对于M 中的任一点????，既是D 中一些弧的发点，又是D 中一些弧的收点，称M 为D 中间点。D 中的每一条弧??????= ????，???? 都对应一个数C（??????），简记为??????，称为弧??????的容量。在运输网络中，C= ?????? ??×??为D 的容量矩阵，?????? 表示从顶点i 到顶点j 的直接运输通过能力。当i=j 时，规定??????=+∞。当i≠j 时，如果不存在弧??????=（i，j），规定??????=0。B= ?????? ??×?? 为D 的费用矩阵，?????? =b（i，j）表示从顶点i 到顶点j 直接运输单位流量的费用。当i=j 时，规定??????=0；当i≠j 时，如果不存在??????=（i，j），则规定??????=+∞。在网络图中，把通过弧?????? 的运量记为??????，称为弧??????上的流量。显然，0??????????????。网络上流量的集合f={??????}称为网络上的流，当{??????}满足下列条件时：

(1)0??????????????；

(2) 对于中间点????,有 ????????? ????????=0； ????????表示由???? 流出的流量和， ????????表示流入????的流量和，即流出量等于流入量；

(3)对于发点??1，记 ????1??? ??????1=??；即用V表示??1的净发出量；那么，对于收点????，则有 ????????? ????????=???，即????的净收量等于??1的净发出量。

则称f 为一可行流，此时V=V ?? 称为可行流的流量。任意网络中，可行流总是存在的。网络上最大流的问题，就是要在给定的网络上，求一个可行流f={??????}，使流量V ?? 取得最大值。

2

算法创新与实践论文

3 最大流问题的算法

3.1 割集矩阵算法

在一个网络图D 中，假设D 的总流量V ?? =1，每条弧（????，???? ）上的流量为?????? 0????????1 ，用矩阵运算来表示该算法：

矩阵的列数为网络图中边的个数再加1（方程组的常数列），矩阵的行数为中间点的个数加1，矩阵的元素为方程中变量（各弧的流量）的系数及方程的常数项，这些数只能是0，1，-1。割集流量关系矩阵中对于变量的系数含义为，若 ??????对应的系数为1，就是对应割集中弧（????，???? ）是从??1流向??1，若系数为-1， 对应割集中弧（????，????）是从??1流向??1若系数是0，则对应割集中弧（????，???? ）是 ???? 和??1无关联；对于常数项列，数1 对应的网络图中的割集，数0 对应的不是网络图中的割集。因此求割集就是对割集流量关系矩阵进行行运算，生成网络割 矩阵。由于在矩阵中（常数项列除外）数字1 所对应的为割集从??1流向??1 的弧， 数字-1 所对应的为割集从??1 流向??1 的弧因而割容量就是网络割矩阵中每行数字1 所对应的弧的容量之和，然后比较所有割容量的大小，最小的一个即为最小割容量，因而也就是我们所求的网络最大流。

3.2 图单纯形算法

求解网络最大流的图单纯形算法步骤如下：

（S1）用广探法寻找正向增广路，建立初始饱和流解。

（1.0）（开始）将始点s 记为“已标号未检查”，s 标号为（-1，∞）； （1.1）（选检查点）在已标号未检查点中选取最早得到标号的顶点 ????，转（1.2）；如果所有标号顶点都已检查，转（1.4）；

（1.2）（检查与标号）考虑???? 的一切出弧（????，????），如果???? 已标号，什么

也不做；否则对????进行标号。如果???? 的标号为 ??，???? ，则当??????

????=min?[????，?????????????]，标????为[i，????]且将????记为“已标号未检查”。如果????=t 则转

3