天津大学管理学院运筹学课件九章二节动态规划应用举例

第二节 动态规划应用举例 本节将通过动态规划的三种应用类型——资源分配问题、复合系统可靠性问题、设备更新问题，进一步介绍动态规划的特点和处理方法。一、资源分配问题1. 问题的一般提法 设有某种资源，总数量为 a ，用于生产 n种产品；若分配数量 xi 用于生产第 i 种产品，其收益为 gi(xi) 。问应如何分配，可使总收益最大？2. 数学规划模型ixi种产品的资源数量为设分配给第决策变量： niii xgMaxz1)( 目标函数：nixaxinii,,1,0 1约束条件：模型的特点—— 变量分离。3. 用动态规划方法求解阶段 k状态 sk决策 xk=1,…,n 表示把资源分配给第 k 种产品的过程；表示在给第 k 种产品分配之前还剩有的资源量；表示分配给第 k 种产品的资源量；状态转移 sk+1 = sk- xk ；阶段指标 vk指标函数 vkn ；；nkiiikkxgxg)()(,1,0,11nkffvMaxfnkkxkk基本方程12S1=ax1x2g1(x1)g2(x2) 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 ；；阶段分配后产生的效益表示第3k)(iii xvk,1,0,1234kffvMaxfkkxkk基本方程问题：本问题是属于离散型还是属于连续型？怎样解？—— 离散型，用表格的方式求解。效益厂设备台数甲 乙 丙0 0 0 01 3 5 42 7 10 63 9 11 114 12 11 125 13 11 12k Sk xk vk vk+fk+1 fkknP3012345012345 0 4 6111212 0+0 4+0 6+011+012+012+0 0 4 6111212012345k Sk xk vk vk+fk+1 fkknP0123452 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 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 v...