动态规划（动态模拟 Programming，DP）是分析解决多阶段决策过程最优化问题的一种方法。它主要求解以时间化分阶段的动态过程的优化问题，对于静态问题，也可以用它来解决。动态规划是考察问题的一种途径，而不是具体的算法。

动态规划起源于20世纪40年代人们对于水利资源多级分配、库存多级存储等问题的研究，美国数学家理查德·贝尔曼（R.Bellman）逐渐发现了多阶段决策问题的背后结构，并指出逆序归纳法到底是如何求解多阶段决策问题的。1949年，他提出了著名的最优化原理（principle of optimality），次年，贝尔曼经过反复斟酌确定了“动态规划”这一名称。1957年，贝尔曼出版了他的书籍《动态规划》（Dynamic Programming），并在1961年、1962年相继再版此书，进一步阐明了动态规划的理论和方法。

动态规划有求解更容易、效率更高等优势，但是，它也存在着应用条件苛刻、通用性不足的限制。动态规划的求解常用到阶段、状态、决策、策略、效果函数等一系列基本概念，一般步骤可分为6步，核心思路为构建基本方程。动态规划具有顺序解法、逆序解法等基本求解方法。

动态规划的常见类型有多维动态规划、随机动态规划。变分法是另一种求最优结果的方法，对于复杂的变分问题，也可以利用动态中华人民共和国城乡规划法进行求解。动态规划问题有许多经典的案例，如背包问题、机器负荷分配问题。动态规划在现实世界的许多领域得到了广泛的应用，例如生产调度、资源分配、设备更新、信息处理、模式识别等，成为了运筹学中的活跃分支。

动态规划是分析解决多阶段决策过程最优化问题的一种方法，为运筹学的一个重要分支。而多阶段决策是指这样一类特殊的活动过程，它们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。动态规划主要求解以时间化分阶段的动态过程的优化问题，对于静态问题，也可以它来解决。它是考察问题的一种途径，而不是具体的算法。

20世纪40年代，人们开始研究水力资源的多级分配和库存的多级存储问题。美国数学家理查德·贝尔曼（R.Bellman）逐渐发现了多阶段决策问题的背后结构，并指出逆序归纳法到底是如何求解多阶段决策问题的。1949年，他提出了著名的最优化原理（principle of optimality），即把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系逐个求解，开始了动态规划的研究。1950年，他经过反复斟酌确定了“动态规划”这一名称。1957年，贝尔曼出版了他的书籍《动态规划》（Dynamic Programming），并在1961年、1962年相继出版第2版和第3版，进一步阐明了动态规划的理论和方法。

（1）求解更容易、效率更高。动态规划方法是一种逐步改善法，它把原问题化成一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少得多，约束集合也简单得多，故比较易于确定最优解。

（2）解的信息更丰富。非线性规划（或线性规划）的方法是对问题的整体进行一次性求解的，因此只能得到全过程的解；而动态规划方法是将过程分解成多个阶段进行求解的，因此不仅可以得到全过程的解，还可以得到所有子过程的解。

（3）对于处理变量为整数的最优化问题有特别的功效。相反，变量的某些约束，例如整数或非负等，对于其他优化技术的应用都将产生困难。实质上，所有其他优化技术，各类约束都能引出严重的麻烦问题。例如，对问题变量加上只能取整数的限制，就不能用经典的方法来解决。然而，在动态规划中，要求某些或全部变量为整数，还将大大地简化计算过程。

（4）确定出绝对（全局）极大或极小，而不是相对（局部）的极值。这一点几乎超过了所有现存的计算方法，特别是经典最优化方法。

（1）没有一个统一的标准模型。由于实际问题不同，其动态规划模型也各有差异，模型构建存在一定困难。

（2）应用条件苛刻、通用性不足。由于构造动态规划模型状态变量必须满足“无后效性”条件，这一条件不仅依赖于状态转移律，还依赖于允许决策集合和指标函数的结构，不少实际问题在取其自然特征作为状态变量时并不满足这一条件，这就降低了动态规划的通用性。

