十动态规划的应用---生产与存储,设备更新问题分析报告.ppt

生产与存贮问题 生产周期分为 n 个阶段，已知 最初库存量： x1 阶段市场的需求：dk 生产的固定成本：K 单位产品的消耗费用：L 单位产品的阶段库存费用：h 仓库容量：M 阶段生产能力为B 一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。 问如何安排各阶段产量，使计划周期内的费用总和最小。 不能超过阶段 k 至阶段 n 的需求总量 xk ? dk+ dk+1+?+ dn，k =1, 2, ?, n 阶段 k 的初始库存量，x1已知，xn+1 = 0 0 ? xk ? min {M， dk+ dk+1+?+ dn}， （k =1, 2, ?, n） 状态变量 xk： 不能超过库存容量M， 决策变量 uk： 不超过生产能力 阶段 k 的产量 uk ? dk+ dk+1+?+ dn-xk 不小于该阶段的需求和库存量之差， 不超过 k?n 阶段的总需求减去第 k 阶段初的库存量， dk-xk ? uk ? min{B，dk+ dk+1+?+ dn-xk} 状态转移方程 为阶段生产费用和库存费用之和，即 阶段 k 的生产费用 k 阶段末的库存费用 动态规划基本方程 阶段效益 fn+1（xn+1）= 0，k = 1, 2, ?, n dk-xk ? uk ? min{B，dk+ dk+1+?+ dn-xk} 例5 已知 n = 3，K = 8，L = 2，h = 2，x1 = 1，M = 4，x4 = 0，B = 6，d1 = 3，d2 = 4，d3 = 3，求解生产与库存问题。 解：递推方程 f 4 ( x4 ) = 0，k = 1, 2, 3 当 时 =8+2(3-x3)=14-2x3 仓库容量：4 dk-xk ? uk ? min{B，dk+ dk+1+?+ dn-xk} 若 x3 = 0, u*3 (0) = 3 则 f3(0) =14 若 x3 = 1, 则 f3 (1) = 12 u*3 (1) = 2 若 x3 = 2, 则 f3 (2) = 10 u*3 (2) = 1 若 x3 = 3, 则 f3 (3) = 8 u*3 (0) = 0 f3(x3)= 14-2x3 u3 =3-x3 x3：0～3 k =2 容量4 4+3 uk ? dk-xk 4-x2 ? u2 ? min{6,7-x2} f2 (x2 )= min {8+2u2+2(x2 +u2-4)+ f3 (x2 + u2-4)} 4-x2 ? u2? min{B，d2+ d3-x2}=min{6,7-x2} 0 ? x2 ? min{M，d2+ d3} =min{4,7}=4 u*2 (0) = 4 x2 = 0 4-x2 ? u2 ? min{6,7-x2} x2 = 1 u*2 (1) = 3 4-x2 ? u2 ? min{6,7-x2} x2 = 2 u*2 (2) = 2 4-x2 ? u2 ? min{6,7-x2} x2 = 3 u*2 (3) = 1 x2 = 4 u*2(4)=0 4-x2 ? u2 ? min{6,7-x2} 结果见下表： k =1 f2=30 2?u1?6 x2= x1+ u1-d1=1+ u1-3= u1- 2 u*1 (1) = 2 x1 =1 f3=14 最优决策为 {1，0，0，0} x2=u1-2=0 x3=x2+u2-d2=0+4-4=0 最优路线为 最优目标函数值为42。 （状态变量） u*1 (1) = 2，u*2 (0) = 4， u*3 (0) = 3 设备更新问题提法如下（以一台机器为例）： n为设备计划使用年数。 Ik(t) 为第k年（阶段）机器役龄为t年的一台机器运行（在使用一年）所得的收入。 Ok(t) 为第k年机器役龄为t年的一台机器运行（再使用一年）时所需运行的费用（或维修费用） 。 Ck(t) 为第k年机器役龄为t年的一台机器更新时所需的净费用（处理一台役龄为t的旧设备，买进一台新设备的更新净费用）。 设备更新问题 ?为折扣因子，表示一年以后的收入是上一年的?单位。 要求在n年内的每年年初作出决策，是继续使用旧设备还是更换