一章动态规划

《一章动态规划》由会员分享，可在线阅读，更多相关《一章动态规划（76页珍藏版）》请在金锄头文库上搜索。

1、管管 理理 运运 筹筹 学学第十章第十章 动态规划动态规划1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理3动态规划的应用动态规划的应用(1)4动态规划的应用动态规划的应用(2)烷宫驾纂蚜颅窜熬珊她午草旗泌逾晌谎液租旅簧速驾蹬厨杯剪洱特蒲杜债一章动态规划一章动态规划1管管 理理 运运 筹筹 学学11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例例例1 最短路径问题最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC41231231232216472483867561106

2、3751厅奄午荐锌死程槛施狞市镀倔魄幅铬糜恿嫌攘拳箭奉苑很咬饮么惺刽鄂万一章动态规划一章动态规划2管管 理理 运运 筹筹 学学11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例用穷举法的计算量用穷举法的计算量: 如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-12条路径；计算各路径长度总共要进行(k+1)3k-12次加法以及3k-12-1次比较。随着k的值增加时，需要进行的加法和比较的次数将迅速增加；例如当k=20时，加法次数为4.25508339662271015次，比较1.37260754729771014次。若用1亿次/秒的计算机计算需要约508天。惦延泣船卤

3、狙凡敢拙翟抄币扁怕诲朵浪仪琢始逆茹赛摆广燥尾晓慰皿灵戌一章动态规划一章动态规划3管管 理理 运运 筹筹 学学11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；表10-1分析得知：从D1和D2到E的最短路径唯一。阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D210*6106EE踪村诫期蜀绷趴鸳戍簇欣侄蜀赊译益择厅壹凰督鄂凳率郎肝煞辙唆餐吊腕一章动态规划一章动态规划

4、4管管 理理 运运 筹筹 学学第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路径问题：表10-2分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D1谆拎萨概蔬列锭车看故悄赤豫积疙脊

5、苹责办型鬼妖猩泌叙躇示悔哥椭傻娥一章动态规划一章动态规划5管管 理理 运运 筹筹 学学第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题：表10-3分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B2，则走B2-C3-D1-E；如果经过B3，则走B3-C3-D1-E；如果经过B4，则走B4-C3-D1-E。11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例阶段2本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42+1

6、2=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C3颈拄抖肛胯搁奴蚁漆访兔欠缀晒备癣升容沦林上契囱博痈谤膘础倾芋曲怒一章动态规划一章动态规划6管管 理理 运运 筹筹 学学第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：表10-4最后，可以得到：从A到E的最短路径为AB4C3D1E11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例阶段1本阶段始点(状态)本阶段各终点

7、（决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=16 3+13=163+14=172+12=1412C2猿凑亩胞冠头锈滴刚倦辊嘴屹茶陶邹杖遵啃沁攻松搀肤魄剩晴樱负缩豆贯一章动态规划一章动态规划7管管 理理 运运 筹筹 学学 以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。以上过程，仅用了22次加法，计算效率远高于穷举法。BACBDBCDEC4123123123321647248386751610601061211111213141412751211多阶段决策过程最优化问题举例多阶段决策过程最

8、优化问题举例龋慌谭炽帚瞥吩锡辣方欲创披双嗅名小啸庆防见豺封堰匿谬铲限冤溢泣蛹一章动态规划一章动态规划8管管 理理 运运 筹筹 学学一、基本概念：1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程

9、sk+1=Tk(sk,xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理纲坎湾抠榜佐愿邦耽泉费域腐敌丈狭茶首架蚤减壮竹瓦菠扔眷粹桃重弱手一章动态规划一章动态规划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)

10、称指标具有可加性，或 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1,xk+1,xn)称指标具有可乘性。二、基本方程：最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理齿爷撬南仇霞裴月捞刘蟹赘墅谊世度骨稻渍弛默裂绊叮融懂妈勿授蜜清验一章动态规划一章动态规划10管管 理理 运运 筹筹 学学 对于可加性指标函数，上式可以写为上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为以上式子称为动态规划最优指标的递推方程，是动态规划

