摘要：在一些物理网络中,当设施（边的容量等）建立后,由于需求增加,需要调整网络的容量来提高服务水平。调整优化的过程中既要考虑扩张成本,同时也要考虑需要调整的总边数,以尽可能小的影响人们的正常生活。本文研究对于一个给定的网络G,已知边ei的初始容量和单位容量扩张成本,在预算成本和扩张总边数的约束下,如何有效地扩张边的容量至xi,使得系统的容量最大,即max{mine i∈Txi,T是网络G中的生成树}。首先求解两个与之相关的模型,然后通过分析两个相关模型与原问题之间的联系与区别,提出了原问题的多项式时间算法。最后,通过算例说明算法的步骤,并分析了不同参数值对系统容量的影响。

关键词：瓶颈容量扩张 最小生成树 多项式时间算法 

单位：湖北经济学院物流与工程管理学院 湖北武汉430205 华中科技大学管理学院 湖北武汉430074