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

New Algorithm for the Continuing Dynamic Programming

作　　者：张鹏[1] 

机构地区：[1]武汉科技大学管理学院,湖北武汉430081

出　　处：《运筹学学报》2012年第1期97-105,共9页Operations Research Transactions

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

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

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

分 类 号：O221.3[理学—运筹学与控制论]