管理运筹学第10章动态规划

《管理运筹学第10章动态规划》由会员分享，可在线阅读，更多相关《管理运筹学第10章动态规划（64页珍藏版）》请在金锄头文库上搜索。

1、管管 理理 运运 筹筹 学学第十章第十章 动态规划动态规划1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理3动态规划的应用动态规划的应用(1)4动态规划的应用动态规划的应用(2)1管管 理理 运运 筹筹 学学11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例例例1最短路径问题最短路径问题下下图图表表示示从从起起点点A到到终终点点E之之间间各各点点的的距距离离。求求A到到E的的最短路径。最短路径。BACBDBCDEC4123123123221647248386756110637512管管 理理 运运 筹筹 学学11

2、多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例用穷举法的计算量用穷举法的计算量:从从A到到E的路径有的路径有432=24条，计算条，计算每条路径的总长度需要做每条路径的总长度需要做4次加法，则计次加法，则计算各路径长度总共要进行算各路径长度总共要进行244=96次加法，次加法，做做23次比较，才能得出结果。次比较，才能得出结果。3管管 理理 运运 筹筹 学学11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例讨论：讨论：1、以以上上求求从从A到到E的的最最短短路路径径问问题题，可可以以转转化化为为四四个个性性质质完完全全相相同同，但但规规模模较较小小的的子子问问题题，即即分分

3、别别从从Di、Ci、Bi、A到到E的最短路径问题。的最短路径问题。第四阶段：两个始点第四阶段：两个始点D1和和D2，终点只有一个；终点只有一个；阶段阶段4本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策)ED1D210*6106EE分析得知：从分析得知：从D1和和D2到到E的最短路径唯一。的最短路径唯一。4管管 理理 运运 筹筹 学学第三阶段：有三个始点第三阶段：有三个始点C1，C2，C3，终点有，终点有D1，D2，对始点，对始点和终点进行分析和讨论分别求和终点进行分析和讨论分别求C1，C2，

4、C3到到D1，D2的最短的最短路径问题：路径问题：11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例阶段阶段3本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D1分析得知：如果经过分析得知：如果经过C1，则最短路为，则最短路为C1-D2-E；如果经过如果经过C2，则最短路为，则最短路为C2-D2-E；如果经过如果经过C3，则最短路为，则最短路为C3-D1-E。5管管

5、 理理 运运 筹筹 学学第第二二阶阶段段：有有4个个始始点点B1,B2,B3,B4，终终点点有有C1,C2,C3。对对始始点点和和终终点点进进行行分分析析和和讨讨论论分分别别求求B1,B2,B3,B4到到C1,C2,C3的的最最短路径问题：短路径问题：11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例阶段阶段2本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最的最短距离短距离本阶段最优终本阶段最优终点（最优决策点（最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=19

6、5+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C3分析得知：如果经过分析得知：如果经过B1，则走，则走B1-C2-D2-E；如果经过如果经过B2，则走，则走B2-C3-D1-E；如果经过如果经过B3，则走，则走B3-C3-D1-E；如果经过如果经过B4，则走，则走B4-C3-D1-E。6管管 理理 运运 筹筹 学学第一阶段：只有第一阶段：只有1个始点个始点A，终点有，终点有B1,B2,B3,B4。对始点和终。对始点和终点进行分析和讨论分别求点进行分析和讨论分别求A到到B1,B2,B3,B4的最短路径问题：的最短路径问题：11多阶段决策过程最优

7、化问题举例多阶段决策过程最优化问题举例阶段阶段1本阶段始本阶段始点点(状态状态)本阶段各终点（决策）本阶段各终点（决策）到到E的最的最短距离短距离本阶段最优终本阶段最优终点点(最优决策最优决策)B1B2B3B4A4+12=16 3+13=163+14=172+12=1414B4最后，可以得到：从最后，可以得到：从A到到E的最短路径为的最短路径为AB4C3D1E7管管 理理 运运 筹筹 学学以上计算过程及结果，可用图以上计算过程及结果，可用图2表示，可以看到，以上方法不仅表示，可以看到，以上方法不仅得到了从得到了从A到到D的最短路径，同时，也得到了从图中任一点到的最短路径，同时，也得到了从图中任

8、一点到E的最短路径。的最短路径。BACBDBCDEC4123123123321647248386751610601061211111213141412751211多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例以上过程，仅用了以上过程，仅用了22次加法，计算效率远高于穷举法。次加法，计算效率远高于穷举法。8管管 理理 运运 筹筹 学学一、基本概念：一、基本概念：1、阶阶段段k：表表示示决决策策顺顺序序的的离离散散的的量量，阶阶段段可可以以按按时时间间或或空空间间划划分。分。2、状状态态sk：能能确确定定地地表表示示决决策策过过程程当当前前特特征征的的量量。状状态态可可以以是是数数量，也

