通过前面两个例题，对动态规划问题有了初步的认识，同时前面也讲到，当状态和决策阶段比较多时，若采用穷举法，就会相当复杂，甚至无法实现决策的目的。为了对建立动态规划问题的模型有基本了解，也为了寻求一种更好的动态规划问题求解算法，下面分别介绍几个基本概念、状态转移方程、优劣指标以及指标递推方程。

1.基本概念

（1）阶段。

针对动态规划问题，为了便于求解和刻画决策过程的推移顺序，需要把所给的问题划分为若干个既相互联系又相互区别的阶段，这就需要对每一个阶段作出不同的决策，以便控制这个阶段的推移过程，这就是所谓的多阶段决策。通常，阶段是按照时间或空间上先后顺序的特征来划分的，但无论如何划分，都要便于将问题转化为多阶段决策。从最初阶段到最后阶段的一系列决策称为策略。显而易见，动态规划的目的就是在若干个决策中寻求最优的策略。用来描述阶段的变量叫做阶段变量，一般以k表示阶段变量，阶段的数量就是多阶段决策从开始到结束时所作出的决策数量，如引例8.1中分为四个阶段。

（2）状态和状态变量。

每个阶段开始时，过程所处的自然状况或客观条件称为状态。在动态规划中，状态是阶段划分的临界点，也是各个阶段决策的依据，或者说是动态规划问题中各个阶段信息的传递点和结合点。状态的变化就意味着阶段的推移，同样阶段的推移也意味着状态发生了变化，所以多阶段决策的过程可以通过各个阶段状态的演变来描述。反映状态变化的量叫做状态变量，它可以用一个数、一组数或一个向量来表述。状态变量必须包含对应阶段决策所需要的全部信息，它不但能描述过程的特征，同时也具有“无后效性”，即当前阶段的状态给定时，这个阶段以后的过程如何演变与该阶段及前面各个阶段的状态无关。状态变量是动态规划中最关键的一个参数，它既是反映前面各阶段决策的结果，又是本阶段作出决策的出发点。用sk表示第k阶段的状态变量，状态变量的取值有一定的允许集合或范围，此集合称为允许状态集合。允许状态集合实际上是关于状态的约束条件，它可以是离散的取值集合，也可以是连续的取值区间，需要视具体问题而定。状态变量取值的全体称为状态空间或状态集合。同样，可以根据状态变量是离散的还是连续的，将动态规划问题分为离散型动态规划和连续型动态规划。

（3）决策和决策变量。

当某一阶段的状态确定以后，可以作出不同的决定或选择，从而确定下一个阶段的状态，这种决定或选择称为决策。下一个阶段进入何种状态取决于这一阶段作出了什么决策，所以决策就是各个阶段对状态演变的诸多可能性的选择。描述决策的变量称为决策变量。由于各个阶段的决策取决于状态变量，用xk表示第k阶段状态为sk的决策变量，它可以用一个数、一组数或一个向量（多维情形）来描述。在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合，记为Xk。每一个阶段的允许决策集合不一定相同，允许决策集合实际是决策的约束条件。

2.状态转移方程

状态转移方程是由一种状态演变为另一种状态的数学描述形式。设第 k阶段开始状态的状态变量为sk，对该阶段作出决策的决策变量为xk，那么针对第k+1阶段的状态变量sk+1也随之确定，即sk+1的值随着sk和xk的变化而变化，所以sk+1与sk、xk有函数关系。为了描述这种由第k阶段转移到第k+1阶段的演变规律，把这个函数记为(www.daowen.com)

这个函数方程称为状态转移方程。在许多问题中，状态转移方程可以用数学解析式来表达，不过有的问题很难用数学解析式来刻画状态转移方程，但这并不妨碍用动态规划来解决现实问题。

3.优劣指标

动态规划的目的就是在若干个决策中寻求最优的策略，即形成可行的最优决策序列，这就需要有衡量策略的指标，这个指标称为优劣指标。优劣指标取决于决策过程的初始状态和各个阶段的决策，即优劣指标是初始状态和决策序列的函数。在每个阶段的每一种状态下作出的每一个决策都会对问题的总效果有直接的影响，这种影响和sk、xk是函数关系，记为dk(sk,xk)。另外，由第k阶段的状态sk开始转移到后面某一状态的这一过程称为第k阶段状态sk的后部过程，则相应的决策序列称为状态sk后部策略。从第k阶段的状态sk开始的每一个后部过程都像全过程一样也规定一个指标，这个指标称为最优后部指标，记为fk(sk)。如果用fk(sk,xk)表示第k阶段状态sk下采取决策为xk的最优后部指标，那么就可以有如下的函数关系式把具有最优后部指标的后部过程称为最优后部过程。

动态规划的方法就是每一个阶段都要找出该阶段下每一种状态的最优后部过程，从而形成最优后部策略。

4.指标递推方程

在计算各个阶段最优后部过程的最优后部指标时，都要用到上一个阶段已经求出的最优后部指标，所以建立最优后部指标的思路就是，首先确定各个阶段每一种状态下决策产生的直接效果dk(sk,xk)，然后从初始状态出发，依次求出当前阶段每一种状态的最优后部过程，从而建立最优后部指标fk(sk,xk)。

基于前面的相关知识，可以给出第k阶段状态sk下采取决策为xk时的最优后部过程的指标递推方程：

如果引入函数关系式fk(sk,xk)=dk(sk,xk)+fk+1(gk(sk,xk))，则模型8.1可以写为

指标递推方程8.1和8.2也称为动态规划的基本方程。只有建立了这个具有递推关系的方程，才能对一个动态规划问题从第一阶段开始逐次进行计算求解，从而寻找到整个过程的最优解。