贝尔曼方程

基本原理 动态规划的理论基础是最优化原理和嵌入原理。

最优化原理 一个最优策略，具有如下性质：不论初始状态和初始决策（第一步决策）如何，以第一步决策所形成的阶段和状态作为初始条件来考虑时，余下的决策对余下的问题而言也必构成最优策略。最优化原理体现了动态规划方法的基本思想。

嵌入原理 一个具有已知初始状态和固定步数的过程总可以看作是初始状态和步数均不确定的一族过程中的一个特殊情况。这种把所研究的过程嵌入一个过程族的原理称为嵌入原理。通过研究过程族的最优策略族的共同性质得出一般通解，此通解自然也适用于原来的特殊问题。动态规划的基本方法就是根据嵌入原理把一个多步决策问题化为一系列较简单的一步决策问题，可显著降低数学处理上的难度。

贝尔曼方程 应用最优化原理和嵌入原理可推导出动态规划的基本方程，称为贝尔曼方程。它具有下面的形式：

式中N表示多段决策过程的总段数,F(xk，uk)为标量函数，表示由第k段到第k+1段的过程中基于状态xk和决策uk的性能损失，表示以xk+1为初始状态的后N-(k+1)段分过程的最优性能目标，xk+1=f(xk，uk)是基于第k段的状态 xk和决策uk而得到的第k+1段的状态向量，【】表示选择决策uk使【】取极小值。这是一个逆向递推方程。采用迭代法按k=N-1,N-2,…,1,0顺序求解贝尔曼方程，即可得到N段决策过程的最优策略{uk，k=0,1,2,…,N-1}和最优轨线{xk，k=0,1,2,…,N },而最优性能值为J壨(x0)。

对于图1中的例子，贝尔曼方程的形式如下：

经迭代计算后，得

………………………

这就是所求的最短距离。从S到G的最短路径是SA2B1C2G。而A2B1C2G，B1C2G，C2G 则分别是从A2，B1,C2到G 的最短路径。

贝尔曼方程是关于未知函数（目标函数）的函数方程组。应用最优化原理和嵌入原理建立函数方程组的方法称为函数方程法。在实际运用中要按照具体问题寻求特殊解法。动态规划理论开拓了函数方程理论中许多新的领域。

特点和应用范围 若多阶段决策过程为连续型，则动态规划与变分法处理的问题有共同之处。动态规划原理可用来将变分法问题归结为多阶段决策过程，用动态规划的贝尔曼方程求解。在最优控制理论中动态规划方法比极大值原理更为适用。但动态规划还缺少严格的逻辑基础。60年代，В．Г．沃尔昌斯基对动态规划方法作了数学论证。动态规划方法有五个特点：①在策略变量较多时，与策略穷举法相比可降低维数；②在给定的定义域或限制条件下很难用微分方法求极值的函数，可用动态规划方法求极值；③对于不能用解析形式表达的函数,可给出递推关系求数值解;④动态规划方法可以解决古典方法不能处理的问题，如两点边值问题和隐变分问题等；⑤许多数学规划问题均可用动态规划方法来解决，例如，含有随时间或空间变化的因素的经济问题。投资问题、库存问题、生产计划、资源分配、设备更新、最优搜索、马尔可夫决策过程，以及最优控制和自适应控制等问题，均可用动态规划方法来处理。