9、可以是字符，数量状态可以是连续的，也可以是离散的。量，也可以是字符，数量状态可以是连续的，也可以是离散的。3、决决策策xk：从从某某一一状状态态向向下下一一状状态态过过渡渡时时所所做做的的选选择择。决决策策是是所在状态的函数，记为所在状态的函数，记为xk(sk)。决策允许集合决策允许集合Dk(sk)：在状态在状态sk下，允许采取决策的全体。下，允许采取决策的全体。4、策策略略Pk,n(sk)：从从第第k阶阶段段开开始始到到最最后后第第n阶阶段段的的决决策策序序列列，称称k子策略。子策略。P1,n(s1)即为全过程策略。即为全过程策略。5、状状态态转转移移方方程程sk+1=Tk(sk,xk)：某

10、某一一状状态态以以及及该该状状态态下下的的决决策策，与下一状态之间的函数关系。与下一状态之间的函数关系。22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理9管管 理理 运运 筹筹 学学6、阶阶段段指指标标函函数数rk(sk,xk)：从从状状态态sk出出发发，选选择择决决策策xk所所产产生生的的第第k阶段指标。阶段指标。过过程程指指标标函函数数Vk,n(sk,xk,xk+1,xn)：从从状状态态sk出出发发，选选择择决决策策xk,xk+1,xn所所产产生生的的过过程程指指标标。动动态态规规划划要要求求过过程程指指标标具具有有 可可 分分 离离 性性 ， 即即 Vk,n(sk, xk

11、, xk+1, , xn) = rk(sk,xk)+Vk+1,n(sk+1,xk+1,xn)称称指指标标具具有有可可加加性性，或或Vk,n(sk,xk,xk+1,xn)=rk(sk,xk)Vk+1,n(sk+1,xk+1,xn)称称指指标标具具有有可可乘性。乘性。二、基本方程：二、基本方程：最最优优指指标标函函数数fk(sk)：从从状状态态sk出出发发，对对所所有有的的策策略略Pk,n，过过程程指标指标Vk,n的最优值，即的最优值，即22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理10管管 理理 运运 筹筹 学学对于可加性指标函数，上式可以写为对于可加性指标函数，上式可以写为上

12、上式式中中“opt”表表示示“max”或或“min”。对对于于可可乘乘性性指指标标函函数数，上式可以写为上式可以写为以以上上式式子子称称为为动动态态规规划划最最优优指指标标的的递递推推方方程程，是是动动态态规规划划的的基基本本方程。方程。终终端端条条件件：为为了了使使以以上上的的递递推推方方程程有有递递推推的的起起点点，必必须须要要设设定定最最优指标的终端条件，一般最后一个状态优指标的终端条件，一般最后一个状态n+1下最优指标下最优指标fn+1(sn+1)=0。22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理11管管 理理 运运 筹筹 学学三、最优化原理三、最优化原理作为整个过

13、程的最优策略具有如下性质：作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。任意子策略都是最优的。22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理12管管 理理 运运 筹筹 学学一、资源分配问题一、资源分配问题例例2.某某公公司司拟拟将将某某种种设设备备5台台，分分配配给给所所属属的的甲甲、乙乙、丙丙三三个个工工厂厂。各各工工厂厂获获得得此此

14、设设备备后后，预预测测可可创创造造的的利利润润如如下下表表所所示示，问问这这5台设备应如何分配给这台设备应如何分配给这3个工厂，使得所创造的总利润为最大？个工厂，使得所创造的总利润为最大？工厂工厂盈利盈利设备台数设备台数甲甲厂厂乙乙厂厂丙丙厂厂0000135427106391111412111251311123 3 动态规划的应用动态规划的应用(1)(1)13管管 理理 运运 筹筹 学学解解：将将问问题题按按工工厂厂分分为为三三个个阶阶段段，甲甲、乙乙、丙丙三三个个厂厂分分别编号为别编号为1、2、3厂。设厂。设sk=分分配配给给第第k个个厂厂至至第第3个个厂厂的的设设备备台台数数（k=1、2、

