、动态规划.ppt

XI’ AN JIAOTONG UNIVERSITY XI’ AN JIAOTONG UNIVERSITY XI’ AN JIAOTONG UNIVERSITY 动态规划动态规划郭菊娥教授 ******@. 西安交通大学 2017-4-14 XI’ AN JIAOTONG UNIVERSITY XI’ AN JIAOTONG UNIVERSITY 西安交通大学郭菊娥第五章:动态规划第五章:动态规划动态规划求解动态规划求解 2动态规划应用举例动态规划应用举例 33 动态规划概念与模型动态规划概念与模型 31 XI’ AN JIAOTONG UNIVERSITY XI’ AN JIAOTONG UNIVERSITY 西安交通大学郭菊娥动态规划概念与模型动态规划概念与模型引言多阶段决策过程动态规划概念与模型动态规划概念动态规划概念与模型与模型动态规划模型动态规划建模 XI’ AN JIAOTONG UNIVERSITY XI’ AN JIAOTONG UNIVERSITY 西安交通大学郭菊娥动态规划概念动态规划概念与与模型模型————引言引言决策 x 1x 2Z u 输入决策输出决策效应第一月 x 1x 2r 1u 1第二月 x 3r 2u 2第三月 x 4r 3u 3 ?静态决策一次性决策?动态决策多阶段决策 XI’ AN JIAOTONG UNIVERSITY XI’ AN JIAOTONG UNIVERSITY 西安交通大学郭菊娥多阶段决策过程多阶段决策过程 T 1x 1x 2r 1u 1T 2x 3r 2u 2T kx kx k+1 r ku kT nx nx n+1 r nu n ……?n个决策子问题决策子问题;K称为阶段变量阶段变量?x k描述 k阶段初的状态,称为状态变量状态变量。一般把输入状态称为该阶段的阶段状态?u k的取值代表 k阶段对第 k子问题所进行的决策,称为 k k 阶段的决策变量阶段的决策变量?r k为k阶段从状况 x k出发,做决策 u k之后的后果,称为 k k阶阶段的阶段效应段的阶段效应 XI’ AN JIAOTONG UNIVERSITY XI’ AN JIAOTONG UNIVERSITY 西安交通大学郭菊娥具有无后效性的多段决策过程具有无后效性的多段决策过程 x 2T 1x 1r 1 (x 1, u 1) u 1(x 1)T 2x 3r 2 (x 2 ,u 2) u 2 (x 2)T kx kx k+1 r k (x k,u k) u k (x k)……T nx nx n+1 r n (x n,u n) u n (x n) ? X k+1=T k (x k, u k) ?系统从 k阶段往后的决策只与 k阶段系统的状态 x k 有关,而与系统以前的决策无关,则称为具有无具有无后效性的多段决策过程后效性的多段决策过程。 XI’ AN JIAOTONG UNIVERSITY XI’ AN JIAOTONG UNIVERSITY 西安交通大学郭菊娥 K K后部子过程后部子过程 T kx kx k+1 r k (x k,u k) u k (x k)…T nx nx n+1 r n (x n,u n) u n (x n) ?多段决策过程中从第 k阶段到最终阶段的过程称为k- k-后部子过程后部子过程,简称 k- k-子过程子过程 XI’ AN JIAOTONG UNIVERSITY XI’ AN JIAOTONG UNIVERSITY 西安交通大学郭菊娥动态规划模型动态规划模型? Opt 表示求优?X k是一个集合,表示 k阶段状态可能取值的范围,称为状态可能集合?U k是一个集合,表示 k阶段决策可能取值的范围,称为决策允许集合,一般来说对于不同状态,可以作的决策的范围是不同的。因此决策允许集合一般写为 U k (x k) ),( 1 1kkk nkuuuxrRopt n????????????????nk Uu Xx uxTxts kk kk kkkk~1 ),(.. 1 XI’ AN JIAOTONG UNIVERSITY XI’ AN JIAOTONG UNIVERSITY 西安交通大学郭菊娥动态规划建模动态规划建模 1 1确定阶段与阶段变量?阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的,阶段数等于多段决策过程中从开始到结束所需要作出决策的数目,阶段变量用 k表示。明确状态变量和状态可能集合 2 2 ?状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。状态变量的确定决定了整个决策过程是不是具有无后效性,因而也决定着能不能用动态规划方法来求解。状态可能集是关于状态的约束条件,因此为了求解必须正确地确定状态可能集 XI’ AN JIAOTONG UNIVER