动态规划的基本概念及方程式

动态规划方法的核心是贝尔曼提出的“最优化原理”，它所处理的问题可以是线性的，也可以是非线性的；可以是动态过程问题，也可以是静态的问题；可以研究一些确定性的问题，也可以研究一些随机性的问题。

动态规划是一种用分阶段选优的技巧来达到整体最优化的数学规划方法。它不同于求函数极值的微分法和求泛函数极值变分法，也不同于求解线性规划的单纯形法，而是用另一种思路寻求最优解的方法。这一方法不仅能对问题作出定性分析，而且利用电子计算机可以得出数值解。

贝尔曼的最优化原理指出：“一个过程的最优策略具有这样的性质，即无论起始状态和初始决策如何，其以后各阶段的诸决策对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略。”

动态规划是根据贝尔曼最优化原理把问题分成若干阶段，利用一种递推关系式一个接一个依次作出最优决策，达到使整个过程取得最优结果。这类问题中，时间t是个很重要的因素，它是在各个时间段中采取最优决策的方法，因此称之为动态规划。

为了给出动态规划的一般模式，以便更广泛地应用，下面给出关于动态规划的几个基本概念和常用符号。

（1）阶段（Stage） 应用动态规划方法，首先要求能把所研究的问题划分成若干个相互联系的阶段，以便构成一个多阶段决策问题。

一般地，可按时间或空间的顺序，自然地分成几个阶段。也有的问题需要人为地划分成若干阶段。

（2）状态与状态变量（State） 状态指的是每一阶段的初始状况，即每一阶段可能的出发位置，或者说是初始条件。

第k阶段的状态常用状态变量sk来描述。在求最短路线的问题中，状态本身不是数量（而是位置），可用示性数来表示。如第二阶段可用数“1”代表位置B1，用数“2”代表位置B2，从而第二阶段的状态变量取值为：

一般地，状态既表示一个阶段的起点，又表示上一阶段的终点。

正确选择状态变量sk，不仅要求它能描述每一个阶段的初始状况，又要能满足无后效性。后谓无后效性是指，如果某阶段状态给定，则这一阶段以后过程的发展不受以前各阶段状态的影响。也就是说，一个过程过去的历史只能通过当前的状态去影响它未来的发展，当前的状态就是未来发展的初始条件。

（3）决策和策略（Decision） 决策就是其阶段状态给定以后，对若干可供选择的方案中某一方案的确定。同样，决策可以用决策变量来表示。第k阶段在状态sk下的决策变量，常记为xk（sk），或简记为xk。

实际问题的决策变量的取值往往限制在一定的范围内，这个范围称为允许决策集合。

各个阶段的决策依次确定以后，形成整个问题的一个决策序列，称为多阶段决策问题的一个策略。

一个有n个阶段的决策问题，由第k（1≤k≤n）阶段的某状态起到终点（过程结束）的过程，称为该问题的一个k—子过程；对应于k—子过程的决策序列，称为k—子策略，也通称为子策略。

（4）状态转移方程 对于第k阶段的状态sk，若选定了决策变量xk的值，那么第k+1阶段的状态sk+1也就确定了。也就是说，新状态sk+1是由其前一阶段的状态sk和决策xk决定的，即sk+1是sk和xk的一个函数：

sk+1=T（sk，xk）

这种函数关系称为状态转移方程。

状态转移方程的形式随问题的不同而异，参见[例5.20]。

（5）指标函数 在求一个多阶段决策问题的最优策略时，必须有一个能衡量策略优劣的数量指标，该数量指标称为指标函数。

指标函数可以表示路程，也可以表示利润、产量、成本、能源消耗等。指标函数随着策略的不同而取相应的值。从第k阶段状态sk出发的最优k—子策略所对应的指标函数值，记为fk（sk）。(www.xing528.com)

指标函数在某一阶段上的值，也叫阶段效应。第k阶段由状态sk出发，选择决策变量xk所产生的阶段效应，记作dk（sk，xk）。

（6）动态规划的基本方程 由动态规划最优化原理可得，从第k阶段状态sk到终点（过程结束）的最优指标函数值应为：

