一类带有限制的网络瓶颈容量扩张问题!

发布时间：2018-06-16 05:52

  本文选题：瓶颈容量扩张 + 最小生成树　； 参考：《中国管理科学》2014年09期

【摘要】：在一些物理网络中,当设施(边的容量等)建立后,由于需求增加,需要调整网络的容量来提高服务水平。调整优化的过程中既要考虑扩张成本,同时也要考虑需要调整的总边数,以尽可能小的影响人们的正常生活。本文研究对于一个给定的网络G,已知边ei的初始容量和单位容量扩张成本,在预算成本和扩张总边数的约束下,如何有效地扩张边的容量至xi,使得系统的容量最大,即max{mine i∈Txi,T是网络G中的生成树}。首先求解两个与之相关的模型,然后通过分析两个相关模型与原问题之间的联系与区别,提出了原问题的多项式时间算法。最后,通过算例说明算法的步骤,并分析了不同参数值对系统容量的影响。
[Abstract]:In some physical networks, when facilities (side capacity, etc.) are set up, the capacity of the network needs to be adjusted to improve the level of service due to the increased demand. In the process of adjustment and optimization, both the cost of expansion and the total number of edges that need to be adjusted should be considered in order to influence people's normal life as little as possible. In this paper, we study how to effectively expand the capacity of a given network to the maximum capacity of the system under the constraints of budget cost and the total number of expanded edges under the constraints of the initial capacity and the unit capacity expansion cost of a given network. That is, max {mine I 鈭，

本文编号：2025611