吉林大学远程教育运筹学课件6

1、第六章第六章 动态规划应用举例动态规划应用举例第六章第六章 动态规划应用举例动态规划应用举例 2 生产与存贮问题生产与存贮问题 生产与存贮问题是实际生产中经常遇到的问题，大量生产可以降低成本，但当超过市场需求时，就造成积压，增加库存费用，完全按市场需求安排生产虽然没有库存费用，但由于开工不足或加班加点造成生产成本得的增加。因此，合理利用库存调节产量，满足需求是十分有意义的。所谓生产存贮问题，就是一个生产部门如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划期内的费用总和为最小的问题。原材料采购部门也会遇到同样问题，在那里需要确定各时期的采购量，使得计划期内总费用最小。

2、这类问题通常是一个多阶段决策问题，可以用动态规划方法求解。在动态模型中，以时期为阶段；取各时期初的库存量为状态变量；选各阶段的产量（或采购量）为决策变量，在确定决策变量时一般要考虑需求量、生产能力、库存限制等因素；指标函数取生产（或采购）费用。 下面举例说明该问题的求解方法。例2 某工厂要制订今后四个时期某产品的生产计划，据估计今后四个时期内，市场对于该产品的需求量如下表所示：时 期 k1 2 3 4需求量 dk2 3 2 4 假定该厂生产每批产品的固定费用为2千元，若不生产则为0；每单位产品的成本为1千元；每件产品的每期保管费为0.5千元；每个时期最大生产能力所允许的生产批量不超过5个单位；

3、最大库存量为4个单位；假定开始时库存量为1个单位，要求第四期末库存为2个单位。试问该厂应如何安排各个时期的产量，才能在满足市场需求的条件下，使总费用最小。 解：按四个时期将问题分成四个阶段k=1，2，3，4；取k期初库存量xk为状态变量；k期内产量uk为决策变量，则 xk+1=xk+uk- dk根据题意，第k期的费用为 2+uk uk0 rk(xk, uk)=0.5xk+ 0 uk=0记fk（xk）为第k期至第4期末最小总费用，则动态规划基本方程为： fk（xk）= min rk(xk, uk) +fk+1（xk+1） uk f5（x5）=0 k=4,3,2,1k=4 注意：xk+1=xk+u

4、k-dk，x4=x5-u4+d4=2+4-u4，而u45，x4=1，2，3，4 于是由动态规划基本方程fk（xk）= min rk(xk, uk) +fk+1（xk+1）有： f4（1）=0.51+2+5=7.5（注意：u4=6-x4） u4（1）=5 f4（2）=0.52+2+4=7 u4（2）=4 f4（3）=0.53+2+3=6.5 u4（3）=3 f4（4）=0.54+2+2=6 u4（2）=2 k=3 x3 =0,1,2,3,4 注意：x3+u3-d3=x41，而d3=2， u33-x3，又x44， u3min5,6-x3于是有： 0.50+2+3+f4（1） 5+7.5 f3（0）

5、=min 0.50+2+4+f4（2）=min 6+7 =12.5 0.50+2+5+f4（3） 7+6.5 u3（0）=3 0.51+2+2+f4（1） 4.5+7.5 f3（1）=min 0.51+2+3+f4（2）=min 5.5+7 =12 0.51+2+4+f4（3） 6.5+6.5 0.51+2+5+f4（4） 7.5+6 u3（1）=2 注意：u33-x3，u3min5,6-x3, x3+u3-2=x4 0.52+2+1+f4（1） 4+7.5 f3（2）=min 0.52+2+2+f4（2）=min 5+7 =11.5 0.52+2+3+f4（3） 6+6.5 0.52+2+4

6、+f4（4） 7+6 u3（2）=1 0.53+0+f4（1） 1.5+7.5 f3（3）=min 0.53+2+1+f4（2）=min 4.5+7 =9 0.53+2+2+f4（3） 5.5+6.5 0.53+2+3+f4（4） 6.5+6 u3（3）=0 0.54+0+f4（2） 2+7 f3（4）=min 0.54+2+1+f4（3）=min 5+6.5 =9 0.54+2+2+f4（4） 6+6 u3（4）=0 k=2 x2 =0,1,2,3,4 注意：0 x2+u2-d2=x34,而d2=3， 3-x2u2min5,7-x2 于是有： 0.50+2+3+f3（0） 5+12.5 f2

