第10章动态规划学习教案

1、会计学1第第10章动态章动态(dngti)规划规划第一页，共76页。2第1页/共75页第二页，共76页。3 阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策) E D1 D2 10* 6 10 6 E E第2页/共75页第三页，共76页。4 第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论(toln)分别求C1，C2，C3到D1，D2 的最短路径问题： 表10-2分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。 1 1 多阶段多阶段(jidu

2、n)(jidun)决策过程最优化问题举例决策过程最优化问题举例 阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策) D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D1第3页/共75页第四页，共76页。5第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题： 表10-3 分析(fnx)得知：如果经过B1，则走B1-C2-D2-E； 如果经过B2，则走B2-C

3、3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。 1 1 多阶段决策过程多阶段决策过程(guchng)(guchng)最优化问题举例最优化问题举例 阶段2本阶段始点（状态） 本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策) C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C3第4页/共75页第五页，共76页。

4、6第一阶段：只有1个始点A，终点(zhngdin)有B1,B2,B3,B4 。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题： 表10-4最后，可以得到：从A到E的最短路径为A B4 C3 D1 E1 1 多阶段决策过程多阶段决策过程(guchng)(guchng)最优化问题举例最优化问题举例 阶段1本阶段始点(状态) 本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策) B1 B2 B3 B4 A 4+12=16 3+13=163+14=172+12=14 12 C2第5页/共75页第六页，共76页。7 以上计算过程及结果，可用图以上计算过程及结果，可用图2

5、表示，可以看到，以上方法不仅表示，可以看到，以上方法不仅得到了从得到了从A到到D的最短路径，同时，也得到了从图中任一点到的最短路径，同时，也得到了从图中任一点到E的最的最短路径。短路径。 以上过程，仅用了以上过程，仅用了22次加法次加法(jif)，计算效率远高于穷举法。，计算效率远高于穷举法。BACBDBCDEC412312312332164724838675161060106121111121314144B1275121 1 多阶段决策过程多阶段决策过程(guchng)(guchng)最优化问题最优化问题举例举例第6页/共75页第七页，共76页。8一、基本概念： 1、阶段k：表示决策顺序的离

6、散的量，阶段可以按时间或空间划分。 2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。 3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。 决策允许集合(jh)Dk(sk)：在状态sk下，允许采取决策的全体。 4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。 5、状态转移方程 sk+1=Tk(sk, xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。2 2 基本概念、基本方程基本概念、基本方程(fngchng)(f

7、ngchng)与最优化与最优化原理原理第7页/共75页第八页，共76页。9 6、阶段指标函数、阶段指标函数vk(sk, xk)：从状态：从状态sk出发，选择决策出发，选择决策xk所产生的第所产生的第k阶段指阶段指标。标。 过程指标函数过程指标函数Vk,n(sk, xk, xk+1, xn)：从状态：从状态sk出发，选择决策出发，选择决策xk, xk+1, , xn所产生的过程指标。动态规划要求过程指标具有可分离所产生的过程指标。动态规划要求过程指标具有可分离性，即性，即 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)+Vk+1(sk+1, xk+1, , xn)称指

