求解上容量无限的双容量网络最小流问题

求解上容量无限的双容量网络最小流问题

王丽1王建2

王丽1王建2（1.华北电力大学经济与管理学院,北京1022062；2.河北大学艺术学院,河北保定071000)

中图分类号：O157.5文献标识码：A文章编号：1003-2738（2012）03-0000-01

摘要：双容量网络的最小流问题是经典的网络流问题之一。针对该问题的上容量无限的情况，分析了问题的求解原理，提出了关键截集的概念，得出网络最小流与关键截集互为对偶。

关键词：运筹学；最小流问题；双容量网络；网络流

一、引言

网络流问题是网络优化的核心问题之一，许多网络优化问题都可以归结为各类网络流问题[1]，其中最经典的是网络最大流问题，得到了诸多理论成果[2-4]。相对应的是网络最小流问题，研究相对较少，但其同样具有重要的应用价值。对于双容量网络的最小流问题（各弧的下容量大于零，并且上容量有限），通常的思路和方法是，先求一个初始可行流，再将其调整为最小可行流[1]。上容量无限的双容量网络最小流问题是特殊的网络流问题，因此可以考虑用特殊的方法求解。

二、问题描述

三、求解思路和原理

根据节2中“上容量无限的双容量网络最小流问题”的描述，基本求解思路是，先给出一个可行

流，再对其进行调整，使其减小为最小可行流。因此，求解该问题的关键点是：（1）如何求得初始可行流；（2）如何调整初始流，在保证流可行的前提下使流量减小；（3）如何求得决定最小流量的弧集。下面分别给出处理上述关键点的原理。

1.求初始可行流。

在网络流问题中，由于零流是最容易得到且最简单的流，因此常将零流作为初始流。其原理如下：

（1）求解所需的流量并非一定要从可行流入手，目标流与初始流的状态无关。

2.调整可行流。

将零流调整为初始可行流后，接下来就需将该流调整为最小可行流，调整原理如下：

（1）将初始可行流调整为最小流，实际就是在保证流可行的前提下，使流量最大程度地减小。

3.最小流与截集的关系。

（1）最大截集与最小截集。

而对于上容量无限的双容量网络来说，各弧的流量不能小于下容量，因此存在一个最小的可行网络流。将截集中所有弧的下容量之和称为该截集的截量，其中截量最大和最小的截集也称为最大截集和最小截集。显然，网络最小可行流与最小截集之间没有必然联系，但是网络最大截问题与上述“下容量为零的双容量网络最小截问题”类似。

（2）关键截集。

在上容量无限的双容量网络中，虽然网络的最大截集的截量通常大于最小流，但是总有一个截集的截量与最小流相等，我们称该截集为关键截集。关键截集决定了网络最小流的大小，该截集中任意弧的下容量发生变化，网络最小流就必定会随之变化，反之亦然，因此最小流和关键截集互为对偶。

四、结论

本文研究网络流问题中在上容量无限的情况下，网络中至少要通过多少流量，以及如何通过，才能使经过各弧的流量不小于下容量。本文采用先将不可行流零流调整为可行流，再将该可行流调整为最小流的思路，首先给出了流量的调整原理，并且分析了流量与截集的关系，提出了关键截集的概念，即决定最小可行流的弧集，得出了网络最小流与关键截集互为对偶的结论。

参考文献:

[1]谢政.网络算法与复杂性理论[M].长沙:国防科技大学出版社,2003,116-123.

[2]Soleimani-damanehM.Maximalflowinpossibilisticnetworks[J].Chaos,SolitonsandFractals,2009,40(1):370-375.

[3]厍向阳,罗晓霞.点和边有容量约束的网络最大流新算法[J].计算机应用,2008,28(1):143-145.

[4]张宪超,贺江,陈国良.节点和边都有容量的有向平面网络中的最小截和最大流[J].计算机学报,2006,29(4):544-551.