摘要
在一些物理网络中,当设施(边的容量等)建立后,由于需求增加,需要调整网络的容量来提高服务水平。调整优化的过程中既要考虑扩张成本,同时也要考虑需要调整的总边数,以尽可能小的影响人们的正常生活。本文研究对于一个给定的网络G,已知边ei的初始容量和单位容量扩张成本,在预算成本和扩张总边数的约束下,如何有效地扩张边的容量至xi,使得系统的容量最大,即max{mine i∈Txi,T是网络G中的生成树}。首先求解两个与之相关的模型,然后通过分析两个相关模型与原问题之间的联系与区别,提出了原问题的多项式时间算法。最后,通过算例说明算法的步骤,并分析了不同参数值对系统容量的影响。
Established infrastructure makes a great impact on demand changes in particular physical network. It is necessary to adjust the capacities of arcs to improve the service of the network when demand increases. The process of adjusting and optimizing should possible to minimize influences on people＇s daily life, by considering not only the expansion cost but also the total edges adjustment. In this paper, a network G, the initial capacity of edge ei and the cost for increasing per unit capacity of ei are initially set.Two factors： the improvement cost and the total edges adjustment are considered in this problem. The task is to determine new capacities x~ so that the capacity of the network can be increased to the maximum extent, i.e. max{ minei∈Xi,T is the spanning tree of network G }. Firstly two related models are solved instead of the original model. The relations and differences between the two related models and the original problem are analyzed. Then an algorithm is present to solve the original problem in polynomial time. Finally, an example is computed to illustrate the steps of the algorithm and analyze the impacts of parameters to the capacity of the system.
出处
《中国管理科学》
CSSCI
北大核心
2014年第9期40-48,共9页
Chinese Journal of Management Science
基金
国家自然科学基金资助项目(71402048)
湖北物流发展研究中心资助项目(2014A16)
关键词
瓶颈容量扩张
最小生成树
多项式时间算法
bottleneck capacity expansion
minimum spanning tree
polynomial time algorithm
