下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、多阶段决策过程最优化问题动态规划的基本模型在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系 的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各 个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个 阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线。这种 把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种 问题称为多阶段决策最优化问题。【例题1】最短路径问题。图中给出了一个地图,地图中每个顶点代表一个城市,两个城市间的连线代表道路,连线上的数值代表道路的长度。现在,
2、想从城市A到达城市E,怎样走路程最短,最短路程的长度是多少?【分析】把从 A到E的全过程分成四个阶段,用 k表示阶段变量,第1阶段有一个初 始状态A,两条可供选择的支路 ABI、AB2 ;第2阶段有两个初始状态 B1、B2,B1有三 条可供选择的支路,B2有两条可供选择的支路。 用dk(Xk, Xk+i)表示在第k阶段由初始 状态Xk到下阶段的初始状态 Xk+i的路径距离,Fk(Xk)表示从第k阶段的Xk到终点E的最短 距离,利用倒推方法求解 A到E的最短距离。具体计算过程如下:S1 : K=4,有:F4(D1)=3 , F4(D2)=4 , F4(D3)=3S2: K=3,有:F3(C1)=
3、mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)=min8,10=8F3(C3)=d3(C3,D3)+f4(D3)=8+3=11F3(C4)=d3(C4,D3)+f4(D3)=3+3=6S2: K=2,有F2(B1)=mi nd2(B1,C1)+F3(C1),d2(B1,C2)+f3(C2),d2(B1,C3)+F3(C3)=mi n9,12,14=9F2(m)=mi nd2(B2,c2)+f3(C2),d2(B2,C4)+F3(C4)=mi n16,10=10S4 : k=1,有:F1(A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2)=min
4、13,13=13因此由A点到E点的全过程的最短路径为A>B2 一 >C4 >D3 >E。最短路程长度为13。从以上过程可以看出,每个阶段中,都求出本阶段的各个初始状态到过程终点E的最短路径和最短距离,当逆序倒推到过程起点A时,便得到了全过程的最短路径及最短距离,同时附带得到了一组最优结果(即各阶段的各状态到终点E的最优结果)。在上例的多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法。根据上例分析和动态规划的基本概念,可以得到动态规划的基本模型如下:(1) 确定问题的决策对象。(2) 对决策过程划分阶段。(3) 对各阶段确定状态变量。(4) 根据状态变量确定费用函数和目标函数。建立各阶段状态变量的转移过程,确定状态转移方程。思考与练习:1、写出本节例题的算法及PASCAL程序。2、若城市路径示意图如下图所示,231 Zb1223234541232214
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 电梯机房管理规章
- 名著阅读《红星照耀中国》-八年级语文上册同步备课精讲(统编版)
- 西京学院《信息检索导论》2023-2024学年第一学期期末试卷
- 西京学院《商务应用文写作》2022-2023学年第一学期期末试卷
- 人教版五年级上册第11课新型玻璃
- 西京学院《机电一体化系统设计》2021-2022学年期末试卷
- 幼儿园小班儿歌《晒太阳》课件
- 西华师范大学《组织行为学》2022-2023学年第一学期期末试卷
- 人教版初中课件
- 西华师范大学《小学课程设计与评价》2023-2024学年第一学期期末试卷
- 学校心理辅导期末考试复习题及参考答案
- 《哈利波特与魔法石》
- 电厂运维安全员职责
- 艺术收藏科普知识讲座
- 期权策略及案例分析
- 平面镜成像-说课
- DB1306-T 102-2021 天花粉产地初加工技术规程
- Unit5PartALet'stryLet'stalk(学习任务单)六年级英语上册(人教PEP版)
- 中心供氧系统故障诊断与维护策略
- 国开2023秋《人文英语3》第5-8单元作文练习参考答案
- 高三一模总结主题班会课件
评论
0/150
提交评论