运筹学-ch5 动态规划(讲义9)-精品文档整理.ppt

《运筹学-ch5 动态规划(讲义9)-精品文档整理.ppt》由会员分享，可在线阅读，更多相关《运筹学-ch5 动态规划(讲义9)-精品文档整理.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Page 1第五章第五章 动态规划动态规划第一节第一节 多阶段决策过程及实例多阶段决策过程及实例Page 2 动态规划动态规划是运筹学的重要分支之一，它是解是运筹学的重要分支之一，它是解决决多阶段决策过程最优化多阶段决策过程最优化的一种方法。该法是由的一种方法。该法是由美国数学家美国数学家贝尔曼贝尔曼（R. Bellman）等人在本世纪）等人在本世纪50年代首先提出的。年代首先提出的。R.Bellman于于1957年发表的年发表的“动态规划动态规划”一书是动态规划方面的第一本著作一书是动态规划方面的第一本著作。目前，动态规划已成功地用于解决资源分配、。目前，动态规划已成功地用于解决资源分配、货

2、物装运、设备更新、生产计划以及复合系统可货物装运、设备更新、生产计划以及复合系统可靠性等许多问题。靠性等许多问题。Page 3引例引例1：某旅客需从某旅客需从A A号站到达号站到达E E号站，试指出一条号站，试指出一条最短路最短路径。交径。交通状况如图所示。箭头表示旅行路线，箭头旁边数字表通状况如图所示。箭头表示旅行路线，箭头旁边数字表示距离。示距离。 解解 一种习惯求解法是首先计算所有可能路线的距一种习惯求解法是首先计算所有可能路线的距离，然后经比较选出一条最短路线，这称为离，然后经比较选出一条最短路线，这称为显枚举或显枚举或穷举法穷举法，当维数增大时，该法计算量将急剧增大，从，当维数增大时

3、，该法计算量将急剧增大，从而变得不可行。而变得不可行。 动态规划是采用递推方式计算动态规划是采用递推方式计算, ,分分4 4个阶段。个阶段。Page 4最短路径为：最短路径为：A AB1B1C3C3D2D2E E 24ED1D2C3C2C1B2B1A533766452123第第4阶段阶段第第3阶段阶段第第2阶段阶段第第1阶段阶段18Page 5引例引例2：机器负荷分配问题：机器负荷分配问题 （P155 例例2）某种机器可以在高、低两种不同的负荷下进行生产。在高负荷某种机器可以在高、低两种不同的负荷下进行生产。在高负荷下生产时，产品的年产量下生产时，产品的年产量 g g 与投入生产的机器台数与投

4、入生产的机器台数 x x 的关系的关系为：为： ，这时机器的完好率为，这时机器的完好率为 a a; ;在低负荷下生产时，在低负荷下生产时，产品的年产量产品的年产量 h h 与投入生产的机器台数与投入生产的机器台数 x x 的关系为：的关系为： 这时机器的完好率为这时机器的完好率为 b b。假定开始时完好的机器台数为假定开始时完好的机器台数为 S S。要求制定一个五年计划，在。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同负荷下每年开始时，决定如何重新分配完好的机器在两种不同负荷下生产的数量，使在五年内产品的总产量达到最高。生产的数量，使在五年内产品的总产量达到最高。(

5、 )gg x( )hh xPage 6第二节第二节 动态规划的基本概念动态规划的基本概念Page 71.阶段（阶段（stage） 原问题可分为若干个子问题，每一子问题称为一个原问题可分为若干个子问题，每一子问题称为一个阶段，用阶段，用 k 表示。表示。k=1,2，.，n 称为阶段变量。称为阶段变量。 2.状态状态 (state) 每一阶段开始时所处的状态（位置），称为状态，每一阶段开始时所处的状态（位置），称为状态，用用 表示。表示。（不受之前状态的影响）（不受之前状态的影响） 如引例如引例1中，中， 状态集状态集 Sk3123,SC C CPage 83. 决策决策 (decision) 从

6、某一阶段某一状态出发，向下一阶段某一状态演变从某一阶段某一状态出发，向下一阶段某一状态演变的选择。的选择。 表示第表示第k个阶段从个阶段从 出发的决策变量。出发的决策变量。 表示第表示第k个阶段从个阶段从 出发的允许决策集合。出发的允许决策集合。如：如：():kkUSD ():kkSkSkS21123D ()=C ,BC C211U ()=CBPage 94. 策略策略 (policy) 一个按顺序排列的决策组成的集合。一个按顺序排列的决策组成的集合。从第一阶段开始至终止：从第一阶段开始至终止：从第从第k 阶段开始至终止：阶段开始至终止： 111122nn()=U (S ),U (S ),.,

