第二节动态规划应用举例 本节将通过动态规划的三种应用 类型资源分配问题、复合系统可 靠性问题、设备更新问题,进一步介 绍动态规划的特点和处理方法
第二节 动态规划应用举例 本节将通过动态规划的三种应用 类型——资源分配问题、复合系统可 靠性问题、设备更新问题，进一步介 绍动态规划的特点和处理方法
资源分配问题 1.问题的一般提法 设有某种资源,总数量为a,用于生产n种产品; 若分配数量x用于生产第评种产品,其收益为g(x,) 问应如何分配,可使总收益最大? 2.数学规划模型 决策变量:设分配给第种产品的资源数量为 目标函数:Maxz=>g(x) 模型的特点 约束条件: ≥0.i=1 变量分离
一、资源分配问题 1. 问题的一般提法 设有某种资源，总数量为a，用于生产n种产品； 若分配数量xi用于生产第i种产品，其收益为gi (xi )。 问应如何分配，可使总收益最大？ 2. 数学规划模型 决策变量： 设分配给第i种产品的资源数量为x = 目标函数： M axz = g (x ) = = = x i n x a 0, 1, , 约束条件： 模型的特点 ——变量分离
3用动态规划方法求解 g1(x1) g2(X gn(n) 2 x 2 阶段k=1,,n表示把资源分配给第k种产品的过程; 状态sk表示在给第k种产品分配之前还剩有的资源量 决策xk表示分配给第k种产品的资源量 状态转移SA+1=Sxk; 阶段指标vk=8,(x1) 基本方程1=Ma,+ 指标函数vmn=∑g(x fn=0,k=n2…1
3.用动态规划方法求解 阶段k 状态sk 决策xk =1,…,n表示把资源分配给第k种产品的过程； 表示在给第k种产品分配之前还剩有的资源量； 表示分配给第k种产品的资源量； 状态转移sk+1 = sk - xk ； 阶段指标vk 指标函数vkn ； ； = = = n i k i i k k g x g x ( ) ( ) = = = + + + 1 0, , ,1 1 f k n f M ax v f 基本方程 1 2 S1=a x1 x2 g1 (x1 ) g2 (x2 ) n xn sn gn (xn ) s2 s3
例3某公司拟将某种高效设备5台分配给所属甲 乙、丙3厂。各厂获此设备后可产生的效益如下 表。问应如何分配,可使所产生的总效益最大? 效益 设备台数 甲 丙 012345 03792 4 612 13 12
例3 某公司拟将某种高效设备5台分配给所属甲、 乙、丙3厂。各厂获此设备后可产生的效益如下 表。问应如何分配，可使所产生的总效益最大？ 效益 厂 设备台数 甲 乙 丙 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12
解:阶段k=12,3依次表示把设备分配给甲、乙、丙厂的过程; 状态sk表示在第阶段初还剩有的可分台数; 决策xk表示第阶段分配的设备台数; 状态转移S+1=-xk 阶段指标vk表示第k阶段分配后产生的效益; 指标函数v3=∑,(x Maxv+ 基本方程 k +1 f,=0,k=3,2,1 问题:本问题是属于离散型还是属于连续型?怎样解? 离散型,用表格的方式求解
解：阶段k 状态sk 决策xk =1,2,3依次表示把设备分配给甲、乙、丙厂的过程； 表示在第k阶段初还剩有的可分台数； 表示第k阶段分配的设备台数； 状态转移sk+1= sk - xk ； 阶段指标vk 指标函数vk3 ； 表示第 阶段分配后产生的效益； = = 3 k v (x ) k = = = + + 0, , ,1 1 f k 3 2 f M ax v f 基本方程 问题：本问题是属于离散型还是属于连续型？怎样解？ ——离散型，用表格的方式求解
效 益 设备台数 甲 丙 012345 03792 5011 046 3 2 X fK f 012345 k012345 k046 +0 6 046 11+ 12+0 2345 2 12+0 12
效益 厂 设备台数 甲 乙 丙 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12 k Sk xk vk vk+fk+1 f k P 3 0 1 2 3 4 5 0 1 2 3 4 5 0 4 6 11 12 12 0+0 4+0 6+0 11+0 12+0 12+0 0 4 6 11 12 12 0 1 2 3 4 5
k k fu f p 0 x0010 0+0 0 0-0 1-0 5+0 0+6 5+4 10 2-0 10 10+0 0+11 5+6 012301234 14 2-1 10 10+4 1111+0 0+12 5+11 10 16 10+6 2-2 -4 5+12 10 10+11 2345 2-3 11+6 11+4 1+0
k Sk xk vk vk+fk+1 f k P 0 1 2 3 4 5 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
k S x k k tfk f& p 0 0 0+21 3+16 7+14 21 0-2-3 9+10 2-2-1 4 12 5 13 13 最优策略:P*13为0-2-3或2-2-1, 即分给甲厂0台、分给乙厂2台、分给丙厂3台, 或分给甲厂2台、分给乙厂2台、分给丙厂1台。 最优值:f1=21。 可见,最优解可以是不唯一的,但最优值是唯一的
k Sk xk vk vk+fk+1 fk P 1 5 0 1 2 3 4 5 0 3 7 9 12 13 0+21 3+16 7+14 9+10 12+5 13+0 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种物品中挑选若干 数量装入背包,问他应如何挑选可使所带的 物品总价值最大?
资源分配问题的应用很广泛，例如： 1.某学生正在备考4门功课，还剩7天时间， 每门功课至少复习1天。若他已估计出各门功 课的复习天数与能提高的分数之间的关系， 问他应怎样安排复习时间可使总的分数提高 最多？ 2.背包问题：旅行者携带的背包中能装的 物品重量为a，现他要从n种物品中挑选若干 数量装入背包，问他应如何挑选可使所带的 物品总价值最大？
二、复合系统工作可靠性问题 1.问题的一般提法 设某工作系统由n个部件串接而成,为提 高系统的可靠性,在每个部件上装有备用件 已知部件让装有x个备用件时,其正常工作的 概率为p(x);每个部件备用件重量为v,系 统要求总重量不超过W。问应如何安排备用件 可使系统可靠性最高? 串接
二、复合系统工作可靠性问题 1. 问题的一般提法 设某工作系统由n个部件串接而成，为提 高系统的可靠性，在每个部件上装有备用件。 已知部件i上装有xi个备用件时，其正常工作的 概率为pi (xi )；每个部件i的备用件重量为wi，系 统要求总重量不超过W。问应如何安排备用件 可使系统可靠性最高？ 串接: 1 2