（3）状态变量存在“维数障碍”。最优指标函数是状态变量的函数，当状态变量的维数增加时，最优指标函数的计算量将成指数倍增长，因此无论是手工计算还是电算，“维数障碍”都是无法完全克服的。

阶段：对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。

阶段变量一般用表示。由于在求解多阶段决策问题时，一般采用反向递推，所以阶段的编号也是逆向的，也可以正向递推。

状态：描述了研究过程所处的状况，即每一阶段开始时所处的状态。在最短路径问题中，状态既是某一阶段某一支路的始点，又是下一阶段某一支路的终点。通常，一个阶段有一个或若干个状态。动态规划中的状态必须满足无后效性，它是指如果某一阶段的状态给定后，则在这阶段以后过程的发展不受这阶段以前各状态的影响。也就是说，过去的历史只能通过当前的状态去影响它未来的发展，当前的状态是以往历史的全部总结。

描述状态的变量称为状态变量。状态变量允许取值的范围称作允许状态集合。用表示第阶段的状态变量它可以是一个数或一个向量。用表示第阶段的允许状态集合。个阶段的决策过程有个状态变量，表示演变的结果。根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便，有时将连续变量离散化；为了分析的方便，有时又将离散变量视为连续的。

决策：当多阶段决策过程处于某一阶段某一状态时，可以作出不同的决定，从而决定下一阶段的状态，这种决定称为决策。

描述决策状态的变量为决策变量，某一阶段某一状态所作出的决策用决策变量表示，第阶段状态的允许决策集合用表示，第阶段各状态的允许决策集合用表示，所有各阶段各状态的允许决策集合用表示，则有。

策略：按顺序排列的决策组合的集合，通常指某一阶段某一状态到终点的顺序排列的决策组合的集合。

用表示从第阶段状态出发到终点的一个子策略。从第阶段状态出发到终点的允许策略集合为，则。

状态转移方程：表示从某一阶段某一状态到下一个阶段另一状态的演变过程。它反映相邻两个阶段的状态和决策变量之间的相互关系。如果给定某一阶段的某一状态及其在该状态下的决策变量，就可以确定下一阶段的某一特定状态（按逆向划分阶段）。这种相邻两个阶段的状态转移关系称为状态转移方程，记为：。

直接效果函数：表示在某一阶段某一状态下，采取某一决策后到下一阶段某一状态的直接效果值。它是状态变量和决策变量的函数，记为：。

总效果（指标）函数：表示在某一阶段某一状态下，采取某一策略后到终点的总效果值。它是状态变量和一系列决策变量的函数，即为从第阶段状态出发到终点的子策略的函数，记为：。

最优效果（指标）函数：表示在某一阶段某一状态下，采取最优策略后到终点的最优效果值。

记为：，其中 是最优化“最优化”的缩写。

最优化原理可以表述为：“一个过程的最优策略具有这样的性质，即无论初始状态和初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略。”

例如，将这一基本原理应用于最短路线问题时可表述为：一方面，一条路线如果是最短路线，则对于该线上的任何一点来说，最短路线以此点为起点的剩余部分，必然是从此点到终点的最短路线；另一方面，无论是从哪一阶段的哪一种状态出发，到终点的最短路线只与此状态有关，而与以前的状态路线无关，即并不受从点是如何到达这点的决策的影响。

最优化原理可以用反证法来证明。假定是由始点到终点的最短路线上的一点，如果存在另一条最短路将与终点相连，则这条最短路线与以前的部分必构成全程的最短路线，这就与原策略为最短路线的假定相矛盾。所以，对于一个过程的最优策略而言，不管其初始状态和决策如何，其后的任一决策都构成最优策略。这也是动态规划可以采用逆序递推法寻优的依据。

作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。作为全过程的最优策略，其后部子策略也必须是最优的。因此，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种方法。

动态规划基本方程式为：

