2、种不同负荷下生产的数量,使五年内产品的总产量最高。多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的的优化方法称为静态规划。最优性原理作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决策序列必然构成最优子序列。这种过去的状态和决策对于今后的决策所形成的状态没有影响，也称为无后效性或者马尔可夫性。(1)阶段（stage）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称
3、阶段变量，常用k表示。(2)状态（state）状态表示每个阶段开始时所处的自然状况或客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定的，称初始状态。(3)决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。4.2动态规划的基本概念（一）(4)策略（policy）
4、把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，或称为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)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下
5、一阶段的状态的演变规律。(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,uj)。把过程指标函数Vk,n对k子过程策略pk,n求最
6、优，得到一个关于状态sk的函数，称为最优值函数，记为fk(sk)。即fk(sk)＝optVk,n(sk,uk,……,sn,un)uk,…,un式中的“opt”（optimization）根据具体问题而取min或max。(7)基本方程通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式，即Vk,n＝∑vj(sj,uj)，则有fk(sk)＝opt{vk(sk,uk)+fk+1(sk+1)}uk∈Dk(sk)(k＝n,n-1,…,1)递推方程fn+1(sn+1)＝0边界条件递推方程和边界条件一起称为动态规划的基本方程。可根据边界条件，从k=n开始，由后
7、向前逆推，逐步求得各阶段的最优决策和相应的最优值，最后求出f1(s1)时，就得到整个问题的最优解。此问题的基本方程为fk(sk)＝Min{dk(uk)+fk+1(sk+1)}uk∈Dk(sk)k＝6,5,4,3,2,1f7(s7)＝04.3动态规划的步骤（一）当k=6时按基本方程由后向前继续递推有:当k=5时当k=4时当k=3时当k=2时当k=1时由此可以看出，A到G的最短路长为18，路径为：A→B1→C2→D1→E2→F2→G现在把动态规划法的步骤归纳如下：(1)将所研究问题的过程划分为n