8、标具有可加性，或称指标具有可加性，或 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1, xk+1, , xn)称指标具有可乘性。称指标具有可乘性。二、基本二、基本(jbn)方程：方程： 最优指标函数最优指标函数fk(sk)：从状态：从状态sk出发，对所有的策略出发，对所有的策略Pk,n，过程指，过程指标标Vk,n的最优值，即的最优值，即 ),()(,)(nkknksDxkkPsVsfoptkkk2 2 基本概念、基本方程基本概念、基本方程(fngchng)(fngchng)与最优化原与最优化原理理第8页/共75页第九页，共76页。10 对于可加性指

9、标函数，上式可以写为对于可加性指标函数，上式可以写为 上式中上式中“opt”表示表示“max”或或“min”。对于可乘性指标。对于可乘性指标函数，上式可以函数，上式可以写为写为 以上式子称为动态规划最优指标的递推方程，是动态以上式子称为动态规划最优指标的递推方程，是动态规划的基本规划的基本方程。方程。 终端条件：为了使以上的递推方程有递推的起点，必终端条件：为了使以上的递推方程有递推的起点，必须要设定须要设定(sh dn)最最优指标的终端条件，一般最后一个状态优指标的终端条件，一般最后一个状态n+1下最优指标下最优指标fn+1(sn+1) = 0。nksfxsvsfkkkkksDxkkoptk

10、kk, 2 , 1)(),()(11)(nksfxsvsfkkkkksDxkkoptkkk, 2 , 1)(),()(11)(2 2 基本基本(jbn)(jbn)概念、基本概念、基本(jbn)(jbn)方程与最方程与最优化原理优化原理第9页/共75页第十页，共76页。11三、最优化原理三、最优化原理(yunl) 作为整个过程的最优策略具有如下性质：作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的策必定构成最优子策略

11、。就是说，最优策略的任意子策略都是最优的。任意子策略都是最优的。2 2 基本基本(jbn)(jbn)概念、基本概念、基本(jbn)(jbn)方程与最优化方程与最优化原理原理第10页/共75页第十一页，共76页。12一、资源分配问题一、资源分配问题 例例2. 某公司拟将某种设备某公司拟将某种设备5台，分配给所属的甲、乙、丙三个台，分配给所属的甲、乙、丙三个工工厂。各工厂厂。各工厂(gngchng)获得此设备后，预测可创造的利润如表获得此设备后，预测可创造的利润如表10-5所示，问这所示，问这5台设备应如何分配给这台设备应如何分配给这3个工厂个工厂(gngchng)，使得所创造的总，使得所创造的总

12、利润为最大？利润为最大？ 表表10-5 盈利 工厂设备台数 甲 厂 乙 厂 丙 厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 123 3 动态动态(dngti)(dngti)规划的应用规划的应用(1)(1)第11页/共75页第十二页，共76页。13解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设 sk= 分配给第k个厂至第3个厂的设备台数（k=1、2、3）。 xk=分配给第k个设备台数。 已知s1=5, 并有 从与的定义，可知以下(yxi)我们从第三阶段开始计算。222223),(xsxsTskskx33

13、xs 3 3 动态动态(dngti)(dngti)规划的应用规划的应用(1)(1)111112),(xsxsTs第12页/共75页第十三页，共76页。14 第三阶段第三阶段: 显然将台设备都分配给第显然将台设备都分配给第3工厂时工厂时，也就是时，第也就是时，第3阶段的指标值（即第阶段的指标值（即第3厂的盈利）厂的盈利）为最大，即为最大，即 由于第由于第3阶段是最后的阶段，故有阶段是最后的阶段，故有 其中可取值为其中可取值为0,1,2,3,4,5。其数值。其数值(shz)计算见表计算见表106。 )5 , 4 , 3 , 2 , 1 , 0(33ss).,(),(max)(333333333ss

14、rxsrsfx3x),(),(max3333333ssrxsrx3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)33xs 第13页/共75页第十四页，共76页。15 表表106 012345000014 4126623111134121245121253x3s),(333xsr)(33sf3*x3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)第14页/共75页第十五页，共76页。16 其中表示取3子过程上最优指标值时的决策，例如在表10-6中可知当=4时，有有此时，即当时，此时取（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利(yn l

15、)）为12，最优3子过程最优指标值也为12。 第二阶段： 当把台设备分配给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利(yn l)即最优2子过程最优指标函数值为 3*x)(33sf3x3s;12)4 , 4(3r,12)4(3f43*x43s43x)5 , 4 , 3 , 2 , 1 , 0(22ss2s)(),(max)(33222222sfxsrsfx3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)第15页/共75页第十六页，共76页。17因为上式也可写成其数值(shz)计算如表107所示。表107 , 223xss0123450 00104 5

