摘要： 研究了带有时间和费用双重限制下的网络容光焕发量扩充问题，即在满足时间和费用约束条件下，如何扩充网络中某些弧的容量使扩充后的网络容量尽可能的大。通过将问题转化为 求其最小生成树，给出了其求解算法。由于在扩充时两个约束条件一般有一者剩余，为了合 理配置扩充资源，讨论了给定容量要求下关于时间和费用的Pareto优化解的情况并给出了有 效算法，用实例来证明了算法的有效性。

关键词: 网络流, 容量扩充, 瓶颈问题, Pareto优化解

Abstract: This paper considers how to increase the capacities of the elements in an arc set A so that the capacity of a given network N can be increased to th e maximum extent while the total time and cost for the increment of capacity is within the given budget bounds. It transforms the problem into finding the minim um spanning tree of N and propose an algorithm for solving it. It further finds all the pareto optimum solutions about time and cost while being given a fixed c apacity demand. Finally the validity of the algorithms are illustrated with exam ples.

中图分类号: 

• TP393.02