《天津大学管理学院运筹学课件九章二节动态规划应用举例》由会员分享，可在线阅读，更多相关《天津大学管理学院运筹学课件九章二节动态规划应用举例（4页珍藏版）》请在金锄头文库上搜索。
1、天津大学管理学院运筹学课件九章二节动态规划应用举例 第二节动态规划应用举例本节将通过动态规划的三种应用类型资源分配问题、复合系统可靠性问题、设备更新问题，进一步介绍动态规划的特点和处理方法。 一、资源分配问题1.问题的一般提法设有某种资源，总数量为a，用于生产n种产品；若分配数量x i用于生产第i种产品，其收益为g i(x i)。 问应如何分配，可使总收益最大？2.数学规划模型ix i种产品的资源数量为设分配给第决策变量?nii ixg Maxz1)(目标函数?n ixa xinii,1,01?约束条件模型的特点变量分离。 3.用动态规划方法求解阶段k状态s k决策x k=1,n表示把资源分配
2、给第k种产品的过程；表示在给第k种产品分配之前还剩有的资源量；表示分配给第k种产品的资源量；状态转移s k+1=s k-x k；阶段指标v k指标函数v kn；?nk iiik kxgx g)()(?,1,0,11?n k ff v Max fnkkxkk基本方程12S1=a x1x2g1(x1)g2(x2)n x n sn gn(x n)s2s3.例3某公司拟将某种高效设备5台分配给所属甲、乙、丙3厂。 各厂获此设备后可产生的效益如下表。 问应如何分配，可使所产生的总效益最大？效益厂设备台数甲乙丙000013542710639111141211125131112解阶段k状态s k决策x k=
3、1,2,3依次表示把设备分配给甲、乙、丙厂的过程；表示在第k阶段初还剩有的可分台数；表示第k阶段分配的设备台数；状态转移s k+1=s k-x k；阶段指标v k指标函数v k3；阶段分配后产生的效益表示第?3k)(ii ixvk?,1,0,1234k ff v Max fk kxkk基本方程问题本问题是属于离散型还是属于连续型？怎样解？离散型，用表格的方式求解。 效益厂设备台数甲乙丙000013542710639111141211125131112k Sk x k v k v k+f k+1f k?knP30123450123450461112120+04+06+011+012+012+00
4、4611121xx345k Sk x k vk vk+f k+1f k?knP0123452000+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-3k Sk x k vk vk+f k+1f k?knP15012345037912130+213+167+149+1012+513+0210-2-32-2-1最优策略P*13为0-2-
5、3或2-2-1，即分给甲厂0台、分给乙厂2台、分给丙厂3台，或分给甲厂2台、分给乙厂2台、分给丙厂1台。 最优值f1=21。 可见，最优解可以是不唯一的，但最优值是唯一的。 资源分配问题的应用很广泛，例如1.某学生正在备考4门功课，还剩7天时间，每门功课至少复习1天。 若他已估计出各门功课的复习天数与能提高的分数之间的关系，问他应怎样安排复习时间可使总的分数提高最多？2.背包问题旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？ 二、复合系统工作可靠性问题1.问题的一般提法设某工作系统由n个部件串接而成，为提高系统的可靠性，在
6、每个部件上装有备用件。 已知部件i上装有x i个备用件时，其正常工作的概率为p i(x i)；每个部件i的备用件重量为w i，系统要求总重量不超过W。 问应如何安排备用件可使系统可靠性最高？串接:122.数学规划模型个备用件个部件安排设给第决策变量ix i)(1i inixp Maxz?目标函数?为非负整数约束条件inii ixW x w1模型的特点变量分离。 3.用动态规划方法求解12S1=Wx1x2p1(x1)p2(x2)n x n sn pn(x n)s2s3.阶段k状态s k决策x k=1,n表示安排第k个部件备用件的过程；表示在给第k个部件安排之前还剩有的容许重量；表示第k个部件上安
7、排的备用件数量；状态转移s k+1=s k-w kx k；阶段指标vk指标函数v kn；的可靠性；部件安排备用件后产生表示第)(ni ikix pk?,1,1n1?n kffvMaxfk kxkk1基本方程可靠性问题的应用很广泛，例如1.某重要的科研攻关项目正在由3个课题组以3种不同的方式进行，各组已估计出失败的概率。 为减少失败的概率，选派了2名高级专家去充实科研力量。 若可估计出各组增加专家后的失败概率，问应如何分派专家可使总的失败概率最小？2.已知x1+x2+xn=c，求z=x1x2xn的最大值。 三、设备更新问题例4某运输公司购进一批卡车投入运营，公司每年初需对卡车作出更新或继续使用的
8、决定。 假设第k年中，r k(t k)表示车龄为t k的车使用一年的收入，u k(t k)表示车龄为t k的车使用一年的维修费用，c k(t k)表示车龄为t k的车更新成新车的费用。 现公司需制定一个10年计划，以决定如何安排使10年的总收入最大。 12S1=？x1x210x10s10v1v2v10s2问题状态和决策怎样设置？决策是更新与否，可用0-1变量表示；状态可设为车龄。 阶段k状态s k决策x k=1,10表示第k年的决策过程；=t k表示第k年的车龄；?年不更新，第年更新第kk01,状态转移t k+1=t k+1(1-x k)阶段指标vk指标函数v kn=r kt k-u kt k-c k(t k)(1-xk)(1-xk)xk；?10k iiv?,110,0,111?kffvMaxfkkxkk1,0基本方程。 内容仅供参考