16、1206 54 1023011 56 110 1424012 114110 161,25012 512 116114 1102122x2s)(),(233222xsfxsr)(22sf2*x00050104101156101110)(),(max)(223222222xsfxsrsfx3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)第16页/共75页第十七页，共76页。18 其中在的这一行里，当时，这里从表105中可知(k zh)，把1台设备交给乙厂所得盈利数即可，知，这里从表106查即可知(k zh)=11。同样可知(k zh)当时，可知(k zh) ;当时，；当时，

17、；当时， ；由于，不可能分2厂5台设备，故时，栏空着不填。从这些数值中取得最大即得，即有=16。在此行中我们在取最大值的 上面加一横以示区别，也可知(k zh)这时的最优决策为1或2。42s12x16115) 3() 1 , 4() 14() 1 , 4()(),(3232223222frfrxsfxsr) 1 , 4(2r5) 1 , 4(2r)3()14(33ff) 3(3f)3(3f22x16610)2()2 , 4()24()2 , 4()(),(3232223222frfrxsfxsr02x12120)04()0 , 4(32 fr32x411)34()3 , 4(32 fr42x1

18、1011)44()4 , 4(32 fr42s52x)54()5 , 4(32 fr)4(2f)4(2f)(),(223222xsfxsr2x3 3 动态动态(dngti)(dngti)规划的应用规划的应用(1)(1)第17页/共75页第十八页，共76页。19第一阶段：第一阶段：把台设备把台设备(shbi)分配给第分配给第1，第，第2，第，第3厂时厂时，最大，最大盈利为其中可取值盈利为其中可取值0,1,2,3,4,5.数值计算见表数值计算见表108 表表10-8 然后按计算表格的顺序推算，可知最优分配方案有两个然后按计算表格的顺序推算，可知最优分配方案有两个： 1.由于，根据，查表由于，根据，

19、查表107可可知，再由知，再由 ，求得。即，求得。即分配分配给甲厂给甲厂0台，乙厂台，乙厂2台，丙厂台，丙厂3台。台。 2.由于，根据由于，根据 ，查表，查表107可可 )5(11ss),5(), 5(max)5(111111xfxrfx1x0123455 316 9+10 12+5 13+0 21 0,21x1s)5(), 5(1211xfxr210147)(1xf1*x01*x5051*12xss02*x3252*23xss333* sx21*x3251*12xss3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)第18页/共75页第十九页，共76页。20知，再由 ,

20、求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到(d do)最高的总盈利21万元。 22*x1232*23xss133* sx3 3 动态动态(dngti)(dngti)规划的应用规划的应用(1)(1)第19页/共75页第二十页，共76页。21二、背包问题二、背包问题 设有设有n种物品，每一种物品数量无限。第种物品，每一种物品数量无限。第i种物品每种物品每件件重量为重量为wi公斤，每件价值公斤，每件价值ci元。现有一只可装载重量为元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。包中物

21、品的价值最高。 这个问题可以用整数规划模型这个问题可以用整数规划模型(mxng)来描述。来描述。设设xi为第为第i种种物品装入背包的件数（物品装入背包的件数（i =1, 2, , n），背包中物品的总），背包中物品的总价值为价值为z，则，则 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2, , xn0 且为整数。且为整数。3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)第20页/共75页第二十一页，共76页。22 下面用动态规划逆序解法求解它。设阶段变量k：第k次装载第k种物品（k=1, 2, , n）状态变量s

22、k：第k次装载时背包还可以装载的重量；决策变量uk = xk：第k次装载第k种物品的件数；决策允许集合：Dk(sk) = xk | 0 xksk/wk，xk为整数；状态转移(zhuny)方程： sk+1 = sk wkxk；阶段指标： vk = ckxk；最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使用价值；递推方程： fk(sk) = max ckxk+fk+1(sk+1) = max ckxk+fk+1(sk wkxk)； xDk(sk) 终端条件： fn+1(sn+1) = 0。3 3 动态动态(dngti)(dngti)规划的应用规划的应用(1)(1)第21页/共75页

