您所在位置：网站首页 > 高等教育 > 大学课件物流运筹方法与工具教学课件 ppt 作者彭秀兰毛磊第七章动态规划第二节模型建立与求解步骤

物流运筹方法与工具教学课件 ppt 作者彭秀兰毛磊第七章动态规划第二节模型建立与求解步骤

9页

卖家[上传人]：E****

文档编号：89254888

上传时间：2019-05-22

文档格式：PPT

文档大小：163KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 9 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、一、建立动态规划模型的基本要求,在明确了动态规划的基本概念和基本思想之后，我们看到，给一个实际问题建立动态规划模型时，必须做到以下五点： 1、将问题的过程划分成恰当的阶段； 2、正确选择状态变量sk，使之既能描述过程的演变，又能满足无后效性； 3、确定决策变量uk及每阶段的允许决策集合Dk(sk)； 4、正确写出状态转移方程； 5、正确写出指标函数Vk,n的关系，它应满足下面三个性质（1）是定义在全过程和所有后部子过程上的数量函数；（2）要具有可分离性，并满足递推关系，即 Vk，n（sk，uk，uk1，un）ksk，uk，Vk，n（sk，uk，un）（3）函数k（sk，uk，Vk，n）要严格单调。,二、模型的求解步骤,动态规划的模型建好后，要进行求解，要求出最优策略，即达到最优效果的的最优策略，以及最优目标函数值fk(sk)opt Vk，n(sk，uk，un)。还是以引例的问题，上述计算过程，可以借助图形直观简明的表示出来，如图7-5所示。在图7-5中，每节点处上方的方格内的数字，表示该点到终点G的最短距离用直线连接的点表示该点到终点G的最短路线未用直线连接的点就说明它不是该点

2、到终点G的最短路线，故这些支路均被舍去了图中粗线表示由始点A到终点G的最短路线（这种在图上直接作业的方法叫做标号法）。,二、模型的求解步骤,图7-5 最优策略的求解步骤如果规定从A点到G点为顺行方向，则由G点到A点为逆行方向，那么，图75是由G点开始从后向前标的。这种以A为始端，G为终端，从G到A的解法称为逆序解法。,二、模型的求解步骤,动态规划方法求最优解时，都是在行进方向确定后，均要逆着这个行进方向，从最后一段向前逆推计算，逐段找到最优途径。如图7-3所示。一般以逆序解法较为常见，那么它们的动态规划基本方程该如何求解呢？设指标函数是取各阶段指标和的形式，即：,式中vj(sj,uj)表示第j段的指标，是满足指标函数三个性质的。所以上式可以写做：,当初始状态给定时，过程的策略就被确定了，则指标函数也就确定了。因些，指标函数是初始状态和策略的函数，记为Vk,nsk,pk,n(sk)。那么上面的递推关系就可以写成：,二、模型的求解步骤,其子策略pk,n(sk)可以看成是由决策uk(sk)和pk+1,n(sk+1)组合成的。即,如果用pk,n(sk)表示初始状态为sk的后部子过程所有子策

3、略中的最优子策略，则最优函数值为：,而,二、模型的求解步骤,所以，在逆序解法时，动态规划的基本方程为：,式中，sk+1=Tk(sk,uk)。以fn+1(sn+1)=0为边界条件，从k=n开始，由后向前逆推，从而逐步求出各阶段的最优决策和相应的最优值，当最后求出f1(s1)时，就可以得到整个问题的解，这就是动态规划的逆序解法。,且,三、动态规划方法的优点,从上面对引例问题的分析计算中，明显可以看出，动态规划方法和穷举法等其它方法相比有以下的优点： 1、减少计算量。计算引例问题若用穷举法，就要对48条路线进行比较，在计算机上运行时比较运算要进行47次；求各条路线的距离，即使采用逐段累加的方法，也要进行6+12+24+48+48138次计算。用动态规划的方法来计算，比较运算（从k=5段开始向前算）共进行了3+3+4+4+115次。每次比较运算相应有两次加法运算，若再去掉中间重复的两次（即B1C1，B2C4各多算了一次），实际只有28次加法运算。可见，动态规划方法比穷举法减少了计算量，而且随着段数的增加，计算量将大大地减少。,三、动态规划方法的优点,2、丰富了计算结果。在动态规划方法中，我们得到的不仅仅是由起点出发到终点的最短路线及相应的最短距离，而且得到了从所有中间各点出发到终点的最短路线及相应的最短距离。这就是说，求出不仅仅是一个最优策略，而且是一族最优策略。这对于许多实际问题是很有用处的，有利于帮助分析所得到的结果。如引例问题中，若因特殊情况出现，运输路线必需经过D2市，那么用其它方法求解时就需重新计算，而用动态规划方法求解时，通过图75和图76明显可以看出，由A市到D2的最短路线是AB1C2D2，最短路程为13，由D2市到G市的最短路线是D2E2F2G，最短路程为6，所以，由A市经D2市到达G市的最短路线是AB1C2D2E2F2G，最短路程为19。,本节思考题及作业题,思考题： 1 .建立动态规划模型的基本要求是什么？ 2 .逆序求解过程是怎样的？即求解步骤是什么？作业题: 教材P191: 4题.,

《物流运筹方法与工具教学课件 ppt 作者彭秀兰毛磊第七章动态规划第二节模型建立与求解步骤》由会员E****分享，可在线阅读，更多相关《物流运筹方法与工具教学课件 ppt 作者彭秀兰毛磊第七章动态规划第二节模型建立与求解步骤》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源

逍遥游复习知识点整理

近现代法德关系史高三展示课3稿

当代大学生人生信仰及追求的调查研究

长相思纳兰性德-ppt课件

课件：危机意识一

英语ppt演讲关于阿甘正传

发达国家基础教育改革的动向与趋势修改版

中国民间美术课件.ppt

生物质发电技术与系统课程ppt 第1章生物质发电技术现状及发展趋势 2学时 -----2016

现代信号处理思考题含答案

执业药师继续教育抑郁症的药物治疗 100分

小学生的成长档案模板不用修改万能型

增订六版现代汉语上册第二章文字思考与练习答案

国家财政ppt课件

加拿大英语介绍

六年级统计图的选择课件

中学生成长档案ppt

中国现代文学史期末复习整理

lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究

风雨贾平凹阅读答案

点击查看更多

新上传的PPT文档

语文教师学年教学总结使用许可协议搅拌反应釜半管夹套的设计 2023会计个人上半年工作总结（4篇）.doc 2021年客服工作总结范文电力安全作业规程电气部分团队行为培训分享集体智慧观看优课直播心得体会问题解决当堂检测工程数学半开卷参考内容高中物理选修高考真题汇编部分商务工作总结范文 2023年实用的晚会主持词合集8篇 2022年学校的辞职报告九篇学习新党章心得体会_5

物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第七章动态规划 第二节模型建立与求解步骤

物流运筹方法与工具教学课件 ppt 作者彭秀兰毛磊第七章动态规划第二节模型建立与求解步骤