7、（0）=min 0.50+2+4+f3（1）=min 6+12 =17.5 0.50+2+5+f3（2） 7+11.5 u2（0）=3 0.51+2+2+f3（0） 4.5+12.5 f2（1）=min 0.51+2+3+f3（1）=min 5.5+12 =16.5 0.51+2+4+f3（2） 6.5+11.5 0.51+2+5+f3（3） 7.5+9 u2（1）=5 0.52+2+1+f3（0） 4+12.5 0.52+2+2+f3（1） 5+12 f2（2）=min 0.52+2+3+f3（2）=min 6+11.5 =16 0.52+2+4+f3（3） 7+9 0.52+2+5+f3（

8、4） 8+9 u2（2）=4注意：3-x2u2min5,7-x2 ,x2+u2-d2=x3 d2=3 0.53+0+f3（0） 1.5+12.5 0.53+2+1+f3（1） 4.5+12 f2（3）=min 0.53+2+2+f3（2）=min 5.5+11.5 =14 0.53+2+3+f3（3） 6.5+9 0.53+2+4+f3（4） 7.5+9 u2（3）=0 0.54+0+f3（1） 2+12 f2（4）=min 0.54+2+1+f3（2）=min 5+11.5 =14 0.54+2+2+f3（3） 6+9 0.54+2+3+f3（4） 7+9 u2（4）=0 k=1 x1 =1

9、 注意：0 x1+u1-d1=x24,而d1=2, 1u15 ， 于是有： 0.51+2+1+f2（0） 3.5+17.5 0.51+2+2+f2（1） 4.5+16.5 f1（1）=min 0.51+2+3+f2（2）=min 5.5+16 =20.5 0.51+2+4+f2（3） 6.5+14 0.51+2+5+f2（4） 7.5+14 u1（1）=4 至此，已算得本问题14期最小总费用为20.5千元。再按计算的顺序反推回去，可找出最优生产计划为：时 期 k1 2 3 4需求量dk2 3 2 4库存量xk 1 3 0 1产 量uk 4 0 3 5 第六章第六章 动态规划应用举例动态规划应用

10、举例 2 生产与存贮问题（续）生产与存贮问题（续） 上讲的例子中，决策变量和状态变量允许取值都是离散的。对于决策变量允许取值连续的情况，有时计算更方便。 例3 某车间需按月生产一定数量的某种部件给总装车间。由于生产条件的变化，该车间在各月份中生产这种部件的费用不同，各月份的生产量于当月月底前全部要存入仓库以备后用。已知总装车间在各月初的需求量以及加工车间生产该部件所需费用如下表：月 份 k 0 1 2 3 4需 求 量 dk 0 8 5 3 2单位成本ck 11 18 13 17 20 设仓库容量限制H=9，开始库存量为2，要求4月末库存量也为2，试制订一个各月的生产计划，使得既满足需要和库容

11、量限制，又使得生产该部件的总成本最低。 解：按月份划分阶段 k=0，1，2，3，4 ；取阶段初库存量为状态变量xk；决策变量uk为k阶段内的生产量。则状态转移方程为： xk+1=xk+uk-dk， k=0，1，2，3，4由于 dk+1xk+1=xk+uk-dkH所以 max0，dk+1+dk-xkukH+dk-xk记fk（xk）为第k阶段至第4阶段末最小总费用，则动态规划基本方程为：kDuduxfucminxfkk1kkkkkKk f5（x5）=0 k=4,3,2,1,0 k=4 因为要求4月末库存量为2，即x4+u4-d4=2，而d4=2，所以， u4=4-x4 ， f4（x4）=c4u4=

12、20（4-x4）=80-20 x4, k=3 注意：4-x4=u40，x44，又x4=x3+u3-d3d4，而d3=3， 5-x3u37-x3 3ux2080u17minxfucminxf33374433733333333xux5xux5333337x17119x20140 x73x20140u3min333xux5u3=7-x3 k=2 注意：u3=7-x30，x37，又x3=x2+u2-d2d3，而d2=5， 8-x2u212-x2 5ux17119u13minxfucminxf2221233221222222222xux8xux822222121315617204124172044min

