吉林大学远程教育-运筹学课件(第6章动态规划应用举例)

1、第六章第六章 动态规划应用举例动态规划应用举例 动态规划是一种将复杂问题转化为比较简单问题的最优化方法，一些线性规划、非线性规划及整数规划都可以用动态规划方法来求解。因此，动态规划在存贮控制、网络流、作业安排、生产控制等方面都有所讨论，在工程技术、工业生产、经济、军事以及自动控制等领域都有广泛的应用，并获得了显著的效果。 但是动态规划不存在一种标准的数学形式，对于动态规划方法的使用，有时可以说是一种艺术，它需要对动态规划问题的一般结构有较深入的了解，在一个具体问题中，如何定义状态、决策、阶段效应等，以及如何得到问题的基本方程表达式，在很大程度上还有赖于分析者的经验、洞察和判断能力。这就需要练习

2、和实践，以及总结已有的研究成果。本章通过一些典型的应用问题，介绍动态规划的建模和基本解题方法。 1 资源分配问题资源分配问题给定一定数量的某种资源，例如人力、资金、设备、材料等，将其投入多种活动，就会产生如何分配资源给各项活动，使投放资源的总效果最优的问题，这就是资源分配问题。资源分配是相当广泛的经济问题，我们前面介绍的线性规划、整数规划、指派问题等都可以看作是求解资源分配的方法。这节介绍的资源分配问题是用前述方法难以解决，但由于其自身特点决定，可以用动态规划求解的实际问题。 现在设有某种资源（例如电、煤等）可用于n项活动，假设资源的数量为a，已知用于第i项活动的资源数为xi时，可以得到的收益

3、为gi（xi），i=1, n。试确定资源的分配方案使总收益最大。 该问题的数学模型可以表示为： maxZ=g1（x1）+g2（x2）+ +gn（xn） s.t x1+x2+ + xn）a x1,x2,xn0当gi（xi）是线性函数时，该问题是线性规划问题；当gi（xi）是非线性函数时，是非线性规划问题 ，如果采用非线性规划方法去求解是比较麻烦的。然而由于这类问题的特点，可以将它看成一个多阶段决策问题，并利用动态规划方法求解。 在应用动态规划方法去处理这一类资源分配问题时，通常将资源分给每项活动的过程看作一个阶段，每个阶段都要确定对一种活动的资源投放量。 这时，状态变量xk可选择k阶段初所拥有的

4、资源量，即xk是要在第k项到第n项活动间分配的资源量。决策变量uk常常选对活动k的资源投放量，决策变量的允许集合是： 0ukxk 在选取上述状态变量和决策变量的情况下，状态转移方程是： xk+1= xk-uk取投放资源时的效益为指标函数，则gk（uk）为阶段效益指标。 设fk（xk）为k阶段到n阶段按最优分配方案获得的最大收益， 则动态规划基本方程是： fk（xk）= maxgk（uk）+fk+1（xk+1） 0ukxk fn+1（xn+1）=0 k=n,n-1, ,1 按基本方程，逆序计算，就可求得这类资源分配问题的最优解。 例1 某公司拟将5百万元资金投放下属的A、B、C三个企业，各企业获

5、得资金后的收益如表所示，试确定总收益最大的投资分配方案。投放资金（百万元） 0 1 2 3 4 5收益（百万元）A0 2 2 3 3 3B0 0 1 2 4 7C0 1 2 3 4 5 解：以分别向A、B、C三个企业分配资金为阶段，k=1,2,3。取k阶段初拥有的资金数为状态变量xk，决策变量uk为分配给企业k的资金数，则状态转移方程是： xk+1=xk-uk令fk（xk）为k企业至第三个企业按最优分配方案获得的最大收益， 则动态规划基本方程是： fk（xk）= maxgk（uk）+fk+1（xk+1） 0ukxk f4（x4）=0 k=3,2,1下面按基本方程具体求解： K=3 x3 =0，

6、1，2，3，4，5 f3（0）=0， u3（0）=0； f3（1）=1, u3（1）=1； f3（2）=2， u3（2）=2； f3（3）=3，u3（3）=3； f3（4）=4， u3（4）=4； f3（5）=5，u3（5）=5 K=2 x2 =0，1，2，3，4，5 f2（0）=0, u2（0）=0； g2（0）+f3（1） 0+1 f2（1）=max g2（1）+f3（0）=max 0+0 =1, u2（1）=0； g2（0）+f3（2） 0+2 f2（2）=max g2（1）+f3（1）=max 0+1 =2, g2（2）+f3（0） 1+0 u2（2）=0； g2（0）+f3（3） 0

