网络最大流的图单纯形解法.doc

Ξ 网络最大流的图单纯形解法 宁宣熙 (南京航空航天大学工商学院 南京, 210016) 摘要 提出网络饱和流的概念, 重新定义了网络最大流问题, 并提出了求解最大流的图单纯形算 法。该方法避免了 2F 算法的缺点, 其计算复杂性为O (2m n )。 关键词: 图论; 网络流; 最大流 中图分类号: O 157. 5 求解最大流的 2F 算法是 1957 年由 Fo rd 和 F u lk e r so n 提出的, 至今已有近 40 年的历 史。由于该算法存在着因增广链选取不当而造成计算复杂性问题, 不少学者又提出了很多改 进算法。这些算法虽然解决了 2F 算法中的缺陷, 但也增加了计算量。以典型的D in ic 最短路 算法来说1 , 其计算复杂性为O (n 2m ) (式中 n 为网络的顶点数, m 为弧数)。 作者在研究网络的堵塞流理论2, 3 中, 提出了网络饱和流的概念, 并发现网络最大流是 饱和流的一个特例, 因而重新定义了网络最大流问题, 并提出了求解最大流的图单纯形算 法。 该算法从根本上避免了 2F 算法的缺点, 使计算复杂性达到O (2m n )。 1 最大流问题的重新定义 定义 1 网络中从始点至终点的一条全部由正向弧构成的路称为正向路。 当正向路上 每条弧中的流量 f ij 小于其容量 ci j 时, 则称其为正向增广路。 定义 2 当网络中不存在对于某可行流 Ν的正向增广路时, 则称可行流 Ν为网络的饱 和流。如图 1 (a ) 和图 1 (b ) 中的流动为饱和流, 而图 1 (c) 中的流动为非饱和流, 因为在 s2A 2t 路上还有可能增加两个单位流量。 很显然, 经典图论中的最大流也是一种饱和流, 而且是网络中流量最大的饱和流。 定义 3 网络中流量最大的饱和流称为网络最大流。 假设通过网络的流量为 F , 根据饱和流的定义可以把最大流问题写成下面的形式 目标函数: m axF Ξ 国家自然科学基金资助项目。  图 1 饱和流和非饱和流 (弧旁数字为 f i j ?ci j )  约束条件: (1) 可行流条件 f i j ≤ci j ∑f j i - ∑f i j = 0  (2) 饱和流条件 在始点至终点的每条正向路上至少有某一条弧(u , v ) 满足 f uv = cuv。 如果不考虑饱和流条件, 那么上述问题就是一个典型的线性规划问题, 其可行域为凸 域, 基本可行解的个数是有限的。 因为饱和流的约束条件是线性的, 而且在可行流约束条件 之内, 其基本可行解的个数也是有限的。在有限个饱和流解集合内找出最大值正是组合优化 问题。因为饱和流约束条件不是固定的一组, 故它是一种具有非固定线性约束条件的特殊线 性规划问题, 因此不可能用线性代数进行迭代的经典单纯形算法, 现提出下面在图上进行的 单纯形步骤去求解最大流问题。 其基本步骤是: ①首先建立网络的初始饱和流解; ②寻找给 定的饱和流解的改进解 (即流量更大的饱和流) ; ③算法停止规则: 当网络中不存在改进的饱 和流解时, 所得的解即为最优解。 因为整个迭代步骤是在图上运用图论的方法进行的, 故称 其为图单纯形解法。 2 最大流问题的图单纯形算法 实施图单纯形算法的具体方法如下: (1) 运用标号法寻找网络的正向路, 建立网络的初始饱和流解。 (2) 寻找饱和流的改进解, 方法是用正向改进链。 定义 4 网络中从始点至终点由正向弧和至少一条反向弧共同构成的链称为正向链。 当正向链中的正向弧都不是饱和弧, 反向弧都不是零流弧时, 则该正向链称为正向改进链。 这里应当提出的是, 在 2F 算法中定义的增广链 ( 或增广路) 实际上是包括本文定义的 正向增广路和正向改进链两部分。 定理 1 对于饱和流 Ν, 如果存在一条正向改进链, 则沿此正向改进链增流 ? Ν后的新当 前流仍然是饱和流。 证明 对于饱和流 Ν, 网络中从始点 s 至终点 t 的每条正向路上至少有一条弧是饱和 弧。这些饱和弧在网络中至少形成一个正向饱和截割组 K = (v s , v t ) ∪(v t , v s ) , 其中正向弧 a f ∈(v s , v t ) 都是饱和弧, 否则 Ν就不是饱和流。 如果对于 Ν存在正向改进链, 则该链通过饱和 截割组 K 的弧只能是其中流量不等于零的反向弧。沿此改进链增流 ? Ν后, 改进链上的反向 弧中流量减少或者变成零流弧, 但原饱和截割组 K 保持不变; 或者改进链上的正向弧成为 新的饱和弧, 形成新的正向饱和截割组 K ′。 因此在这几种可能情况下, 增流后的新当前流 Ν+ ? Ν仍然是饱和流。 与此同时, 也实现了正向饱和截割组的过渡与转移。