English

运筹学学报 ›› 2012, Vol. 16 ›› Issue (1): 97-105.

• 运筹学 • 上一篇    下一篇

连续型动态规划的新算法研究

张鹏1   

  1. 1. 武汉科技大学管理学院, 湖北武汉, 430081
  • 收稿日期:2011-05-30 修回日期:2011-11-05 出版日期:2012-03-15 发布日期:2012-03-15
  • 通讯作者: 张鹏 E-mail:zhangpeng300478@yahoo.com.cn
  • 基金资助:

    教育部人文社科研究项目(08JC630062); 湖北省自然科学基金项目(2010CDB03304, 2010CDB02103); 湖北省科技厅软科学项目(2010DHA018).

New Algorithm for the Continuing Dynamic Programming

 ZHANG  Peng1   

  1. 1. School of Management, Wuhan University of Science and Technology,  Hubei Wuhan 430081, China
  • Received:2011-05-30 Revised:2011-11-05 Online:2012-03-15 Published:2012-03-15

PDF

1156

被引次数

4

摘要： 提出了求解一维连续型动态规划问题的自创算法----离散近似迭代法,并结合 双收敛方法求解多维连续型动态规划问题. 该算法的基本思路为：在给定其它状态向
 量序列的基础上,每次对一个状态变量序列进行离散近似迭代,并找出该状态变量的 最优序列,直到所有状态向量序列都检查完.当模型为非凸非凹动态规划时,
 证明了该算法的收敛性.当模型为凸动态规划时,证明了该算法的线性收敛性. 最后, 以一个具体算例验证了该模型和算法的有效性.

关键词: 动态规划问题, 多维, 离散近似迭代方法, 双收敛法

Abstract: The paper proposes the discrete approximate iteration method to solve single-dimensional continuing dynamic programming model. At the same time, multidimensional continuing dynamic programming model is solved by the discrete approximate iteration method and bi-convergent method. The algorithm is as following: Firstly, let state value of one of state equations be unknown and the others be known. Secondly, use the discrete approximate iteration method to find the optimal value of the unknown state values and then continue iterating until all state equations have found optimal values. If the objective function is non-concave and non-convex, the convergence of the algorithm is proved. If the objective function is convex, the linear convergence of the algorithm is proved. At last, the effectiveness of the formation and the algorithm is proved by an example.

Key words:  dynamic programming, dimension, discrete approximate iteration, bi-convergent method