10.3 动态规划的应用(1)

基本概念、基本方程与最优化原理动态规划的应用(1)动态规划的应用(2)本章内容123432一、资源分配问题例2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？工厂盈利设备台数甲厂乙厂丙厂000013542710639111141211125131112§3动态规划的应用(1)3解：按甲、乙、丙工厂分为三个阶段，编号1、2、3。设=分配给第k个厂至第3个厂的设备台数。=分配给第k个厂的设备台数。已知,并有从与的定义和本题目已知数据的特点，可知222223),(xsxsTskskx33xs111112),(xsxsTs§3动态规划的应用(1)kskx51s4第三阶段:将台设备都分配给第3工厂时，第3阶段的指标值（盈利）为最大，即由于第3阶段是最后的阶段，故有其中可取值为0,1,2,3,4,5。其数值计算见表。)5,4,3,2,1,0(33ss).,(),(max)(333333333ssrxsrsfx3x;),(),(max3333333ssrxsrx33xs§3动态规划的应用(1)53x3s)(33sf3*x§3动态规划的应用(1)01234500-------------------------001-----4--------------------412----------6---------------623---------------11----------1134--------------------121245-------------------------12125),(333xsr表示取3子过程上最优指标值时的的决策。3*x)(33sf3x6例：在表中可知当时，有此时，即当时，此时取（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优3子过程最优指标值也为12。43s;12)4,4(3r,12)4(3f43*x43s43x§3动态规划的应用(1)7第二阶段：当把台设备分配给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利，即最优2子过程最优指标函数值为)5,4,3,2,1,0(22ss2s)](),([max)(33222222sfxsrsfx因为上式也可写成,223xss)(),(max)(223222222xsfxsrsfx§3动态规划的应用(1)8数值计算如表。§3动态规划的应用(1)0123450------------------------------001------------------------512------------------1023------------1424------161,252122x2s)(),(233222xsfxsr)(22sf2*x00051150104106101110406011012012041145651256114110110110119例如在的这一行里，当时，查前两表可知，当时，同样可知当时，；当时，当时，42s12x16115)3()1,4()14()1,4()(),(3232223222frfrxsfxsr5)1,4(2r11)3(3f22x16610)2()2,4()24()2,4()(),(3232223222frfrxsfxsr02x12120)04()0,4(32fr32x15411)34()3,4(32fr§3动态规划的应用(1)42x11011)44()4,4(32fr10由于，不可能分2厂5台设备，故当时，栏不填。从这些数值中取最大，即得。在取最大值的上加一横，可知的最优决策为1或2。42s52x)54()5,4(32fr16)4(2f)(),(223222xsfxsr2x§3动态规划的应用(1)11第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中然后按计算表格的顺序推算，可知最优分配方案有两个：)5(11ss)],5(),5([max)5(111111xfxrfx01234551x1s)5(),5(1211xfxr210147)(1xf1*x§3动态规划的应用(1)163109512013212,0.5,4,3,2,1,01x1222*x1232*23xss133*sx§3动态规划的应用(1)21*x3251*12xss1.由于，根据，查表10－7可知，再由，求得。即分配给甲厂0台，乙厂2台，丙厂3台。2.由于，根据，查表10－7可知，再由,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。01*x5051*12xss*22x3252*23xss333*sx13二、背包问题设有种物品，每种物品数量无限。第种物品每件重量为公斤，每件价值元。现有一只可装载重量为公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。用整数规划模型来描述。设为第种物品装入背包的件数，背包中物品的总价值为，则且为整数§3动态规划的应用(1)niiwicWiXin),…2,1,=(iz0x.....,,x,xw≤xw+…+xw+xws.t.xc+…+xc+xc=zmaxn21nn2211nn221114用动态规划方法解：设阶段变量：第k次装载第k种物品状态变量：第k次装载时背包还可以装载的重量；决策变量：第k次装载第k种物品的件数；决策允许集合：；状态转移方程：；阶段指标：；最优过程指标函数：第k到n阶段容许装入物品的最大价值；递推方程：终端条件：§3动态规划的应用(1)n),…2,1,=(kkkSkkxu}0,1,2....nx,/wSx0|x{)(SDkkkkkkkkkk1kxwsskkkxcv)(sfkk};xw(sfx{cmax)}(sfx{cmax)(sfkkk1kkk1k1kkkkk)(sDxkk0)(sf1n1n15例3.某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这10个工作日中获利最大？咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润123443221347281120§3动态规划的应用(1)16解：我们把此问题分成四个阶段。第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。设＝分配给第k种咨询项目到第四种咨询项目的客户的总工作日（第k阶段的状态变量）。=在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知＝10，并有kx1s,),(111112xsxsTsks§3动态规划的应用(1),3),(222223xsxsTs.4),(333334xsxsTs17第四阶段：将个工作日尽可能分配给第四类咨询项目，即时，第四阶段的指标值为最大，表示取不大于的最大整数，符号为取整符号，故有由于第四阶段是最后的阶段，故有4s)10,...,1,0(4s7/44sx7/4s).7/,(),(max4444444ssrxsrx)7/,(),(max)(4444*44444ssrxsrsfx§3动态规划的应用(1)4x因为至多为10，数值计算见表。4s18010－001－002－003－004－005－006－007020180201902011002014x4s),(444xsr)(44sf4*x000000020202020§3动态规划的应用(1)19第三阶段：当把个工作日分配给第四类和第三类咨询项目时，则对每个值，都有一种最优分配方案，使其最大盈利即最优3子过程最优指标函数值为因为，故因为至多为10，所以的取值可为0,1,2。数值计算见表。)10,....,2,1,0(33ss3s.)(),(max)(44333333sfxsrsfx4334ssx.)4(),(max)(334333333xsfxsrsfx3s3x§3动态规划的应用(1)20§3动态规划的应用(1)0120--------001--------002--------003--------004----1115----1116----1117----2008222922210222)(33sf3x)4(),(334333xsfxsr3s3x0000000000200200011011011011011011011000020020002202202221第二阶段：同样以每个值都有一种最优分配方案，使其最大盈利即最优2子过程最优指标函数值为：因为，故因为至多为10，所以的取值为0,1,2,3。其数值计算见表。.)3(),(max)(223222222xsfxsrsfx2233xss.)3(),(max)(223222222xsfxsrsfx2s2x2s§3动态规划的应用(1)22§3动态规划的应用(1)01230------------001------------002------------003--------814--------1105--------1106----1627----2008----2209243102810000002s2x22()fs*2x222322(,)(3)rsxfsx0080240240160160160160161180808081181181182001101102002202202201123第一阶段：已知，又因为，同样有因为,故可取值为0,1,2,…,10。其数值计算见表。101s.)(),(max)(112111111xsfxsrsfx112xss.)10(),10(max)10(121111xfxrfx101s1x§3动态规划的应用(1)24由上表知，，从而，由表的的这一行可知由由表的的这一行可知由，查表的这一行得综上所述得最优解为：最大盈利为28。28)10(1f01*x10010101*2xs102s,12*x731032*23xss73s03*x7073*34xss74s14*x,1,0,1,04*3*2*1*xxxx§3动态规划的应用(1)012345678910102801121(10,)(10)rxfx0282244226208161011121114816018020011()fs*1x1x1s25§3动态规划的应用(1)现在我们假设该咨询公司的工作计划有所改变，只有8个工作日来处理这四类咨询项目，那么该咨询公司如何选择客户使得获利最大？我们只要在第一阶段上把改成8，重新计算即可，如下表所示，这是动态规划的一个好处。1s0123456788220.1)8(),8(1211xfxr1*x)(11sf1x1s16422020211611881001401601226从而得到两组最优解如下：最优解（即最大盈利）都为22。一旦咨询的工作日不是减少而是增加，那么我们不仅要重新计算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加的工作日的新的信息，也可得到新的结果。3042)4321xx