7、+3 f2（3）=max g2（1）+f3（2）=max 0+2 =3, g2（2）+f3（1） 1+1 g2（3）+f3（0） 2+0 u2（3）=0； g2（0）+f3（4） 0+4 g2（1）+f3（3） 0+3 f2（4）=max g2（2）+f3（2）=max 1+2 =4, g2（3）+f3（1） 2+1 g2（4）+f3（0） 4+0 u2（4）=0或4； g2（0）+f3（5） 0+5 g2（1）+f3（4） 0+4 f2（5）=max g2（2）+f3（3）=max 1+3 =7, g2（3）+f3（2） 2+2 g2（4）+f3（1） 4+1 g2（5）+f3（0） 7+0

8、 u2（5）=5； K=1 x1 =5 g1（0）+f2（5） 0+7 g1（1）+ f2（4） 2+4 f1（5）=max g1（2）+ f2（3）=max 2+3 =7, g1（3）+ f2（2） 3+2 g1（4）+ f2（1） 3+1 g1（5）+f2（0） 3+0 u1（5）=0.至此，算得本问题最大总收益7百万元，由u1（5）=0顺次可求得最优投资方案为： u1（5）=0； u2（5）=5； u3（0）=0即将5百万元全部投放到企业B，届时可得收益7百万元。第六章第六章 动态规划应用举例动态规划应用举例第六章第六章 动态规划应用举例动态规划应用举例 2 生产与存贮问题生产与存贮问题

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

10、产量（或采购量）为决策变量，在确定决策变量时一般要考虑需求量、生产能力、库存限制等因素；指标函数取生产（或采购）费用。 下面举例说明该问题的求解方法。例2 某工厂要制订今后四个时期某产品的生产计划，据估计今后四个时期内，市场对于该产品的需求量如下表所示：时 期 k1 2 3 4需求量 dk2 3 2 4 假定该厂生产每批产品的固定费用为2千元，若不生产则为0；每单位产品的成本为1千元；每件产品的每期保管费为0.5千元；每个时期最大生产能力所允许的生产批量不超过5个单位；最大库存量为4个单位；假定开始时库存量为1个单位，要求第四期末库存为2个单位。试问该厂应如何安排各个时期的产量，才能在满足市场

11、需求的条件下，使总费用最小。 解：按四个时期将问题分成四个阶段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+uk-dk，x4=x5-u4+d4=2+4-u4，而u45，x4=1，2，3，4 于是由动态规划基本方程fk（xk）= min

12、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）=min 0.50+2+4+f4（2）=min 6+7 =12.5 0.50+2+5+f4（3） 7+6.5 u3（0）=3

13、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+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

14、）=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（0）=min 0.50+2+4+f3（1）=min 6+12 =17.5 0.50+2+5+f3（2） 7+11.5 u2（

15、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（4） 8+9 u2（2）=4注意：3-x2u2min5,7-x2 ,x2+u2-d2=x3 d2=3 0.53+0+f3（0）

16、 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 注意：0 x1+u1-d1=x24,而d1=2, 1u15 ， 于是有： 0.51+2+1+f2（0） 3.5+17.5 0

17、.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 第六章第六章 动态规划应用举例动态规划应用举例 2 生产与存贮问题（续）生产与存贮问题（续） 上讲的例子中，决策变量和状态变量允许取值都是离散的。对于决策变量允许取值连

18、续的情况，有时计算更方便。 例3 某车间需按月生产一定数量的某种部件给总装车间。由于生产条件的变化，该车间在各月份中生产这种部件的费用不同，各月份的生产量于当月月底前全部要存入仓库以备后用。已知总装车间在各月初的需求量以及加工车间生产该部件所需费用如下表：月 份 k 0 1 2 3 4需 求 量 dk 0 8 5 3 2单位成本ck 11 18 13 17 20 设仓库容量限制H=9，开始库存量为2，要求4月末库存量也为2，试制订一个各月的生产计划，使得既满足需要和库容量限制，又使得生产该部件的总成本最低。 解：按月份划分阶段 k=0，1，2，3，4 ；取阶段初库存量为状态变量xk；决策变量u

