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

摘要：

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

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

所属期刊栏目：22

分类号：C931(管理学)

资助基金：国家自然科学基金资助项目71402048;湖北物流发展研究中心资助项目2014A16

在线出版日期：2014-10-29（万方平台首次上网日期，不代表论文的发表时间）

页码：40-48