动态规划简介_第1页
动态规划简介_第2页
动态规划简介_第3页
动态规划简介_第4页
动态规划简介_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、动态规划法简介多阶段决策过程最短路问题特点：若O-H-P-D是最短路，则H-P-D是从H到D的最短路。最短路求解过程动态规划法减少了计算量,丰富了计算结果动态规划的基本概念1.阶段:反映问题时间或空间的自然特性k;2.状态:表示在某阶段开始所处的自然状态或客观条件sk;3.决策:可作出的选择dk,允许决策集合;4.策略:决策序列(子策略);过程:状态序列(子过程);对状态要求具有无后效性,允许决策集合只与当时的状态有关;5.状态转移方程:决策对下一阶段状态的影响sk+1 =Tk(sk ,dk);收益或支出函数r=rk(sk ,dk);6.最优值函数 fk(sk );递推方程 fk(sk )=o

2、ptrk(sk ,dk)+fk+1(sk+1);kskdksk+1rk动态规划最优性原理Bellman最优性原理：作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的决策必定构成一个最优策略。换言之，最优策略的子策略总是最优的。同样，最优轨线的子轨线也是最优的。用动态规划方法解优化问题1)将问题恰当的划分阶段；2)状态变量的选择:能描述过程的演变，满足无后效性；3)确定决策变量及允许决策集合；4)写出状态转移方程和阶段效益式；5)最优值函数:是定义在全过程和所有后部子过程的函数，具有可分离性，与原问题目标相关,写出递推方程及初始条件。例 用动态规

3、划方法求如下优化问题的最优解：. 0,5s.t.3min321321232221xxxxxxxxxz例 用动态规划方法求如下优化问题的最优解：分两步：逆推确定各状态的最优值函数及最优决策规则，顺推确定最优过程及最优策略。动态规划的主要缺点是所谓的“维数灾”。且为整数。, 0,5s.t.3min321321232221xxxxxxxxxz资源分配问题例例: 某公司拟将某公司拟将50万元资金投放下属万元资金投放下属A、B、C三个部门，各三个部门，各部门在获得资金后的收益如表所示，用动态规划方法求总部门在获得资金后的收益如表所示，用动态规划方法求总收益最大的投资分配方案（投资数以收益最大的投资分配方案（投资数以10万元为单位）。万元为单位）。 投放资金（万投放资金（万元）元） 0102030405

人人文库> 全部分类> 教育资料 > 备课教案

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论