19、k为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=20（4-x4）=80-20 x4, k=3 注意：4-x4=u40，x44，又x4=x3+u3-d3d4，而d3=3， 5-

20、x3u37-x3 3ux2080u17minxfucminxf33374433733333333xux5xux5333337x17119x20140 x73x20140u3min333xux5u3=7-x3 k=2 注意：u3=7-x30，x37，又x3=x2+u2-d2d3，而d2=5， 8-x2u212-x2 5ux17119u13minxfucminxf2221233221222222222xux8xux822222121315617204124172044min2228xxxxuxux u2=12-x2k=1 注意： d2x2=x1+u1-d1H=9，而d1=8， 13-x1u117-

21、x1 81315618minmin11117221117111111111313uxuxfucxfxuxxux11111171832513260135132605min11113xxxxuxux u1=13-x1 k=0 注意：d1x1=x0+u0-d0H=9，而d0=0,x0=26u07 0000711007001832511minmin0066duxuxfucxfuu240289u7min070u6 u0=7 至此，已算得本问题的最小总费用为240，再按计算顺序反推回去，可得最优生产计划如下：月 份 k 0 1 2 3 4需 求 量 dk 0 8 5 3 2库 存 量 xk 2 9 5 7

22、 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，6；取第k周的价格为状态变量xk；记决策变量：uk= 1，买 0，不买 记 fk（xk）为第k周至第6周在价格xk下的最小期

23、望费用。 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=600， u5（6）=1；f5（7）=min700，0.3f6（5）+0.3f6（6）+0.4f6（7） =min700，610=

24、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=574， u4（7）=0；K=3 x3=4，6，8f3（4）=min400，0.3f4（5）+0.3f4（6）+0.4f4（7）

25、 =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）+0.4f3（8） =min400，0.1400+0.5551.81+0.4551.8 =min400，536.62=400，

26、 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）+

27、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； u2（4）=1；u2（6）=0；u2（8）=0； u3（4）=1；u3（6）=0；u3（8）=0；知：第1、2、3周若价格为4百元/公斤时，就采购，否则以后采购。 2由u4（5）=1；u4（6）=0；u4（7）=0；知：第4周若价格为5百元/公斤时，就采购，否则以后采购。 3由u5

28、（5）=1；u5（6）=1；u5（7）=0；知：第5周若价格为4或5百元/公斤时，都要采购，否则第6周采购。 4在第6周，无论什么价格都要采购。 本问题最小费用是： 0.1f1（4）+0.5f1（6）+0.4f1（8） =0.1400+0.5522.958+0.4522.958 =510.662（百元）运运 筹筹 学学第六章第六章 动态规划应用举例动态规划应用举例4 复合系统工作可靠性问题复合系统工作可靠性问题 某种工作系统由n个部件串联组成，称部件正常工作的概率为部件的可靠性，称整个系统正常工作的概率为系统的可靠性。如图：部件1部件2部件n 在这样的串联系统中，只要有一个部件失灵，整个系统就

29、不能正常工作。为了提高系统工作的可靠性，可以给各部件设置备用件，并且设计备用件自动投入装置，一旦部件损坏，则备用件自动投入运行。显然，部件的备用件越多，部件的工作可靠性就越大，从而，整个系统的工作可靠性也就越大。但是备用件多了，整个系统的成本、重量、体积都相应增大。而系统所允许的总成本、总重量、总体积往往都是有限的，因此，复合系统工作可靠性问题主要讨论在上述限制条件下，如何选择各部件的备用件数量，使系统的工作可靠性最大。下面我们先研究这类问题的数学模型。设部件i 装有ui个备用件时，它正常工作的概率为pi（ui）。因此整个系统正常工作的概率为： niiiupP1 设装部件i 的一个备用件费用为

30、ci元，要求总费用不超过C元，则这个问题只有一个约束条件，它的静态模型为：CucupPiniiniii11max 这是一个非线性规划问题。象资源分配问题一样，可以用动态规划方法求解这类问题。不过与以前的资源分配问题不同，本问题的总效果不是等于各阶段效果的和，而是各阶段效果的乘积。下面构造它的动态规划模型： 以向各部件分配备用件的顺序为阶段 k=1，2，n; 以k阶段初拥有的未分配的费用数xk为状态变量；决策变量uk表示部件k拥有的元件数，则 xk+1=xk-ckuk记fk（xk）为部件k至部件n最大工作可靠性，则 fk（xk）= maxpk(uk) fk+1（xk+1） fn+1（xn+1）=

