《动态最优化第12讲 动态规划的扩展形式》由会员分享，可在线阅读，更多相关《动态最优化第12讲 动态规划的扩展形式（32页珍藏版）》请在金锄头文库上搜索。
1、动态最优化方法 第12讲 动态规划的扩展形式 第十二讲 动态规划的扩展形式 扩展形式：扩展形式： 1. 无限期动态规划无限期动态规划 2. 随机动态规划随机动态规划 3. 连续动态规划连续动态规划 第十二讲 动态规划的扩展形式 （一）无限期动态规划 例子：机器负荷问题。例子：机器负荷问题。 高？才使产品总产量达到最同负荷下工作的数量， 好机器在两种不始时，如何重新分配完长期规划，使在每年开 。要求制定一个机器数量为：假定开始时拥有完好的 。从而年完好率为： 率为：。低负荷下机器年折旧的关系为：数量 和投入生产的机器产品产量）在低负荷下生产时，（ ：从而机器的年完好率为。此时机器的折旧率为 的关
2、系为：和投入生产的机器数量量负荷下生产时，产品产 ）在高产。（两种不同负荷下进行生某种机器可以在高、低 1000 90 , 1 . 05 2; 70 , 30:8 1 0 2222 2 111 11 x .b usu s.a .us us （一）无限期动态规划 1 0 , 0 1 ,n 58, 9 . 07 . 0 0 ; :210 n k kkkn kkkkkk kkkk kkkkkk kk k k uxvV uxuuxvk uxux xuuxDu ux kuk x，,，k 个年度的总产量： 年度产量：第 状态转移方程： 数量。其中：在低负荷下生产的机器 为该年度中分配机器数量。则分配在高负
3、荷下生产的 年度中：表示第决策变量数量年度初拥有的完好机器第 表示；状态变量为变量设以年度为阶段，阶段 建立该问题的动态规划方程组： 第十二讲 动态规划的扩展形式 （一）无限期动态规划 第十二讲 动态规划的扩展形式 0 0 , 1 , 2 , 1 9 . 07 . 058 , , ,1 1 1 121, , 1 NN kkkkkkk xDu kk kkkkkkk xu kk nkkkknk uu kk kkk xf Nk uxufuxuMaxxf N n uxTfuxvoptxf uuuuxVoptxf n- nxxf kkk kk nk 态规划基本方程组：是有限制，此问题的动若 ，满足递推关
4、系： 有：品产量（最优值函数）年度末）这段期间的产（第 年度开始方案到第出发采用最优负荷分配表示由令 基本方程组： （一）无限期动态规划 第十二讲 动态规划的扩展形式 需检验此极限的存在性 产量（目标函数）为：案问题。无限过程的总 过程的最优方可以提出对整个无限期制定负荷分配方案时， 的终止期，在去，如果生产没有预定分配可以无限期进行下 1 0 , 0 ,limlim n k kkk n n n uxvV 扩展到无限期： （一）无限期动态规划 第十二讲 动态规划的扩展形式 检验目标函数的收敛性： 存在所以，目标函数的极限 故： 而： 略，都有，对任意选取的允许策本例中，由于对所有的 00 1
5、0 0, 0 1 0 0 1 0 , 0 0 01111 80 9 . 01 1 89 . 0lim8lim 9 . 08, 9 . 0883558,0 9 . 09 . 09 . 07 . 0 0 xxxV xuxvV xxuxuxuuxv xxuxux n n k k n n n n k k n k kkkn k kkkkkkkkk n nnnnn （一）无限期动态规划 第十二讲 动态规划的扩展形式 pVoptpVPp V kV xDkxuxu xDxD uxTx k Pp n n k kk kk kkkk * , 0 , 0 1100 00 1 , lim 03 , 1, 2 ,1 ,
6、0 3 使得：最优策略 意义在于求限期决策过程的最优化上述三个条件成立，无 存在。极限 策略，有意义，且对所有允许对所有）目标函数（ 非空；使得对所有允许策略 非空，则存在有意义，而且设）允许决策集合（ 有意义；）状态转移方程（ 有：条件，即对所有 个须先满足策过程的最优化问题，对于定义一个无限期决 （一）无限期动态规划 第十二讲 动态规划的扩展形式 平稳决策过程： 过程。则该过程叫做平稳决策 及并可以分别表示为： 无关，都与阶段序数以及报酬函数 状态转移方程，允许策略集合决策变量 段状态变量如果它的第对于多阶段决策过程， , , , , uxvuxTxDxux kuxvuxT xDu xk
7、kkkkkk kkk k 表示。平稳策略，用单一函数 则这种策略称为组成，即函数 是由同一列如果构成策略的函数序 xu xuxuxu xuxu , , 1100 （一）无限期动态规划 第十二讲 动态规划的扩展形式 平稳无限期决策过程的基本方程： 的子策略。 是其后部出发的策略，是由其中： 或者： 存在，故得：时，因为当 为：段子过程中的目标函数，前由于对任一 0000 00000000 2100000100 , 0 1 1 000 1 0 , 0 , , , lim , 0 uxTpxxp uxTpuxTVuxvxpxV uuuxTVuxvuuxV Vn uxvuxvuxvV nn n n k
8、k n k kkk n k kn （一）无限期动态规划 第十二讲 动态规划的扩展形式 平稳无限期决策过程的基本方程： xfuxvoptxf xpxVoptxf xpxVoptuxvoptxpxV xp uxTxuuxx xDu xp xpxDu , , , , , , * * 00 的基本方程：则平稳无限期决策过程 令最优值函数为： 充要条件是下式成立： 是最优策略的的允许策略则平稳无限期决策过程 ，且令于对于平稳决策过程，由 （二）随机动态规划 第十二讲 动态规划的扩展形式 ）便是一个随机过程。（具有随机性。 影响，由于受许多随机因素的年的年降水量如：某地第 。随时间演变的随机现象随机过程：
9、研究对象是 , 2 , 1nx xn n n 随机过程与随机过程的动态规划： kkkkk k xuxTx x , , 1 1 方程：状态转移方程是个随机 变量，记为：下一阶段状态是个随机 数来描述。某个已知的概率分布函是完全确定的，只能用 定过程那样决策产生的状态不像确随机动态规划问题：由 （二）随机动态规划 第十二讲 动态规划的扩展形式 求解确定过程的动态规划问题（顺推过程例子）： njUu nkxuxTxTS uvVMax jj kkkkk n j jj , 2 , 1, , 3 , 2, : 1 1 求解 nkxuxTfuvMaxxf uvMaxxf kkkkkkk Uu kk Uu k
10、k , 3 , 2, : 1 1111 11 求解的递推关系 （二）随机动态规划 第十二讲 动态规划的扩展形式 求解随机过程的动态规划问题： 望。表示随机变量的数学期。期望收益的形式 值或变量，目标函数用期望目标值因此也是个随机 ，状态转移方程为：假设状态转移是随机的 E : , 1 VE xuxTx kkkkk n i ii yfyyE ydFydyyyfyE yFyfy 1 , 学期望：对于离散分布密度，数 学期望：对于连续分布情形，数 分布函数为，概率密度函数为若随机变量为 （二）随机动态规划 第十二讲 动态规划的扩展形式 njUu nkxuxTxTS uxvEuvEVMax jj kk
11、kkk n j jjj n j jj , 2 , 1, , 3 , 2, , 1 1 1 1 题转变为随机形式：把上述确定动态规划问 求解随机过程的动态规划问题： （二）随机动态规划 nk uxxdFxfuxvEMax xfuxvEMaxxf uxxdFuxvMaxxf kkkkkkkk Uu kkkkk Uu kk Uu kk kk , 3 , 2 , , , 1111 111 10110111 11 解：对于连续函数来说，求 求解随机过程的动态规划问题： 第十二讲 动态规划的扩展形式 （二）随机动态规划 第十二讲 动态规划的扩展形式 1, 2 , 1, 10 , 1 1 111 n k k
12、k n k kkkkkk Uu kk pskp pxfuxvMaxxf kk 其中， 离散情形，求解： 求解随机过程的动态规划问题： （二）随机动态规划 无限期平稳随机决策过程（倒推过程例子）： 第十二讲 动态规划的扩展形式 给定 0 1 0 , 2, 1 , 0, , x txuxTxTS uxvEMax kkkkk k kk kkkkktt u ktt u t xxuxTEuxv xVEuxvxV t t , ,max ,max 1 尔曼方程）：动态规划基本方程（贝 （三）连续型动态规划 第十二讲 动态规划的扩展形式 的某一函数表示终端状态其中： （状态转移方程） ：假设存在如下规划问题 TxTTxS xx uxtf dt dx TS TTxSdtuxtFJMax T tu , 0 , , 0 0 求解。也可以用动态规划方法 论求解，式，可以用最优控制理目标函数为连续时间形 TTxSTxTV xxuxtf dt dx TTxSdtuxtFMaxxtV t T tu , 0, , 0 00 0 0 显然： 受约束于： 出发的值函数：定义从 （三）连续型动态规划 第十二讲 动态规划的扩展形式
