什么是动态规划?

什么是动态规划?

[拼音]：dongtai guihua

[外文]：dynamic programming

研究多段（多步）决策过程最优化问题的一种数学方法，英文缩写DP，是最优控制和运筹学的重要数学工具。为了寻找系统最优决策，可将系统运行过程划分为若干相继的阶段（或若干步），并在每个阶段（或每一步）都作出决策。这种决策过程就称为多段（多步）决策过程。多段决策过程的每一阶段的输出状态就是下一阶段的输入状态。某一阶段所作出的最优决策，对于下一阶段未必是最有利的。多段决策过程的最优化问题必须从系统整体出发，要求各阶段选定的决策序列所构成的策略最终能使目标函数达到极值。

发展简况

20世纪40年代，人们开始研究水力资源的多级分配和库存的多级存储问题。50年代初,美国数学家R.贝尔曼首先提出动态规划的概念，1957年发表《动态规划》一书。在1961、1962年相继出版的第二版和第三版中，又进一步阐明了动态规划的理论和方法。

多段决策过程

又称为多步决策过程(或系统)，是一种适合采用动态规划的过程(或系统)。多段决策过程包括阶段、状态、决策、策略和目标函数 5个要素。

（1）阶段:把所要求解的过程划分成若干相互联系的阶段,并用k表示阶段变量。

（2）状态:表示某一阶段出发位置的状态，它既是上一阶段的输出又是本阶段的输入，并用向量xk表示第k阶段的状态，称为状态变量。

（3）决策:指给定k阶段的状态后,从该状态转移到下一阶段某一状态的选择。用Uk表示第k阶段当状态处于Xk时的决策变量。对于系统的每一个状态，都可以从若干种可能的决策（或控制）中任选一种。选定决策并加以实施，即可引起系统状态的变化。系统的下一阶段状态由现在的状态和决策确定，与过去的历史无关，即系统是无记忆的。

（4）策略：由过程中每一阶段所选决策构成的整个序列，又称为方案。

（5）目标函数：策略的目标是使状态变量的某个特定函数的值为最大（或最小）。这个特定函数就是目标函数。使目标函数值为最大（或最小）的策略称为最优策略。图1中求最短路径的例子说明了多段决策过程及其构成要素。图中S是出发点，G是目的地，各边上的数字表示两点间的距离。求从S到G的最短路径和距离数。首先，可将图1划分成四个阶段，然后逆向依次寻求使总的距离为最小的最短路径。先从第一阶段开始,从C1到G只有一条路线,同样从C2到G也只有一条路线。到了第二阶段，从B1到G有经过C1或C2两条路线，经选择后由B1经C2到G距离最小。如此继续进行下去，就把一个最短路径问题变成了多段决策问题（图2）。最后求得最短路径为SA2B1C2G。

基本原理

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

最优化原理

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

嵌入原理

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

贝尔曼方程

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

式中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年代，В．Г．沃尔昌斯基对动态规划方法作了数学论证。动态规划方法有五个特点：

（1）在策略变量较多时，与策略穷举法相比可降低维数；

（2）在给定的定义域或限制条件下很难用微分方法求极值的函数，可用动态规划方法求极值；

（3）对于不能用解析形式表达的函数,可给出递推关系求数值解；

（4）动态规划方法可以解决古典方法不能处理的问题，如两点边值问题和隐变分问题等；

（5）许多数学规划问题均可用动态规划方法来解决，例如，含有随时间或空间变化的因素的经济问题。投资问题、库存问题、生产计划、资源分配、设备更新、最优搜索、马尔可夫决策过程，以及最优控制和自适应控制等问题，均可用动态规划方法来处理。

参考书目

R.E. Bellman，Dynamic Programming， princeton Univ.Press,Princeton,N.J.,1957.S.E. Dreyfus，Dynamic Programming and the Calculus of Variations，Academic Press, New York,1965.S.E.Dreyfus and A.M.Law, The Art and Theory of Dynamic Programming， Academic Press，New York，1977.