31、1 k=n,n-1,2,1 例6 某工厂设计一种电子设备，由D1，D2，D3串联组成。已知三种元件的单价和可靠性如下表所示，要求设计中所使用的费用不超过105元。试问应如何设计，可使设备的可靠性最大？元 件单价 ck（元） 可靠性 pkD1300.9D2150.8D3200.5 解：按元件种类分成三个阶段，k=1，2，3；设状态变量xk表示从元件Dk到D3允许使用的费用；决策变量uk为部件Dk所使用的并联元件个数；则 xk+1=xk-ckuk；用可靠性作为指标，则部件的可靠性为1-（1-pk）uk。记fk（xk）为部件Dk至部件D3的最大工作可靠性，则 fk（xk）= max1-（1-pk）u

32、k fk+1（xk+1） f4（x4）=1 k=3,2,1 k=3 x3=105-（30+15），105-（30+152）， 105-（30+153）或105-（302+15） =60，45，30 f3（30）=0.5 u3（30）=1 f3（45）=1-（1-0.5）2=0.75 u3（45）=2 f3（60）=1-（1-0.5）3=0.875 u3（60）=3 k=2 x2=105-30，105-（302）=75,45 f2（45）=0.8f3（30）=0.80.5=0.4 u2（45）=1 1-（1-0.8）3f3（30） 0.9920.5 f2（75）=max 1-（1-0.8）2f3

33、（45）=max 0.960.75 0.8f3（60） 0.80.875 =max0.496,0.72,0.7=0.72 u2（75）=2 k=1 x1=105 f1（105）=max1-（1-0.9）2f2（45）,0.9f2（75） =max0.990.4,0.90.72 =max0.396,0.648=0.648 u1（105）=1 最优设计方案：D1=1（个）；D2=2（个）；D3=2（个）最大可靠性为0.648，总费用100元。 运 筹 学第六章第六章 动态规划应用举例动态规划应用举例 5 设备更新问题 一种设备（例如汽车、机床等）在使用过程中总会变旧，以至于损坏，通常，或者对旧设备

34、进行维修，或者卖掉旧设备再买新的（更新）。在给定的年限n年内，使用该设备进行生产，设备应使用多少年后再进行更新，以使得n年内总的纯收入最大，这就是设备更新问题。一般说来，一种设备使用时间过长，由于收入减少，维修费用增大，所以从经济上看并不合算。但是，使用时间过短，频繁更换设备也是不合算的，这类问题存在一个最佳的更新周期。 在讨论设备的最佳更新周期问题时，一般要考虑下面几个因素： 1rk(t)在第k年机龄为t的一台设备运转一年带来的收入额。显然， rk(t)是t的递减函数，这是因为设备随着使用时间的增加（即机龄的增长）而变旧，因而收入减少。 2Ok(t)在第k年机龄为t的一台设备所需的维修费。

35、Ok(t)是t的递增函数，这是因为随着使用年限的增加，设备变旧，维修费用也逐渐增加。 3Ck(t) 在第k年卖掉旧设备购买新设备所需款项。 Ck(t) 是t的递增函数，因为随着设备的老化，旧设备越不值钱，卖旧买新所需的款项越大。 这类设备更新问题因为在计划期每年都要作出决策，以决定是否更新设备，所以是多阶段决策问题，可以用动态规划方法求解。 例7 已知一种设备在五年计划开始时，机龄为1，在未来五年内的收入rk(t)、运行费Ok(t)、更新费用Ck(t)如下表所示。试制定五年中的设备更新策略，使五年内的总收入达到最大。产品年代k-t第一年k-t=1第二年k-t=2第三年k-t=3第四年第五年期前

36、k-t=0机龄 t 01234012301201012345rk(t)2221201816272524222926243028321816161414Ok(t)6688 10 56895564548 89910Ck(t) 2729323437293134363132333233343234363638 解：以年为阶段 k=1，2，3，4，5；取k年初设备的机龄为状态变量xk；记决策变量），更新（简记为）继续使用（简记为RKxukk0, 1则0, 11, 11kkkkkkxuxuxx 记fk（xk）为第k年到第5年底的最大总收入，则动态规划基本方程是： 100:max111kkkkkkkkkkk

