第七章动态规划.ppt

动态规划应用举例 k=1时 通过以上例子可以看出，利用动态规划方法求解多阶段问题，之所以减少计算量，原因之一是充分利用了前阶段已计算好的结果。 s1 本阶段费用 s2 f2(s2) d(s1,u1)+f2(s2) f1(s1) u1 生产费用 存储费用 d(s1,u1) 1 2 3 4 5 3+2 3+3 3+4 3+5 0.5 5.5 6.5 7.5 8.5 0 1 2 3 16 15.5 15 13.5 21.5 22 22.5 22 21.5 第二十九页，共六十一页，2022年，8月28日 动态规划应用举例 　例7.3 假定某厂在明年头4个月对燃料的需求量以及各月的固定订货费和单位存储费用如下表。 　　如果每吨燃料的价格是800元，该厂每个月开始时采购，问每月应采购多少，才能在保证供应的情况下使总成本最少？ 月份i 需求量ξi 固定订货费Ki 单位存储费hi 1 2 3 4 2 1 4 2 200 150 100 100 50 40 40 40 第三十页，共六十一页，2022年，8月28日 动态规划应用举例 解 设zi和ui(i=1,2,3,4)分别是月份i的订货量和期末存货量，则在采用顺序计算时，其基本方程是： 　　下面按各阶段分别计算如下（为了简单起见，金额以百元为单位）： 　　阶段1：ξ1=2，0≤u1≤1+4+2=7，见下表： 第三十一页，共六十一页，2022年，8月28日 动态规划应用举例 u1 f1(z1|u1)=c1(z1)+0.5u1 最优值 最优解 z1=2 3 4 5 6 7 8 9 f1(u1) z1* 0 1 2 3 4 5 6 7 18 26.5 35 43.5 52 60.5 69 77.5 18 26.5 35 43.5 52 60.5 69 77.5 2 3 4 5 6 7 8 9 　阶段2：ξ2=1，0≤u2≤4+2=6，见下表： 第三十二页，共六十一页，2022年，8月28日 动态规划应用举例 u2 f2(z2|u2)=c2(z2)+0.4u2+f2(u2+ξ2-z2) 最优值 最优解 z2=0 1 2 3 4 5 6 7 f2(u2) z2* 0 1 2 3 4 5 6 0+26.5=25.6 0.4+35=35.4 0.8+43.5=44.3 1.2+52=53.2 1.6=60.5=62.1 2+69=71 2.4+77.5=79.9 9.5+18=27.5 9.9+26.5=36.4 10.3+35=45.3 10.7+43.5=54.2 11.1+52=63.1 11.5+60.5=72 11.9+69=80.9 35.9 44.8 53.7 62.6 71.5 80.4 44.3 53.2 58.1 71 79.9 52.7 61.6 70.3 79.4 61.1 70 78.9 69.5 78.4 77.9 26.5 35.4 44.3 52.7 61.1 69.5 77.9 0 0 0,3 4 5 6 7 第三十三页，共六十一页，2022年，8月28日 动态规划应用举例 阶段3：ξ3=4，0≤u3≤2，见下表： 阶段4：ξ4=2，u4=0，见下表： u3 f3(z3|u3)=c3(z3)+0.4u3+f3(u3+ξ3-z3) 最优值 最优解 z3=0 1 2 3 4 5 6 f3(u3) z3* 0 1 2 0+61.1=61.1 0.4+69.5=69.9 0.8+77.9=78.7 9+52.7=61.7 9.4+61.1=70.5 9.8+69.5=79.3 61.3 70.1 78.9 60.4 69.7 78.5 59.5 68.8 78.1 67.9 77.2 76.3 59.5 67.9 76.3 4 5 6 u4 f4(z4|u4)=c4(z4)+0.4u4+f3(u4+ξ4-z4) 最优值 最优解 z4=0 1 2 f4(u4) z4* 0 0+76.3=76.3 9+67.9=76.9 17+59.5=76.5 76.3 0 第三十四页，共六十一页，2022年，8月28日 动态规划应用举例 例7.4 资源分配问题 设某种资源，如资金、材料、机器设备、劳动力等，可以投入n种生产。如果以数量为xi的资源投入第i种产品的生产，所得的效益为g（xi）(i=1,2,…,n)。问如何分配这种资源，才能使总的经济效益最大。 　　公司有资金8万元，投资A、B、C三个项目单位投资为2万元。每个项目的投资效益率与投入该项目的资金有关。