《天津大学管理学院运筹学课件九章二节动态规划应用举例》由会员分享，可在线阅读，更多相关《天津大学管理学院运筹学课件九章二节动态规划应用举例（17页珍藏版）》请在装配图网上搜索。
1、第二节 动态规划应用举例 本节将通过动态规划的三种应用类型资源分配问题、复合系统可靠性问题、设备更新问题，进一步介绍动态规划的特点和处理方法。一、资源分配问题1.问题的一般提法 设有某种资源，总数量为a，用于生产n种产品；若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，可使总收益最大？2.数学规划模型模型的特点变量分离。3.用动态规划方法求解阶段k状态sk决策xk=1,n表示把资源分配给第k种产品的过程；表示在给第k种产品分配之前还剩有的资源量；表示分配给第k种产品的资源量；状态转移sk+1=sk-xk；阶段指标vk指标函数vkn 12S1=ax1x2g1(x1)g2(x
2、2)nxnsngn(xn)s2s3.例3 某公司拟将某种高效设备5台分配给所属甲、乙、丙3厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总效益最大？效益厂设备台数甲 乙 丙0 0 0 01 3 5 42 7 10 63 9 11 114 12 11 125 13 11 12解：阶段k状态sk决策xk=1,2,3依次表示把设备分配给甲、乙、丙厂的过程；表示在第k阶段初还剩有的可分台数；表示第k阶段分配的设备台数；状态转移sk+1=sk-xk；阶段指标vk指标函数vk3 问题：本问题是属于离散型还是属于连续型？怎样解？离散型，用表格的方式求解。效益厂设备台数甲 乙 丙0 0 0
3、01 3 5 42 7 10 63 9 11 114 12 11 125 13 11 12k Sk xk vk vk+fk+1 fk3012345012345 0 4 6111212 0+0 4+0 6+011+012+012+0 0 4 6111212012345k Sk xk vk vk+fk+1 fk0123452 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+010 2-0 0 0 0+11 1 5 5+6 2 10 10+4 3 11 11+014 2-1 0 0 0+12 1 5 5+11 2 10 10+6
4、 3 11 11+4 4 11 11+016 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+021 2-3k Sk xk vk vk+fk+1 fk15012345 0 3 7 912130+21 3+167+149+1012+513+021 0-2-3 2-2-1最优策略：P*13 为0-2-3或2-2-1，即分给甲厂0台、分给乙厂2台、分给丙厂3台，或分给甲厂2台、分给乙厂2台、分给丙厂1台。最优值：f1=21。可见，最优解可以是不唯一的，但最优值是唯一的。资源分配问题的应用很广泛，例如：1.某学生正在备考
5、4门功课，还剩7天时间，每门功课至少复习1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，问他应怎样安排复习时间可使总的分数提高最多？2.背包问题：旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？二、复合系统工作可靠性问题1.问题的一般提法 设某工作系统由n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。已知部件i上装有xi个备用件时，其正常工作的概率为pi(xi)；每个部件i的备用件重量为wi，系统要求总重量不超过W。问应如何安排备用件可使系统可靠性最高？串接:122.数学规划模型模型的特点变量分离
6、。3.用动态规划方法求解12S1=Wx1x2p1(x1)p2(x2)nxnsnpn(xn)s2s3.阶段k状态sk决策xk=1,n表示安排第k个部件备用件的过程；表示在给第k个部件安排之前还剩有的容许重量；表示第k个部件上安排的备用件数量；状态转移sk+1=sk-wkxk；阶段指标vk指标函数vkn 可靠性问题的应用很广泛，例如：1.某重要的科研攻关项目正在由3个课题组以3种不同的方式进行，各组已估计出失败的概率。为减少失败的概率，选派了2名高级专家去充实科研力量。若可估计出各组增加专家后的失败概率，问应如何分派专家可使总的失败概率最小？2.已知x1+x2+xn=c，求z=x1x2xn的最大值
7、。三、设备更新问题例4 某运输公司购进一批卡车投入运营，公司每年初需对卡车作出更新或继续使用的决定。假设第k年中，rk(tk)表示车龄为tk的车使用一年的收入，uk(tk)表示车龄为tk的车使用一年的维修费用，ck(tk)表示车龄为tk的车更新成新车的费用。现公司需制定一个10年计划，以决定如何安排使10年的总收入最大。12S1=？x1x2 10 x10s10v1v2v10s2问题：状态和决策怎样设置？决策是更新与否，可用0-1变量表示；状态可设为车龄。阶段k状态sk决策xk=1,10表示第k年的决策过程；=tk表示第k年的车龄；状态转移tk+1=tk +1(1-xk)阶段指标vk指标函数vk
8、n=rktk -uktk -ck(tk)(1-xk)(1-xk)xk四、其他随机型问题举例例5 某瓷厂接受订制一个瓷瓶的任务。瓷瓶用电炉烧制。据技术分析估计，每个瓷瓶出炉后的合格率为0.5，各瓶合格与否相互独立（即一炉如装有n个瓷瓶，那么出炉后都不合的概率为0.5n）。制造一个瓷瓶的原料费为100元，烧一炉的费用为300元。现因厂中条件限制最多只能烧3炉，每炉最多装4个瓷瓶。若3炉的瓷瓶无1个合格，则因不能履行合同而被罚款1600元。试用动态规划方法确定一种生产方案（即每炉该装几个瓷瓶），使总的期望成本为最小。9、静夜四无邻，荒居旧业贫。4月-234月-23Wednesday,April 12
9、,202310、雨中黄叶树，灯下白头人。05:26:2805:26:2805:264/12/2023 5:26:28 AM11、以我独沈久，愧君相见频。4月-2305:26:2805:26Apr-2312-Apr-2312、故人江海别，几度隔山川。05:26:2805:26:2805:26Wednesday,April 12,202313、乍见翻疑梦，相悲各问年。4月-234月-2305:26:2805:26:28April 12,202314、他乡生白发，旧国见青山。12 四月 20235:26:28 上午05:26:284月-2315、比不了得就不比，得不到的就不要。四月 235:26 上
10、午4月-2305:26April 12,202316、行动出成果，工作出财富。2023/4/12 5:26:2805:26:2812 April 202317、做前，能够环视四周；做时，你只能或者最好沿着以脚为起点的射线向前。5:26:28 上午5:26 上午05:26:284月-239、没有失败，只有暂时停止成功！。4月-234月-23Wednesday,April 12,202310、很多事情努力了未必有结果，但是不努力却什么改变也没有。05:26:2805:26:2805:264/12/2023 5:26:28 AM11、成功就是日复一日那一点点小小努力的积累。4月-2305:26:28
11、05:26Apr-2312-Apr-2312、世间成事，不求其绝对圆满，留一份不足，可得无限完美。05:26:2805:26:2805:26Wednesday,April 12,202313、不知香积寺，数里入云峰。4月-234月-2305:26:2805:26:28April 12,202314、意志坚强的人能把世界放在手中像泥块一样任意揉捏。12 四月 20235:26:28 上午05:26:284月-2315、楚塞三湘接，荆门九派通。四月 235:26 上午4月-2305:26April 12,202316、少年十五二十时，步行夺得胡马骑。2023/4/12 5:26:2805:26:2
12、812 April 202317、空山新雨后，天气晚来秋。5:26:28 上午5:26 上午05:26:284月-239、杨柳散和风，青山澹吾虑。4月-234月-23Wednesday,April 12,202310、阅读一切好书如同和过去最杰出的人谈话。05:26:2805:26:2805:264/12/2023 5:26:28 AM11、越是没有本领的就越加自命不凡。4月-2305:26:2805:26Apr-2312-Apr-2312、越是无能的人，越喜欢挑剔别人的错儿。05:26:2805:26:2805:26Wednesday,April 12,202313、知人者智，自知者明。胜人
13、者有力，自胜者强。4月-234月-2305:26:2805:26:28April 12,202314、意志坚强的人能把世界放在手中像泥块一样任意揉捏。12 四月 20235:26:28 上午05:26:284月-2315、最具挑战性的挑战莫过于提升自我。四月 235:26 上午4月-2305:26April 12,202316、业余生活要有意义，不要越轨。2023/4/12 5:26:2805:26:2812 April 202317、一个人即使已登上顶峰，也仍要自强不息。5:26:28 上午5:26 上午05:26:284月-23MOMODA POWERPOINTLorem ipsum dolor sit,eleifend nulla ac,fringilla purus.Nulla iaculis tempor felis amet,consectetur adipiscing elit.Fusce id urna blanditut cursus.感感 谢谢 您您 的的 下下 载载 观观 看看专家告诉
天津大学管理学院运筹学课件九章二节动态规划应用举例