15、3）。）。xk=分配给第分配给第k个设备台数。个设备台数。已知已知s1=5,并有并有从从sk与与xk的定义，可知的定义，可知以下以下我们从第三阶段开始计算。我们从第三阶段开始计算。3 3 动态规划的应用动态规划的应用(1)14管管 理理 运运 筹筹 学学第三阶段：第三阶段：s3=x3012345000014 4126623111134121245121253 3 动态规划的应用动态规划的应用(1)012345000014 41266231111341212451212515管管 理理 运运 筹筹 学学01234500+00010+45+0 5120+65+410+010230+115+610+

16、411+014240+125+1110+611+411+0161,250+125+1210+1111+611+411+02123 3 动态规划的应用动态规划的应用(1)第二阶段：第二阶段：S3=S2-X216管管 理理 运运 筹筹 学学第一阶段：第一阶段：s1=5,s2=s1-x1=5-x101234550+213167+149+1012+513+0210,23 3 动态规划的应用动态规划的应用(1)（1）x1=0s2=s1-x1=5-0=5x2=2s3=s2-x2=5-2=3x3=3。即分配给甲厂。即分配给甲厂0台，乙厂台，乙厂2台，丙厂台，丙厂3台利润最台利润最大，最大利润为大，最大利润为

17、21万元。万元。（2）x1=2s2=s1-x1=5-2=3x2=2s3=s2-x2=3-2=1x3=1。即分配给甲厂。即分配给甲厂2台，乙厂台，乙厂2台，丙厂台，丙厂1台利润最台利润最大，最大利润为大，最大利润为21万元。万元。17管管 理理 运运 筹筹 学学二、背包问题二、背包问题设设有有n种种物物品品，第第i种种物物品品数数量量为为ni，第第i种种物物品品每每件件重重量量为为wi公公斤斤，第第i种种物物品品每每件件价价值值为为ci元元。现现有有一一只只可可装装载载重重量量为为W公公斤斤的的背背包包，求求各各种种物物品品应应各各取取多多少少件件放入背包，使背包中物品的价值最高。放入背包，使背

18、包中物品的价值最高。这这个个问问题题可可以以用用整整数数规规划划模模型型来来描描述述。设设xi为为第第i种种物物品品装装入入背背包包的的件件数数（i =1,2,n），背背包包中中物物品品的的总价值为总价值为z，则则Maxz=c1x1+c2x2+cnxns.t.w1x1+w2x2+wnxnW xini(i=1,2,n)x1,x2,xn 0且为整数。且为整数。3 3 动态规划的应用动态规划的应用(1)18管管 理理 运运 筹筹 学学下面用动态规划逆序解法求解它。设下面用动态规划逆序解法求解它。设阶段变量阶段变量k：装载第：装载第k种物品（种物品（k=1,2,n）状态变量状态变量sk：装载第：装载第

19、k种物品到第种物品到第n种物品的重量；种物品的重量；决策变量决策变量xk：装载第：装载第k种物品的件数；种物品的件数；决策允许集合：决策允许集合：Dk(sk)=xk|0 xk sk/wk，xk为整数为整数；状态转移方程：状态转移方程：sk+1=sk wkxk；阶段指标：阶段指标：rk=ckxk；最最优优过过程程指指标标函函数数fk(sk)：第第k到到n阶阶段段容容许许装装入入物物品品的的最最大大使用价值；使用价值；递推方程：递推方程：fk(sk)=maxckxk+fk+1(sk+1)=maxckxk+fk+1(sk wkxk)；x Dk(sk)终端条件：终端条件：fn+1(sn+1)=0。3

20、3 动态规划的应用动态规划的应用(1)19管管 理理 运运 筹筹 学学例例3.某某咨咨询询公公司司有有10个个工工作作日日可可以以去去处处理理四四种种类类型型的的咨咨询询项项目目，每每种种类类型型的的咨咨询询项项目目中中待待处处理理的的客客户户数数量量、处处理理每每个个客客户户所所需需工工作作日日数数以以及及所所获获得得的的利利润润如如下下表表所所示示。显显然然该该公公司司在在10天天内内不不能能处处理理完完所所有有的的客客户户，它它可可以以自自己己挑挑选选一一些些客客户户，其其余余的的请请其其他他咨咨询询公公司司去去做做，应应如如何何选选择择客客户户使使得得在在这这10个工作日中获利最大？个

21、工作日中获利最大？咨询项目咨询项目类型类型待处理客待处理客户数户数处理每个客户所处理每个客户所需工作日数需工作日数处理每个客户处理每个客户所获利润所获利润1234432213472811203 3 动态规划的应用动态规划的应用(1)20管管 理理 运运 筹筹 学学3动态规划的应用动态规划的应用(1)解：用整数规划来解有：解：用整数规划来解有：设设xi为处理第为处理第i种咨询项目的客户数，则其整数规划种咨询项目的客户数，则其整数规划模型为：模型为：Maxz=2x1+8x2+11x3+20x4S.t.x1+3x2+4x3+7x410x14x23x32x42x1,x2,x3,x40且为整数。且为整数

