第五章动态规划教学重点：用递推的方法求解最短路线问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
，有限资源分配问题，旅行售货员问题，最优线路问题等。教学难点：有限资源分配问题。教学课时：10学时主要教学环节的组织：将最优化原理应用于几种典型多阶段问题当中，结合实例给学生以具体的认识，通过习题加以巩固。第一节多阶段决策问题教学重点：通过具体实例得多阶段决策问题的模型，讨论多阶段决策问题的解决方法。教学难点：多阶段决策问题的解法。教学课时：1学时主要教学环节的组织：给出具体的多阶段决策问题，讨论多阶段决策问题的算法一递推法。实例最短路问题例1最短路问题就是从某地出发，途经若干中间点最后到达目的地，要求找出路程或费用最小的路线。一般的最短路问题将在下一章讨论，这里只讨论分层的最短路问题。下面的管道设计问题（例5.1.1）就是其中之一。从A点到E点要铺设一条煤气管道，中间必须经过三个中间站，第一站可在B1、B2、B3中选择，第二站可在C1、C2、C3中选择，第三站可在D1、D2、D3中选择，要求选择一条由A到E的铺管路线，使总长度最短。其中两点连线上的数字
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示两点间管线的长度。从A点到E点铺设管道，可以按其地理特点自然地分成四个阶段：（如下图所示）从A到B是第一阶段，从B到C是第二阶段，从C到D是第三阶段，从D到E是第四阶段。广、阶段1广_、阶段2厂一阶段3—阶段4&、0e在阶段2,从B3点出发，只有C1、C3两种可选择的点，如选C1,则C1就是阶段2在B3点的决策结果；C1点既是阶段2铺设管道的终点，又是阶段3铺设管道的起点；同样的理由，可以递推得其余阶段的铺设路线，如阶段3在C1点的决策是D1，阶段4在D1点的决策只有E点；由于到E点是整个铺设管道的终点，至此，决策过程完成，铺设一条A点到E点的管道是由四个阶段的管道组成的，如A---B3---C1---D1---E，它也称为一个策略。可以看出，各个阶段的决策不同，铺设的管道也不同，并且当某个阶段的始点给定后，它直接影响着后面各阶段的行进路线和管道的长短，而后面各阶段的路线的选取不受这点以前各阶段路线的影响。因此，最短路线问题可简化为四个阶段决策问题，使由这四个阶段决策组成决策序列，也称为策略所决定的一条路线的总长度最短。例2资源分配问题(略)例3生产-库存问题(略)一般多阶段决策问题有一个系统，可以分成若十个阶段，任意一个阶段k，系统的状态可以用七表示(可以是数量、向量、集合等)。在每一阶段k的每一状态都有一个决策集合Q3)，在Q(x)中选定一个决策qeQ(x)，状态x就转移到新的状态kkkkkkkkx=T(x,q)，并且得到效益R(x,q)。我们的目的就是在每一个阶段都在它k+1kkkkkk的决策集合中选择一个决策，使所有阶段的总效益ZRk(xk,qk)达到最大。我们k称之为多阶段决策问题。多阶段决策问题的基本要素：阶段数、状态变量、决策变量、状态转移方程和目标函数。多阶段决策问题的分类阶段数：有限阶段决策问题和无限阶段决策问题；状态变量：连续多阶段决策问题和离散多有限阶段决策问题；阶段个数是否明确：定期多阶段决策问题和不定期多阶段决策问题；参数取值情况：确定多阶段决策问题和不确定多阶段决策问题。第二节最优化原理教学重点：最优化原理。教学难点：无。教学课时：1学时主要教学环节的组织：介绍最优化原理。动态规划最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，必须构成最优策略。动态规划原理还应该包括如下性质：对于多阶段决策的最优策略如果用它的前i步产生的情况来形成一个前i步问题，那么所给最优策略的前i阶段的策略构成这前i步问题的一个最优策略。用动态规划求解多阶段决策问题的一般步骤：第1步明确问题，找出阶段数第2步确定变量，找出状态变量和决策变量第3步找出状态转移方程第4步写出递推关系式第5步求解递推关系式第三节确定性的定期多阶段决策问题教学重点：旅行售货员问题，多阶段资源分配问题，可靠性问题。教学难点：多阶段资源分配问题。教学课时：4学时主要教学环节的组织：用具体的实例计算以上问题。1、旅行售货员问题旅行售货员问题是图论中一个著名问题，就是在网络N上找一条从v0点出发，经过v,v，…,v各一次最后返回v的最短路线和最短路程。现把它看成12N0一个多阶段决策问题。从v0出发，经过n个阶段，每个阶段的决策是选择下一个点。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用(七,V)表示状态，七是所处的点，V是还没有经过的点集合。在状态(七,V)的决策集合d中，取决策(v.,V)，获得的效益是v,到v的距离ij，转入下一个状态(v.,九}，现在用最优化原理来找递推公式。用f(vj，V)表示从vj点出发，经过V中的点各一次，最后回到v0点的最短路程，V是一个顶点集合，V=k,d产i到j的弧长，则ff(v,V)=min{d+f(v,V\{v})},k=1,2,...,n
4)=%最后求0%，"牛巧口八)，nim{di2十f2(7；2?I)03卜均(巧」)』i4+&(叫」也，由l)l--min顶十20,5十IX,6T22\—23,勺(叫)=巧最优路线为口|f巧*外*处-*%，路程长为23.2、多阶段资源分配问题(ay+b(x—y))},k>2下面讨论有限资源分配问题，它的递推公式是：/(x)=max{g(y)+h(x—y)+f1f(x)=max{g(y)+h(x—y)}1v0
本文档为【第五章 动态规划 山大刁在筠 运筹学讲义】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483