37、kkfxCOrRxfxOxrKxf f6（x6）=0 k=5,4,3,2,1 k=5 x5 =1,2,3,4,5 23523max33432:528:max1100:211:max165556555RKfCOrRfOrKfu5（1）=1 18518max33432:624:max1200:322:max265556555RKfCOrRfOrKfu5（2）=1 13813max36432:922:max1300:433:max365556555RKfCOrRfOrKf u5（3）=1 696max37432:1016:max1400:544:max465556555RKfCOrRfOrKf u5

38、（4）=1 4104max38432:1014:max1500:655:max565556555RKfCOrRfOrKfu5（5）=1k=4 x4=1,2,3,4 391739max2332430:18526:max1100:211:max154445444RKfCOrRfOrKf u4（1）=1 291529max2334430:13824:max1200:322:max254445444RKfCOrRfOrKfu4（2）=1 161516max2334430:6818:max1300:433:max354445444RKfCOrRfOrKf 13139max2336430:4914:max

39、1400:544:max454445444RKfCOrRfOrKfu4（4）=0 u4（3）=1k=3 x3=1,2,3 483248max3931529:29625:max1100:211:max143334333RKfCOrRfOrKfu3（1）=1 313128max3932529:16820:max1200:322:max243334333RKfCOrRfOrKf u3（2）=0 272720max3936529:13916:max1300:433:max343334333RKfCOrRfOrKfu3（3）=0k=2 x2=1,2 464146max4829527:31621:max1

40、100:211:max132223222RKfCOrRfOrKf u2（1）=1 363635max4834527:27816:max1200:322:max232223222RKfCOrRfOrKf u2（2）=0 k=1 x1=1 463046max4632622:36818:max1100:211:max121112111RKfCOrRfOrKf u1（1）=1 至此，根据计算过程反推回去，可得最优更新策略如下：u1（1）=1，K；u2（2）=0，R；u3（1）=1；u4（2）=1；u5（3）=1，K。运运 筹筹 学学第六章第六章 动态规划应用举例动态规划应用举例 6 排序问题 设有n个

41、不同零件A1，A2，An需要在m台不同机床B1，B2，Bm上加工，每个零件都必须依次经过B1，B2，Bm各道加工工序。 已知零件Ai在机床Bj上的加工时间（i=1,2n;j=1,2m),问应如何确定各零件的加工顺序，使在第一台机床B1上加工第一个零件开始到在第m台机床Bm上将最后一个零件加工完为止，所用的总时间最少？这就是所谓的mn同序加工的排序问题。对于m3的排序问题，目前尚无有效解法，而对于只有两个工序，即m=2的排序问题，可以用动态规划方法加以解决。本节我们就讨论它的解法。 设n个不同零件依次在机床A、B上加工，用ai、bj分别表示零件i在A、B上的加工时间。 n个零件在机床A上有个加工

42、顺序，在机床B上也有个加工顺序，不难证明，使得总工期最少的加工顺序，一定在A、B机床上具有相同的加工顺序。 事实上，若顺序不一样，在A上加工完的某零件不能马上在B上加工，而要等到另一个或一些零件在B上加工完后，才能加工，这势必使B的等待加工时间加长，从而使总的加工时间延长。 当加工顺序取定后，在机床A上没有等待时间，而在机床B上则常常等待。因此，寻找最优排序方案只有尽量减少在机床B上等待加工的时间。 现在我们以在机床A上更换零件的时刻为阶段 k=1，2,n. 以X表示在机床A上等待加工的零件集合；以x表示不属于X 的在A上加工的零件；以t表示在A上加工完x时刻算起到B上加工完x所需时间。这样在

43、A上加工完一个零件后，就有（X,t）与之对应，选取（X,t）作为描述加工过程的状态变量。 令f（X,t）表示由状态（X,t）出发，对未加工的零件采取最优加工顺序后，将X中所有零件加工完所需的时间。 令f（X,t,i）表示由状态（X,t）出发，在A上先加工零件i ，然后再对以后的零件采取最优加工顺序后，将X中所有零件加工完所需的时间。注意，这时t表示从零件i-1在A上加工完的时刻算起直到在B上把它加工完所需的时间。 令f（X,t,i,j）表示由状态（X,t）出发，在A上相继加工零件i,j，然后再对以后的零件采取最优加工顺序后，将X中所有零件加工完所需的时间。 于是，不难得到 ai+ f（X/i,