22、。21管管 理理 运运 筹筹 学学解：用动态规划来求解此题。解：用动态规划来求解此题。我我们们把把此此问问题题分分成成四四个个阶阶段段，第第一一阶阶段段我我们们决决策策将将处处理理多多少少个个第第一一种种咨咨询询项项目目类类型型中中的的客客户户，第第二二阶阶段段决决策策将将处处理理多多少少个个第第二二种种咨咨询询项项目目类类型型中中的的客客户户，第第三三阶阶段段、第第四四阶段我们也将作出类似的决策。我们设阶段我们也将作出类似的决策。我们设sk：分分配配给给第第k种种咨咨询询项项目目到到第第四四种种咨咨询询项项目目的的所所有有客客户户的的总工作日（第总工作日（第k阶段的状态变量）。阶段的状态变量

23、）。xk：在在第第k种种咨咨询询项项目目中中处处理理客客户户的的数数量量（第第k阶阶段段的的决决策策变量）。变量）。已知已知s110并有并有s2=T1(s1,x1)=s1-x1,s3=T2(s2,x2)=s2-3x2s4=T3(s3,x3)=s3-4x23 3 动态规划的应用动态规划的应用(1)22管管 理理 运运 筹筹 学学第四阶段：第四阶段：x4=s4/7=0,1010000100020003000400050006000702020180202019020201100202013 3 动态规划的应用动态规划的应用(1)23管管 理理 运运 筹筹 学学第三阶段：第三阶段：x3=s3/4=0

24、,1,2,s4=s3-4x301200+00010+00020+00030+00040+011+011150+011+011160+011+011170+2011+020080+2011+022+022290+2011+022+0222100+2011+022+02223 3 动态规划的应用动态规划的应用(1)24管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)第二阶段：第二阶段：x2=s2/3=0,1,2,3；s3=s2-3x2012300+00010+00020+00030+ +08+08140+118+011050+118+011060+118+016+016270+2

25、08+1116+020080+228+1116+022090+228+1116+024+0243100+228+2016+1124+028125管管 理理 运运 筹筹 学学第一阶段：第一阶段：s2=s1-x1=10-x133动态规划的应用动态规划的应用(1)01234567891000+2+4+6+8+10+12+14+16+18+20+282422201611118000280x1=0s2=s1-x1=10-0=10x2=1s3=s2-3x2=10-31=7x3=0s4=s3-4x3=7-40=7x4=1。即第一个咨询项目处理的客户数为即第一个咨询项目处理的客户数为0户，第二个咨询项目处户，

26、第二个咨询项目处理的客户数为理的客户数为1户，第三个咨询项目处理的客户数为户，第三个咨询项目处理的客户数为0户，户，第四个咨询项目处理的客户数为第四个咨询项目处理的客户数为1户，获得的利润最大，最户，获得的利润最大，最大利润为大利润为28。26管管 理理 运运 筹筹 学学三、生产与存贮问题三、生产与存贮问题例例4.某某公公司司为为主主要要电电力力公公司司生生产产大大型型变变压压器器，由由于于电电力力公公司司采采取取预预订订方方式式购购买买，所所以以该该公公司司可可以以预预测测未未来来几几个个月月的的需需求求量量。为为确确保保需需求求，该该公公司司为为新新的的一一年年前前四四个个月月制制定定一项

27、生产计划，这四个月的需求如下表所示。一项生产计划，这四个月的需求如下表所示。33动态规划的应用动态规划的应用(1)27管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)每台变压器在仓库中由这个月存到下个月的储存费为每台变压器在仓库中由这个月存到下个月的储存费为1，仓库，仓库的最大储存能力为的最大储存能力为3台，另外，知道在台，另外，知道在1月月1日时仓库里存有一日时仓库里存有一台变压器，要求在台变压器，要求在4月月30日仓库的库存量为零。试问该公司应日仓库的库存量为零。试问该公司应如何制定生产计划，使得四个月的生产成本和储存总费用最如何制定生产计划，使得四个月的生产成本和储存总