7、U (S )nPSkkk+1k+1nn()=U (S ),U(S),.,U (S )knkPS（后部子策略）（后部子策略）Page 105. 状态转移状态转移 由一个状态转移到下一个状态的演变过程，用方程由一个状态转移到下一个状态的演变过程，用方程1kkk=T (S ,U )kS（状态转移方程）（状态转移方程）若状态若状态 给定，决策变量给定，决策变量 确定，则第确定，则第 k+1 阶阶段的状态段的状态 就确定了。就确定了。T 称为状态转移函数。称为状态转移函数。kSkU1kSPage 116. 指标函数指标函数阶段指标：阶段指标： k 阶段中，评价从状态阶段中，评价从状态 出发作出决策出发作

8、出决策 所产生效果的数量指标。记为：所产生效果的数量指标。记为：kSkU(,)kkkV S U如：如： 211211()(,)3UBCV B C指指B1到到C1的路长的路长指标函数：指标函数： 评价由评价由k 阶段状态阶段状态 出发到终点的后部子策略出发到终点的后部子策略 产生效果的数量指标。产生效果的数量指标。 记为：记为： kS()knkPSkkk+1k+1nn+1=S ,U ,S,U,.,U ,SknknVVPage 12最优指标函数：最优指标函数： 从从k 阶段状态阶段状态 出发到终点的所有后部子出发到终点的所有后部子 策略中指标函数值的最优者。策略中指标函数值的最优者。 kSknkk

9、kkk+1k+1nn+1(U ,.,U)f (S )=S ,U ,S,U,.,U ,Sopt knVkkf (S )称为称为 的最优指标函数的最优指标函数kS11f (S )表示全过程的最优指标函数，相应的策略即为表示全过程的最优指标函数，相应的策略即为最优策略。最优策略。Page 13如：如：31f (C )表示从第三阶段状态表示从第三阶段状态C1出发至终点的最优出发至终点的最优指标函数指标函数。3112f (C )=4(,)CDE21f (B )1f (A)表示从第二阶段状态表示从第二阶段状态B1出发至终点的最优出发至终点的最优指标函数指标函数。表示从第一阶段状态表示从第一阶段状态A出发至

10、终点的最优出发至终点的最优指标函数指标函数。21f (B )=61f (A)=11Page 14第三节第三节 最优性原理与递推方程最优性原理与递推方程Page 15Bellman的最优性原理的最优性原理 一个过程的最优策略是这样的。即无论过去状态和决一个过程的最优策略是这样的。即无论过去状态和决策如何，对前面决策形成的状态而言，余下的策略必构策如何，对前面决策形成的状态而言，余下的策略必构成最优策略。成最优策略。 Principle of Optimality: An optimal policy has the property that whatever the initial state

11、 and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. (See Bellman, 1957, Chap. III.3.)（最优策略的子策略必最优）（最优策略的子策略必最优） 必要条件必要条件下面求引例下面求引例1 的递推解法：的递推解法：Page 16最短路径为：最短路径为：A AB1B1C3C3D2D2E E 24ED1D2C3C2C1B2B1A5337664

12、52123第第4阶段阶段第第3阶段阶段第第2阶段阶段第第1阶段阶段18引例引例1Page 17动态规划是通过求解下面递推过程动态规划是通过求解下面递推过程 1nkkkkk+1k+1(U ,.,U)n+1n+1f (S )=(S ,U )+f(S)(),1,2,.,(S)=0opt kkkkVUDSknf 求得最优策略及最优指标函数的。求得最优策略及最优指标函数的。 上式称为动态规划的上式称为动态规划的递推方程递推方程或基本方程。（逆序解法）或基本方程。（逆序解法） 充要条件充要条件Page 18用递推法求解动态规划的方法：用递推法求解动态规划的方法： 1.规定过程的分段，构造出状态，定义状态变

