版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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种物品中挑选若干数量装入背包,问他应如何挑选可使所带的物品总价值最大?,二、复合系统工作可靠性问题,1. 问题的一般提法 设某工作系统由n个部件串接而成,为提高系统的可靠性,在每个部件上装有备用件。已知部件i上装
5、有xi个备用件时,其正常工作的概率为pi(xi);每个部件i的备用件重量为wi,系统要求总重量不超过W。问应如何安排备用件可使系统可靠性最高?,串接:,2. 数学规划模型,模型的特点 变量分离。,3.用动态规划方法求解,阶段k 状态sk 决策xk,=1,n表示安排第k个部件备用件的过程; 表示在给第k个部件安排之前还剩有的容许重量; 表示第k个部件上安排的备用件数量;,状态转移sk+1,= sk- wkxk ;,阶段指标vk 指标函数vkn,可靠性问题的应用很广泛,例如: 1.某重要的科研攻关项目正在由3个课题组以3种不同的方式进行,各组已估计出失败的概率。为减少失败的概率,选派了2名高级专家
6、去充实科研力量。若可估计出各组增加专家后的失败概率,问应如何分派专家可使总的失败概率最小? 2.已知x1+x2+xn=c,求z=x1x2xn的最大值。,三、设备更新问题,例4 某运输公司购进一批卡车投入运营,公司每年初需 对卡车作出更新或继续使用的决定。假设第k年中,rk(tk) 表示车龄为tk的车使用一年的收入,uk(tk)表示车龄为tk的 车使用一年的维修费用,ck(tk)表示车龄为tk的车更新成新 车的费用。现公司需制定一个10年计划,以决定如何安排 使10年的总收入最大。,问题:状态和决策怎样设置?, 决策是更新与否,可用0-1变量表示;状态可设为车龄。,阶段k 状态sk 决策xk,= 1,10表示第k年的决策过程; = tk表示第k年的车龄;,状态转移tk+1,= tk +1,(1-xk),阶段指标vk 指标函数vkn,= rktk - uktk - ck(tk),xk,四、其他随机型问题举例,例5 某瓷厂接受订制一个瓷瓶的任务。瓷瓶用电炉烧制。 据技术分析估计,每个瓷瓶出炉后的合格率为0.5,各瓶合格 与否相互独立(即一炉如装有n个瓷瓶,那么出炉后都不合 的概率为0.5n)。制造一个瓷瓶的原料费为100元,烧一炉的 费
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026事业单位工勤技能-新疆-新疆电工二级(技师)历年参考题库含答案详解
- 酒店前台技能培训课件
- 干燥综合征的皮肤表现
- 血管超声课件
- 痤疮瘢痕的治疗
- 消防设施操作员消防安全管理法规考点题库及答案
- 药理学专项训练题库及解析及答案
- 中医临床技能操作考核要点解析及模拟试题及答案
- 营养师职业资格考试临床营养学专项训练题库及答案
- 经典漆介绍课件
- 《韧战》(2023年福建省中考满分作文15篇附审题指导)
- 艾灸治疗鼻炎
- 《相似植物如何区别》课件
- 驾驶员素质提升培训
- My family幼儿园家庭成员介绍手抄报
- 国家安全教育大学生读本-第一章完全准确领会总体国家安全观
- 2016年公务员国考《申论》真题卷及答案(副省级)
- 《外科学》教案:第七章 麻醉
- 产后康复经络与腧穴
- 2023航标灯光强测量和灯光射程计算
- 化工传递过程基础全部
评论
0/150
提交评论