3.2 动态规划的基本原理和递推方程
1.基本原理
贝尔曼等给出的动态规划最优化原理可以这样叙述：作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面决策所形成的状态而言，余下的诸决策必须构成最优决策。简言之，一个最优策略的子策略总是最优的。
但是，随着人们对动态规划研究的深入，逐渐认识到：对于不同类型的问题所建立严格定义的动态规划模型，必须对相应的最优性原理给予必要验证。就是说，最优原理不是对任何决策过程都普遍成立的。而且最优性原理与动态规划的基本方程，并不是无条件等价的，二者之间也不存在确定的蕴含关系。可见动态规划的基本方程在动态规划的理论和方法中起着非常重要的作用。而反映动态规划基本方程的是最优性原理，它是策略最优性的充分必要条件，而最优原理仅仅是策略最优性的必要条件，它是最优性原理的推论。在求解最优策略时，更需要的是其充分条件。所以，动态规划的基本方程或者说最优性定理才是动态规划的理论基础[《运筹学》教材编写组（钱颂迪等），2014]。
2.动态规划数学模型
式中 opt——最大max或最小min。
具体可写为
一般取f*n+1（Sn+1）=0，称边界条件。
式中 f*i（Si）、f*i+1（Si+1）——第i阶段状态为Si及其第i+1阶段状态为Si+1时的最优目标函数值。
约束条件：
3.动态规划计算步骤
（1）将问题按时空特性划分为若干阶段。对无阶段性问题，可设法处理为几个阶段性问题（如[例3.1]输水线路选择问题，后面例题的水量分配问题等）。
（2）按标号法或采用递推方程逆序递推，直到初始状态S1。递推求解的同时，同时必须标记或记录局部最优决策，不然求解结束后，最优路线就找不到了。应该注意到，动态规划的求解结果可能存在多解情况。
【例3.2】用动态规划递推公式法求解[例3.1]问题（图3.1）。(https://www.daowen.com)
将问题人为划分为4个阶段（图3.1）计算：
n=4，第4阶段：
局部最优决策：d3（F1）=G1，d3（F2）=G1
n=2，第2阶段：
局部最优决策：d2（E1）=F1，d2（E2）=F1
n=1，第1阶段：
局部最优决策：d1（A）=E2
即
全局最优决策可从上面每步保存的局部最优决策中按正序顺序找出来：