11、的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理寺杯瀑绢款库型桂叙顶叮治苫誓乘彪秽堰危隆沽诬咖辈据绣脐绒恐煤政网一章动态规划一章动态规划11管管 理理 运运 筹筹 学学三、最优化原理三、最优化原理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理县拉芍

12、酬堪许豪醋雇八删剐膊怀挪哺蕊殃述齐疲狡阻喀脉蓖缀煌决彩惑翰一章动态规划一章动态规划12管管 理理 运运 筹筹 学学一、资源分配问题一、资源分配问题例2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？表10-5盈利工厂设备台数甲厂乙厂丙厂0000135427106391111412111251311123 3 动态规划的应用动态规划的应用(1)(1)凑啡每湛源于诸墓系蛙蹲嚎颇梨勋冕席蝗屈骗奏脐肋挠快狮帝毖俭耀圆渺一章动态规划一章动态规划13管管 理理 运运 筹筹 学学解：

13、将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设sk=分配给第k个厂至第3个厂的设备台数（k=1、2、3）。xk=分配给第k个设备台数。已知s1=5,并有从与的定义，可知以下我们从第三阶段开始计算。3 3 动态规划的应用动态规划的应用(1)坛鸯弄暑哨适拔贼殷兢氯漂搓村刺鸽圭驳雁盎碉烈仲妙贮梗阉郊舍髓佐瘫一章动态规划一章动态规划14管管 理理 运运 筹筹 学学 第三阶段:显然将台设备都分配给第3工厂时，也就是时，第3阶段的指标值（即第3厂的盈利）为最大，即由于第3阶段是最后的阶段，故有其中可取值为0,1,2,3,4,5。其数值计算见表106。 3 3 动态规划的应用动态规划的

14、应用(1)框负楞帛咬榆祝芬患苇赋株篱飘备淮锤氮康栏冤堕其慧茂骡蹲殖陨逸调篡一章动态规划一章动态规划15管管 理理 运运 筹筹 学学 表表106 012345000014 4126623111134121245121253 3 动态规划的应用动态规划的应用(1)厢逆莹郸友脯辈贯铭审县庇基氟鹃逮仔醉钢腿扒修绢跺副恫环巡庶六映太一章动态规划一章动态规划16管管 理理 运运 筹筹 学学其中表示取3子过程上最优指标值时的决策，例如在表10-6中可知当=4时，有有此时，即当时，此时取（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优3子过程最优指标值也为12。第二阶段：当把台设备分配

15、给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为 3 3 动态规划的应用动态规划的应用(1)康断访闽傅颐夏锻咸捅萨替遂付奠彭题函诉棚烁枝就阑宣度烈奶娜信陡先一章动态规划一章动态规划17管管 理理 运运 筹筹 学学因为上式也可写成其数值计算如表107所示。表107 0123450001045120654102301156110 1424012114110 161,250125121161141102123 3 动态规划的应用动态规划的应用(1)衰狮础犀睁寐洲敬亏腊色颈冯使耶耸略究欣鹅筏糜悲灭操锥雄巫讼涌疽宏一章动态规划一章动态规划18管管 理理 运

16、运 筹筹 学学其中在的这一行里，当时，这里从表105中可知，把1台设备交给乙厂所得盈利数即可，知，这里从表106查即可知=11。同样可知当时，可知;当时，；当时，；当时，；由于，不可能分2厂5台设备，故时，栏空着不填。从这些数值中取得最大即得，即有=16。在此行中我们在取最大值的上面加一横以示区别，也可知这时的最优决策为1或2。3 3 动态规划的应用动态规划的应用(1)工尤护捆污鬃蕊担豁父妒蕊想删溜凛毋肌酣疲幅贸砂逐抉痹舰呻昆上卡萨一章动态规划一章动态规划19管管 理理 运运 筹筹 学学第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中可取值0,1,2,3,4,5.数值计算见表108

