1、 4-2 4-2 动态规划的动态规划的 基本概念和模型基本概念和模型 阶段和阶段变量；阶段和阶段变量；状态和状态变量；状态和状态变量；决策、决策变量和决策序列；决策、决策变量和决策序列；状态转移方程；状态转移方程；阶段效应和目标函数等。阶段效应和目标函数等。把所研究的把所研究的多段决策过程多段决策过程恰当地划分为若恰当地划分为若干个干个相互独立又相互联系的部分相互独立又相互联系的部分，每一个部，每一个部分就称为一个分就称为一个阶段阶段。事实上一个阶段也就是。事实上一个阶段也就是需要作出一个决策需要作出一个决策的子问题部分。的子问题部分。通常阶段是按照过程进行的时间和空间上通常阶段是按照过程进行
2、的时间和空间上的先后顺序划分的，并用的先后顺序划分的，并用表示。表示。等于多段决策过程中从开始到结束等于多段决策过程中从开始到结束所需要作出所需要作出，划分阶段的目的是划分阶段的目的是便于求解。便于求解。一次性决策一次性决策多阶段决策多阶段决策 状态状态是描述系统状况所必须的信息。一是描述系统状况所必须的信息。一般定义为某一个般定义为某一个阶段的初始点、初始位置阶段的初始点、初始位置或初始情况或初始情况。状态变量必须状态变量必须包含包含在给定的阶段上确定在给定的阶段上确定全部允许决策全部允许决策所需要的信息所需要的信息，阶段阶段k k的状的状态表示为态表示为x xk k。比如：在最短路问题中，
3、状。比如：在最短路问题中，状态就是网络中的各个节点。态就是网络中的各个节点。状态变量的取值有一定的允许范围，状态变量的取值有一定的允许范围，称为称为状态可能集状态可能集。状态可能集可以是状态可能集可以是一个离散取值的集合，也可以是一个一个离散取值的集合，也可以是一个连续的区间，视所给问题而定。连续的区间，视所给问题而定。状态可能集是关于状态的约束条件。状态可能集是关于状态的约束条件。状态可能集用相应阶段状态状态可能集用相应阶段状态x xk k的大写的大写字母字母X Xk k表示，其中表示，其中x xk k X Xk k 3.3.决策、决策变量和决策序列决策、决策变量和决策序列 决策决策就是决策
4、者从本阶段出发对下一阶段就是决策者从本阶段出发对下一阶段状态的状态的选择选择。多段决策过程的发展是用各个阶段的状态多段决策过程的发展是用各个阶段的状态演变来描述的。因为用状态描述的过程具有演变来描述的。因为用状态描述的过程具有无后效性无后效性，因此在进行阶段决策时，因此在进行阶段决策时，只须根只须根据当前的状态而无须考虑过去的历史据当前的状态而无须考虑过去的历史。在阶。在阶段段k k如果给出了决策变量如果给出了决策变量u uk k随状态变量随状态变量 x xk k变变化的函数，称为决策函数，表示为化的函数，称为决策函数，表示为u uk k(x(xk k)。决策变量的允许取值范围，称为决策变量的
5、允许取值范围，称为允许决策允许决策集合集合。允许决策集合是决策的约束条件。允许决策集合是决策的约束条件。u uk k的允许决策集合表示为的允许决策集合表示为U Uk k，u uk k U Uk k。U Uk k要根据要根据相应的状态可能集相应的状态可能集X Xk k并结合具体问题来确定。并结合具体问题来确定。n21u,u,u 决策序列又叫策略决策序列又叫策略。策略有。策略有和和之分。全过程策略是整个之分。全过程策略是整个n n段段决策过程中依次进行的决策过程中依次进行的n n个阶段决策构成个阶段决策构成的决策序列，简称策略，表示为：的决策序列，简称策略，表示为：从阶段从阶段k k到阶段到阶段n
6、 n依次进行的阶段决策构依次进行的阶段决策构成的决策序列称为成的决策序列称为k-k-子策略子策略，表示为：，表示为：n1kku,u,u 当当k=1k=1时，时，k-k-子策略就是全过程策略。子策略就是全过程策略。在在n n段决策问题中，各阶段的状态可能集段决策问题中，各阶段的状态可能集和决策允许集确定了决策的允许范围。和决策允许集确定了决策的允许范围。特别地，过程的初始状态不同，决策和策特别地，过程的初始状态不同，决策和策略也就不同，即策略是初始状态的函数。略也就不同，即策略是初始状态的函数。多阶段过程的发展就是用阶段状态的相多阶段过程的发展就是用阶段状态的相继演变来描述的。对具有无后效性的多
7、段继演变来描述的。对具有无后效性的多段决策过程，系统由从阶段决策过程，系统由从阶段k k到阶段到阶段k+1k+1的状的状态转移方程表示为：态转移方程表示为：1(,()kkkkkxT x ux1k 1()kkkxux1()kkkkxaub xu 即即 阶段的状态完全由阶段的状态完全由k k 阶段的状态和决阶段的状态和决策策u uk k 确定，与系统过去的状态确定，与系统过去的状态 x x1 1,x,x2 2,x,xk-k-1 1及其决策及其决策u u1 1(x(x1 1)，u u2 2(x(x2 2)，,u,uk-1k-1(x(xk-1k-1)无关。无关。如如 ,T Tk k(x(xk k,u,
8、uk k)称为称为或或。变换。变换函数可以分为确定型和随机型两种类型，据函数可以分为确定型和随机型两种类型，据此形成确定型动态规划和随机型动态规划。此形成确定型动态规划和随机型动态规划。5.5.阶段效应和目标函数阶段效应和目标函数 多段决策过程中，在阶段多段决策过程中，在阶段k k的状态的状态x xk k执行决执行决策策u uk k ，不仅带来系统状态的转移，而且也必，不仅带来系统状态的转移，而且也必然带来对目标函数的影响。然带来对目标函数的影响。阶段效应就是执阶段效应就是执行阶段决策时所带来的目标函数的增量行阶段决策时所带来的目标函数的增量。在具有无后效性的多段决策过程中，阶在具有无后效性的
9、多段决策过程中，阶段效应完全由阶段段效应完全由阶段k k的状态的状态x xk k和决策和决策u uk k决定，决定，与阶段以前的状态和决策无关，表示为与阶段以前的状态和决策无关，表示为 )u,(xrkkk 多阶段决策过程关于多阶段决策过程关于目标函数的总目标函数的总效应是由各阶段的阶段效应累积形成效应是由各阶段的阶段效应累积形成。适于动态规划求解的问题的目标，必适于动态规划求解的问题的目标，必需具有需具有关于阶段效应的可分离形式、关于阶段效应的可分离形式、递推性和对于变元递推性和对于变元R RK+1K+1的严格单调性的严格单调性。k-k-子过程的目标函数可以表示为子过程的目标函数可以表示为:)
10、u,(xr)u,(xr)u,(xr )u,x,u,x,u,R(xRnnn1k1k1kkkknn1k1kkkk 其中其中 表示某种运算，可以是加、减、乘、表示某种运算，可以是加、减、乘、除、开方等。经济管理领域中最常见的目标除、开方等。经济管理领域中最常见的目标函数取阶段效应之和的形式，即：函数取阶段效应之和的形式，即：nkiiiinn1k1kkkk)u,(xr)u,x,u,x,u,R(xR 阶段有四个阶段,做4次决策阶段阶段1 1:决定由s到a,b,c:状态变量x1取为阶段1所在地：阶段1的决策是下一步走到哪里，取为下一步的所在点:阶段阶段2 2:决定由a,b,c到d,e,f:状态变量x2取为
11、阶段2所在地：阶段2的决策是下一步走到哪里，取为下一步的所在点:()kkux11 xXs11(),uU sa b c()kkux22,xXa b c222222()(),()(),()(),u aUad fu bUbd e fu cUcd f决策允许集合状态可能集合决策允许集合状态可能集合阶段阶段3 3:决定由d,e,f到h,g:状态变量x3取为阶段3所在地：阶段3的决策是下一步走到哪里，取为下一步的所在点:阶段阶段4 4:决定由h,g到t:状态变量x4取为阶段4所在地：阶段4无需选择，取为下一步所在点 t()kkux33,xXd e f333333()(),()(),()()u dU dh
12、gu eU eh gufUfg()kkux44,xXg h4444()()()()u dUdtu eUet决策允许集合状态可能集合决策允许集合状态可能集合状态转移方程状态转移方程根据xk和uk的选取方法可知：1(,)kkkkkxT x uuk+1阶段的状态是在k阶段状态的条件下，经过决策uk选择的结果。uk本身是下一步所到达节点，它同时也就是k+1阶段的状态。阶段效应阶段效应由阶段k的状态xk经过决策uk到达下一阶段状态xk+1的直接结果是选择了从xk到xk+1所经过的路程的长度。总的目标函数是总路程最短，各阶段所选择的路程的总和就是总目标函数R。决策变量选为终止位置：cbavu,11；fed
13、v,2 阶段阶段从起点到终点可以划分为从起点到终点可以划分为4个阶段；个阶段；sx 1；cbax,2；fedx,3；ghx,4；tx 5 二、多阶段决策过程的数学模型二、多阶段决策过程的数学模型（DPDP的建模）的建模）1 建模条件：建模条件：恰当地划分问题的阶段，：恰当地划分问题的阶段，把问题化为多阶段决策过程；把问题化为多阶段决策过程；(详见下页）详见下页）动态规划基本方程动态规划基本方程 （DPDP基本方程）基本方程）四四 个个 条条 件件（1 1）状态变量和状态可能集状态变量和状态可能集：x xk kXXk k能描述过程的演变特征；能描述过程的演变特征；满足无后效性满足无后效性指系统从
14、某个阶段往后的指系统从某个阶段往后的发展，完全由本阶段所处的状态及其往后的发展，完全由本阶段所处的状态及其往后的决策决定，与系统以前的状态和决策无关。决策决定，与系统以前的状态和决策无关。即过程即过程过去的历史只能通过当前的状态去影过去的历史只能通过当前的状态去影响未来的发展响未来的发展，当前状态是未来过程的初始，当前状态是未来过程的初始状态。状态。例子：负指数分布具有无记忆性例子：负指数分布具有无记忆性 Ps+t|s=Pt=ePs+t|s=Pt=e-t-t可知性可知性各阶段状态变量的值直接或间接各阶段状态变量的值直接或间接均为已知均为已知。（2 2）决策变量及各阶段的允许决策集合；）决策变量
15、及各阶段的允许决策集合；u uk kUUk k （3 3）能写出状态转移方程；）能写出状态转移方程；x xk+1k+1=T=Tk k(x(xk k,u,uk k)（4 4）能根据题意列出）能根据题意列出阶段效应和目标函数；阶段效应和目标函数；11,(,)nnkkkkuuopt Rr x u 式中式中optopt指最优化指最优化,根据问题要求取根据问题要求取maxmax或或minmin。11,1(,)(,).1,2,nnkkkkuukkkkkkkkopt Rr x uxT x uxXstuUkn 11,(,)nnkkkkuuopt Rr x u 1(,)kkkkxT x ukkxXkkuUDP模
16、型的数学表达式模型的数学表达式：求解结果要求：求解结果要求：*n*2*1u,u,u 求出求出，即最优决策序列；，即最优决策序列；其中其中,;1),(1nkuxTxkkkk n1k*k*kk*)u,(xrR 求出求出:()()*1n*k*2*1x,x,x,x 求出求出，即执行最优策略时的最优，即执行最优策略时的最优状态序列：状态序列：n)1(k )(kkxfkx亦称亦称条件最优目标函数条件最优目标函数)。该该函数是为了便于应用最优性原理，建立函数是为了便于应用最优性原理，建立动态规划基本方程所定义的动态规划基本方程所定义的辅助函数辅助函数 ，是在阶段是在阶段k k从初始状态从初始状态 出发，执行
17、最优决出发，执行最优决策序列或策略到达过程终点时的目标函数取策序列或策略到达过程终点时的目标函数取值。值。对于目标函数是阶段效应之和的多段决策对于目标函数是阶段效应之和的多段决策过程而言过程而言:为了将关于多段决策过程的任一阶段状为了将关于多段决策过程的任一阶段状态态 的最优策略和最终的最优策略相区别，的最优策略和最终的最优策略相区别，称前者为称前者为，意即相对于状态，意即相对于状态 时的最优策略。构成条件最优策略的决策时的最优策略。构成条件最优策略的决策称为称为。阶段。阶段k k处于状态处于状态 的条件最优决策表示为的条件最优决策表示为 ，简记，简记为为 ，相应的条件最优策略表示为，相应的条
18、件最优策略表示为:n1kku,u,u kxkxkx)(kkxuku 执行条件最优策略时的阶段状态序列称执行条件最优策略时的阶段状态序列称为为条件最优路线条件最优路线，表示为，表示为 条件最优目标函数值条件最优目标函数值亦称执行条件最优亦称执行条件最优策略时的目标函数值，因此策略时的目标函数值，因此1nn1kkx,x,x,xk 1kkkxT(x,u),k 1n.其中其中,nkiiii)u,(xr)(xfkk2.2.最优化原理最优化原理 最优策略最优策略具有的具有的基本性质基本性质是：是：；3.DP3.DP基本方程基本方程 包括包括主体部分主体部分和和边界条件边界条件两个部分。特别，当两个部分。特
19、别，当目标函数为阶段效应求和形式时，基本方程为目标函数为阶段效应求和形式时，基本方程为)1,1,(0)()(),()(1111nnkxfxfuxrxfnnkkkkkukkoptk 0)(1,2,1)(),(),()(1111nnkkkkknkiiiikkxfnkxfuxrOptuxroptxf 四、动态规划的分类四、动态规划的分类1 1、按决策的特性分、按决策的特性分a a、时间多段决策过程时间多段决策过程b b、空间多段决策过程空间多段决策过程2、按允许决策集合的连续或不连续分、按允许决策集合的连续或不连续分a a、连续多段决策过程连续多段决策过程b b、离散多段决策过程离散多段决策过程3.
20、3.按构成决策序列的决策数目有限或无限分按构成决策序列的决策数目有限或无限分 a a、有限多段决策过程有限多段决策过程 b b、无限多段决策过程无限多段决策过程 按状态变化的确定或随机性分按状态变化的确定或随机性分 a a、确定型多段决策过程确定型多段决策过程 b b、随机性多段决策过程随机性多段决策过程按决策序列与时间起点的关系分按决策序列与时间起点的关系分 a a、定常定常(与时间起点无关与时间起点无关)多段决策过程多段决策过程 b b、非定常多段决策过程非定常多段决策过程 实际的多段决策问题，常常归结实际的多段决策问题，常常归结为它们的各种复合情况。为它们的各种复合情况。今后只限于今后只限于定常的，确定性的、定常的，确定性的、有限的多段决策过程有限的多段决策过程的讨论。的讨论。
