动态规划

---

一种用于作出最优多级决策的数学技术。

它提供了一种系统的步骤，借以确定如何组合一系列互相有关的多级决策才能获得最大的总效益。动态规划问题没有标准的数学构成。动态规划方法只是表为求解问题的一般性步骤。可按下述方式刻划一个动态规划问题：(1)整个过程分成许多阶段，每一个阶段需要作出一个决策；(2)每一个阶段有若干种可能状态；(3)每一个阶段上的决策效益是从一种状态转移到下一阶段某个状态时对目标函数所作出的贡献；(4)对于已给定的状态，余下各阶段的最优决策与以前各阶段所采取的决策无关；(5)求解过程从寻求最后阶段的每种状态下的最优决策开始；(6)给定了第(n+1)阶段上每种状态下的最优决策，可求得一个逆推关系式，来识别第n阶段上每种状态下的最优决策；(7)应用这个逆推关系式，求解过程逐阶段由后向前推移—每次寻求该阶段上每种状态下的最优决策—直到求出从初始阶段开始的最优决策。

动态规划可分为确定型动态规划和随机型动态规划。