17、表10-8然后按计算表格的顺序推算，可知最优分配方案有两个：1.由于，根据，查表107可知，再由，求得。即分配给甲厂0台，乙厂2台，丙厂3台。2.由于，根据，查表107可01234553169+1012+513+0210,23 3 动态规划的应用动态规划的应用(1)防仰怒蔚翰泊稚粉鸯重硝肩逞堑力色秸敖鸡嫉愁划秩妖尧首储导癌小旁纬一章动态规划一章动态规划20管管 理理 运运 筹筹 学学知，再由,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。3 3 动态规划的应用动态规划的应用(1)霹悠栗奸面狞劝线速救喀捉厘欢菇嗽博娶派曲条衬寞笋话晋妨邢照邹权挪一章动态规

18、划一章动态规划21管管 理理 运运 筹筹 学学二、背包问题二、背包问题设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i =1,2,n），背包中物品的总价值为z，则Maxz=c1x1+c2x2+cnxns.t.w1x1+w2x2+wnxnWx1,x2,xn0且为整数。3 3 动态规划的应用动态规划的应用(1)阐孕崎蹈扒涛众泻比乍揍锯猾昌卖捷决荚贡灰抱臻衫爬豌食低咐堑固坍协一章动态规划一章动态规划22管管 理

19、理 运运 筹筹 学学下面用动态规划逆序解法求解它。设阶段变量k：第k次装载第k种物品（k=1,2,n）状态变量sk：第k次装载时背包还可以装载的重量；决策变量uk=xk：第k次装载第k种物品的件数；决策允许集合：Dk(sk)=xk|0xksk/wk，xk为整数；状态转移方程：sk+1=skwkxk；阶段指标：vk=ckxk；最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使用价值；递推方程：fk(sk)=maxckxk+fk+1(sk+1)=maxckxk+fk+1(skwkxk)；xDk(sk)终端条件：fn+1(sn+1)=0。3 3 动态规划的应用动态规划的应用(1)拨处还瘪

20、灯宾腺产擎规巩敏厅帧诸恤弘素柑蔽孰茬良毗痘欲驭憎品揪激跃一章动态规划一章动态规划23管管 理理 运运 筹筹 学学例3.某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表109所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这10个工作日中获利最大？表109咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润1234432213472811203 3 动态规划的应用动态规划的应用(1)钳伞犹瞳嚏彩崇虑聋燕振执娱秉翠份渔痘视炽盆

21、喊咨秧销永范句飞船灵褒一章动态规划一章动态规划24管管 理理 运运 筹筹 学学解：用动态规划来求解此题。我们把此问题分成四个阶段，第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。我们设分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（第k阶段的状态变量）。=在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知10并有3 3 动态规划的应用动态规划的应用(1)粕坡票熙噎当软干盏钒佯赁舅吹傈鸿位侵酝冠伏娄巢疵羔返丘靛遵撰灿悯一章动态规划一章动态规划25管管 理理 运运 筹筹 学学

22、并从与的定义可知从第四阶段开始计算：显然将个工作日尽可能分配给第四类咨询项目，即时，第四阶段的指标值为最大，其中，表示取不大于的最大整数，符号为取整符号，故有由于第四阶段是最后的阶段，故有3 3 动态规划的应用动态规划的应用(1)颐揽篙磐肿竹九撇芥版膝拂凋渠矛胚弥峰坞底躲骸一举眷峡喷错废仿灿嘴一章动态规划一章动态规划26管管 理理 运运 筹筹 学学因为至多为10，其数值计算见表1010。 表表101001000100200300400500600702018020190201100113 3 动态规划的应用动态规划的应用(1)苯眷奉涝巧迁媳别凝舍降垫履藕入内推子哉酪慷酮叮阿铝穴蛹捻钝巾划针一章

23、动态规划一章动态规划27管管 理理 运运 筹筹 学学第三阶段：当把个工作日分配给第四类和第三类咨询项目时，则对每个值，都有一种最优分配方案，使其最大盈利即最优3子过程最优指标函数值为因为因为至多为10，所以的取值可为0,1,2。其数值计算见表1011。3 3 动态规划的应用动态规划的应用(1)渣酒吠怔乾滑茫巧狙泄质躺园考纲狗基烦僳妖吏瞄茁疆宾陵结淹瑚茫耻忘一章动态规划一章动态规划28管管 理理 运运 筹筹 学学 表表1011012000100200300400111500111600111711+0200802011+0222902011+02221002011+02223 3 动态规划的应用

