刘凤鸣

（浙江海洋学院 数理与信息学院，浙江 舟山 316000）

1 动态规划的基本概念

多阶段决策过程，是指一类特殊的过程，它们可以按时间顺序分解成若干个相互联系的阶段，称为“时段”，在每个时段都要做决策，全部过程的决策是一个决策序列。多阶段决策问题也称为序贯决策问题。

多阶段决策问题的目标是要达到整个活动过程的总体最优。在每个阶段进行决策时不应仅考虑本阶段最优，尤其应考虑对最终目标的影响，从而做出对全局来说最优的决策。动态规划是符合这种要求的一种决策方法。

动态规划开始只是应用于多阶段决策性问题，后来渐渐被发展为解决离散最优化问题的有效手段，进一步应用于一些连续性问题上。然而，动态规划更像是一种思想而非算法，它没有固定的数学模型，没有固定的实现方法，其正确性也缺乏严格的理论证明。因此，一直以来动态规划的数学理论模型是一个研究的热点。一个多阶段决策过程最优化问题的动态规划模型通常包含以下基本要素：阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数，在建立动态规划数学模型时，主要是确定这些动态规划的基本要素。

2 动态规划算法的基本步骤

2.1 划分阶段

应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。

2.2 选择状态

正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性.动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的。……