其中可根据题意而取或。称为阶段指标函数，它是由状态和决策变量确定的，在不同的问题中，阶段指标函数的含义是不同的，它可能是距离、利润、成本、产品的产量或资源消耗等。则称为最优指标函数，它表示从第阶段的起到终点为止的最短距离、最大利润或最低成本等。是将阶段的指标与子过程的最优指标聚合起来的运算，对每一个来说，可以取不同的运算，但在大多数实际问题中，一般是全取加法或全取乘法。在动态规划的基本方程中，由于状态转移的无后效性，所以，该式被称为状态转移律或状态转移方程，其具体形式由具体问题而决定。基本方程中的递推关系式中并不是新的自变量，只有为自变量。

（1）将实际问题的全过程根据时间或空间顺序恰当地划分成若干阶段，用表示阶段变量。一个阶段表示需要作出一次决策的子问题，各子问题应具有同一模式。

（2）正确选择状态变量，使它既能描述过程的状态演变特征，又要满足无后效性。同时，还必须具有可知性，即，规定的各阶段状态变量的值，通过直接或间接的方式可以得知。

（3）确定决策变量、允许决策集合和相邻两阶段的状态转移律：。

（4）根据题意写出总效果（指标）函数以及最优效果（指标）函数。

（5）根据最优化原理，写出动态规划基本方程。

（6）根据问题的各种性质，结合其他数学技巧，求解方程。

动态的求解方法多样。顺序解法和逆序解法为两种基本方法，顺序解法的寻优方向与过程的行进方向相同，逆序解法的方向相反。此外，一些决策问题中，阶段变量不易确定，可考虑更一般的方法——函数迭代法。而满足同一种条件决策过程的方法还有策略迭代法。

顺推解法：由前向后推算最优解的方法。运用顺推法求解时，需根据实际决策从最初阶段开始，即边界条件从开始，由前向后进行顺推，逐步求得各个阶段的最优决策和相应的最优值，最后求得最优后部指标即最后阶段的最优指标，从而得到整个问题的最优解。

该方法的基本方程为：

或写成：

顺推法的求解过程就是根据边界条件，从开始由前向后进行顺推，根据基本方程求出各个阶段的，最后求得的就是整个动态规划问题的最优解。

逆推法：由后向前推算最优解的方法。运用逆推法求解时，需根据实际决策从最后阶段开始，即边界条件从开始，由后向前进行逆推，逐步求得各个阶段的最优决策和相应的最优值，最后求得最优后部指标即最初阶段的最优指标，从而得到整个问题的最优解。

该方法的基本方程为：

或写成：

逆推法的求解过程就是根据边界条件，从开始，由后向前进行逆推，根据基本方程求出各个阶段的，最后求得的就是整个动态规划问题的最优解。

另一类动态规划问题的阶段数目是不能事先予定的，而要通过最优指标函数值的计算来确定，其最优策略是由个最优决策组成的，因此也要通过最优指标函数值的计算来确定。这种动态规划问题，一般叫做确定性不定期决策过程最优化问题，可以使用函数迭代法和策略迭代法来求解。

问题：设有个点。任意两点，之间有一弧连结，其长度为（可以代表距离、费用等），，其中表示和之间没有连结弧，试求任一点到的最短路线。

设表示点到点的最短矩离，则由最优化原理可列出基本方程：

函数迭代法：基本思想是以阶段数作为参数，先求不同参数下的最优解（值），再从这些最优解中选出最优者，从而确定了最优阶段数，更进一步讲，从到的步数虽然不定，但不会超过步，否则将会出现回路，不是最短路。每一条从到的步最短路都可以求出。令，就可以求出所有最短路，把它们加以比较，从中选出最优者，最后确定了最优阶段数（步数）和最优策略及最短路。迭代步骤可具体为：设表示从开始，经过步到的最短距离，所以时有：

按下列递推关系求。

当时，停止迭代。这时满足，且不超过。

