大学运筹学教程经典课件第九篇——动态规划.ppt

* 根据题意 x1=2所以 D1(x1)={d1| 6?d1?7}由此 d1=7f1(x1)=-7d1-18x1+442 =-7×7－18×2＋442 =357 将以上结果总结成下表： 生 产 库 存 问 题 * 设 备 更 新 问 题 * 一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略， 设 备 更 新 问 题 * * 设 备 更 新 问 题 * 例5.10：设具体数据如下： 设 备 更 新 问 题 * * * * * * * * * 97 * 由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。  这两个决策是  设 备 更 新 问 题 * * * * * 则 Max z= c1x1+c2x2+…+cnxn  s.t. w1x1+w2x2+…+wnxn≤W  x1,x2,…,xn为正整数 阶段k：第k次装载第k种物品（k=1,2,…,n） 状态变量xk：第k次装载时背包还可以装载的重量； 决策变量dk：第k次装载第k种物品的件数； 背 包 问 题 * 4. 决策允许集合： Dk(xk)={dk|0? dk?xk/wk，dk为整数}； 5. 状态转移方程：xk+1=xk-wkdk 6. 阶段指标：vk=ckdk 7. 递推方程 fk(xk)=max{ckdk+fk+1(xk+1)} =max{ckdk+fk+1(xk-wkdk)} 8. 终端条件：fn+1(xn+1)=0 背 包 问 题 * 例5.7:对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及 W=5用动态规划求解 f4(x4)=0 对于k=3 背 包 问 题 * 对于k =3 列出 f3(x3)的数值表如下： * 对于k=2 列出f2(x2)的数值表 * 对于k=1 列出f1(x1)的数值表 * * 机器负荷分配问题 * * 构造动态规划模型如下： 阶段k：运行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，…，依次类推；k=6表示第五年末（即第六年初）。 状态变量xk：第k年初完好的机器数（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好机器数。 决策变量dk：第k年投入高负荷运行的机器数； 状态转移方程：xk+1=0.7dk+0.9(xk-dk) 决策允许集合：Dk(xk)={dk|0?dk?xk} 阶段指标：vk(xk ,dk)=8dk+5(xk-dk) 终端条件：f6(x6)=0 机器负荷分配问题 * 递推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)} dk?Dk(xk)= max{8dk+5(xk- dk)+fk+1[0.7dk+0.9(xk-dk)]}  0?dk?xk 机器负荷分配问题 * f5(x5)=max{8d5+5(x5-d5)+f6(x6)} 0?d5?x5 =max{3d5+5x5}=8x5, d5*=x5 0?d5?x5f4(x4)=max{8d4+5(x4-d4)+f5(x5)} 0?d4?x4 =max{8d4+5(x4-d4)+8x5} 0?d4?x4 =max{8d4+5(x4-d4)+8[0.7d4+0.9(x4-d4)]} 0?d4?x4 =max{1.4d4+12.3x4}=13.7x4, d4*=x4 0?d4?x4 机器负荷分配问题 * f3(x3)=max{8d3+5(x3-d3)+f4(x4)} 0?d3?x3=max{8d3+5(x3-d3)+13.7x4} 0?d3?x3=max{8d3+5(x3-d3)+13.7[0.7d3+0.9(x3-d3)]} 0?d3?x3=max{0.28d3+17.24x3}=17.52x3, d3*=x3 0?d3?x3 机器负荷分配问题 * f2(x2)=max{8d2+5(x2-d2)+f3(x3)} 0?d2?x2 =max{8d2+5(x2-d2)+17.52x3} 0?d2?x2 =max{8d