23、第二十二页，共76页。23例例3.某咨询公司有某咨询公司有10个工作日可以去处理四种类型个工作日可以去处理四种类型的咨的咨询项目，每种类型的咨询项目中待处理的客户数量、处理询项目，每种类型的咨询项目中待处理的客户数量、处理每个每个客户所需工作日数以及所获得的利润如表客户所需工作日数以及所获得的利润如表109所示。显所示。显然该公然该公司在司在10天内不能处理完所有的客户，它可以自己挑选一些天内不能处理完所有的客户，它可以自己挑选一些客客户，其余的请其他咨询公司去做，应如何户，其余的请其他咨询公司去做，应如何(rh)选择客户选择客户使得在这使得在这10个工作日中获利最大？个工作日中获利最大？ 表

24、表109 咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润1234432213472811203 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)第22页/共75页第二十三页，共76页。24解：用动态规划来求解此题。解：用动态规划来求解此题。我们把此问题分成四个阶段我们把此问题分成四个阶段(jidun)，第一阶段，第一阶段(jidun)我我们决策将们决策将处理多少个第一种咨询项目类型中的客户，第二阶段处理多少个第一种咨询项目类型中的客户，第二阶段(jidun)决决策将处理多少个第二种咨询项目类型中的客户，第三阶策将处理多少个第二种咨询项目类型中的客户，第

25、三阶段、第四阶段段、第四阶段(jidun)我们也将作出类似的决策。我们设我们也将作出类似的决策。我们设分配给第分配给第k种咨询项目到第四种咨询项目的所种咨询项目到第四种咨询项目的所有客户的总工作日（第有客户的总工作日（第k阶段阶段(jidun)的状态变量）。的状态变量）。 =在第在第k种咨询项目中处理客户的数量（第种咨询项目中处理客户的数量（第k阶段阶段(jidun)的决策变量）。的决策变量）。已知已知10并有并有 kx1s,),(111112xsxsTsks3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)第23页/共75页第二十四页，共76页。25 并从与的定义可知并

26、从与的定义可知从第四阶段开始从第四阶段开始(kish)计算：计算：显然将个工作日尽可能分配给第四显然将个工作日尽可能分配给第四类咨询项目，即时，第四阶段的指标值为最大，类咨询项目，即时，第四阶段的指标值为最大，其中，表示取不大于的最大整数，符号为其中，表示取不大于的最大整数，符号为取整符号，故有取整符号，故有由于第四阶段是最后的阶段，故有由于第四阶段是最后的阶段，故有,3),(222223xsxsTs.4),(333334xsxsTskskx447xs 4s)10, 1 , 0(4s7/44sx 7/4s7/4s ).7/,(),(max4444444ssrxsrx),7/,(),(max)(

27、4444*44444ssrxsrsfx3 3 动态动态(dngti)(dngti)规划的应用规划的应用(1)(1)第24页/共75页第二十五页，共76页。26因为因为(yn wi)至多为至多为10，其数值计算见表，其数值计算见表1010。 表表10104s01000100200300400500600702018020190201100114x4s),(444xsr)(44sf4*x0000000202020203 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)第25页/共75页第二十六页，共76页。27第三阶段：第三阶段：当把个工作日分配给第四类和第当把个工作日分配给第

28、四类和第三类咨询项目三类咨询项目(xingm)时，则对每个值，都有一种时，则对每个值，都有一种最优分配方最优分配方案，使其最大盈利即最优案，使其最大盈利即最优3子过程最优指标函数值为子过程最优指标函数值为 因为因为因为至多为因为至多为10，所以的取值可为，所以的取值可为0,1,2。其数值。其数值计算计算见表见表1011。)10, 3 , 2 , 1 , 0(33ss3s. )(),(max)(33222222sfxsrsfx2233xss. )4(),(max)(334333333xsfxsrsfx3s3x3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)第26页/共75

