《动态规划应用举例课件》由会员分享，可在线阅读，更多相关《动态规划应用举例课件（30页珍藏版）》请在金锄头文库上搜索。
1、,第二节 动态规划应用举例 本节将通过动态规划的三种应用 类型资源分配问题、复合系统可 靠性问题、设备更新问题，进一步介 绍动态规划的特点和处理方法。,一、资源分配问题,1. 问题的一般提法 设有某种资源，总数量为a，用于生产n种产品；若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，可使总收益最大？,2. 数学规划模型,模型的特点 变量分离。,3.用动态规划方法求解,阶段k 状态sk 决策xk,=1,n表示把资源分配给第k种产品的过程； 表示在给第k种产品分配之前还剩有的资源量； 表示分配给第k种产品的资源量；,状态转移sk+1,= sk- xk ；,阶段指标vk 指标函
2、数vkn,例3 某公司拟将某种高效设备5台分配给所属甲、乙、丙3厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总效益最大？,解：,阶段k 状态sk 决策xk,=1,2,3依次表示把设备分配给甲、乙、丙厂的过程； 表示在第k阶段初还剩有的可分台数； 表示第k阶段分配的设备台数；,状态转移sk+1,= sk- xk ；,阶段指标vk 指标函数vk3,问题：本问题是属于离散型还是属于连续型？怎样解？,离散型，用表格的方式求解。,3,012345,012345,0 4 6 111212,0+0 4+0 6+0 11+0 12+0 12+0,0 4 6 111212,012345,2,
3、0 0 0+0 0 0-0,0 0 0+4 1 5 5+0,5 1-0,0 0 0+6 1 5 5+4 2 10 10+0,10 2-0,0 0 0+11 1 5 5+6 2 10 10+4 3 11 11+0,14 2-1,0 0 0+12 1 5 5+11 2 10 10+6 3 11 11+4 4 11 11+0,16 1-3 2-2,0 0 0+12 1 5 5+12 2 10 10+11 3 11 11+6 4 11 11+4 5 11 11+0,21 2-3,1,5,21 0-2-3 2-2-1,最优策略：P*13 为0-2-3或2-2-1， 即分给甲厂0台、分给乙厂2台、分给丙厂
4、3台， 或分给甲厂2台、分给乙厂2台、分给丙厂1台。,最优值： f1=21。,可见，最优解可以是不唯一的，但最优值是唯一的。,资源分配问题的应用很广泛，例如： 1.某学生正在备考4门功课，还剩7天时间，每门功课至少复习1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，问他应怎样安排复习时间可使总的分数提高最多？ 2.背包问题：旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？,一九九九年硕士研究生入学试题,某大学生正在计划如何安排在7天时间里复习完4门考试课程。他要求每天只能安排一门课程复习，每门课程至少需要复习1
5、天，据他估计各门课程的复习时间与所能带来的成绩提高关系如下表。用动态规划法求出使其总成绩提高最多的复习天数安排计划（资源分配问题）,解：,阶段k：,将7天分配给甲乙丙丁四门课程，划分四个阶段，k=1，2，3，4,状态sk：,分配给第k门课程的天数，k=1,2,3,4 1XkSk,状态转移:,S k+1=Sk-Xk,第k阶段初还剩的天数。,状态集：,S1=7,S2=3,4,5,6,S3=2,3,4,5, S4=1,2,3,4,决策Xk：,阶段指标Vk:,第k阶段分配后提高的分数,指标函数：,Vk4=Vi,递推方程：,K=4, S4=1,2,3,4, 1X4S4, S5=S4-X4 ,f5(S5)
6、=0,K=3, S3=2,3,4,5, 1X3S3, S4=S3-X3,K=2, S2=3,4,5,6, 1X2S2, S3=S2-X2,K=1, S1=7, 1X1S1, S2=S1-X1,最优解为:,S1=7,X1*=1,第1门复习1天,S2=S1-X1*=7-1=6,X2*=2,第2门复习2天,S3=S2-X2*=6-2=4,X3*=1,第3门复习1天,S4=S3-X3*=4-1=3,X4*=3,第4门复习3天,最优值为:,f1(S1)=21,总成绩最多提高21分,背包问题,1.一般提法：,旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，已知第i种物品的单件
7、重量为ai，其价格是ci（xi），问他应如何挑选可使所带的物品的总价值最大？,2.模型：,决策变量xi,表示第i种物品装入的件数（i=1n）,模型为：,Maxz=Vi（xi）,wi（xi）w,xi 0 且为整数（i=1n）,具有变量分离的静态模型,3.用动态规划法求解：,阶段k：,将可装入物品按1,2,.,n排序,每段装一种物品,共划分为n个阶段。,即k=1，2，. ，n,状态sk：,背包中装入第kn种物品的总重量,（第k阶段还能装入物品的量）,S1=a,决策xk：,装入第k种物品的件数,状态转移：,S k+1=sk-wkxk,0 xk（sk/wk）,基本方程：,k=n，n-1，.，3，2，1
8、,f n+1（s n+1）=0,由背包问题模型可求解静态问题模型：,如求解线性规划问题,Maxz=5x1+2x2+x3,x1+2x2+x3 12 x1，x2，x3 0,由动态规划法：,阶段：k=1，2，3,表示给xk赋值的过程,状态sk：,第k个阶段初可赋给xk到x3的值,（约束右端项的剩余值）,决策xk：,Xk的取值,0 x1s1,状态转移：,S 1=12,0 x2s2/2,0 x3s3,S 2=s1-x1,S 3=s2-2x2,阶段指数：,V1=5x1,基本方程：,f 4（s 4）=0,k=3，2，1,V2=2x2,V3=x3,Xk为连续型；用求极值方法求最大值,二、复合系统工作可靠性问题
9、,1. 问题的一般提法 设某工作系统由n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。已知部件i上装有xi个备用件时，其正常工作的概率为pi(xi)；每个部件i的备用件重量为wi，系统要求总重量不超过W。问应如何安排备用件可使系统可靠性最高？,串接:,2. 数学规划模型,模型的特点 变量分离。,3.用动态规划方法求解,阶段k 状态sk 决策xk,=1,n表示安排第k个部件备用件的过程； 表示在给第k个部件安排之前还剩有的容许重量； 表示第k个部件上安排的备用件数量；,状态转移sk+1,= sk- wkxk ；,阶段指标vk 指标函数vkn,由可靠性问题模型可求解静态模型,如：求解非线性规划问题：,Maxz=xi,xi=c xi 0,由动态规划方法：,阶段k=1，.，n：,给xk赋值的过程,状态sk：,第k到n阶段赋值和,决策xk：,Xk的取值,阶段指标：,Vk=xk,转移：,S k+1=sk-xk,基本方程:,f n+1=1,k=n，., 1,可靠性问题的应用很广泛，例如： 1.某重要的科研攻关项目正在由3个课题组以3种不同的方式进行，各组已估计出失败的概率。为减少失败的概率，选派了2名高级专家去充实科研力量。若可估计出各组增加专家后的失败概率，问应如何分派专家可使总的失败概率最小？ 2.已知x1+x2+xn=c，求z=x1x2xn的最大值。,
