随机网络瓶颈容量扩张相关机会规划模型

中国管理科学 ›› 2004, Vol. ›› Issue (6): 113-117.

随机网络瓶颈容量扩张相关机会规划模型

吴云¹, 周建², 杨郡¹

1. 华中科技大学管理学院武汉 430074;
2. 法国里昂大学计算机系

收稿日期:2004-05-17 修回日期:2004-10-21 出版日期:2004-12-28 发布日期:2012-03-07
基金资助:
国家自然科学基金资助项目(70271027)

Dependent - Chance Programming Model for Stochastic Network Bottleneck Capacity Expansion

WU Yun¹, ZHOU Jian², YANG Jun¹

1. College of Management, Huazhong Unvierstiy of Science and Technology, Wuhan 430074, Chnia;
2. Department of Computer Sceinces, Unvierstiy of Angers, France

Received:2004-05-17 Revised:2004-10-21 Online:2004-12-28 Published:2012-03-07

摘要/Abstract

摘要： 文章研究的问题为,在不确定环境中,怎样去增加网络中一组边的容量到一个指定的容量,以至于网络瓶颈扩张的费用不超过给定的总费用上限的概率尽可能的大.本文假定每一条边的单位扩张费用Wi是一个随机的变量,它服从一定的概率分布.带有随机单位扩张费用W的网络瓶颈容量扩张问题可以根据一些规则,列出它的相关机会规划模型的通用表达式.随后,本文将网络瓶颈容量算法、随机模拟方法和遗传算法合成在一起,设计出该问题的混合智能通用算法.最后,给出数值算例.

关键词: 瓶颈容量扩张, 相关机会规划模型, 混合智能算法, 随机规划

Abstract: This paper considers how to increase the capacities of the elements in a set E efficiently so that probability of the total cost for the increment of capacity can be under an upper limit to maximum extent, while the final expansion capacity of a given family F of subsets of E has a given limit bound.The paper supposes the cost is a stochastic variable with some distribution.Network bottleneck capacity expansion problem with stochastic cost is originally formulated as dependent-chance programming model according to some criteria.For solving the stochastic model efficiently,network bottleneck capacity algorithm,stochastic simulation and genetic algorithm are integrated to produce a hybrid intelligent algorithm.Finally a numerical example is presented.

Key words: bottleneck capacity expansion, dependent-chance programming model, hybrid intelligent algorithm, stochastic programs

中图分类号:

C931

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

WU Yun, ZHOU Jian, YANG Jun. Dependent - Chance Programming Model for Stochastic Network Bottleneck Capacity Expansion[J]. Chinese Journal of Management Science, 2004, (6): 113-117.

参考文献

[1] Ahu ja R.K, Magnanti T.L, Orlin J.B..Network flows [M]. Englewood Cliffs, NJ: Prentice-Hall, 1993.
[2] Averbakh I, Berman O, Punnen AP. Constrained matroidal bottleneck problem [J].Discrete Applied Mathematics,1995,63:201-214.
[3] Krumke, S.O, marthe, M.V., Ravi, R., and Ravi,S. S.. Approximation algorithms for certain network improvement [J].Journal of Combinatorial Optimization,1998,(2):257-288.
[4] Zhang,J.,Yang,C.,and Lin,Y..A class of bottleneck expansion problems[J]. Computer and Operational Research,2000,124:77-88.
[5] Yang C and Liu,J..A capacity expansion problem with budget constraint and bottleneck limitation[J]. Acta mathematica Scientia,2002,22:207-212.
[6] 王洪国,马诏汉.关于无向网络容量扩张的问题[J].山东大学学报,2000,35(4):418-424.
[7] 王洪国,马诏汉.关于有向网络容量扩张的问题[J].高校应用数学学报,2001,16(4):471.
[8] X.G. Yang and J.Z.Zhang. A network improvement Problem under different norms [J]. Computational Optimization and Applications, 2004,27:305-319.
[9] Charnes, A., & Cooper, W. W. Management models and industrial[J]. applications of linear programming, 1961.
[10] Liu B.dependent- chance programming: a class of stochastic programming [J]. Computers & Mathematics with Applications, 1997,34(12):89-104.
[11] K. IWAMURA and B. Liu. Dependent-chance integer programming applied to capital budgeting [J].Journal of the Operations Research Society of Japan, 1999,42:117 -127.
[12] Ryan SM. Capacity expansion for random exponential demand growth[ R]. Working Paper, No. 00-109, Industrial and Manufacturing Systems Engineering, Iowa State University, Ames, IA, August 2000.
[13] H. Katagiri, H. Ishii. Chance constrained bottleneck spanning tree problem with fuzzy random edge costs[J ]. Journal of the Operations Research Society of Japan, 2000,43(1):128-137.
[14] H. Katagiri, masatoshi Sakawa, Hiroaki Ishii. Fuzzy random bottleneck spanning tree problem using possibility and necessity measures [J]. European Journal of Operational Research, 2004,152:88-95.
[15] Liu B. Uncertain Programming [M]. New York: wiley,1999.