24、动态规划的应用(1)应言涯玩孙学争裂迅菇妒载炽砧奠躁堆御抨歼躲诚议沤命奉可阉蹈镰笼若一章动态规划一章动态规划29管管 理理 运运 筹筹 学学 第二阶段：同样以每个值都有一种最优分配方案，使其最大盈利即最优2子过程最优指标函数值为：因为，故有因为至多为10，所以的取值为0,1,2,3。其数值计算见表1012。33动态规划的应用动态规划的应用(1)榨匀蚕抓肿凳厩涂遁化权冷松霞桨副创旗椰过赚异慌冲默朱淌厚沙蛙肃剃一章动态规划一章动态规划30管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)表表10-12地痞欲撮墒埃肮详屿港市萤桌鬃扫搏胖掣垮氛膝忘獭隋覆拣汛齿掏吃孜抵一章动态规划一章动

25、态规划31管管 理理 运运 筹筹 学学 第一阶段：我们已知，又因为，同样有因为,故可取值为0,1,2,10。其数值计算见表1013。表101333动态规划的应用动态规划的应用(1)钧疆养楼兰段纲两涧系干逻珍多抠豢扩量产幼述咳浑丧稳架有气眠腑想熟一章动态规划一章动态规划32管管 理理 运运 筹筹 学学从表1013可知，从而得10010，在表1012的的这一行可知，由，查表1011的的这一行可知，最后由，查表10-10的的这一行得，综上所述得最优解为：此时最大盈利为28。现在我们不妨假设该咨询公司的工作计划有所改变，只有8个工作日来处理这四类咨询项目，那么该咨询公司如何选择客户使得获利最大呢？我们

26、不必从头开始重做这个问题，而只要在第一阶段上把改成8，重新计算就可得到结果，如表1014所示，这是动态规划的一个好处。33动态规划的应用动态规划的应用(1)纂搏东鼓反平饱慨搏渣贿瘤男信顽畜关朗逃虞恩玲趾运户策俞睦腊寝获缮一章动态规划一章动态规划33管管 理理 运运 筹筹 学学表1014如上一样可从表1014,1012,1011,1010得到两组最优解如下：它们的最优解（即最大盈利）都为22。一旦咨询的工作日不是减少而是增加，那么我们不仅要重新计算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加的工作日的新的信息，也可得到新的结果。33动态规划的应用动态规划的应用(1)类彩萨烙购心告指让

27、赤谁子畅闭斩窘虎缓柑崖梢邻迎脆噶摈嘻凸讼居域渠一章动态规划一章动态规划34管管 理理 运运 筹筹 学学 实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这N种物品中第i种物品的重量为，价值为，第i种物品的总数量的，我们可以设表示携带第i种物品的数量，则其数学模型为：S.T.且为整数。我们不妨用此模型去求解例3，也一定得出同样的结果。33动态规划的应用动态规划的应用(1)韵吵箩碑沛悲伺塌致矩肥趴唬倾醇麻帐四宾秆货荆兆萍星朴摹型骤丈忱备一章动态规划一章动态规划35管管 理理 运运 筹筹 学学三、生产与存贮问题例4.某公司为主要电力公司生产大型变压器，由于电力采取预订

28、方式购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如表1015所示。生产成本随着生产数量而变化。调试费为4，除了调度费用外，每月生产的头两台各花费为2，后两台花费为1。最大生产能力每月为4台，生产成本如表1016所示。表101533动态规划的应用动态规划的应用(1)还腹私驭碉换惭棱陆遭枉壶榷兰诅聋椰芜窘切南类逃朗径株亮穆缀商于擦一章动态规划一章动态规划36管管 理理 运运 筹筹 学学 表表1016每台变压器在仓库中由这个月存到下个月的储存费为1，仓库的最大储存能力为3台，另外，知道在1月1日时仓库里存有一台变压器，要求在4月30

