《动态规划问题》课件.ppt

1、第四章第四章动态规划问题天马行空官方博客：http:/ 一次性决策l动态决策 多阶段决策决策x1x2Zu输入决策输出决策效应第一月x1x2r1u1第二月x3r2u2第三月x4r3u3多段决策过程多段决策过程T1x1x2r1u1T2x3r2u2Tkxkxk+!rkukTnxnxn+1rnunn个决策子问题K称为阶段变量xk描述k阶段初的状态，称为状态变量一般把输入状态称为该阶段的阶段状态。uk的取值代表k阶段对第k子问题所进行的决策，称为k阶段的决策变量rk为k阶段从状况xk出发,做决策uk之后的后果，称为k阶段的阶段效应。具有无后效性的多段决策过程具有无后效性的多段决策过程 Xk+1=Tk(x

2、k,uk)系统从k阶段往后的决策只与k阶段系统的状态xk有关,而与系统以前的决策无关，则称为具有无后效性的多段决策过程。T1x1x2r1(x1,u1)u1(x1)T2x3r2(x2,u2)u2(x2)Tkxkxk+!rk(xk,uk)uk(xk)Tnxnxn+1rn(xn,un)un(xn)K后部子过程后部子过程多段决策过程中从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程。Tkxkxk+!rk(xk,uk)uk(xk)Tnxnxn+1rn(xn,un)un(xn)动态规划模型动态规划模型Opt表示求优Xk是一个集合，表示k阶段状态可能取值的范围，称为状态可能集合。Uk是一个集合，