策略迭代法：基本思想是先给出初始策略（即），然后按某种方法求出新策略直至求出最优策略。若对某一，对所有成立，则称策略收敛，而且就是最优策略，这里的表示第步从出发应该到达的下一点。由可以计算出从到的距离，根据距离修改策略，直至求出最优策略。

迭代步骤：

（1）选择一个没有回路的初始策略。

（2）由策略求出指标函数，即由方程组

解出，其中为已知。

（3）由求。

就是使取最小值的那个，即它是的解。

（4）按（2）、（3）步反复迭代，直至时，就是最优策略，记作。

多维动态规划：有个或个以上的状态变量，或者在每一阶段要选择个或个以上的决策变量的动态规划模型。当动态规划维数超过维时，所需计算机的存贮量和计算量太大，常无法求解，所以，各种改进算法被相继提出，如：动态规划逐次逼进法、状态增量动态规划、导数动态规则、离散微分动态规划等。

例如：设有两种原料，数量分别为和，需要用于生产种产品，对第种产品来说，当使用第一种原料数为，使用第二种原料数为时，其收益为。需要寻求一个最佳策略，即如何分配这两种原料于种产品才能使总收益为最大。

求解思路：如果用线性规划求解，则其数学模型为：

在约束条件

下使目标函数为最大，可以看出，它有两个约束条件，如果用动态规划方法求解，其状态变量和决策变量都是二维的。

设级的输入状态变量为，表示分配用于生产第种产品到第种产品的第一种原料总数量，表示分配用于生产第种产品到第种产品的第二种原料总数量，级的决策变量为。因此有状态传递方程为：

由最优化原理，可以建立动态规划递推方程为：

。

随机动态规划：如果一个动态规划的状态转移律是不确定的，即对给定的状态和策略，下一阶段的状态不是确定的，而是一个已知概率分布的随机变量，那么这个动态规划称为随机动态规划。在随机动态规划中，由于下一阶段的状态不确定，只能根据各阶段的期望值进行优化处理。

这时，基本方程应表示为：

。

例如：某科研单位为某厂承担一种新产品试制任务，双方签订的合同规定须在三个月内由科研部门向厂方交出一台合格样品，否则应向厂方交付元的赔偿费。该科研单位的已有资科表明，进行试制时合格的概率为，并知投产一批的固定成本为元，而每台产品的试制费用为元。若投产一批后均不合格，可继续试制，但每投产试制一批的周期为一个月。厂方已按合同付给研究单位一笔费用。问：研究单位应确定怎样一个试制计划，可使总的研制费用的期望值最小。

求解思路：可按一月为一个阶段把整个合同期分为三个阶段，分别以表示。设状态变量为，并且假定尚没有一台合格品产生时为，至少得到一台合格品时为 。决策变量设为，它表示第批投产试制台新产品。这样，充许决策集合当时为，当时。于是，状态转移律是以如下分布表示的随机变量,。以表示第阶段的研制费用支出，则。用表示第阶段以后的总研制费用的最小期望值，则有，于是可以建立如下基本方程：

。

变分法是另一种求最优结果的方法，它与动态规划之间有明显的差别。用变分法时，最优函数（极值）是满足边界条件的一个或多个微分方程的确定解，不需逐点计算，而是一次求得，或者用近似解的序列逼近总函数。用动态规划方法时，不是一次就求出整个最优函数，而是逐点移动，沿着极值曲线，从前一个点加上已知导数情况，计算下一个点。尽管有这些差别，两种方法之间是有着密切联系的。事实上，变分问题的解，常常是难以求得的，存在很多实际困难，常通过动态规划的思想进行求解。

在变分法求解最优控制问题中，已得出若系统的状态方程为：

性能指标函数为：

求满足式的约束条件，使为最小的，可采用求最优化方法引入辅助变量（或称约瑟夫·拉格朗日乘子），构造新泛函，然后求新泛函的无条件极值，得到的欧拉方程为