29、页第二十七页，共76页。28 表表1011 0 1 2000 1 00 200 300 40011 1 50011 1 60011 1 7 11+0 20 0 8020 11+0 22 2 9020 11+0 22 2 10020 11+0 22 23x3s)4(),(334333xsfxsr)(33sf3*x000000200011011011022022022003 3 动态规划动态规划(guhu)(guhu)的应用的应用(1)(1)第27页/共75页第二十八页，共76页。29 第二阶段：第二阶段： 同样以每个值都有一种同样以每个值都有一种(y zhn)最优分配方案，使其最优分配方案，使其

30、最大盈利即最大盈利即最优最优2子过程最优指标函数值为：子过程最优指标函数值为：因为，故有因为，故有因为至多为因为至多为10，所以的取值为，所以的取值为0,1,2,3。其数值计算。其数值计算见表见表1012。. )3(),(max)(223222222xsfxsrsfx2233xss. )3(),(max)(223222222xsfxsrsfx2s2x2s3 3 动态动态(dngti)(dngti)规划的应用规划的应用(1)(1)第28页/共75页第二十九页，共76页。30表表10-12第29页/共75页第三十页，共76页。31 第一阶段：第一阶段： 我们我们(w men)已知，又因为已知，又因

31、为 ，同，同样有样有 因为因为 ,故可取值为故可取值为0,1,2, ,10。其数值计算。其数值计算见表见表1013。 表表1013101s. )(),(max)(112111111xsfxsrsfx112xss.)10(),10(max)10(121111xfxrfx101s1x3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1) (1) 第30页/共75页第三十一页，共76页。32 从 表 1 0 1 3 可 知 ， 从 而 得10010，在表1012的的这一行可知，由，查表1011的的这一行可知，最后由，查表10-10的的这一行得，综上所述得最优解为：此时最大盈利为28。现在

32、我们不妨假设该咨询公司的工作计划有所改变，只有8个工作日来处理这四类咨询项目，那么该咨询公司如何选择客户使得获利最大呢？我们不必从头开始重做这个问题，而只要在第一阶段上把改成8，重新(chngxn)计算就可得到结果，如表1014所示，这是动态规划的一个好处。28)10(1f01*x1*210 xs102s12*x731032*23xss73s03*x7073*34xss74s14*x0, 1, 03*2*1*xxx, 14*x4s3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1) (1) 第31页/共75页第三十二页，共76页。33表表1014如上一样可从表如上一样可从表101

33、4,1012,1011,1010得到两组最优解得到两组最优解如下：如下：它们的最优解（即最大盈利）都为它们的最优解（即最大盈利）都为22。一旦咨询的工作日不是减少而是增加，那么我们不仅一旦咨询的工作日不是减少而是增加，那么我们不仅(bjn)要重新计要重新计算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加的工作日的新的信息，也可得到新的结果。的工作日的新的信息，也可得到新的结果。3042)4321xxxx1001)4*3*2*1*xxxx3 3 动态动态(dngti)(dngti)规划的应用规划的应用(1) (1) 第32页/共

34、75页第三十三页，共76页。34 实际上，背包问题实际上，背包问题(wnt)我们也可以用整数规划来求解，如果背包携带物品重量的限制为我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这公斤，这N种物品中第种物品中第i种物品的重量为，价值为，第种物品的重量为，价值为，第i种物品的总数量的，我们可以设表示携带第种物品的总数量的，我们可以设表示携带第i种物品的数量，则其数学模型为：种物品的数量，则其数学模型为：S.T. 且为整数。且为整数。 我们不妨用此模型去求解例我们不妨用此模型去求解例3，也一定得出同样的结果。，也一定得出同样的结果。iwicinix,max1Niiixcf0),

35、2 , 1(1iiiNiiixNinxWxw3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1) (1) 第33页/共75页第三十四页，共76页。35三、生产与存贮问题 例4.某公司为主要电力公司生产大型变压器，由于电力采取预订方式(fngsh)购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如表1015所示。生产成本随着生产数量而变化。调试费为4，除了调度费用外，每月生产的头两台各花费为2，后两台花费为1。最大生产能力每月为4台，生产成本如表1016所示。表10153 3 动态规划动态规划(guhu)(guhu)的