13、量；规定过程的分段，构造出状态，定义状态变量；2.定义决策变量，确定允许决策集合；定义决策变量，确定允许决策集合；3.确定状态转移规律，写出转移方程；确定状态转移规律，写出转移方程；4.定出指标函数，写出递推方程，求解。定出指标函数，写出递推方程，求解。 Page 19第四节第四节 动态规划应用举例动态规划应用举例Page 20一、资源分配问题：一、资源分配问题： 所谓所谓分配问题分配问题，就是将数量一定的一种或若，就是将数量一定的一种或若干种资源干种资源( (例如原材料、资金、机器设备、劳力例如原材料、资金、机器设备、劳力、食品等等、食品等等) )，恰当地分配给若干个使用者，而，恰当地分配给

14、若干个使用者，而使目标函数为最优。使目标函数为最优。Page 21例例1. 资源连续分配问题资源连续分配问题 某工厂有某工厂有100台机器，拟分四期使用，在每一期有两种台机器，拟分四期使用，在每一期有两种生产任务。根据经验，要把生产任务。根据经验，要把 台机器投入第一种任务，台机器投入第一种任务，则在一个生产周期中将有则在一个生产周期中将有 机器报废；余下的机器全机器报废；余下的机器全 部投入第二种任务，则在一个生产周期中将有部投入第二种任务，则在一个生产周期中将有 机器报机器报废。如果在一个周期中用于第一种任务，每台机器可收益废。如果在一个周期中用于第一种任务，每台机器可收益10；用于第二种

15、任务，每台机器可收益；用于第二种任务，每台机器可收益7。问怎样分配机器。问怎样分配机器使总收益最大？使总收益最大？x13110Page 22解：构造动态规划模型如下：解：构造动态规划模型如下：阶段变量阶段变量k k：运行周期（：运行周期（k=1,2,3,4k=1,2,3,4），其中），其中k=1k=1表示第一表示第一期初，期初，依次类推；，依次类推；k=4k=4表示第四期初。表示第四期初。状态变量状态变量S Sk k：第：第k k期初完好的机器数（期初完好的机器数（k=1,2,3,4k=1,2,3,4），），决策变量决策变量x xk k：第：第k k期初投入第一种任务的机器数；期初投入第一种任

16、务的机器数； 则第则第k k期初投入第二种任务的机器数：期初投入第二种任务的机器数：S Sk k-x-xk k 状态转移方程状态转移方程： （0 0 x xk k S Sk k） 阶段指标阶段指标：V Vk k(x(xk k ,S,Sk k)=10 x)=10 xk k+7(S+7(Sk k-x-xk k) ) 边界条件边界条件：f f5 5(S(S5 5)=0)=0921310()kkkkSxSxPage 23则递推方程为：则递推方程为：kkkkkk+1k+10 x55f (S )=10+7(S -x )+f(S)1,2,.,4(S )=0max kkSxkf注注：允许决策集是整数集，但不可

17、能一一列举，计：允许决策集是整数集，但不可能一一列举，计算量太大。此时可认为状态变量和决策变量都是连算量太大。此时可认为状态变量和决策变量都是连续的，得到最优解后再做取整处理。续的，得到最优解后再做取整处理。Page 24k=4时时：f4(S4)=max10 x4+7(S4-x4)+f5(S5) 0 x4 S4 =max3x4+7S4 (取取x4*=S4) =10S4, k=3时：时：f3(S3)=max10 x3+7(S3-x3)+f4(S4) 0 x3 S S3 =max10 x3+7(S3-x3) +102/3x3+9/10(S3-x3) = max2/3x3+16S3 = 50/3S3

18、 (取取x3*=S3) Page 25k=2时时：f2(S2)=max10 x2+7(S2-x2)+f3(S3) 0 x2 S S2 2 =max10 x2+7(S2-x2) +50/32/3x2+9/10(S2-x2) = max-8/9x2+22S2 = 22S2 (取取x2*=0) Page 26k=1时时：f1(S1)=max10 x1+7(S1-x1)+f2(S2) 0 x1 S S1 1 =max10 x1+7(S1-x1) +222/3x1+9/10(S1-x1) = max-2.13x1+26.8S1 = 26.8S1 (取取x1*=0) Page 27最优策略为：最优策略为：

