有上下界网络最大流与最小截问题  

Problem of Maximum Flow & Minimum Cut Set of Network with Lower & Upper Arc Capacities

作　　者：谢凡荣[1] 贾仁安[2] 

机构地区：[1]南昌大学数学系,江西南昌330031 [2]南昌大学系统工程研究所,江西南昌330031

出　　处：《运筹与管理》2008年第2期24-31,共8页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(7076100410761006);江西省高校省级教改课题(赣教高字[2004]100号);江西省教育厅项目(赣教技字[2007]10号);江西省自然科学基金项目(2007GZS2120);南昌大学科学基金项目(04Z02914)

摘　　要：为了便于建立与有上下界网络最大流与最小截问题有关的决策支持系统,本文给出一个求有上下界网络最大流与最小截的数值算法,证明了算法的理论依据,并举例说明了算法在堵塞流理论中的应用。该算法能判定问题是否有可行解,在问题有可行解的情况下能求得问题的最优解。该算法具有易于编程实现、收敛性好等优点。数值实验表明该算法有较高的计算效率,可用于求解最小饱和流问题。For convenience to build decision support system relative to the problem of maximum flow ＆ minimum cut set of network with lower ＆ upper arc capacities, a numerical algorithm for finding maximum flow ＆ minimum cut set in network with lower ＆ upper arc capacities, is proposed in this paper. The theory, on which the algorithm is based, is strictly proved. And the application of the algorithm to blocking flow theory is illustrated with an exampie. The algorithm can judge whether the problem has a feasible solution or not, which can find the optimal solution to the problem while a feasible solution exists, and has good performance in the sense of being implemented on computer, convergence, etc. Numerical experiments demonstrate that the algorithm is an efficient and robust method to solve the problem, which can still be used to solve the minimum saturated flow problem.

关 键 词：运筹学 决策支持系统 数值实验 有上下界网络 最大流 最小截 最小饱和流 

分 类 号：N945[自然科学总论—系统科学] O224[理学—运筹学与控制论]