28、费用最少？少？生产成本的调试费为生产成本的调试费为4，生产成本除了调试费用外，每月生，生产成本除了调试费用外，每月生产的头两台各花费为产的头两台各花费为2，后两台花费为，后两台花费为1。最大生产能力每。最大生产能力每月为月为4台，生产成本如下表所示。台，生产成本如下表所示。28管管 理理 运运 筹筹 学学解：我们按月份来划分阶段，第解：我们按月份来划分阶段，第i个月为第个月为第i阶段阶段：（：（i=1,2,3,4).设设sk为第为第k阶段期初库存量；阶段期初库存量；k=1,2,3,4xk为第为第k阶段生产量；阶段生产量；k=1,2,3,4dk为第为第k阶段需求量；阶段需求量；k=1,2,3,4

29、，因为下个月初的库存量等于上个月初的库存量加上上个因为下个月初的库存量等于上个月初的库存量加上上个月的产量减去上个月的需求量，我们就得到了如下状态转月的产量减去上个月的需求量，我们就得到了如下状态转移方程：移方程：33动态规划的应用动态规划的应用(1)各月的生产成本和储存费用分别用各月的生产成本和储存费用分别用ck(xk)和和hk(sk,xk)表示，表示，即阶段指标函数为：即阶段指标函数为：rk(sk,xk)=ck(xk)+hk(sk,xk)29管管 理理 运运 筹筹 学学第四阶段：第四阶段：r4(s4,x4)=c4(x4)+h4(s4,x4)=c4(3-s4)33动态规划的应用动态规划的应用

30、(1)30管管 理理 运运 筹筹 学学第三阶段：第三阶段：r3(s3,x3)=c(x3)+h(s3,x3),s4=s3+x3-133动态规划的应用动态规划的应用(1)x3s3r3(s3,x3)+f4(s3+x3-1)01234f3(s3)x3*06+0+98+1+89+2+610+3+013410+0+96+1+88+2+69+3+09020+1+86+2+68+3+09030+2+66+3+08031管管 理理 运运 筹筹 学学第二阶段：第二阶段：r2(s2,x2)=c(x2)+h(s2,x2),s3=s2+x2-433动态规划的应用动态规划的应用(1)x2s2r2(s2,x2)+f3(s2

31、+x2-4)01234f2(s2)x2*010+0+1323419+0+1310+1+922428+0+139+1+910+2+9 19336+0+138+1+99+2+910+3+818232管管 理理 运运 筹筹 学学第一阶段：第一阶段：r1(s1,x1)=c(x1)+h(s1,x1),s2=s1+x1-2=x1-133动态规划的应用动态规划的应用(1)x1s1r1(s1,x1)+f2(x1-1)01234f1(s1)x1*16+0+238+1+209+2+1910+3+8291,2利用递推关系可以从得到两组最优解：利用递推关系可以从得到两组最优解：(1)x1=1s2=x1-1=1-1=0

32、x2=4s3=s2+x2-4=0+4-4=0x3=4s4=s3+x3-1=0+4-1=3x4=0，即，即1、2、3、4月份分别生产月份分别生产1、4、4、0台变压器，能使四个月的生台变压器，能使四个月的生产成本和存储总费用最省，最小费用为产成本和存储总费用最省，最小费用为29。(2)x1=2s2=x1-1=2-1=1x2=4s3=s2+x2-4=1+4-4=1x3=0s4=s3+x3-1=1+0-1=0x4=3，即，即1、2、3、4月份分别生产月份分别生产2、4、0、3台变压器，能使四个月的生台变压器，能使四个月的生产成本和存储总费用最省，最小费用为产成本和存储总费用最省，最小费用为29。33

33、管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)四、系统可靠性问题四、系统可靠性问题例例5.某科研项目组由三个小组用不同的手段分别研究，某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为它们失败的概率各为0.40，0.60，0.80。为了减少三个小组。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：家，到各小组后，各小组科研项目失败概率如下表：高级科学家高级科学家小组小组12300.400.600.8010.200.400.5020.150.200.3

34、0问如何分派科学家才能使三个小组都失败的概率（即科研问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？项目最终失败的概率）最小？34管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)解：用逆序算法。设解：用逆序算法。设阶段：每个研究小组为一个阶段，共分为阶段：每个研究小组为一个阶段，共分为3个阶段进行，且个阶段进行，且阶段阶段123小组小组123决策变量决策变量xk：分配给第：分配给第k小组的高级科学家人数，相应的失小组的高级科学家人数，相应的失败概率为败概率为rk(sk,xk)（k=1,2,3），即为阶段指标函数；），即为阶段指标函数；状态变量状态变

