第二节动态规划应用举例 本节将通过动态规划的三种应用 类型资源分配问题、复合系统可 靠性问题、设备更新问题,进一步介 绍动态规划的特点和处理方法
第二节 动态规划应用举例 本节将通过动态规划的三种应用 类型——资源分配问题、复合系统可 靠性问题、设备更新问题，进一步介 绍动态规划的特点和处理方法
资源分配问题 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 基本方程 问题：本问题是属于离散型还是属于连续型？怎样解？ ——离散型，用表格的方式求解