19、 *11100,0Sx*2290,0Sx*3381,81Sx*4454,54Sx最大收益为：最大收益为： 1(100)2680fPage 28练习练习. 资源分配问题资源分配问题 某施工单位有某施工单位有500台挖掘设备，在超负荷施工情况下，台挖掘设备，在超负荷施工情况下，年产值为年产值为20万元万元/台，但其完好率为台，但其完好率为0.4；正常负荷施工情况；正常负荷施工情况下，年产值为下，年产值为15万元万元/台，完好率为台，完好率为0.8。在四年内合理安排。在四年内合理安排两种不同负荷下施工的挖掘机设备数量，使四年年末仍有两种不同负荷下施工的挖掘机设备数量，使四年年末仍有160台设备保持完

20、好，并使产值最大。台设备保持完好，并使产值最大。Page 29解：构造动态规划模型如下：解：构造动态规划模型如下：阶段变量阶段变量k k：运行周期（：运行周期（k=1,2,3,4k=1,2,3,4）；）；状态变量状态变量S Sk k：第：第k k期初完好的挖掘机台数（期初完好的挖掘机台数（k=1,2,3,4k=1,2,3,4），），决策变量决策变量x xk k：第：第k k期初用于超负荷施工的机器数；期初用于超负荷施工的机器数； 则第则第k k期初用于正常负荷施工的机器数：期初用于正常负荷施工的机器数：S Sk k-x-xk k 状态转移方程状态转移方程： （0 0 x xk k S Sk k

21、） 阶段指标阶段指标：V Vk k(x(xk k ,S,Sk k)=20 x)=20 xk k+15(S+15(Sk k-x-xk k)=5x)=5xk k+15S+15Sk k 边界条件边界条件：f f5 5(S(S5 5)=0)=010.40.8()kkkkSxSxPage 30则递推方程为：则递推方程为：kkkkk+1k+10 x4455f (S )=5+15S +f(S)1,2,.,402400(S )=0max kkSxkxSf5440.40.8160SxS 注：要考虑注：要考虑160台台 Page 31k=4时时：f4(S4)=max5x4+15S4+f5(S5) 0 x4 2 2

22、S4-400 =max5x4+15S4 =25S4-2000 (取取x4*=2S4-400)k=3时：时：f3(S3)=max5x3+15S3+f4(S4) 0 x3 S S3 =max5x3+15S3 +25-0.4x3+0.8S3-2000 = max-5x3+35S3 -2000 = 35S3 -2000 (取取x3*=0) Page 32k=2时时：f2(S2)=max5x2+15S2+f3(S3) 0 x2 S S2 2 =max5x2+15S2 +35-0.4x2+0.8S2-2000 = max-9x2+43S2-2000 = 43S2-2000 (取取x2*=0) Page 3

23、3k=1时时：f1(S1)=max5x1+15S1+f2(S2) 0 x1 S S1 1 =max5x1+15S1 +43-0.4x1+0.8S1-2000 = max-12.2x1+49.4S1 -2000 = 49.4S1-2000 (取取x1*=0) Page 34最优策略为：最优策略为： *11500,0Sx*22400,0Sx*33320,0Sx*44256,112Sx11()22700fS最大收益为：最大收益为： Page 35例例2.资源平行分配问题资源平行分配问题 (投资分配投资分配) 某工业部门根据国家计划安排，拟将某种高效率的设某工业部门根据国家计划安排，拟将某种高效率的设

24、备备5台分配给甲乙丙三个工厂，各厂获得这台设备后，可台分配给甲乙丙三个工厂，各厂获得这台设备后，可以盈利如下表。问如何分配可使盈利最大？以盈利如下表。问如何分配可使盈利最大？甲甲乙乙丙丙000013542710639111141211125131112工厂工厂设备数设备数Page 361kkkssx()kkV x解解: 将问题按工厂分为三个阶段，将问题按工厂分为三个阶段， 甲、乙、丙三个工厂分别编号为甲、乙、丙三个工厂分别编号为1、2、3阶段变量：阶段变量：k=1,2,3状态变量：状态变量：Sk表示为分配给第表示为分配给第k个工厂至第个工厂至第n个工厂的设备台数。个工厂的设备台数。决策变量：决

25、策变量： xk表示为分配给第表示为分配给第k个工厂的设备台数。个工厂的设备台数。表示为表示为xk台设备分配到第台设备分配到第k个工厂所得的盈利值。个工厂所得的盈利值。状态转移方程：状态转移方程：(0)kkxS阶段指标：阶段指标：Page 3711044()max()() , 3,2,1()0kkkkkkkkxsfsV xfSkfs逆推方程为：逆推方程为：Page 383333334433( )max()()max()xxf sV xfxV x下面从最后一个阶段开始向前逆推计算。下面从最后一个阶段开始向前逆推计算。k=3时：时：因为此时只有一个工厂，有多少台设备就全部分配给工厂丙，因为此时只有一