44、t-ai+bi），当tai时 f（X,t,i）= ai+ f（X/i, bi）， 当tai时 其中X/i表示集合X去掉i后剩下的零件集合。记 Zi（t）=max t-ai,0+bi，它表示从X/i出发,从零件i在A上加工完的时刻算起直到在B上把它加工完所需的时间。从而 f（X,t,i）=ai+ f（X/i, Zi（t）同理 f（X,t,i,j）=ai+ aj + f（X/i,j, Zij（t）其中Zij（t）表示从X出发, 在A上相继加工零件i,j，从A将j加工完的时刻算起直到在B上把j加工完所需的时间。从而 Zij（t）=maxZi（t）-aj,0+ bj=maxmaxt-ai,0+bi-a

45、j,0+bj =maxmax（ t-ai+bi-aj,bi-aj),0+bj =max t-ai-aj+bi+bj,bi+bj-aj,bj由 f（X,t,i,j）=ai+ aj + f（X/i,j, Zij（t）及 Zij（t）=max t-ai-aj+bi+bj,bi+bj-aj,bj将i,j对调，即先加工j,后加工i，则有 f（X,t,j,i）=ai+ aj + f（X/i,j, Zji（t） Zji（t）=max t-ai-aj+bi+bj,bi+bj-ai,bi由于f（X,t）是t的单调上升函数，故当Zij（t）Zji（t）时 f（X/i,j, Zij（t） f（X/i,j, Zji（

46、t）从而 f（X,t,i,j） f（X,t,j,i）这就是说，不管t值为何，当Zij（t）Zji（t）时，零件i放在零件j之前加工可以使总的加工时间短些。而由Zij（t）和Zji（t）的表达式可知，这只须下面的不等式成立即可。即 maxbi+bj-aj,bj maxbi+bj-ai,bi将上面不等式两边同时减去bi与bj得 max-aj,-bimax-ai,-bj 即 minaj,biminai,bj 这个条件就是零件i应该排在零件j之前的条件。 由条件 minaj,biminai,bj可知：当ai小于aj，bi，bj时，先安排加工零件i；当bj小于ai，aj，bi时后安排加工零件j,可以使总

47、的加工时间短些。由此得到最优排序操作方法如下： 写出工时矩阵 a1 a2 an b1 b2 bn 找出工时矩阵中的最小元素，若它在上行，则将相应的零件排在最前面位置；若它在下行，则将相应的零件排在最后面位置。 将排定位置的零件所对应的列从矩阵中划掉，然后对余下的零件重复的操作，但那时最前（后）位置是在已排定位置之后（前）。如此作下去，直到把所有零件都排完为止。 例8 设有5个零件在机床A、B上加工，加工顺序是先A后B，每个零件所需加工时间如下表所示。试确定加工顺序，使机床连续加工完所有零件的加工总时间最少，并求出总时间。零件号 1 2 3 4 5加工时间机床A 3 7 4 5 7机床B 6 2

48、 7 3 4 解：工时矩阵为 3 7 4 5 7 6 2 7 3 47236534774 由此得最优加工顺序为：13542按加工顺序及所需时间绘示意图（称为甘特图）如下：AB 3 4 7 5 7 6 7 4 3 3 2由甘特图可知，最少总加工时间为28小时。运 筹 学第六章第六章 动态规划应用举例动态规划应用举例运 筹 学第六章第六章 动态规划应用举例动态规划应用举例 7 货郎担问题v 货郎担问题也称旅行员问题，是运筹学里一个著名问题。设有n个城市，以1，2，n表示，dij表示从i城到j城的距离。一个推销员从城市1出发到其它每个城市去一次且仅仅一次，然后回到城市1，问他应如何选择行走路线，使总的路程最短。这个问题属于组合最优化问题，目前尚无有效解法。如果用穷举法，计算次数为n！,当n很大时，例如n=20，计算次数20！=2.4329021018，实际上这是无法计算的。但当n不太大时，利用动态规划方法求解却是很方便的。v 规定推销员是从城市1出发，设推销员走到i城，s表示到达i城之前中途所经过的城市集合。选取（i,s）作为描述过程的状态变量，定义fk(i,s)为从1城出发经由k个中间城市的s集到i城的