拓展模块_Ch05.doc
《拓展模块_Ch05.doc》由会员分享,可在线阅读,更多相关《拓展模块_Ch05.doc(7页珍藏版)》请在文库网上搜索。
1、天天文档在线 联系qq:744421982Ch5 动态规划Dynamic Programming动态规划是最优化理论的一个分支,是求解多阶段决策过程的基本方法之一。所谓多阶段决策过程是指这样的一类决策问题:由问题的特性可将过程按时间、空间等标志分为若干相互联系又相互区别的阶段,在它的每一阶段都需要做出决策,从而使整个过程达到最好的效果。因此各个阶段的决策选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就得到了一个决策序列,因而也就决定了整个过程的一条活动路线。这样一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题就成为多阶段决策问题。动态规
2、划问题的基本特征:1、问题具有多阶段决策的特征。阶段可以按时间划分,也可以按空间划分。2、每一阶段都有相应的“状态”与之对应,描述状态的量称为“状态变量”。3、每一阶段都面临一个决策,选择不同的决策将会导致下一阶段不同的状态,同时,不同的决策将会导致这一阶段不同的目标函数值。4、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题,各子问题与原问题具有完全相同的结构。能否构造这样的递推归结,是解决动态规划问题的关键。这种递推归结的过程,称为“不变嵌入”。动态规划的基本概念:阶段k:表示决策顺序的离散的量,阶段可以按时间或空间划分。状态Sk:能确定地表示决策过程当前特征的量。状态
3、可以是数量,也可以是字符,数量状态可以是连续的,也可以是离散的。状态变量xk:表示每一状态可以取不同值的变量。决策(Decision)dk:从某一状态向下一状态过度时所做的选择。决策是所在状态的函数,记为dk(xk)。决策允许集合Dk(xk):在状态xk下,允许采取决策的全体。状态转移方程xk+1=Tk(xk,dk):某一状态以及该状态下的决策,与下一状态之间的函数关系。阶段指标函数vk(xk,dk):从状态xk出发,选择决策dk所产生的第k阶段指标。过程指标函数V(xk,dk,dk+1,dn):从状态xk出发,选择决策dk,dk+1,dn所产生的过程指标。动态规划要求过程指标具有可分离性,即
4、Vk,n(xk, dk,dk+1,dn)=vk(xk,dk)+Vk+1(xk+1,dk+1,dn)称指标具有可加性,或Vk,n(xk, dk,dk+1,dn)=vk(xk,dk)Vk+1(xk+1,dk+1,dn)称指标具有可乘性。最优指标函数fk(xk):从状态xk出发,对所有的策略Pk,n,过程指标Vk,n的最优值,即对于可加性指标函数,上式可以写为上式中“opt”表示“max”或“min”。对于可乘性指标函数,上式可以写为以上式子称为动态规划最优指标的递推方程,是动态规划的基本方程。终端条件:为了使以上的递推方程有递推的起点,必须要设定最优指标的终端条件,即确定最后一个状态n下最优指标f
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 拓展 模块 _Ch05