全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

, PP. 40-48

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

Full-Text   Cite this paper   Add to My Lib

Abstract:

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

References

[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]  Wang Qin, Yuan Jinjiang, Zhang Jianzhong. An inverse model for the most uniform problem[J]. Operations Research Letters, 2008, 36(1): 26-30.
[12]  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.
[13]  Zhang Jianzhong, Yang Xiaoguang, Cai M C. A network improvement problem under different norms[J]. Computational Optimization and Applications, 2004, 27(3): 305-319.
[14]  杨珺, 王玲, 杨超. 优化设施服务的网络调整费用均衡问题研究[J]. 中国管理科学, 2009, 17(5): 75-80. 浏览

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133