一般地，状态既表示一个阶段的起点，又表示上一阶段的终点。

正确选择状态变量sk，不仅要求它能描述每一个阶段的初始状况，又要能满足无后效性。后谓无后效性是指，如果某阶段状态给定，则这一阶段以后过程的发展不受以前各阶段状态的影响。也就是说，一个过程过去的历史只能通过当前的状态去影响它未来的发展，当前的状态就是未来发展的初始条件。

（3）决策和策略（Decision） 决策就是其阶段状态给定以后，对若干可供选择的方案中某一方案的确定。同样，决策可以用决策变量来表示。第k阶段在状态sk下的决策变量，常记为xk（sk），或简记为xk。

实际问题的决策变量的取值往往限制在一定的范围内，这个范围称为允许决策集合。

各个阶段的决策依次确定以后，形成整个问题的一个决策序列，称为多阶段决策问题的一个策略。

一个有n个阶段的决策问题，由第k（1≤k≤n）阶段的某状态起到终点（过程结束）的过程，称为该问题的一个k—子过程；对应于k—子过程的决策序列，称为k—子策略，也通称为子策略。

（4）状态转移方程 对于第k阶段的状态sk，若选定了决策变量xk的值，那么第k+1阶段的状态sk+1也就确定了。也就是说，新状态sk+1是由其前一阶段的状态sk和决策xk决定的，即sk+1是sk和xk的一个函数：

sk+1=T（sk，xk）

这种函数关系称为状态转移方程。

状态转移方程的形式随问题的不同而异，参见[例5.20]。

（5）指标函数 在求一个多阶段决策问题的最优策略时，必须有一个能衡量策略优劣的数量指标，该数量指标称为指标函数。

指标函数可以表示路程，也可以表示利润、产量、成本、能源消耗等。指标函数随着策略的不同而取相应的值。从第k阶段状态sk出发的最优k—子策略所对应的指标函数值，记为fk（sk）。

指标函数在某一阶段上的值，也叫阶段效应。第k阶段由状态sk出发，选择决策变量xk所产生的阶段效应，记作dk（sk，xk）。

（6）动态规划的基本方程 由动态规划最优化原理可得，从第k阶段状态sk到终点（过程结束）的最优指标函数值应为：

式（5.29）称为动态规划的基本方程。其中“opt”是英文“最优化”（optimize）的字头，可根据实际问题的要求而取“min”或“max”；dk（sk，xk）是第k阶段的阶段效应；fk+1（sk+1）是第k+1阶段从状态sk+1出发到终点的最优子策略的指标函数值；sk+1=T（sk，xk）。

显然，若fk+1（sk+1）均已得到，则由状态sk出发，对所有可能的决策算出阶段效应，就可以应用动态规划的基本方程求出fk（sk）。这样，对一个多阶段决策问题，先求出最后一个阶段各状态下的最优指标函数值（一般地，这是可以根据问题的条件直接得到的），再应用动态规划的基本方程逐段前推计算，一直到求出f1（s1）为止，就得到了整个过程（即所研究的多阶段决策问题）的最优解，包括最优指标函数值和最优策略。这就是动态规划的基本方法。

式（5.29）称为动态规划的基本方程。其中“opt”是英文“最优化”（optimize）的字头，可根据实际问题的要求而取“min”或“max”；dk（sk，xk）是第k阶段的阶段效应；fk+1（sk+1）是第k+1阶段从状态sk+1出发到终点的最优子策略的指标函数值；sk+1=T（sk，xk）。

显然，若fk+1（sk+1）均已得到，则由状态sk出发，对所有可能的决策算出阶段效应，就可以应用动态规划的基本方程求出fk（sk）。这样，对一个多阶段决策问题，先求出最后一个阶段各状态下的最优指标函数值（一般地，这是可以根据问题的条件直接得到的），再应用动态规划的基本方程逐段前推计算，一直到求出f1（s1）为止，就得到了整个过程（即所研究的多阶段决策问题）的最优解，包括最优指标函数值和最优策略。这就是动态规划的基本方法。