• 论文 • 上一篇    下一篇

高维0-1瓶颈问题的动态规划算法

罗宗俊   

  1. 贵州民族大学, 贵阳 550025
  • 收稿日期:2012-01-03 出版日期:2013-03-15 发布日期:2013-03-12

罗宗俊. 高维0-1瓶颈问题的动态规划算法[J]. 数值计算与计算机应用, 2013, 34(1): 38-46.

Luo Zongjun. DYNAMIC PROGRAMMING ALGORITHM ON HIGHER-DIMENSIONAL 0-1 BOTTLENECK PROBLEMS[J]. Journal of Numerical Methods and Computer Applications, 2013, 34(1): 38-46.

DYNAMIC PROGRAMMING ALGORITHM ON HIGHER-DIMENSIONAL 0-1 BOTTLENECK PROBLEMS

Luo Zongjun   

  1. Guizhou Minzu University, Guiyang 550025, China
  • Received:2012-01-03 Online:2013-03-15 Published:2013-03-12
在本文中, 我们通过一个实际问题归纳出一个数学模型(正文中的模型Ⅰ),并通过新变量的引用, 将模型Ⅰ转化成一个高维0-1瓶颈规划(正文中的模型Ⅱ).对模型Ⅱ, 我们建立了求模型Ⅱ最优解的动态规划算法(带有阀值Q). 该算法与普通动态规划相比大大节约了运算量. 最后指出了该算法对0-1瓶颈问题的求解具有一定的普遍性.
In this paper, we present the following mathematical model Ⅰ: max f(X) where X={xij}, f(X)= , ai and cij are known positive integers. Model Ⅰ transform into the following model through quotation of new variables: max g(Y) where Y={yij}, g(Y)= ai and wij are known positive integers. Besides, the dynamic programming algorithm with a threshold Q is established for finding an optimal solution to model Ⅱ. At last, we indicate the universality of this algorithm in finding higher-dimensional 0-1 bottleneck problems.

MR(2010)主题分类: 

()
[1] Gross O. The Bottleneck Assignment Problem, The Rand Corporation, 1959, P-1630.
[2] Ford L R, Jr and Fulkerson D R. Flows in Networks. Princeton University Press. New Jersey, 1962, 57-59.
[3] Barsow A R. What is Linear Programming (Moscow, 1959), 90-101(in Russian).
[4] Garfinkel R S. An Improved Algorithm for the Bottleneck Assignment Problem, Oper Res. 1971, 19.
[5] Lawler E L. Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.
[6] Benjamin Lev and Howard J Weiss. Introduction Mathematical Programming, New York, 1982, 159-161.
[7] Garfinkel R S and Nemhauser G L. Integer Programming, John Wiley and sons, 1972.
[8] 罗宗俊. 一个m维整数瓶颈运输问题及其算法[J]. 数值计算与计算机应用, 2001, 22(1).
[9] 罗宗俊. 一个Bottleneck问题及其算法[J]. 数值计算与计算机应用,1986, 7(1).
[10] 罗宗俊. 一个二维整数瓶颈问题及其算法[J]. 数学杂志,1996, 1(2).
[11] 林治勋. 最优化原理的逻辑基础[J]. 运筹学杂志, 1992, 11(1).
[12] 罗宗俊. 一类组合最优化问题及其算法[J]. 应用数学,1996, 9(3).
No related articles found!
阅读次数
全文


摘要