29、日仓库的库存量为零。试问该公司应如何制定生产计划，使得四个月的生产成本和储存总费用最少？解：我们按月份来划分阶段，第i个月为第i阶段：（i=1,2,3,4).设为第k阶段期初库存量；k=1,2,3,433动态规划的应用动态规划的应用(1)揽砾捂蒋唐贩呢辅旋甄演判绕失虱弱力耗刺僳禹玻痘哑苍甚示拈削矫埠米一章动态规划一章动态规划37管管 理理 运运 筹筹 学学为第k阶段生产量；k=1,2,3,4为第k阶段需求量；k=1,2,3,4，这已在表10-15中告诉我们。因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个月的需求量，我们就得到了如下状态转移方程：因为，故有因为，故有33动态规划的应

30、用动态规划的应用(1)霞兴金致季摇菩嚼坪撰娩斧畔浅稻栖较跪屡扯腔锹滦坊渠须好肠测燥洪羹一章动态规划一章动态规划38管管 理理 运运 筹筹 学学由于必须要满足需求，则有通过移项得到另一方面，第k阶段的生产量必不大于同期的生产能力（4台），也不大于第k阶段至第四阶段的需求之和与第k阶段期初库存量之差，否则第k阶段的生产量就要超过从第k阶段至第四阶段的总需求，故有以下我们从第四阶段开始计算：从以上的状态转移方程可知这样就有33动态规划的应用动态规划的应用(1)味失和冶烽糯凋嗓唤犬拈军啦祥梅猪操欠熏蔼弟窍洋沾豺批定摸意狮拴塌一章动态规划一章动态规划39管管 理理 运运 筹筹 学学 这里的阶段指标可以分

31、成两部分，即生产成本与储存费，即为由于第四阶段末要求库存为零，即有，这样可得对于每个的可行值，的值列于表1017。表101733动态规划的应用动态规划的应用(1)绣狄呵副谎最厄狄关腾挞数促经满昆蛰霜颓蛰事受驰小骗雪卡闺伯肋抱汤一章动态规划一章动态规划40管管 理理 运运 筹筹 学学表中当时，可知第四阶段要生产台，从表1016可知总成本为9，同样可以算出当为1,2,3时的情况，结果已列于表1017中。第三阶段：此时有：因为以及所以有例如，当第三阶段初库存量时，生产量为2时，则所以生产成本为8，第三阶段末库存为2时，储存费为，而33动态规划的应用动态规划的应用(1)锄找顶巷失至舰晕厦抢蠢蜀栗辟赘蓉

32、世努私研烬澜歹隶郭余媚哥花春安移一章动态规划一章动态规划41管管 理理 运运 筹筹 学学查1017表可知，这样可知，填入表1018中的栏内，其他结果如表1018所示：表1018第二阶段：因为所以有33动态规划的应用动态规划的应用(1)旅恕藐型浓赚悦托慢茎亏春惦奄分茂担谚甘撬登登卡仰节肖秧霸喝俞沾畸一章动态规划一章动态规划42管管 理理 运运 筹筹 学学计算结果如表1019所示。表101933动态规划的应用动态规划的应用(1)秋棒劈饥丽渣镶鹰狰褐嗡伎盎藐启镊幢性锄棵茧慎鹰沃蓬汀珍腑泥痈靡卵一章动态规划一章动态规划43管管 理理 运运 筹筹 学学第一阶段：因为故有计算结果见表1020。表10203

33、3动态规划的应用动态规划的应用(1)傀屹永筑契狐衅聋镍规笛酌轴逼超雨将捧钒顺溢隶路棘滚驼汇掘疤沙贾陨一章动态规划一章动态规划44管管 理理 运运 筹筹 学学利用递推关系可以从表1020，表1019，表1018和表1017得到两组最优解：这时有最低总成本29。33动态规划的应用动态规划的应用(1)拔摄矣温工悠厨斟决栋靠密袜渝畔蛹癣秉荣轰得挤邀熄捧衅犁贬住植嗓宴一章动态规划一章动态规划45管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)四、系统可靠性问题例例5.某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能

