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

中国管理科学 ›› 2014, Vol. 22 ›› Issue (9): 40-48.

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

刘慧¹, 杨超², 杨珺²

1. 湖北经济学院物流与工程管理学院, 湖北武汉 430205;
2. 华中科技大学管理学院, 湖北武汉 430074

收稿日期:2012-03-07 修回日期:2013-05-06 出版日期:2014-09-20 发布日期:2014-09-27
作者简介:刘慧（1982-），女（汉族），湖北谷城人，湖北经济学院物流与工程管理学院，讲师，博士，研究方向：网络优化与决策、物流管理.
基金资助:
国家自然科学基金资助项目（71402048）；湖北物流发展研究中心资助项目（2014A16）

A Class of Network Bottleneck Capacity Expansion Problem with Constraints

LIU Hui¹, YANG Chao², YANG Jun²

1. School of Logistics and Engineering Management, Hubei University of Economics, Wuhan 430205, China;
2. School of Management, Huazhong University of Science & Technology, Wuhan 430074, China

Received:2012-03-07 Revised:2013-05-06 Online:2014-09-20 Published:2014-09-27

摘要/Abstract

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

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

Abstract: 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 e_i and the cost for increasing per unit capacity of e_i 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_i so that the capacity of the network can be increased to the maximum extent, i.e. max{ min_e_i_∈_T x_i,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.

Key words: bottleneck capacity expansion, minimum spanning tree, polynomial time algorithm

中图分类号:

C931

刘慧, 杨超, 杨珺. 一类带有限制的网络瓶颈容量扩张问题[J]. 中国管理科学, 2014, 22(9): 40-48.

LIU Hui, YANG Chao, YANG Jun. A Class of Network Bottleneck Capacity Expansion Problem with Constraints[J]. Chinese Journal of Management Science, 2014, 22(9): 40-48.

参考文献

[1] Zhang, Jianzhong, Yang Chao, Lin Yixun. A class of bottleneck expansion problems[J]. Computer & Operations Research, 2001, 28(6): 505-519.

[2] Zhang Jianzhong, Lin Zhenhong. An oracle strongly polynomial algorithm for bottleneck expansion problems[J]. Optimization Methods and Software, 2001, 17(1): 61-75.

[3] Burkard R E, Klinz B, Zhang Jianzhong. Bottleneck capacity expansion problem with general budget constraints[J]. RAIRO-Operations Research, 2001, 35: 1-20.

[4] Yang Chao, Chen Xueqi. An inverse maximum capacity path problem with lower bound constraints[J]. Acta Mathematica Scientia, 2002, 22(2): 207-212.

[5] Burkard R E, Lin Yixun, Zhang Jianzhong. Weight reduction problems with certain bottleneck objectives[J]. European Journal of Operational Research, 2004, 153(1): 191-199.

[6] Yang Chao, Hao Chunyan, Zhang Jianzhong. On the optimum capacity of capacity expansion problems[J]. Mathematical Methods of Operations Research, 2007, 66(2): 225-233.

[7] 王洪国, 马诏汉. 关于无向网络容量扩张的问题[J]. 山东大学学报, 2000, 35(4): 418-424.

[8] 王洪国, 马诏汉. 关于有向网络容量扩张的问题[J]. 高校应用数学学报, 2001, 16(4): 471-476.

[9] 吴云, 周建, 杨珺. 随机网络瓶颈容量扩张相关机会规划模型[J]. 中国管理科学, 2004, 12(6): 113-117.

[10] Zhang Jianzhong, Lin Zhenhong, Ma Zhongfan. Some reverse location problems[J]. European Journal of Operational Research, 2000, 124(1): 77-88.

[11] 杨晓光, 张建中, 蔡茂诚. 两个逆网络选址问题的计算复杂性[J]. 系统科学与数学, 2002, 22: 321-327.

[12] Wang Qin, Yuan Jinjiang, Zhang Jianzhong. An inverse model for the most uniform problem[J]. Operations Research Letters, 2008, 36(1): 26-30.

[13] Zhang Jianzhong, Yang Xiaoguang, Cai M C. Inapproximability and a polynomially solvable special case of a network improvement problem[J]. European Journal of Operational Research, 2004, 155(1): 251-257.

[14] Zhang Jianzhong, Yang Xiaoguang, Cai M C. A network improvement problem under different norms[J]. Computational Optimization and Applications, 2004, 27(3): 305-319.

[15] 杨珺, 王玲, 杨超. 优化设施服务的网络调整费用均衡问题研究[J]. 中国管理科学, 2009, 17(5): 75-80.