35、量sk：分配给第：分配给第k小组至第小组至第3小组的高级科学家人数小组的高级科学家人数（k=1,2,3)。则状态转移方程为：则状态转移方程为：s1=1s2=s1-x1s3=s2-x2递推方程为：递推方程为：fk(sk)=minrk(sk,xk)fk+1(sk+1)35管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)第一阶段：第一阶段：s3=x3x2s2r2(s2,x2)f3(s2-x2)f2(s2)x2*01200.600.800.48010.600.500.400.800.30020.600.300.400.500.200.800.162x3s3r3(s3,x3)f3(s3

36、)x3*01200.800.80010.500.50120.300.302第二阶段：第二阶段：s3=s2-x236管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)第一阶段：第一阶段：x1s1r1(s1,x1)f2(2-x1)f1(s1)x1*01220.400.160.200.300.150.480.061最优解为最优解为x1=1s2=s1-x1=2-1=1x2=0s3=s2-x2=1-0=1x3=1；即当分配给第即当分配给第1、2、3小组的高级科学家人数分别为小组的高级科学家人数分别为1、0、1人时，科研项目最终失败的概率最小，最小概率为人时，科研项目最终失败的概率最小，最

37、小概率为0.060。37管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *一、一、连续确定性动态规划连续确定性动态规划对于状态变量和决策变量只取连续值，过程的对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。续确定性动态规划问题。38管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *机器负荷分配问题机器负荷分配问题例例1一种机器能在高低两种不同的负荷状态下工作。设一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为机

38、器在高负荷下生产时，产量函数为P1=8u1，其中其中u1为在高为在高负荷状态下生产的机器数目，年完好率为负荷状态下生产的机器数目，年完好率为a=0.7，即到年底即到年底有有70的机器保持完好。在低负荷下生产时，产量函数为的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中其中u2为在低负荷状态下生产的机器数目，年完好为在低负荷状态下生产的机器数目，年完好率为率为b=0.9。设开始生产时共有设开始生产时共有1000台完好的机器，请问每台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才年应该如何把完好机器分配给高、低两种负荷下生产，才能使得能使得5年内生产的产品总产量

39、最高年内生产的产品总产量最高。39管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *解解建立动态规划模型：建立动态规划模型：分为分为5个阶段，每个阶段为个阶段，每个阶段为1年。设状态变量年。设状态变量sk表示在第表示在第k阶段初拥有的完好机器数目；阶段初拥有的完好机器数目；k=1,2,3,4,5。决策变量决策变量xk表示第表示第k阶段中分配给高负荷状态下生产的机阶段中分配给高负荷状态下生产的机器数目；器数目；k=1,2,3,4,5。显然显然sk-xk为分配给低负荷状态下生产为分配给低负荷状态下生产的机器数目。的机器数目。状态转移方程为状态转移方程为sk+1=0.7x

40、k+0.9(sk-xk)阶段指标阶段指标rk(sk,xk)=8xk+5(sk-xk)最优指标函数最优指标函数(k=1,2,3,4,5),f6(s6)=040管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *第第5阶段：阶段：因为因为f5(s5)=max8x5+5(s5-x5)=max5s5+3x5,而而0x5s5,故有故有x5*=s5，于是有，于是有f5(s5)=8s5。第第4阶段：阶段：41管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *故有故有x4*=s4，f4(s4)=13.6s4。对前几个阶段依次类推，可得对前几个阶段依次类推，

41、可得f3(s3)=max17.24s3+0.28x3,而而0x3s3，故当，故当x3*=s3时，有时，有f3(s3)=17.5s3，f2(s2)=max20.768s2-0.704x2,而而0x2s2，故当，故当x2*=0时，有时，有f2(s2)=20.768s2，f1(s1)=max23.6912s1-1.1236x1,而而0x1s1，故当，故当x1*=0时，有时，有f1(s1)=23.6912s1。综上所述，得最优解为综上所述，得最优解为x1*=0，x2*=0，x3*=s3，x4*=s4,x5*=s5。因为因为期初共有完好机器期初共有完好机器1000台，故台，故s1=1000,有有f1(s

42、1)=23.6912s123691.2，即即5年最大的产量为年最大的产量为23691.2。而。而s2=0.7x1*+0.9(s1-x1*)=0.9s1=0.91000=900,s3=0.7x2*+0.9(s2-x2*)=0.9s2=0.9900=810,s4=0.7x3*+0.9(s3-x3*)=0.7s3=0.7810=567s5=0.7x4*+0.9(s4-x4*)=0.7s4=0.7567=397s6=0.7x5*+0.9(s5-x5*)=0.7s5=0.7397=278这意味着前两年应把年初完好机器完全投入低负荷生产，后三年应把这意味着前两年应把年初完好机器完全投入低负荷生产，后三年应

