摘要
为解决连续型凸动态规划的``维数灾" 问题, 提出了一种新的算法---离散近似迭代法. 该算法的基本思路为: 首先, 将连续型状态变量离散化, 根据网络图的构造方法将动态规划问题转化为多阶段有向赋权图; 其次, 运用极大代数求出起点至终点的最短路, 即获得模型的一个可行解; 最后, 以该可行解为基础, 继续迭代直到前后两个可行解非常接近. 文章还证明了该算法的收敛性和线性收敛, 并以一个具体例子验证了算法的有效性.
Abstract
In order to solve the ``dimension curse", the paper proposes a new discrete approximate iteration method to solve the continuing convex dynamic programming model. Firstly, according to the network approach, the state variables are discretized and the model is transformed into multiperiod weighted digraph. Secondly, the max-plus algebra and the max-plus algebra are used to solve the shortest path that is the admissible solution. Thirdly, based on the admissible solution, the iteration is continued until the two admissible solutions are close each other. The method is proved to be convergent and linearly convergent. Finally, an example shows that the method is highly effective.
关键词
凸动态规划问题 /
/
离散近似迭代方法 /
极大代数 /
/
旋转算法
{{custom_keyword}} /
Key words
Convex dynamic programming /
discrete approximate iteration /
max-plus algebra /
pivoting algorithm
{{custom_keyword}} /
张鹏.
, {{custom_author.name_cn}}.
连续型凸动态规划的离散近似迭代法研究. 系统科学与数学, 2011, 31(8): 943-951. https://doi.org/10.12341/jssms11678
ZHANG Peng.
, {{custom_author.name_en}}.
THE DISCRETE APPROXIMATE ITERATION METHOD ON THE CONTINUING CONVEX DYNAMIC PROGRAMMING. Journal of Systems Science and Mathematical Sciences, 2011, 31(8): 943-951 https://doi.org/10.12341/jssms11678
中图分类号:
90C35
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}