1、运筹学动态规划动态规划的概念与模型l 静态决策 一次性决策l 动态决策 多阶段决策决策x1 x2Zu输入 决策输出决策效应第一月x1 x2r1u1第二月x3r2u2第三月x4r3u3多段决策过程T1x1 x2r1u1T2x3r2u2Tkxk xk+!rkukTnxn xn+1rnun n个决策子问题K称为阶段变量xk描述 k阶段初的状态，称为状态变量一般把输入状态称为该阶段的阶段状态。uk的取值代表 k阶段对第 k子问题所进行的决策，称为 k阶段的决策变量rk为 k阶段从状况 xk出发 ,做决策 uk之后的后果，称为 k阶段的阶段效应。 具有无后效性的多段决策过程Xk+1=Tk (xk, uk
2、)系统从 k阶段往后的决策只与 k阶段系统的状态 xk有关 ,而与系统以前的决策无关，则称为具有无后效性的多段决策过程。 T1x1 x2r1 (x1, u1)u1(x1)T2x3r2 (x2 ,u2)u2 (x2)Tkxk xk+!rk (xk,uk)uk (xk)Tnxn xn+1 rn (xn,un)un (xn)K后部子过程多段决策过程中从第 k阶段到最终阶段的过程称为 k-后部子过程，简称 k-子过程。 Tkxk xk+!rk (xk,uk)uk (xk)Tnxn xn+1rn (xn,un)un (xn)动态规划模型Opt表示求优Xk是一个集合，表示 k阶段状态可能取值的范围，称为状
3、态可能集合。Uk是一个集合，表示 k阶段决策可能取值的范围，称为决策允许集合，一般来说对于不同状态，可以作的决策的范围是不同的。因此决策允许集合一般写为 Uk(xk)。 动态规划的建模动态规划建模 确定阶段与阶段变量 明确状态变量和状态可能集合。 确定决策变量和决策允许集合。 确定状态转移方程。 明确阶段效应和目标。动态规划的建模 确定阶段与阶段变量阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的，阶段数等于多段决策过程中从开始到结束所需要作出决策的数目，阶段变量用 k表示。 明确状态变量和状态可能集合。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。状态变量的确定决定了
4、整个决策过程是不是具有无后效性，因而也决定着能不能用动态规划方法来求解。状态可能集是关于状态的约束条件，因此为了求解必须正确地确定状态可能集。动态规划的建模 确定决策变量和决策允许集合。与静态问题相同，决策变量应能够反映对问题所作的决策，决策变量也应有其相应的约束条件，在建模时应明确决策允许集合 Uk(xk)。 确定状态转移方程。系统 k阶段从状态 xk出发作了决策 uk(xk)之后的结果之一是系统状态的转移，这一结果直接影响系统往后的决策过程，因此必须明确状态的转移过程，即根据问题的内在关系，明确 xk+1=Tk(xk,uk)中的函数 Tk（ ）。动态规划的建模 明确阶段效应和目标。阶段效应 rk(xk,uk)是在阶段 k以 xk出发作了决策 uk之后所产生的后果，必须明确 rk与 xk， uk的关系，才能构成目标函数。目标函数是由阶段效应经过某种集结而得到的，如何集结视具体问题而定，同时还应根据问题确定目标是求最大还是最小。由于在经济系统中的大多数情况下，目标的集结方法都是求和，因此，在不作说明的情况下，往后的讨论都针对目标为和的形式进行。
