3、策阶段。这类问题就称为多阶段决策问题。多阶段决策问题的过程如下图所示：阶段1状态1决策1阶段2状态2决策2阶段n状态n决策n状态3……状态n+1第2节动态规划的基本概念和基本方程（1）阶段（stage）（2）状态（state）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。这些决策步骤就称为阶段。描述阶段的变量称阶段变量，常用k表示。状态表示每个阶段开始时所处的自然状况或客观条件。它描述了影响决策的因素随决策进程的变化情况。它既是前面阶段所作决策的结果，又是本阶段作出决策的
4、出发点和依据。描述状态的变量称状态变量，第k阶段的状态变量常用sk表示。通常，第一阶段的状态变量s1是确定的，称初始状态。2.1动态规划的基本概念描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内，称为允许决策集，记为Dk(sk)。决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。（3）决策（decision）（4）策略（policy）把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终
5、止的决策过程，或称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n={u1,u2,…,un}称为全过程策略，简称策略；而在k-子过程上的决策序列pk,n={uk,uk+1,…,un}称为k-子过程策略，也简称子策略。（5）状态转移方程若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定了，即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1=Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律
6、。（6）指标函数和最优值函数指标函数分为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段上（由状态和决策产生的）目标损益值的度量，用vk(sk,uk)表示。过程指标函数是指过程所包含的各阶段上（由状态和决策所产生的）总的目标损益值，记为Vk,n＝Vk,n(sk,uk,sk+1,uk+1,…,sn,un)动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数。常见的两种过程指标函数形式是：①各阶段指标函数的和Vk,n=vj(sj,uj)；②各阶段指标函数的积Vk,n=vj(sj,
7、uj)。把过程指标函数Vk,n对k-子过程策略pk,n求最优，得到一个关于状态sk的函数，称为（k-子过程）最优值函数，记为fk(sk)。即fk(sk)＝optVk,n(sk,uk,…,sn,un){uk,…,un}式中的“opt”（optimization）可根据具体问题而取min或max。2.2动态规划的基本方程动态规划的最优性原理（贝尔曼原理）：作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简言之，最优策略的子策略也必是最优的
8、。根据此原理，要求全过程最优策略，可从子过程策略的最优化入手。对于过程指标函数是阶段指标函数和的形式，考虑k-子过程最优值函数fk(sk):则有递推方程：还需有边界条件，一般取：于是，得基本方程（k=n,n-1,…,2,1）利用基本方程，由后向前逆序递推，就可实现对动态规划问题的求解。类似地，对于过程指标函数是阶段指标函数积的形式，其基本方程为：（k=n,n-1,…,2,1）例最短路问