13、2228xxxxuxux u2=12-x2k=1 注意： d2x2=x1+u1-d1H=9，而d1=8， 13-x1u117-x1 81315618minmin11117221117111111111313uxuxfucxfxuxxux11111171832513260135132605min11113xxxxuxux u1=13-x1 k=0 注意：d1x1=x0+u0-d0H=9，而d0=0,x0=26u07 0000711007001832511minmin0066duxuxfucxfuu240289u7min070u6 u0=7 至此，已算得本问题的最小总费用为240，再按计算顺序反推

14、回去，可得最优生产计划如下：月 份 k 0 1 2 3 4需 求 量 dk 0 8 5 3 2库 存 量 xk 2 9 5 7 4 产 量 uk 7 4 7 0 0u3=7-x3 u4=4-x4 例4 （不确定性采购问题）某部门欲一次采购某种原料100 公斤，由于生产需要，必须在6周内采购完毕。原料在未来的6周内可能有几种价格，而每种价格的概率预先是已知的，设在前三周和后三周的价格及其相应的概率如下表所示：第1周第3周第4周第6周单价（百元/公斤）概率单价（百元/公斤）概率4680.10.50.45670.30.30.4 试确定采购方案，使期望费用最小。 解：以周为阶段 k=1，2，3，4，5

15、，6；取第k周的价格为状态变量xk；记决策变量：uk= 1，买 0，不买 记 fk（xk）为第k周至第6周在价格xk下的最小期望费用。 k=6 x6=5，6，7 f6（5）=500，u6（5）=1； f6（6）=600， u6（6）=1； f6（7）=700，u6（7）=1。 K=5 x5=5，6，7 f5（5）=min500，0.3f6（5）+0.3f6（6）+0.4f6（7） =min500，0.3500+0.3600+0.4700 =min500，610=500， u5（5）=1；f5（6）=min600，0.3f6（5）+0.3f6（6）+0.4f6（7） =min600，610=60

16、0， u5（6）=1；f5（7）=min700，0.3f6（5）+0.3f6（6）+0.4f6（7） =min700，610=610， u5（7）=0；K=4 x4=5，6，7f4（5）=min500，0.3f5（5）+0.3f5（6）+0.4f5（7） =min500，0.3500+0.3600+0.4610 =min500，574=500， u4（5）=1；f4（6）=min600，0.3f5（5）+0.3f5（6）+0.4f5（7） =min600，574=574， u4（6）=0；f4（7）=min700，0.3f5（5）+0.3f5（6）+0.4f5（7） =min700，574=5

17、74， u4（7）=0；K=3 x3=4，6，8f3（4）=min400，0.3f4（5）+0.3f4（6）+0.4f4（7） =min400，0.3500+0.3574+0.4574 =min400，551.8=400， u3（4）=1；f3（6）=min600，0.3f4（5）+0.3f4（6）+0.4f4（7） =min600，551.8=551.8， u3（6）=0；f3（8）=min800，0.3f4（5）+0.3f4（6）+0.4f4（7） =min800，551.8=551.8， u3（8）=0；K=2 x2=4，6，8f2（4）=min400，0.1f3（4）+0.5f3（6）

18、+0.4f3（8） =min400，0.1400+0.5551.81+0.4551.8 =min400，536.62=400， u2（4）=1；f2（6）=min600， 0.1f3（4）+0.5f3（6）+0.4f3（8） =min600，536.62=536.62， u2（6）=0；f2（8）=min800，0.1f3（4）+0.5f3（6）+0.4f3（8） =min800，536.62=536.62， u2（8）=0； K=1 x1=4，6，8f1（4）=min400，0.1f2（4）+0.5f2（6）+0.4f2（8） =min400，0.1400+0.5536.62+0.4536.62 =min400，522.958=400， u1（4）=1；f1（6）=min600，0.1f2（4）+0.5f2（6）+0.4f2（8） =min600，522.958=522.958 u1（6）=0；f1（8）=min800，0.1f2（4）+0.5f2（6）+0.4f2（8） =min800，522.958=522.958， u1（8）=0； 综上所述，我们得到最优采购方案： 1由u1（4）=1；u1（6）=0；u1（8）=0