论文部分内容阅读
在一些物理网络中,当设施(边的容量等)建立后,由于需求增加,需要调整网络的容量来提高服务水平。调整优化的过程中既要考虑扩张成本,同时也要考虑需要调整的总边数,以尽可能小的影响人们的正常生活。本文研究对于一个给定的网络G,已知边ei的初始容量和单位容量扩张成本,在预算成本和扩张总边数的约束下,如何有效地扩张边的容量至xi,使得系统的容量最大,即max{mine i∈Txi,T是网络G中的生成树}。首先求解两个与之相关的模型,然后通过分析两个相关模型与原问题之间的联系与区别,提出了原问题的多项式时间算法。最后,通过算例说明算法的步骤,并分析了不同参数值对系统容量的影响。
In some physical networks, when the facilities (such as the capacity of the edge) are established, the demand for the network will need to be adjusted to improve the service level. In the process of adjustment and optimization, it is necessary to consider the expansion cost while taking into account the total number of edges that need to be adjusted so as to affect people’s normal life as little as possible. In this paper, we study the initial capacity of edge ei and the unit capacity expansion cost for a given network G. How to effectively expand the capacity of the edge to xi under the constraint of budget cost and total expansion of edge makes the system capacity maximum , Max {mine i ∈ Txi, T is the spanning tree in network G}. First, we solve two related models, and then propose the polynomial time algorithm of the original problem by analyzing the relations and differences between the two related models and the original problem. Finally, an example is given to illustrate the steps of the algorithm, and the influence of different parameter values on the system capacity is analyzed.