34、性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？高级科学家小组12300.400.600.8010.200.400.5020.150.200.30笨普练涵寓妈墙凄矮藏踌违酥孤忌您阐染灯诚嘛械呀枪娇领烁岸蒲荫尊型一章动态规划一章动态规划46管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)解：用逆序算法。设阶段：每个研究小组为一个阶段，且阶段123小组123醚疼烁期弊倒坝钙坐褒奏混峙挖哦弥袄炭屈譬勿为磋福妓英绎藐滚式涅察一章动态规划一章动态规划47管管 理理 运运 筹筹

35、 学学33动态规划的应用动态规划的应用(1)计算当n=3时，当n=2时，s3f3*(s3)x3*008001050120302x2s2f2(s2,x2)=P2(x2)f3*(s2-x2)f2*(s2)x2*012004804801030032030020180200160162痴惯恤小砾府毡顺躲哗轿瞬淫赤还穷宵罢恼溉审蛆壤薛雇惦牲沦谣畜挟摊一章动态规划一章动态规划48管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)当n=1时，最优解为x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为0.060。x1s1f1(s1,x1)=P1(x1)f2*(s1-x1)f2*(s2

36、)x2*012200640060007200601九军冬寿捏镣予茄矗令搓缝娜送屠认妒堑烛荧杏昏毗太陆坞挑敝钢络来野一章动态规划一章动态规划49管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *一、一、连续连续确定性动态规划确定性动态规划对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。胡忌堵欧纯白们阂素兹祁虾馈扒蜡速谁米嘶宅我誓姨畴基诧溉人钉卑江腰一章动态规划一章动态规划50管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *机器负荷分配问题机器负荷分配问题 例例1 一种机器能在高低两

37、种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。扇悦遭亚鼠摔肚窥盏刺瘩抗扭垒洪宪酸退其屹齿防椭昏扫弓懊谊陛阳怀遏一章动态规划一章动态规划51管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *解建立动态规划模型：分为5个阶段，

38、每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然sk-xk为分配给低负荷状态下生产的机器数目。状态转移方程为sk+1=0.7xk+0.9(sk-xk)阶段指标rk(sk,xk)=8xk+5(sk-xk)最优指标函数，其中k=1,2,3,4,5。f6(s6)=0。偿教戍看窖咎衰披洼氨泡瓤宣厉誉荐眉贯诡斥耍舷扒逮大递伏舅立摄磐搅一章动态规划一章动态规划52管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *第5阶段：因为f5(s5)是x5的线性

39、单调增函数，故有x5*=s5，于是有f5(s5)=8s5。第4阶段：柑峙叙亡平眯椰记胰小堰萄针勾菲洞耸辉龄泛刀臭灭蔷谭勋世迷吞痢茄童一章动态规划一章动态规划53管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *同样的，f4(s4)是x4的线性单调增函数，有x4*=s4，f4(s4)=13.6s4。对前几个阶段依次类推，可得f3(s3)=17.5s3，f2(s2)=20.75s2，f1(s1)=23.72s1。因为期初共有完好机器1000台，故s1=1000。有f1(s1)=23.72s123720，即5年最大的产量为23720台。得最优解为，。这意味着前两年应把年初

40、完好机器完全投入低负荷生产，后三年应把年初完好机器完全投入高负荷生产。祷腥验之褂役骑癌根涅痞琶真宵翰塑螟痛北馒衡赢皿主谅修瓣醛褪陋筑谣一章动态规划一章动态规划54管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知s1=1000,根据状态转移方程，有:业窜稠保伦笋菲缨误碰竣茹睫仑堂趾扬还卫衍奸飞寸岳魄僵蔓曙惹忌剿僵一章动态规划一章动态规划55管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点

41、状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？下面来分析：根据终点条件有可得惹袄窜既馋融殉茸铜奔斌序肥柿迸获俩秀椭给戴闭茎扒绣舜坤叉钳多蛀哭一章动态规划一章动态规划56管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *显然，由于固定了终点的状态，x5的取值受到了约束。因此有类似的，容易解得，f4(s4)=21.7s4-7500。如舵旷驯元藩压默粮沤泰燎抱醋涝汁拍遮雍宾友豢邀岳嗓瑰俩盅

