《运筹学》胡运权清华版-7-01动态规划_第1页
《运筹学》胡运权清华版-7-01动态规划_第2页
《运筹学》胡运权清华版-7-01动态规划_第3页
《运筹学》胡运权清华版-7-01动态规划_第4页
《运筹学》胡运权清华版-7-01动态规划_第5页
已阅读5页，还剩18页未读， 继续免费阅读

下载本文档

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

文档简介

第七章动态规划,多阶段决策问题动态规划的基本概念和基本原理动态规划模型的建立逆推解法与顺推解法动态规划应用举例,第一节多阶段决策问题,多阶段决策问题,在实际生产经营活动中，存在着一类将过程划分为若干个相互联系的阶段，而每个阶段都需要做出决策，并且一个阶段的决策确定后，常影响下一阶段的决策，即多阶段决策问题。,在这类多阶段决策问题中，整个问题的各个阶段所确定的决策构成一个决策序列，通称为策略。对应于一个策略，就有确定活动效果，且可用数量指标来衡量。因此多阶段决策问题就需要在允许选择的那些策略中选择最优策略，使在预定的标准下达到最好的效果。,在多阶段决策问题中，阶段往往可用时段来表示，随着时间的推移，在每一时段上选择最恰当的决策，以期在整体上达到最优。动态规划是解决多阶段决策过程的方法。,5阶段决策问题,例4.最短路问题,如何求解最短路问题？,（1）最短路问题的特点：若AB1C2D2E2F是从A到F的最短路，则必有B1C2D2E2F是从B1到F的最短路，C2D2E2F是从C2到F的最短路，D2E2F是从D2到F的最短路，E2F是从E2到F的最短路即：若某一点在最优路线上，那么从那一点到终点的最短路线也在最优路线上。,（2）解决最短路问题的方法：假设每一个点都在最优路线上，然后做相关计算。具体地：从最后阶段的两个始点E1和E2开始，由后向前，计算每一个点到F的最短路线，直到结点A，这时找到A到F的最短路。,最短路问题的求解,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,5,4,2,3,6,8,7,7,1,2,4,5,7,5,12,10,8,9,注：同时得到所有顶点到终点最短路。,用动态规划求解最短路问题的思路将大问题分成结构相似的小问题，递推求解。,最短路问题：,子问题1在第5阶段应怎样走，使得第5阶段初各起点E1、E2到终点F的路长最短？,子问题2根据上一步的结果，在第4阶段应怎样走，使得第4阶段初各起点D1、D2、D3到终点F的路长最短？,子问题3根据上一步的结果，在第3阶段应怎样走，使得第3阶段初各起点C1、C2、C3、C4到终点F的路长最短？,子问题4根据上一步的结果，在第2阶段应怎样走，使得第2阶段初各起点B1、B2到终点F的路长最短？,子问题5根据上一步的结果，在第1阶段应怎样走，使得第1阶段初起点A到终点F的路长最短？即为所求！,例:W先生每天驾车去公司上班。如图，W先生的住所位于A，公司位于F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。,A3B14C13D1,4532,B22C23D24E1,1234,C34D35E22F,A,B1,B2,C1,C2,C3,D1,D2,D3
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论