北邮《运筹学》课件 第6章 动态规划.ppt

4.2设备更新问题*例2假设有关数据如下表所示。试制定5年中的设备更新策略，使在5年内的总收入达到最大。机龄项目第一年第二年第三年第四年第五年期前01234012301201012345收入2221201816272524222926243028321816161414运行费用6688105689556454889910更新费用27293234372931343631323332333432343636384.2设备更新问题第三年第四年第五年期前0120101234529262430283218161614145564548899103132333233343234363638*产品年序项目第一年第二年012340123收入222120181627252422运行费用6688105689更新费用2729323437293134364.2设备更新问题解：因第j年开始机龄为t年的机器，其制造年序应为j?t年，因此，I5(0)为第五年新产品的收入，故I5(0)=32。I3(2)为第一年的产品其机龄为2年的收入，故I3(2)=20。同理O5(0)=4，O3(2)=8。而C5(1)是第5年机龄为1年的机器(应为第四年的产品)的更新费用，故C5(1)=33。同理C5(2)=33，C3(1)=31，其余类推。*4.2设备更新问题*当j=5时，由于设T=1，故从第5年开始计算时，机器使用了1、2、3、4、5年，则递推关系式为因此 同理 4.2设备更新问题*当j=4时，递推关系为故 同理 4.2设备更新问题*当j=3时，有故 同理 4.2设备更新问题*当j=2时，有故 4.2设备更新问题*当j=1时，有故 根据上面计算过程反推之，可求得最优策略如下表，相应最佳收益为46单位。年机龄最佳策略11K22R31K42K53K4.3货郎担问题*货郎担问题在运筹学里是一个著名的命题。有一个串村走户卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄。问应如何选择行走路线，能使总的行程最短。类似的问题有旅行路线问题，应如何选择行走路线，使总路程最短或费用最少等。现在把问题一般化。设有n个城市，以1，2，…，n表示之。dij表示从i城到j城的距离。一个推销员从城市1出发到其他每个城市去一次且仅仅是一次，然后回到城市1。问他如何选择行走的路线，使总的路程最短。这个问题属于组合最优化问题，当n不太大时，利用动态规划方法求解是很方便的。4.3货郎担问题*由于规定推销员是从城市1开始的，设推销员走到i城，记表示由1城到i城的中间城市集合。S表示到达i城之前中途所经过的城市的集合，则有因此，可选取(i,S)作为描述过程的状态变量，决策为由一个城市走到另一个城市，并定义最优值函数fk(i,S)为从1城开始经由k个中间城市的S集到i城的最短路线的距离，则可写出动态规划的递推关系为 边界条件为为最优决策函数，它表示从1城开始经k个中间城市的S集到i城的最短路线上紧挨着i城前面的那个城市。4.3货郎担问题*例3求解四个城市旅行推销员问题，其距离矩阵如下表所示。当推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，使总的行程距离最短。i1234j108562608537905497904.3货郎担问题*解:由边界条件可知：当k=1时，即从1城开始，中间经过一个城市到达i城的最短距离是：4.3货郎担问题*当k=2时，即从1城开始，中间经过二个城市(它们的顺序随便)到达i城的最短距离是：4.3货郎担问题*当k=3时，即从1城开始，中间经过三个城市(顺序随便)回到1城的最短距离是：所以 由此可知，推销员的最短旅行路线是1→3→4→2→1，最短总距离为23。第2节动态规划的最优性原理*第3节动态规划的求解方法*考查如图所示的n阶段决策过程。其中取状态变量为决策变量为。在第k阶段，决策xk使状态sk(输入）转移为sk+1(输出)，设状态转移函数为