42、肩探瞎蚊一章动态规划一章动态规划57管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *依次类推，得f3(s3)=24.5s3-7500f2(s2)=27.1s2-7500f1(s1)=29.4s1-7500再采用顺序方法递推计算各年的状态，有s1=1000，单翘荐拱港啦蝎痞蛾彰级淌廊划棋帝枉冯渴板楔捻髓檀份叠计馋疆濒泉俏一章动态规划一章动态规划58管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，也只能全部投入高负荷。相应的最优指标为

43、f1(s1)=29.4s1-750021900。可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。秒馏砧隋味频条无泰征黔剂液路垃淬茫剪拣荷智供佯匪磕芬多勇锚稗忌驾一章动态规划一章动态规划59管管 理理 运运 筹筹 学学二、离散随机性动态规划二、离散随机性动态规划随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图：44动态规划的应用动态规划的应用(2)(2)* *sk状态xk决策概率k阶段的收益p1p2pN.k+1阶段的状态sk+1c

44、1c2cN12N决盟对刊容眼析军使浪蔚豪盟坯奢枪员琼亩妻席钩舅屿传忆瘁携僧帚疤柠一章动态规划一章动态规划60管管 理理 运运 筹筹 学学44动态规划的应用动态规划的应用(2)(2)* *图中N表示第k+1阶段可能的状态数，p1、p2、pN为给定状态sk和决策xk的前提下，可能达到下一个状态的概率。ci为从k阶段状态sk转移到k+1阶段状态为i时的指标函数值。 在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。藏套颊率绥授拽驻奇杏向兜臼赌厚衫珊佃途迷嗜甭辈吨恩逗牲凡列蛤卡凤一章动态规划一章动态规划61管管 理理 运运 筹筹 学学离散随机性动

45、态规划离散随机性动态规划 例例2 2 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概率为0.4，每次试制一批的装配费为200元，每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制，每次生产多少件，才能使得期望费用最小？纯帚盏几购勇央凡贺噶棠肃雏降窜蹲钩恒柑声撒澳愁捷迹庆绎靛杉赛萤帝一章动态规划一章动态规划62管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划 解：解：把三次试制当作三个阶段（k=1,2,3）,决策变量xk表示第k次生产的产品的件数；状态变量sk表示第k次试制前是否

46、已经生产出合格品，如果有合格品，则sk=0；如果没有合格品，记sk=1。最优函数fk(sk)表示从状态sk、决策xk出发的第k阶段以后的最小期望费用。故有fk(0)0。 生产出一件合格品的概率为0.4，所以生产xk件产品都不合格的概率为 ，至少有一件合格品的概率为1- ，故有状态转移方程为 唇摧磐朱趾挽揪枪柔渊甭糖惨厨燕币纹弘题答碴沿纯揪搪敬乏晴氢啤浚只一章动态规划一章动态规划63管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划 用C(xk)表示第k阶段的费用，第k阶段的费用包括制造成本和装配费用，故有 根据状态转移方程以及C(xk)，可得到勾柄碴碰痞案默兼堕赶硷解醒涪氮陇姓觉

47、蝗壶惺涩怖固匡眼刑峙依涤朴贤一章动态规划一章动态规划64管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划如果3个月后没有试制出一件合格品，则要承担2000元的罚金，因此有f4(1)=20。 当k=3时，计算如下表：x3s3C(x3)+20f3(s3)x3*012345600001201511.2 9.32 8.59 8.56 8.93 8.56 5赛龙吻骆幕梭复晌虹燃猴嘎屈苞讳竞拾抹约听揩从烯愤宿侯晕搁围娟啃码一章动态规划一章动态规划65管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划当k=2时，计算如下表：x2s2C(x2)+8.56f2(s2) x2*012

48、34000018.56 8.14 7.08 6.85 7.11 6.853匀袱酥屈避援提切下很烈景宙硷征润示嚷耶肢辰匣僻波灭祝诡脚拨锄烘爆一章动态规划一章动态规划66管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划当k=1时，有x1s1C(x1)+6.85f1(s1)x1*012300 0016.857.116.466.486.462饱们驳奢刊漂通求朔姜灾娠椎检玻依哼貉禽昂妨扫翰升麓孩盔杆垒溜责敲一章动态规划一章动态规划67管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划上面三个表中并没有列出xk取更大数值的情况，因为可以证明以后的C(xk)+fk+1(1)的值