26、个工厂，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值，如下表。故它的盈利值就是该段的最大盈利值，如下表。Page 39s3x3V3(x3)s4f4(s4)V3(x3) +f4(s4)f3(s3) x3*表中表中x3*表示使表示使f3(s3)为最大值时的最优决策。为最大值时的最优决策。Page 40s3x3V3(x3)s4f4(s4)V3(x3) +f4(s4)f3(s3) x3*000000001140044122600662331100111134412001212455120012125表中表中x3*表示使表示使f3(s3)为最大值时的最优决策。为最大值时的最优决策。P

27、age 41k=2时时S2x2V2(x2)s3f3(s3)V2(x2) +f3(s3)f2(s2) x2*0123Page 42S2x2V2(x2)s3f3(s3)V2(x2) +f3(s3)f2(s2) x2*45Page 43k=2时时S2x2V2(x2)s3f3(s3)V2(x2) +f3(s3)f2(s2) x2*0000000010105104045512012051021064069101023012305101132101164011111411142Page 44S2x2V2(x2)s3f3(s3)V2(x2) +f3(s3)f2(s2) x2*4012340510111143

28、21012116401216161511161,250123450510111111543210121211640121721171511212Page 45k=1时时S1x1V1(x1)s2f2(s2)V1(x1) +f2(s2)f1(s1)x1*5Page 46k=1时时S1x1V1(x1)s2f2(s2)V1(x1) +f2(s2)f1(s1) x1*5012345037912135432102116141050211921191713210，2最优分配方案有两个：最优分配方案有两个：（1）（2）*1230,2,3xxx*1232,2,1xxx最优赢利为最优赢利为21万元万元Page 4

29、7在本问题中，若原设备仅有在本问题中，若原设备仅有4台，如何求最优分配方案？台，如何求最优分配方案？只需在最后的表格中修改即可：只需在最后的表格中修改即可：S1x1V1(x1)s2f2(s2)V1(x1) +f2(s2)f1(s1) x1*40123403791243210161410501617171412171，2Page 48最优分配方案有两个：最优分配方案有两个：（1）（2）*1231,2,1xxx*1232,2,0 xxx最优赢利为最优赢利为17万元万元Page 49练习：练习：资源平行分配问题资源平行分配问题 有一部火车每天沿着公路给有一部火车每天沿着公路给4个零售店卸下个零售店卸

30、下6箱货物，箱货物，如果各零售店出售该货物所得利润如下表所示，试求在如果各零售店出售该货物所得利润如下表所示，试求在各零售店卸下几箱货物，能使获得总利润最大？各零售店卸下几箱货物，能使获得总利润最大？1234000001423426455376764788657986671086零售店零售店箱数箱数Page 50s4x4V4(x4)s5f5(s5)V4(x4) +f5(s5)f4(s4) x4*00000000114004412250055233600663446006645560066566600666k=4时时Page 51s3x3V3(x3)s4f4(s4)V3(x3) +f4(s4)f

31、3(s3) x3*00000000101031040434020120352105405757130123035732106540689792k=3时时Page 52s3x3V3(x3)s4f4(s4)V3(x3) +f4(s4)f3(s3) x3*40123403578432106654069101181135012345035788543210666540691112128123,4k=3时时Page 53s3x3V3(x3)s4f4(s4)V3(x3) +f4(s4)f3(s3)x3*6012345603578886543210666654069111313128133,4k=3时时Pa

32、ge 54k=2时时S2x2V2(x2)s3f3(s3)V2(x2) +f3(s3)f2(s2) x2*000140270390,14110,1,25131,2,36152,3,4Page 55k=1时时S1x1V1(x1)s2f2(s2)V1(x1) +f2(s2)f1(s1)x1*6171,2最优分配方案有六个：最优分配方案有六个：(1,1,3,1), (1,2,2,1) (1,3,1,1)(2,0,3,1), (2,1,2,1) (2,2,1,1)Page 56最优分配方案有五个：最优分配方案有五个：(1,1,3,1), (1,2,2,1) (1,3,1,1)(2,1,2,1) (2,2

33、,1,1)上例若增加条件：上例若增加条件：“每个零售店至少要有一箱货物每个零售店至少要有一箱货物” 如何求解？如何求解？Page 57练习：练习：资源平行分配问题资源平行分配问题 某公司打算向它的三个营业区增设六个零售店，每某公司打算向它的三个营业区增设六个零售店，每个营业区至少增设一个。从各区赚取的利润（单位：万个营业区至少增设一个。从各区赚取的利润（单位：万元）与增设的销售店个数有关，数据如下表。如何增设元）与增设的销售店个数有关，数据如下表。如何增设可使获得总利润最大？可使获得总利润最大？A区利润区利润B区利润区利润C区利润区利润01002001501200210160228022017