43、把年初完好机器完全投入高负荷生产。年初完好机器完全投入高负荷生产。42管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *下一步工作是确定每年初的状态，按照从前向下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已后的顺序依次计算出每年年初完好的机器数目。已知知s1=1000,根据状态转移方程，有根据状态转移方程，有:43管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *上面所讨论的最优策略过程，初始端状态上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态台是固定的，终点状态s6没有要求。

44、这种情没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优况下得到最优决策称为初始端固定终点自由的最优策略。策略。如果终点附加一定的条件，则问题就称为如果终点附加一定的条件，则问题就称为“终终端固定问题端固定问题”。例如，规定在第。例如，规定在第5年度结束时仍要年度结束时仍要保持保持500台机器完好（而不是台机器完好（而不是278台），应如何安排台），应如何安排生产才能使得总产量最大？生产才能使得总产量最大？下面来分析：下面来分析：根据终点条件有根据终点条件有可得可得44管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *显然，由于固定了终点的状态，显然，由于

45、固定了终点的状态，x5的取值受到的取值受到了约束。因此有了约束。因此有类似的，类似的，容易解得容易解得，f4(s4)=21.7s4-7500。45管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *依次类推，得依次类推，得f3(s3)=24.5s3-7500f2(s2)=27.1s2-7500f1(s1)=29.4s1-7500再采用顺序方法递推计算各年的状态，有再采用顺序方法递推计算各年的状态，有s1=1000，46管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *可见，为了使终点完好的机器数量增加到可见，为了使终点完好的机器数量增加到5

46、00台，需要安排前四年中全部完好机器都要投入低负台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第荷生产，且在第5年，也只能全部投入高负荷。年，也只能全部投入高负荷。相应的最优指标为相应的最优指标为f1(s1)=29.4s1-750021900。可以看到，因为增加了附加条件，总产量可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。要比终点自由情况下的产量要低。47管管 理理 运运 筹筹 学学二、离散随机性动态规划二、离散随机性动态规划随机型的动态规划是指状态的转移律是不确定的，即对随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到

47、达状态是具有确定概率给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图：全确定。随机型动态规划的基本结构如下图：44动态规划的应用动态规划的应用(2)(2)* *sk状态xk决策概率k阶段的收益p1p2pN.k+1阶段的状态sk+1c1c2cN12N48管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *图图中中N表表示示第第k+1阶阶段段可可能能的的状状态态数数，p1、p2、pN为为给给定定状状态态sk和和决决策策xk的的前前提提

48、下下，可可能能达达到到下下一一个个状状态态的的概概率率。ci为为从从k阶阶段段状状态态sk转转移移到到k+1阶阶段状态为段状态为i时的指标函数值。时的指标函数值。 在随机性的动态规划问题中，由于下一阶段到在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。的期望效益值进行优化。49管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划 例例2 2 某公司承担一种新产品研制任务，合同要某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔求三个月内交出一件合格的样品，

49、否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概元。根据有经验的技术人员估计，试制品合格的概率为率为0.4，每次试制一批的装配费为，每次试制一批的装配费为200元，每件产元，每件产品的制造成本为品的制造成本为100元。每次试制的周期为元。每次试制的周期为1个月。个月。问该如何安排试制，每次生产多少件，才能使得期问该如何安排试制，每次生产多少件，才能使得期望费用最小？望费用最小？50管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划 解：把三次试制当作三个阶段（解：把三次试制当作三个阶段（k=1,2,3）,决决策变量策变量xk表示第表示第k次生产的产品的件数；状态变量

50、次生产的产品的件数；状态变量sk表示表示第第k次试制前是否已经生产出合格品，如果有次试制前是否已经生产出合格品，如果有合格品，则合格品，则sk=0；如果没有合格品，记如果没有合格品，记sk=1。最优最优函数函数fk(sk)表示从状态表示从状态sk、决策决策xk出发的第出发的第k阶段以阶段以后的最小期望费用。故后的最小期望费用。故有有fk(0)0。 生产出一件合格品的概率为生产出一件合格品的概率为0.40.4，所以生产，所以生产x xk k件产品都不合格的概率为件产品都不合格的概率为 ，至少有一件合格品，至少有一件合格品的概率为的概率为1- 1- ，故有状态转移方程为，故有状态转移方程为 51管

51、管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划 用用C(xk)表示表示第第k阶段的费用，第阶段的费用，第k阶段的费用包阶段的费用包括制造成本和装配费用，故有括制造成本和装配费用，故有 根据状态转移方程以及根据状态转移方程以及C(xk)，可得到可得到52管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划如如果果3个个月月后后没没有有试试制制出出一一件件合合格格品品，则则要要承承担担2000元元的的罚金，因此有罚金，因此有f4(1)=20。 当当k=3时，计算如下表：时，计算如下表：x3s3C(x3)+20f3(s3)x3*012345600001201511.2 9