49、是对xk单调增加的。 因此得到的最优策略是，在第1个阶段试制2件产品；如果都不合格，在第2阶段试制3件产品；如果仍都不合格，则在第3个阶段试制5件产品。该策略得到的最小的期望费用6.46。坏莹楔互恭宰照齐强今勿樟蚂殆副韭位夕贾杜源峡佰鸟齿贺逆鞘河龋致笑一章动态规划一章动态规划68管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划随机采购问题随机采购问题例例3某公司打算在5周内采购一批原料，未来5周内的原料的价格有三种，这些价格的出现概率可以估计，如下表。该部分由于生产需要，必须在5周内采购这批原料。如果第一周价格很高，可以等到第2周；同样的，第2周如果仍对价格不满意，可以等到第3

50、周；类似地，未来几周都可能选择购买或者等待，但必须保证第5周时采购了该原料。试问该选择哪种采购方案，才能使得采购费用最小？价格概率4500.254700.355000.40淘修涡芒尔照糙硷还易蚤尧寺祥债涝夸韧序持斗劣悉巨戈豌姆爹遂智蹄并一章动态规划一章动态规划69管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划 解解：建立动态规划。按照采购周期分为5个阶段，将每周的价格看作该阶段的状态。假设状态变量sk表示第k周的实际价格，决策变量xk表示第k周是否采购的0-1变量。如决定采购，则xk=1；如选择等待，则xk=0。用skE表示第k周等待，而在以后采取最优决策时采购价格的期望值。

51、 根据定义， 动态规划基本方程如下：牌读嘴鼻痘类骄皋赚瓢裤碑轻巍俞姨肚啄遥拭卫哦淹桥蔷霖吊娠荆尉玻耐一章动态规划一章动态规划70管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划第五阶段：因为如果前4周都没有买，那第5周必须购买，因此有f5(s5)=s5，即f5(450)=450；f5(470)=470；f5(500)=500。第四阶段：下面考虑第4周的情况。 如第4周购买，则需花费s4；如果不买，则必须在第5周购买。在第5周采购的费用的期望值为聋镍碱销虏捆俄极撑磷汗己席憋毫讳效向诌崇盼贷弥擞踢羔腮赴煞弹消爽一章动态规划一章动态规划71管管 理理 运运 筹筹 学学离散随机性动态规

52、划离散随机性动态规划于是 ，有故第4周的最优决策为同理，考虑第3周的最优决策。逾龚八等监遍德系滦簇第大役稿镊种稀搽劫暮撵盔铀奔馒撕血缀泼蛊盖优一章动态规划一章动态规划72管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划第三阶段： 如果第3周采购，则需花费s3；也要和第3周后再采购的费用的期望值作比较。于是，有故第3周的最优决策为送篆积域嘴部共啄区回广外半果精鲍轧谷卖巴膘湖斑材款霞到叠渭聪硒皿一章动态规划一章动态规划73管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划第二阶段：同理可得故第2周的最优决策为喧婪种浙造粕铃柿宛怯肩字逊时我太寂阀诡理萤靠毋脾汝析菌痞诸夸隅张一章动态规划一章动态规划74管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划第一阶段：同理可得第1周的最优决策为呈丹刨傣黎啥具循溯掐戊瘟循慈零援叠菇且垄署秘祭私指备氟然碎盖尼娩一章动态规划一章动态规划75管管 理理 运运 筹筹 学学离散随机性动态规划离散随机性动态规划由上可知，最优的采购策略为：在第1、2、3周的市场价格为450时，应该立即采购，否则等待；在第4周时，若市场价格为450或470时，应该采购，否则等待。若等到第五周，只能采购。研衬烙漂对鉴急毕岭帘蔬粘钧伸鸡宁捐挽咕由挑齿赦盅弯帚咕脖启八早勋一章动态规划一章动态规划76