《动态规划应用举例》PPT课件

《《动态规划应用举例》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二节动态规划应用举例本节将通过动态规划的三种应用类型——资源分配问题、复合系统可靠性问题、设备更新问题，进一步介绍动态规划的特点和处理方法。一、资源分配问题1.问题的一般提法设有某种资源，总数量为a，用于生产n种产品；若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，可使总收益最大？2.数学规划模型模型的特点——变量分离。3.用动态规划方法求解阶段k状态sk决策xk=1,…,n表示把资源分配给第k种产品的过程；表示在给第k种产品分配之前还剩有的资源量；表示分配给第k种产品的资源量；状态转移sk+1=sk-xk；阶段指标vk指标函数vkn12S1=ax1x2

2、g1(x1)g2(x2)nxnsngn(xn)s2s3...例3某公司拟将某种高效设备5台分配给所属甲、乙、丙3厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总效益最大？效益厂设备台数甲乙丙000013542710639111141211125131112解：阶段k状态sk决策xk=1,2,3依次表示把设备分配给甲、乙、丙厂的过程；表示在第k阶段初还剩有的可分台数；表示第k阶段分配的设备台数；状态转移sk+1=sk-xk；阶段指标vk指标函数vk3问题：本问题是属于离散型还是属于连续型？怎样解？——离散型，用表格的方式求解。效益厂设备台数甲乙丙00001354

3、2710639111141211125131112kSkxkvkvk+fk+1fk30123450123450461112120+04+06+011+012+012+0046111212012345kSkxkvkvk+fk+1fk0123452000+000-0000+4155+051-0000+6155+421010+0102-0000+11155+621010+431111+0142-1000+12155+1121010+631111+441111+0161-32-2000+12155+1221010+1131111+641111+451111+0212-3kSkxkvkv

4、k+fk+1fk15012345037912130+213+167+149+1012+513+0210-2-32-2-1最优策略：P*13为0-2-3或2-2-1，即分给甲厂0台、分给乙厂2台、分给丙厂3台，或分给甲厂2台、分给乙厂2台、分给丙厂1台。最优值：f1=21。可见，最优解可以是不唯一的，但最优值是唯一的。资源分配问题的应用很广泛，例如：1.某学生正在备考4门功课，还剩7天时间，每门功课至少复习1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，问他应怎样安排复习时间可使总的分数提高最多？2.背包问题：旅行者携带的背包中能装的物品重量为a，现他要从n种物品中

5、挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？一九九九年硕士研究生入学试题某大学生正在计划如何安排在7天时间里复习完4门考试课程。他要求每天只能安排一门课程复习，每门课程至少需要复习1天，据他估计各门课程的复习时间与所能带来的成绩提高关系如下表。用动态规划法求出使其总成绩提高最多的复习天数安排计划（资源分配问题）解：阶段k：将7天分配给甲乙丙丁四门课程，划分四个阶段，k=1，2，3，4状态sk：分配给第k门课程的天数，k=1,2,3,41XkSk状态转移:Sk+1=Sk-Xk第k阶段初还剩的天数。状态集：S1={7},S2={3,4,5,6},S3={2,3

6、,4,5},S4={1,2,3,4}决策Xk：阶段指标Vk:第k阶段分配后提高的分数指标函数：Vk4=Vi递推方程：k=4,3,2,1f5(S5)=0fk(Sk)=max{vk(Sk,Xk)+fk+1(Sk+1)}1xkSkK=4,S4={1,2,3,4},1X4S4,S5=S4-X4,f5(S5)=0K=3,S3={2,3,4,5},1X3S3,S4=S3-X3K=2,S2={3,4,5,6},1X2S2,S3=S2-X2K=1,S1={7},1X1S1,S2=S1-X1最优解为:S1=7X1*=1第1门复习1天S2=S1-X1*=7-1=6X2*=2第

7、2门复习2天S3=S2-X2*=6-2=4X3*=1第3门复习1天S4=S3-X3*=4-1=3X4*=3第4门复习3天最优值为:f1(S1)=21总成绩最多提高21分背包问题1.一般提法：旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，已知第i种物品的单件重量为ai，其价格是ci（xi），问他应如何挑选可使所带的物品的总价值最大？2.模型：决策变量xi表示第i种物品装入的件数（i=1~n）模型为：Maxz=∑Vi（xi）∑wi（xi）≤wxi≥0且为整数（i=