36、应用的应用(1) (1) 第34页/共75页第三十五页，共76页。36 表表1016每台变压器在仓库中由这个月存到下个月的储存费为每台变压器在仓库中由这个月存到下个月的储存费为1，仓库的最大储存能力为仓库的最大储存能力为3台，另外，知道在台，另外，知道在1月月1日时仓库里存日时仓库里存有一台变压器，要求在有一台变压器，要求在4月月30日仓库的库存量为零。试问该公日仓库的库存量为零。试问该公司应如何制定生产计划司应如何制定生产计划(jhu)，使得四个月的生产成本和储存总费，使得四个月的生产成本和储存总费用最少？用最少？解：我们按月份来划分阶段，第解：我们按月份来划分阶段，第i个月为第个月为第i阶

37、段：（阶段：（i=1,2,3,4). 设设 为第为第k阶段期初库存量；阶段期初库存量； k=1,2,3,4 ks3 3 动态动态(dngti)(dngti)规划的应用规划的应用(1) (1) 第35页/共75页第三十六页，共76页。37为第为第k阶段生产量阶段生产量(chnling)； k=1,2,3,4为第为第k阶段需求量；阶段需求量； k=1,2,3,4，这已在表，这已在表10-15中告诉我们。中告诉我们。因为下个月的库存量等于上个月的库存量加上上个月的因为下个月的库存量等于上个月的库存量加上上个月的产量产量(chnling)减去上个月的需求量，我们就得到了如下状态转移方减去上个月的需求量

38、，我们就得到了如下状态转移方程：程：因为，故有因为，故有因为，故有因为，故有kxkd, 1112dxss11s, 1121dxs, 2223dxss, 3334dxss, 4445dxss05s, 4440dxs3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1) (1) 第36页/共75页第三十七页，共76页。38由于必须要满足由于必须要满足(mnz)需求，则有需求，则有通过移项得到通过移项得到 另一方面，第另一方面，第k阶段的生产量必不大于同期的生产能力阶段的生产量必不大于同期的生产能力（4台），也不大于第台），也不大于第k阶段至第四阶段的需求之和与第阶段至第四阶段的需求之和

39、与第k阶段阶段期初库存量之差，否则第期初库存量之差，否则第k阶段的生产量就要超过从第阶段的生产量就要超过从第k阶段阶段至第四阶段的总需求，故有至第四阶段的总需求，故有以下我们从第四阶段开始计算：以下我们从第四阶段开始计算：从以上的状态转移方程可知从以上的状态转移方程可知这样就有这样就有),4, 3 ,2, 1(,kdxskkkkkksdxkx44 ,)(minkikiksdx,0444dxs,34444ssdx)3 ,(),(min)(444444444ssrxsrsfx3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1) (1) 第37页/共75页第三十八页，共76页。39 这

40、里的阶段指标可以分成两部分，即生产成本与这里的阶段指标可以分成两部分，即生产成本与储存费，即为储存费，即为 由于第四阶段末要求库存为零，即有，由于第四阶段末要求库存为零，即有，这样这样(zhyng)可得可得 对于每个的可行值，的值列于表对于每个的可行值，的值列于表1017。 表表1017),(nnnxsr),()(),(nnnnnnnnxshxcxsr001),(444xsh)3()3 ,()3()3 ,()(444444444444scsshscssrsf4s)(44sf3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1) (1) 第38页/共75页第三十九页，共76页。40表

