运筹学动态规划.ppt

运筹学动态规划.ppt

ID:58383709

大小:328.01 KB

页数:79页

时间:2020-09-07

运筹学动态规划.ppt_第1页
运筹学动态规划.ppt_第2页
运筹学动态规划.ppt_第3页
运筹学动态规划.ppt_第4页
运筹学动态规划.ppt_第5页
资源描述:

《运筹学动态规划.ppt》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、第八章动态规划多阶段决策过程:是指这样一类决策过程,它可以按时间分为若干阶段(称为时段),每一个阶段都需要做出决策,以便在过程的最终阶段得到最优结局。动态规划的一个重要特点是利用所谓的“最优化原理”,将问题用函数方程来表示(即递推方程),然后利用方程递推地进行计算、求解。一、最短路线问题最短路线问题:是指给定始点和终点,并且已知由始点到终点的各种可能的途径,需要找出由始点到终点的最短路线。这里的最短路线可以是通常意义下的距离,也可以是运输的时间或运输费用等等。例由A到D地要铺设一条煤气管道。其中须经过两级中间站,第一级中间站分别为B1和B2,第二级中间站分别为C

2、1、C2、C3。两站之间有连线的就表示可铺设管道,没有连线的就表示不能铺设管道。连线中间的数字表示两点间铺设管道的长度,试确定一条由A点到D点的铺设管道的最短路线。AB2B1C3C2C1D21233134341符号和概念AB2B1C3C2C1D21233134341n:表示由当前的状态到终点之间的阶段数。如由A点到D点n=3;由B2到D点n=2等等。n=3n=2n=1符号和概念AB2B1C3C2C1D21233134341s:表示当前所处的位置,称为状态变量。如s可以是A、B1、B2、C1、C2等等。符号和概念AB2B1C3C2C1D21233134341Xn(

3、s):称为决策变量,它表示由阶段数为n的某个状态s演变到下一个阶段的某个状态,决策者做出的一种选择。如,X2(B1)表示已处于B1状态,还有2个阶段就到达D点了,此时决策者可选择的地点;X2(B1)可取C1,C2或C3。符号和概念AB2B1C3C2C1D21233134341fn(s):表示由阶段数为n的某个状态s至终点的最短距离。例如,f2(B1)表示由阶段数为2的状态B1沿最优路线到达终点的距离,即B1到D点的最短距离。显然本例就是要求f3(A)及f3(A)所确定的最短路线。符号和概念AB2B1C3C2C1D21233134341d(s,Xn(s)):表示当

4、前处于状态s时,选取决策变量Xn(s)后,由点s到点Xn(s)的距离。例如,d(B1,C3)=1,d(C2,D)=3分析要求出f3(A)的值及相应的策略从起点A开始分析AB2B1C3C2C1D21233134341当处于状态A时, 有几种可供选择的路线AB2B1C3C2C1D21233134341当处于状态A时, 有两种可供选择的路线①A→B1:表明由A点所选择的下一点是B1由B1状态到终点D的最短距离为f2(B1)∴若选此条路线,则由A出发到达终点的最短距离可表示为d(A,B1)+f2(B1)②A→B2:表明由A点所选择的下一点是B2由B2状态到终点D的最短距

5、离为f2(B2)∴若选此条路线,则由A出发到达终点的最短距离可表示为d(A,B2)+f2(B2)综合考虑两种情况可知,由状态A出发,到终点D的最优路线应是上述两种最短距离中的最小值,即可见,要计算f3(A)就得先计算f2(B1)和f2(B2)。由B1、B2点出发 分别有几种可供选择的路线?AB2B1C3C2C1D21233134341由B1点出发 有三种可供选择的路线①B1→C1最短距离为d(B1,C1)+f1(C1)②B1→C2最短距离为d(B1,C2)+f1(C2)③B1→C3最短距离为d(B1,C3)+f1(C3)综合考虑三种情况可知,由状态B1出发,到终

6、点D的最优路线应是上述三种最短距离中的最小值,即可见,要计算f2(B1)就得先计算和f1(C1)、f1(C2)、f1(C3)。由B2点出发 有三种可供选择的路线①B2→C1最短距离为d(B2,C1)+f1(C1)②B2→C2最短距离为d(B2,C2)+f1(C2)③B2→C3最短距离为d(B2,C3)+f1(C3)综合考虑三种情况可知,由状态B2出发,到终点D的最优路线应是上述三种最短距离中的最小值,即可见,要计算f2(B2)就得先计算和f1(C1)、f1(C2)、f1(C3)。由于由状态C1、C2、C3出发到达终点D只需经过一个阶段,所以由以上分析可以看出,计

7、算f3(A)的过程实际是一个倒推的过程,即由最后的阶段向前逐级进行计算。AB2B1C3C2C1D21233134341当n=1时图示AB2B1C3C2C1D21233134341当n=2时图示AB2B1C3C2C1D21233134341当n=3时图示AB2B1C3C2C1D21233134341所以,铺设管道的最短路线应是A→B1→C1→D。总结对于最短路线问题,一般地有如下的递推关系式:这个递推公式是根据最优化原理得到的最优化原理一个过程的最优策略具有这样的性质,即无论其初始状态和初始决策如何,其今后诸决策对第一个决策所形成的状态作为初始状态和过程而言,必须

8、构成最优策略。二、动态规

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。