资源预览内容
第1页 / 共30页
第2页 / 共30页
第3页 / 共30页
第4页 / 共30页
第5页 / 共30页
第6页 / 共30页
第7页 / 共30页
第8页 / 共30页
第9页 / 共30页
第10页 / 共30页
亲,该文档总共30页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
,第二节 动态规划应用举例 本节将通过动态规划的三种应用 类型资源分配问题、复合系统可 靠性问题、设备更新问题,进一步介 绍动态规划的特点和处理方法。,一、资源分配问题,1. 问题的一般提法 设有某种资源,总数量为a,用于生产n种产品;若分配数量xi用于生产第i种产品,其收益为gi(xi)。问应如何分配,可使总收益最大?,2. 数学规划模型,模型的特点 变量分离。,3.用动态规划方法求解,阶段k 状态sk 决策xk,=1,n表示把资源分配给第k种产品的过程; 表示在给第k种产品分配之前还剩有的资源量; 表示分配给第k种产品的资源量;,状态转移sk+1,= sk- xk ;,阶段指标vk 指标函数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,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台、分给丙厂3台, 或分给甲厂2台、分给乙厂2台、分给丙厂1台。,最优值: f1=21。,可见,最优解可以是不唯一的,但最优值是唯一的。,资源分配问题的应用很广泛,例如: 1.某学生正在备考4门功课,还剩7天时间,每门功课至少复习1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系,问他应怎样安排复习时间可使总的分数提高最多? 2.背包问题:旅行者携带的背包中能装的物品重量为a,现他要从n种物品中挑选若干数量装入背包,问他应如何挑选可使所带的物品总价值最大?,一九九九年硕士研究生入学试题,某大学生正在计划如何安排在7天时间里复习完4门考试课程。他要求每天只能安排一门课程复习,每门课程至少需要复习1天,据他估计各门课程的复习时间与所能带来的成绩提高关系如下表。用动态规划法求出使其总成绩提高最多的复习天数安排计划(资源分配问题),解:,阶段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)=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种物品的单件重量为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,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为连续型;用求极值方法求最大值,二、复合系统工作可靠性问题,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的最大值。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号