41、中当时，可知第四阶段要生产表中当时，可知第四阶段要生产台，从表台，从表1016可知总成本为可知总成本为9，同样可以算出当为，同样可以算出当为1,2,3时时的情况的情况(qngkung)，结果已列于表，结果已列于表1017中。中。第三阶段：第三阶段：此时有：此时有：因为以及所以有因为以及所以有例如，当第三阶段初库存量时，生产量为例如，当第三阶段初库存量时，生产量为2时，时，则所以生产成本为则所以生产成本为8，第三阶段末库存，第三阶段末库存为为2时，储存费为，而时，储存费为，而04s3344sx4s)(1)(),()(),(3333333333333dxsxcxshxcxsr,3334dxss,

42、13d)() 1(1)(min)(443333)4,4min(133333sfxsxcsfsxs) 1() 1(1)(min3343333)4,4min(1333xsfxsxcsxs13s3x2121333dxs221),2()()(4333444fdxsfsf3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1) (1) 第39页/共75页第四十页，共76页。41查1017表可知，这样可知，填入表1018中的栏内，其他结果(ji gu)如表1018所示 ： 表1018 第二阶段：因为所以有6) 2 (4f,16628)2()2 , 1 (43 fr2, 133xs, 422232

43、dxssd3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1) (1) 第40页/共75页第四十一页，共76页。42 计算结果如表1019所示。 表1019 )(),(min)(33222)4,8min(422222sfxsrsfsxs)(),()(min3322222)4,8min(4222sfxshxcsxs)()(1)(min222322222)4,8min(4222dxsfdxsxcsxs)4()4(1)(min2232222)4,8min(4222xsfxsxcsxs3 3 动态动态(dngti)(dngti)规划的应用规划的应用(1) (1) 第41页/共75页第四十

44、二页，共76页。43第一阶段：第一阶段：因为因为(yn wi)故有故有计算结果见表计算结果见表1020。 表表1020, 1, 2211111sdxssd)(),(min) 1 ()(22111411111sfxsrfsfx)21 ()21 (1)(min12111411xfxxcx3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1) (1) 第42页/共75页第四十三页，共76页。44利用递推关系利用递推关系(gun x)可以从表可以从表1020，表，表1019，表，表1018和表和表1017得到两组最优解：得到两组最优解： 这时有最低总成本这时有最低总成本29。0441)43

45、21xxxx3042)4321xxxx3 3 动态规划动态规划(guhu)(guhu)的应用的应用(1) (1) 第43页/共75页第四十四页，共76页。45高级科学家小组12300.400.600.8010.200.400.5020.150.200.30第44页/共75页第四十五页，共76页。46阶段123小组123第45页/共75页第四十六页，共76页。47 s3 f3*(s3) x3*008001050120302 x2s2f2(s2,x2)=P2(x2) f3*(s2-x2) f2*(s2) x2*012004804801030032030020180200160162第46页/共75

46、页第四十七页，共76页。48 x1s1f1(s1,x1)=P1(x1) f2*(s1-x1)f2*(s2)x2*01220064 0060 0072 0060 1第47页/共75页第四十八页，共76页。49第48页/共75页第四十九页，共76页。50第49页/共75页第五十页，共76页。51)()58max)(11kkkkkkksfxsxsf（kksx 0第50页/共75页第五十一页，共76页。52 )(2 .126 .13max)(9 . 07 . 0 8)(58max8)(58max)()(58max)(44404444440544405544404444444444xsxxsxxsxsx

47、sxsfxsxsfsxsxsxsx 第51页/共75页第五十二页，共76页。530*1x0*2x3*3sx 4*4sx 5*5sx 第52页/共75页第五十三页，共76页。549009 . 0)(9 . 07 . 01*11*12sxsxs8109 . 0)(9 . 07 . 02*22*23sxsxs5677 . 0)(9 . 07 . 03*33*34sxsxs3977 . 0)(9 . 07 . 04*44*45sxsxs第53页/共75页第五十四页，共76页。55500)(9 . 07 . 05556xsxs25005 . 455sx第54页/共75页第五十五页，共76页。5675005 .18)25005 . 4(5)25005 . 4(8max)(555555sssssf75007 . 07 .21max75005 .18)(58max)()(58max)(4405444055444044444444xssxsxsfxsxsfsxsxsx0*4x第55页/共75页第五十六页，共76页。570