52、.32 8.59 8.56 8.93 8.56 553管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划当当k=2时，计算如下表：时，计算如下表：x2s2C(x2)+8.56f2(s2) x2*01234000018.56 8.14 7.08 6.85 7.11 6.85354管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划当当k=1时，有时，有x1s1C(x1)+6.85f1(s1)x1*012300 0016.85 7.116.46 6.486.46 255管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划上上面面三三个个表表中中并并没没有有列列

53、出出xk取取更更大大数数值值的的情情况况，因因为为可可以以证证明明以以后后的的C(xk)+fk+1(1)的的值值是是对对xk单调增加的。单调增加的。 因此得到的最优策略是，在第因此得到的最优策略是，在第1个阶段试制个阶段试制2件件产品；如果都不合格，在第产品；如果都不合格，在第2阶段试制阶段试制3件产品；如件产品；如果仍都不合格，则在第果仍都不合格，则在第3个阶段试制个阶段试制5件产品。该策件产品。该策略得到的最小的期望费用略得到的最小的期望费用6.46。56管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划随机采购问题随机采购问题例例3某某公公司司打打算算在在5周周内内采采购购

54、一一批批原原料料，未未来来5周周内内的的原原料料的的价价格格有有三三种种，这这些些价价格格的的出出现现概概率率可可以以估估计计，如如下下表表。该该部部分分由由于于生生产产需需要要，必必须须在在5周周内内采采购购这这批批原原料料。如如果果第第一一周周价价格格很很高高，可可以以等等到到第第2周周；同同样样的的，第第2周周如如果果仍仍对对价价格格不不满满意意，可可以以等等到到第第3周周；类类似似地地，未未来来几几周周都都可可能能选选择择购购买买或或者者等等待待，但但必必须须保保证证第第5周周时时采采购购了了该该原原料料。试试问问该该选选择哪种采购方案，才能使得采购费用最小？择哪种采购方案，才能使得采

55、购费用最小？价格价格概率概率4500.254700.355000.4057管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划 解：建立动态规划。按照采购周期分为解：建立动态规划。按照采购周期分为5个阶个阶段，将每周的价格看作该阶段的状态。假设状态变段，将每周的价格看作该阶段的状态。假设状态变量量sk表示第表示第k周的实际价格，决策变量周的实际价格，决策变量xk表示第表示第k周周是否采购的是否采购的0-1变量。如决定采购，则变量。如决定采购，则xk=1；如选如选择等待，则择等待，则xk=0。用用s sk kE E表示第表示第k周等待，而在以后周等待，而在以后采取最优决策时采购价格的

56、期望值。采取最优决策时采购价格的期望值。 根据定义，根据定义， 动态规划基本方程如下：动态规划基本方程如下：58管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划第五阶段：第五阶段：因因为为如如果果前前4周周都都没没有有买买，那那第第5周周必必须须购购买买，因因此此有有f5(s5)=s5，即即f5(450)=450；f5(470)=470；f5(500)=500。第四阶段：第四阶段：下面考虑第下面考虑第4周的情况。周的情况。 如第如第4周购买，则需花费周购买，则需花费s4；如果不买，则必须如果不买，则必须在第在第5周购买。在第周购买。在第5周采购的费用的期望值为周采购的费用的期望

57、值为59管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划于是于是 ，有，有故第故第4周的最优决策为周的最优决策为同理，考虑第同理，考虑第3周的最优决策。周的最优决策。60管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划第三阶段：第三阶段： 如果第如果第3周采购，则需花费周采购，则需花费s3；也要和第也要和第3周后再采购的费用的期望值作比较。周后再采购的费用的期望值作比较。于是于是，有，有故第故第3周的最优决策为周的最优决策为61管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划第二阶段：第二阶段：同理可得同理可得故第故第2周的最优决策为周的最优决策为62管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划第一阶段：第一阶段：同理可得同理可得第第1周的最优决策为周的最优决策为63管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划由由上上可可知知，最最优优的的采采购购策策略略为为：在在第第1、2、3周周的的市市场场价价格格为为450时时，应应该该立立即即采采购购，否否则则等等待待；在在第第4周周时时，若若市市场场价价格格为为450或或470时时，应应该该采采购购，否否则则等等待待。若若等等到到第第五五周，只能采购。周，只能采购。64