3、表示k阶段决策可能取值的范围，称为决策允许集合，一般来说对于不同状态，可以作的决策的范围是不同的。因此决策允许集合一般写为Uk(xk)。),(11kkknkuuuxrRoptnnkUuXxuxTxtskkkkkkkk1),(.1动态规划的建模动态规划的建模 动态规划建模确定阶段与阶段变量明确状态变量和状态可能集合。确定决策变量和决策允许集合。确定状态转移方程。明确阶段效应和目标。动态规划的建模动态规划的建模确定阶段与阶段变量阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的，阶段数等于多段决策过程中从开始到结束所需要作出决策的数目，阶段变量用k表示。明确状态变量和状态可能集合。状态变量

4、必须包含在给定的阶段上确定全部允许决策所需要的信息。状态变量的确定决定了整个决策过程是不是具有无后效性，因而也决定着能不能用动态规划方法来求解。状态可能集是关于状态的约束条件，因此为了求解必须正确地确定状态可能集。动态规划的建模动态规划的建模确定决策变量和决策允许集合。与静态问题相同，决策变量应能够反映对问题所作的决策，决策变量也应有其相应的约束条件，在建模时应明确决策允许集合Uk(xk)。确定状态转移方程。系统k阶段从状态xk出发作了决策uk(xk)之后的结果之一是系统状态的转移，这一结果直接影响系统往后的决策过程，因此必须明确状态的转移过程，即根据问题的内在关系，明确xk+1=Tk(xk,

5、uk)中的函数Tk（）。动态规划的建模动态规划的建模明确阶段效应和目标。阶段效应rk(xk,uk)是在阶段k以xk出发作了决策uk之后所产生的后果，必须明确rk与xk，uk的关系，才能构成目标函数。目标函数是由阶段效应经过某种集结而得到的，如何集结视具体问题而定，同时还应根据问题确定目标是求最大还是最小。由于在经济系统中的大多数情况下，目标的集结方法都是求和，因此，在不作说明的情况下，往后的讨论都针对目标为和的形式进行。动态规划解的概念动态规划解的概念多段决策过程中所要求解的是，从起始状态x1开始，进行一系列的决策，使目标R达到最优最优目标值 R*最优策略 使得目标达到最优的决策序列。最优路线

6、 在采取最优策略时，系统从x1开始所经过的状态序列求解动态规划模型 找到最优策略、最优路线和最优目标值。),(*2*1nuuu),(*1*2*1nxxx),(*1kkkkuxTx动态规划最优性原理动态规划最优性原理多段决策过程的特点 每个阶段都要进行决策 相继进行的阶段决策构成的决策序列 前一阶段的终止状态又是后一阶段的初始状态阶段最优决策不能只从本阶段的效应出发，必须通盘考虑，整体规划。阶段k的最优决策不应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优，即关于整个k后部子过程的最优决策。动态规划最优性原理动态规划最优性原理最优性原理 “最优策略具有的基本性质是：无论初始状态

7、和初始决策如何，对于前面决策所造成的某一状态而言，下余的决策序列必构成最优策略”。AMB动态规划最优性原理动态规划最优性原理最优性原理的含意 最优策略的任何一部分子策略，也是相应初始状态的最优策略。每个最优策略只能由最优子策略构成。显然，对于具有无后效性的多段决策过程而言，如果按照k后部子过程最优的原则来求各阶段状态的最优决策，那么这样构成的最优决策序列或策略一定具有最优性原理所提示的性质。贝尔曼函数贝尔曼函数贝尔曼函数fk(xk)：在阶段k从初始状态xk出发，执行最优决策序列或策略，到达过程终点时，整个k-子过程中的目标函数取值，称为条件最优目标函数，亦称贝尔曼函数。nkuxroptxfnk

8、iiiiuukknk,.,2,1),()(条件最优策略 多段决策过程的任一阶段状态xk的最优策略 处于条件xk时的最优策略。条件最优决策 构成条件最优策略的决策)(kkxu,1nkkuuu贝尔曼函数贝尔曼函数条件最优目标函数值fk(xk)执行条件最优策略时的目标函数值nkiiiikkuxrxf),()(条件最优路线 执行条件最优策略时的阶段状态序列),(1kkkkuxTx,11nnkkxxxx贝尔曼函数贝尔曼函数条件最优k-子策略 系统从xk出发，在k-后部子过程中的最优策略k-子过程条件最优目标函数 fk(xk)是从xk出发系统在k-后部子过程中的最优目标值，多段决策问题所求解的最优目标函数

9、值 R*=f1(x1*)动态规划基本方程 fk(xk)与fk1(xk1)之间的递推关系动态规划方法的依据是最优性原理动态规划基本方程动态规划基本方程设在阶段k的状态xk执行了任意选定决策uk后的状态是xk+1=Tk(xk,uk)。这时k-后部子过程就缩小为k+1后部子过程。根据最优性原理，对k+1后部子过程应采取最优策略，由于无后效性，k后部子过程的目标函数值为),(),(1kkkkkkkuxTfuxr),(),()(1kkkkkkkukkuxTfuxroptxfk),(1kkkkuxTx动态规划基本方程动态规划基本方程),(1kkkkuxTxnkiiiiuukkuxroptxfnk),()(

10、),(),(11nkiiiiuukkkuuxroptuxroptnkk)(),(11kkkkkuxfuxroptk动态规划基本方程动态规划基本方程),(1kkkkuxTxnkiiiikkuxrxf),()(nkiiiikkkuxruxr1),(),()(),(11kkkkkuxfuxroptk动态规划方法基本原理动态规划方法基本原理动态规划方法基本原理),(),()(1kkkkkkkukkuxTfuxroptxfk),(1kkkkuxTxrk(xk,uk)和xk+1=Tk(xk,uk)都是已知的函数求fk(xk)需要首先求关于xk的所有k+1段状态xk+1的fk+1(xk+1)逆序地求出条件最

11、优目标函数值集合和条件最优决策集合状态xk+1是由前面阶段的状态决定的用问题给定的初始条件，即可顺序地求出整个多段决策问题的最优目标函数值、最优策略和最优路线。动态规划问题求解的一般步骤动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合k=n时，动态规划基本方程是)(),()(11nnnnnunnxfuxroptxfn0)(11nnxf边界条件),()(nnnunnuxroptxfnk=n时的动态规划基本方程成为)(,()(nnnnnnxuxrxf动态规划问题求解的一般步骤动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合k=n1时，动态

12、规划的基本方程是)(),()(111111nnnnnunnxfuxroptxfn所有的fn(xn)都已经求出，因此可以根据xn=Tn-1(xn-1,un-1)就阶段n-1每个可能状态xn-1Xn-1求条件最优决策及相应的条件最优目标函数值fn1(xn1)();(111111nnnnnnXxxuxf动态规划问题求解的一般步骤动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合k=1时，动态规划的基本方程是)(),()(22111111xfuxroptxfu所有的f2(x2)都已经求出，因此可以根据x2=T1(x1,u1)就阶段1每个可能状态x1X1求条件最优决策及相应的

13、条件最优目标函数值f1(x1)();(111111Xxxuxf动态规划问题求解的一般步骤动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合)();(111111Xxxuxf),(111uxr)(22xf)();(111111nnnnnnXxxuxf),(111nnnuxr)(nnxf)();(nnnnnnXxxuxf),(nnnuxr动态规划问题求解的一般步骤动态规划问题求解的一般步骤 顺序地求出最优目标值、最优策略和最优路线若x1已知，则)(11*11xfoptRXx)(*11xf)(11*xfR)()(111*1xuxu阶段1的条件最优决策就是阶段1的关于整个过

14、程的最优决策若x1未知)()(*11*1*1xuxu动态规划问题求解的一般步骤动态规划问题求解的一般步骤顺序地求出最优目标值、最优策略和最优路线)(11*11xfoptRXx)(*11xf*1x)()(*1*1*11xuxu),(*1*11*2uxTx)()(*2*2*22xuxu)()(*1*1*11nnnnxuxu),(*1*11*nnnnuxTx)()(*nnnnxuxu),(*1nnnnuxTx),(*2*22*3uxTx 动态规划四大要素、一个方程动态规划四大要素、一个方程五个关键因素 四大要素、一个方程：状态变量及其可能集合决策变量及其允许集合状态转移方程阶段效应动态规划基本方程：

15、),(1kkkkuxTx),(kkkuxr),(),()(1kkkkkkkukkuxTfuxroptxfk动态规划应用举例动态规划应用举例-最短路问题例 某旅行者希望从s地起到t地，其间的道路系统如图41所示，图上圆圈表示途径的地方，称为节点，连结两地的箭线表示道路，其上的数字表示该段道路长度，箭头表示通行的方向。试求s到t的最短路。adbetcfs9757845646547图4-1动态规划应用举例动态规划应用举例-最短路问题adbetcfs9757845646547第一阶段第一阶段 第二阶段第二阶段 第三阶段第三阶段划分阶段划分阶段 k=1,2,3 代表三个阶段代表三个阶段动态规划应用举例动

16、态规划应用举例-最短路问题adbetcfs9757845646547状态变量状态变量xk取为取为k阶段所在地，则有：阶段所在地，则有：,2211cbaXxsXx,4433tXxfedXx动态规划应用举例动态规划应用举例-最短路问题adbetcfs9757845646547k阶段决策是决定下一步走到哪里，阶段决策是决定下一步走到哪里，uk(xk)取为下一步的所在点。取为下一步的所在点。,)(11cbasUu,)()(22fdaUau,)()(22edbUbu,)()(22fedcUcu33tUu动态规划应用举例动态规划应用举例-最短路问题逆序求条件最优目标函数集和条件最优决策集由于第3阶段末已到

17、达t，往后的距离自然是零，因此f4(t)=0对3阶段所有可能的状态X3=d,e,f计算f3()如下)(),(min)(4433333xfudrdfUutdutftdr)(5)(),(min343)(),(min)(4433333xfudrefUuteuter)(70),(min33)(),(min)(4433333xfufrffUutfutfr)(40),(min33动态规划应用举例动态规划应用举例-最短路问题逆序求条件最优目标函数集和条件最优决策集也可以用表格方法计算如下t/tF3()U3()def5+07+04+0574tttr3(x3,u3)+f4(x4)f3(x3)u3(x3)动态规划

18、应用举例动态规划应用举例-最短路问题逆序求条件最优目标函数集和条件最优决策集对2阶段所有可能的状态X2=a,b,c计算f2()如下)(),(min)(3322)(222xfuarafaUu)(),(min3322,2xfuarfdu)(),()(),(min3232fffardfdarfau)(84457min2)(),(min)(3322)(222xfubrbfbUu)(),()(),(min3232efebrdfdbrdbu)(107655min2动态规划应用举例动态规划应用举例-最短路问题逆序求条件最优目标函数集和条件最优决策集对2阶段所有可能的状态X2=a,b,c计算f2()如下)()

19、,(min)(3322)(222xfucrcfcUu)(),()(),()(),(min323232fffcrefecrdfdcrdcu)(9467554min2动态规划应用举例动态规划应用举例-最短路问题逆序求条件最优目标函数集和条件最优决策集也可以用表格方法计算如下d/de/ef/fF2()U2()abc7+55+54+56+75+74+46+48109fddf2(x2)u2(x2)r2(x2,u2)+f3(x3)动态规划应用举例动态规划应用举例-最短短问题逆序求条件最优目标函数集和条件最优决策集对1阶段所有可能的状态X1=s计算f1()如下)(),(min)(2211)(111xfusrsfsUu)(),()(),()(),(min212121cfcsrbfbsrafasrcsu)(169710889min1a/ab/bc/cF2()U2()s9+88+107+916f动态规划应用举例动态规划应用举例-最短路问题顺序求最优策略、最优路线和最优目标函数值16)(11*11xfoptRXxsx*1csu)(*1cx*2dcu)(*2tx*4tdu)(*3dx*3动态规划应用举例动态规划应用举例-最短路问题16)(11*11xfoptRXxsx*1csu)(*1cx*2dcu)(*2tx*4tdu)(*3dx*3