34、033302251804340230200销售店增加数销售店增加数Page 58例例3. （生产存贮问题）（生产存贮问题）某工厂要对一种产品制定今后四个时某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的期的生产计划，据估计在今后四个时期内，市场对该产品的需求量如下表所示。需求量如下表所示。假定该厂生产每批产品的固定成本为假定该厂生产每批产品的固定成本为3千元，若不生产就为千元，若不生产就为0；每单位产品成本为；每单位产品成本为1千元；每个时期最大生产能力为千元；每个时期最大生产能力为6个单个单位；每个时期末未售出的产品，每单位需付存贮费位；每个时期末未售出的

35、产品，每单位需付存贮费0.5千元。千元。还假定第一时期的初始库存为还假定第一时期的初始库存为0，第四时期末的库存也为，第四时期末的库存也为0。试问该厂应如何安排各个时期的生产与库存，才能在满足市试问该厂应如何安排各个时期的生产与库存，才能在满足市场需要的条件下，使总成本最小。场需要的条件下，使总成本最小。时期时期1234需求量需求量2324Page 591kkkkssxd()()()kkkkVxc xh S解解: 阶段变量：阶段变量：k =1，2, 3，4，表示四个时期，表示四个时期状态变量：状态变量：Sk表示表示k阶段初的库存。阶段初的库存。决策变量：决策变量： xk表示表示k阶段的生产数量

36、。阶段的生产数量。表示表示k阶段阶段 Sk 状态时状态时生产生产xk产品的生产费用产品的生产费用ck及存贮费用及存贮费用hk 。状态转移方程：状态转移方程：(06)kx阶段指标：阶段指标：Page 60110655( )min()() , 4,3,2,1( )0kkkkkkkxf sV xfSkf s逆推方程为：逆推方程为：Page 61s4x4c4(x4)h4(S4)s5f5(s5)V4(x4) +h4(S4)+f5(s5)f4(s4)x4*0470007741360.5006.56.532251006623141.5005.55.51400200220k=4时时Page 62s3x3c3(

37、x3)h3(S3)s4f4(s4)c3(x3)+ h3(S3)+f4(s4)f3(s3) x3*0234565678900123476.565.521212.51313.511116112345456780.50123476.565.52111212.51310.510.55k=3时时Page 63s3x3c3(x3)h3(S3)s4f4(s4)c3(x3)+ h3(S3)+f4(s4)f3(s3) x3*2012340456710123476.565.52811.51212.510803012304561.512346.565.52811.5129.580k=3时时Page 64s3x3c3

38、(x3)h3(S3)s4f4(s4)c3(x3)+ h3(S3)+f4(s4)f3(s3) x3*4012045223465.52811.5980501042.5345.5288.580600342550k=3时时Page 65k=2时时S2x2c2(x2)h2(S2)s3f3(s3)c2(x2)+ h2(S2)+f3(s3)f2(s2)x2*034566789001231110.5881717.51617165123456567890.50123411.510.588816.51715.516.517.515.54Page 66k=2时时S2x2c2(x2)h2(S2)s3f3(s3)c2(

39、x2)+ h2(S2)+f3(s3)f2(s2)x2*212345645678910123451110.588881616.5151617181533012345604567891.501234561110.58888512.51614.515.516.517.515.512.50Page 67k=2时时S2x2c2(x2)h2(S2)s3f3(s3)c2(x2)+ h2(S2)+f3(s3)f2(s2)x2*4012345045678212345610.58888512.5141516171512.50Page 68k=1时时S1x1c1(x1)h1(S1)s2f2(s2)c1(x1) +h