变分法求最优控制的必要条件是欧拉方程。在动态规划哈密顿一卡尔·雅可比方程中的，与经典变分法中求最优化引入的辅助变量是相对应的。所以，动态规划是最优问题的一种现代变分法，它包含了经典变分法的内容。

动态规划主要求解多决策过程的最优化问题，包括最短路线问题、资源分配问题、生产—库存问题等经典案例。其中，确定性的定期多阶段决策问题包括旅行售货员问题、多阶段生产分配问题、可靠性问题；确定性的不定期多阶段决策问题包括最优线路问题、有限资源分配问题。目前，动态规划在现实世界的许多领域得到了广泛的应用，例如生产调度、资源分配、设备更新、工业控制和多级工艺设备的优化设计以及信息处理、模式识别等，成为了运筹学中的活跃分支。

背包问题是一个经典的最优化问题，即原问题的最优解一定包含子问题的最优解，下面可以递归地定义最优解的值。

问题：对于每个物品，可以有两个选择，放入或者不放入背包，有个物品，故而需要做出个选择。设表示做出第次选择后，所选物品放入一个容量为的背包获得的最大价值，其中表示第件物品的重量，表示第件物品的价值。对于第件物品，有两种选择，放或者不放。

（1）如果放入第件物品，则。这表示，前次选择后，所选物品放入容量为的背包所获得的最大价值为，加上当前所选的第个物品的价值即为。

（2）如果不放入第件物品，则有，这表示当不选第件物品时，就转化为前次选择后所选物品占容量为时的最大价值为。

综上所述，。

问题：设有某种机器，可以在高、低两种不同的负荷下进行生产，产量函数分别为，机器的年折损完好率分别为和。假定，开始生产时，完好的机器数量为，要求制定一个年生产计划，在每年开始时，决定如何重新分配完好的机器在两种不同负荷下生产的数量，使在年内产品的总产量达到最高。这就是机器负荷分配问题，也可以看作是带回收的资源分配问题。

解：将问题划分为个阶段，每一年为一个阶段，。状态变量选为第阶段初拥有的完好机器数，显然。决策变量选为第阶段安排在高负荷下生产的机器数，则第阶段在低负荷下生产的机器数为，决策变量的约束条件是：。由于在高负荷下生产的机器年折损完好率是，在低负荷下生产的机器年折损完好率是，因此，状态转移方程是：。阶段指标函数即为阶段产量。若用表示由出发采用最优分配方案到结束时这段期间的产品产量，则有：

。

最短路线问题是指给定始点及终点，并知道由始点到终点的各种可能的途径，问题是要找一条由始点到终点的最短的路线。例如，运输部门要选择一条费用最低的运输路线；建筑公司要辅设一条使两点之间总距离最短的公路；旅行者希望找到一条由出发地至目的地的距离最短的行进路线等。而且，有些与运输根本没有关系的问题也可以化为求最短路线的模型，用动态规划方法来求解。

问题：如下图所示，给定一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），试求一条由到的铺管线路，使总距离为最短（或总费用最小）。

解：由图可知，从点到点可以分为个阶段。从到为第一阶段，从到为第二阶段，从到为第三阶段，从到为第四阶段。在第一阶段，为起点，终点有、、三个，因而这时走的路线有三个选择，一是走到，二是走到，三是走到。若选择走到，则就是在第一阶段的决策结果，它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，从点出发，对应于点就有一个可供选择的终点集合，若选择由走至，则就是第二阶段的终点，同时又是第三阶段的始点。同理递推下去，可以看到：各个阶段的决策不同，铺管路线就不同。当某阶段的始点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段路线的影响。对于这样的问题，可以用穷举法来解决。即把由到所有可能的每一条路线的距离都算出来，然后互相比较找出最短者，相应地可以得出最短路线。这样，由到的个阶段中，若第一阶段选择，则一共有条不同的路线，若第一阶段选择或，则一共有条不同的路线，比较这些不同路线的距离值，就可以找出最短路线为：，相应最短距离为。