运筹学动态规划.ppt

第八章动态规划一、最短路线问题例符号和概念符号和概念符号和概念符号和概念符号和概念分析当处于状态A时，有几种可供选择的路线当处于状态A时，有两种可供选择的路线综合考虑两种情况可知，由状态A出发，到终点D的最优路线应是上述两种最短距离中的最小值，即可见，要计算f3(A)就得先计算f2(B1)和f2(B2)。由B1、B2点出发分别有几种可供选择的路线？由B1点出发有三种可供选择的路线综合考虑三种情况可知，由状态B1出发，到终点D的最优路线应是上述三种最短距离中的最小值，即可见，要计算f2(B1)就得先计算和f1(C1)、f1(C2)、f1(C3)。由B2点出发有三种可供选择的路线综合考虑三种情况可知，由状态B2出发，到终点D的最优路线应是上述三种最短距离中的最小值，即可见，要计算f2(B2)就得先计算和f1(C1)、f1(C2)、f1(C3)。由于由状态C1、C2、C3出发到达终点D只需经过一个阶段，所以由以上分析可以看出，计算f3(A)的过程实际是一个倒推的过程，即由最后的阶段向前逐级进行计算。当n=1时图示当n=2时图示当n=3时图示总结最优化原理二、动态规划的应用1、“背包”问题/最优装载问题例数学模型思路分析思路分析递推公式状态变量的确定当n=1时求解例题可见要计算f3(5),要先计算f2(5)、f2(0)可见，要计算f2(5)、f2(0)，要先计算f1(5)、f1(3)、f1(1)、f1(0)将f1值代入f2中，得到将f2值代入f3中，得到∴“背包”问题的最优解为X1=1,X2=1,X3=0,最优值为13。2、投资分配问题/资源分配问题分析分析例：解∴要计算f2(30)，f2(20)，f2(10)，f2(0)，要先计算f1(30)，f1(20)，f1(10)，f1(0)将以上结果代入前面各式得最优解为最优值为803、多阶段生产安排问题/多阶段配置问题分析分析分析例解：当k=1时当k=2时当k=3时将已知数据代入上式得第一阶段：把全部原料100吨投入Ⅱ型产品生产收益=0.5*100=50万元，回收=0.4*100=40吨第二阶段：把全部原料40吨投入Ⅱ型产品生产收益=0.5*40=20万元，回收=0.4*40=16吨第三阶段：把全部原料16吨投入Ⅰ型产品生产收益=0.6*16=9.6万元，回收=0.1*16=1.6吨∴三个阶段总收益为：50+20+9.6=79.6万元4、多阶段存储问题例分析分析分析分析解由表可知从而知这样，得到煤场每年各季度的购煤量和季初存储量的最优安排如下表，全年总存储费为80400元。思考题与练习题