40、1(S1) +f2(s2)f1(s1)x1*023456567890012341615.51612.512.52121.52320.521.520.55最优分配方案为最优分配方案为： （5,0,6,0）Page 69练习练习. 某工厂根据合同需要，其月底交货任务如下表所示。某工厂根据合同需要，其月底交货任务如下表所示。 假定该厂生产能力为每月假定该厂生产能力为每月4百件，该厂仓库的存货能力百件，该厂仓库的存货能力为为3百件，已知每百件，已知每100件货物的生产费为件货物的生产费为10000元，在进行生产元，在进行生产的月份，工厂要支出经常费的月份，工厂要支出经常费4000元，仓库保管费为每百件

41、货元，仓库保管费为每百件货物每月物每月1000元。假定开始时及元。假定开始时及6月底交货后无存货。试问该厂月底交货后无存货。试问该厂应如何安排各个月份的生产，才能在满足交货任务的条件下应如何安排各个月份的生产，才能在满足交货任务的条件下，使总费用最小？，使总费用最小？月份月份123456需求量需求量（百件）（百件）125321Page 70例例4.可靠性问题可靠性问题 考虑设计一种有三个主要元件的电器设备。这三个元考虑设计一种有三个主要元件的电器设备。这三个元件是串联的，所有只要有一个元件故障将使整个设备发件是串联的，所有只要有一个元件故障将使整个设备发生故障。设备的可靠性（不发生故障的概率）

42、可以通过生故障。设备的可靠性（不发生故障的概率）可以通过在每个元件上并联备用的元件进行改进，每个元件可以在每个元件上并联备用的元件进行改进，每个元件可以由一个，两个，或三个元件并联。设计这种设备的总资由一个，两个，或三个元件并联。设计这种设备的总资金为金为10（单位：千元）。对元件（单位：千元）。对元件 i (i=1,2,3)配备配备 个元个元件后的可靠性为件后的可靠性为 ，成本为，成本为 ，具体数据由，具体数据由下表给出。试确定个元件并联的元件数目，使得在不超下表给出。试确定个元件并联的元件数目，使得在不超过总设计费用条件下，设备的可靠性最大。过总设计费用条件下，设备的可靠性最大。ix()i

43、iCx()iiRxPage 71i=1i=2i=3RCRCRC10.610.730.5220.820.850.7430.930.960.95ixPage 72解：可看作一个三阶段动态规划问题解：可看作一个三阶段动态规划问题 （非线性规划）（非线性规划） 设备的总可靠性设备的总可靠性 阶段变量阶段变量k k： 状态变量状态变量S Sk k： 决策变量决策变量x xk k： 状态转移方程状态转移方程： 阶段指标阶段指标: :1()kkkkSSCxk=1,2,3k=1,2,3；( (表示元件号表示元件号) )表示设计表示设计k号元件前剩有的资金数号元件前剩有的资金数选择选择k号元件的并联数号元件的并

44、联数112233()()()RRxRxRx()kkRx第第k号元件的并联数为号元件的并联数为 时的可时的可靠性靠性kxPage 73则递推方程为：则递推方程为：kkkk+1k+1x1,2,33144f (S )=()f(S)1,2,3()(1)(S )=1max kkkkkiikRxkCxSCf注注：剩余的资金至少可以买一个。：剩余的资金至少可以买一个。Page 74下面从最后一个阶段开始向前逆推计算：下面从最后一个阶段开始向前逆推计算：k=3时：时：326SPage 75s3x3R3(x3)S4f4(s4)R3f3f3x3*23456Page 76s3x3R3(x3)S4f4(s4)R3f3

45、f3x3*210.5010.50.51310.5110.50.514120.50.720110.50.70.7251230.50.70.93011110.50.70.90.9361230.50.70.94211110.50.70.90.93Page 77（填表）（填表）S2x2R2S3f3R2f3f2x2*56789259SPage 78S2x2R2S3f3R2f3f2x2*510.720.50.350.351610.730.50.350.3517120.70.8420.70.50.490.40.49181230.70.80.95320.90.50.50.630.40.450.63191230.70.80.96430.90.70.50.630.560.450.631259SPage 79S1x1R1S2f2R1f2f1x1*101230.60.80.99870.630.630.490.3780.5040.4410.5042110S 最优安排为：最优安排为：*1232,1,3xxxPage 80 应用：生产存储问题，背包问题，货郎担问题，求解静应用：生产存储问题，背包问题，货郎担问题，求解静态规划问题等等态规划问题等等 动态规划没有统一的公式和求解方法，需具体分析题目。动态规划没有统一的公式和求解方法，需具体分析题目。