第六章 动态规划应用举例 §2生产与存贮问题 生产与存贮问题是实际生产中经常遇到的问题，大量生产可以 降低成本，但当超过市场需求时，就造成积压，增加库存费用，完 全按市场需求安排生产虽然没有库存费用，但由于开工不足或加班 加点造成生产成本得的增加。因此，合理利用库存调节产量，满足 需求是十分有意义的。所谓生产存贮问题，就是一个生产部门如何 在己知生产成本、库存费用和各阶段市场需求条件下，决定各阶段 产量，使计划期内的费用总和为最小的问题。原材料采购部门也会 遇到同样问题，在那里需要确定各时期的采购量，使得计划期内总 费用最小。 这类问题通常是一个多阶段决策问题，可以用动态规划方法求 解。在动态模型中，以时期为阶段；取各时期初的库存量为状态变 量；选各阶段的产量（或采购量）为决策变量，在确定决策变量时 一般要考虑需求量、生产能力、库存限制等因素；指标函数取生产 (或采购)费用。 下面举例说明该问题的求解方法
第六章 动态规划应用举例 §2 生产与存贮问题 生产与存贮问题是实际生产中经常遇到的问题，大量生产可以 降低成本，但当超过市场需求时，就造成积压，增加库存费用，完 全按市场需求安排生产虽然没有库存费用，但由于开工不足或加班 加点造成生产成本得的增加。因此，合理利用库存调节产量，满足 需求是十分有意义的。所谓生产存贮问题，就是一个生产部门如何 在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段 产量，使计划期内的费用总和为最小的问题。原材料采购部门也会 遇到同样问题，在那里需要确定各时期的采购量，使得计划期内总 费用最小。 这类问题通常是一个多阶段决策问题，可以用动态规划方法求 解。在动态模型中，以时期为阶段；取各时期初的库存量为状态变 量；选各阶段的产量（或采购量）为决策变量，在确定决策变量时 一般要考虑需求量、生产能力、库存限制等因素；指标函数取生产 （或采购）费用。 下面举例说明该问题的求解方法
例2某工厂要制订今后四个时期某产品的生产计划，据估 计今后四个时期内，市场对于该产品的需求量如下表所示： 时期k 1 2 3 4 需求量dk 2324 假定该厂生产每批产品的固定费用为2千元，若不生产则为0： 每单位产品的成本为1千元；每件产品的每期保管费为0.5千元；每 个时期最大生产能力所允许的生产批量不超过5个单位；最大库存 量为4个单位；假定开始时库存量为1个单位，要求第四期末库存为 2个单位。试问该厂应如何安排各个时期的产量，才能在满足市场 需求的条件下，使总费用最小。 解：按四个时期将问题分成四个段k=1,2,3,4；取k期初 库存量x为状态变量；k期内产量u为决策变量，则Xk+=X+udk 根据题意，第k期的费用为 2+k 4>0 rk(xkuk)=0.5xk+ 0 4=0 记人(xk)为第k期至第4期末最小总费用，则动态规划基本方程为： 无（xk)=min{rk(风)+东+1(x+1)】 后(x5)=0 k=4,3,2,1
例2 某工厂要制订今后四个时期某产品的生产计划，据估 计今后四个时期内，市场对于该产品的需求量如下表所示： 时 期 k 1 2 3 4 需求量 dk 2 3 2 4 假定该厂生产每批产品的固定费用为2千元，若不生产则为0； 每单位产品的成本为1千元；每件产品的每期保管费为0.5千元；每 个时期最大生产能力所允许的生产批量不超过5个单位；最大库存 量为4个单位；假定开始时库存量为1个单位，要求第四期末库存为 2个单位。试问该厂应如何安排各个时期的产量，才能在满足市场 需求的条件下，使总费用最小。 解：按四个时期将问题分成四个阶段k=1，2，3，4；取k期初 库存量xk为状态变量；k期内产量uk为决策变量，则 xk+1=xk+uk- dk 根据题意，第k期的费用为 2+uk uk＞0 rk (xk , uk )=0.5xk+ 0 uk=0 记fk（xk）为第k期至第4期末最小总费用，则动态规划基本方程为： fk（xk）= min｛ rk (xk , uk ) +fk+1（xk+1）｝ uk f5（x5）=0 k=4,3,2,1
=4 注意：Xk+1Xu-dk,.x4Xu4+d4=2+4u4 而u4≤5，∴.X4=1,2,3,4 于是由动态规划基本方程人（xk)=min{「k(Xk,k)+东+1(Xk+1） 有：4（1)=0.5×1+2+5=7.5（注意：u4=6-X4) u(1)=5 f(2)=0.5×2+2+4=7 u4(2)=4 f4(3)=0.5×3+2+3=6.5 山4(3)=3 斤(4)=0.5×4+2+2=6 u4(2)=2 k=3 3=0,1,2,3,4注意：X3+u3-d3X21,而d3=2, .u≥3-x3,又x≤4，.u3≤min{5,6-x3} 于是有： 0.5×0+2+3+f(1) 5+7.5 §(0)=min0.5×0+2+4+f(2)=min6+7 =12.5 0.5×0+2+5+f(3) 7+6.5 u3(0)=3 0.5×1+2+2+f(1) 4.5+7.5 5(1)=min0.5×1+2+3+f（2) =min 5.5+7 =12 0.5×1+2+4+f(3) 6.5+6.5 0.5×1+2+5+f(4) 7.5+6 3(1)=2
k=4 注意：xk+1=xk+uk-dk，∴x4=x5-u4+d4=2+4-u4， 而u4≤5，∴x4=1，2，3，4 于是由动态规划基本方程fk（xk）= min｛ rk (xk , uk ) +fk+1（xk+1）｝ 有： f4（1）=0.5×1+2+5=7.5（注意：u4=6-x4） u4（1）=5 f4（2）=0.5×2+2+4=7 u4（2）=4 f4（3）=0.5×3+2+3=6.5 u4（3）=3 f4（4）=0.5×4+2+2=6 u4（2）=2 k=3 x3 =0,1,2,3,4 注意：x3+u3-d3=x4≥1，而d3=2， ∴u3≥3-x3，又x4≤4， ∴u3≤min｛5,6-x3｝ 于是有： 0.5×0+2+3+f4（1） 5+7.5 f3（0）=min 0.5×0+2+4+f4（2）=min 6+7 =12.5 0.5×0+2+5+f4（3） 7+6.5 u3（0）=3 0.5×1+2+2+f4（1） 4.5+7.5 f3（1）=min 0.5×1+2+3+f4（2）=min 5.5+7 =12 0.5×1+2+4+f4（3） 6.5+6.5 0.5×1+2+5+f4（4） 7.5+6 u3（1）=2
注意：ug23-x3,u3≤min{5,6-X3},X3+u3-2-x4 0.5×2+2+1+f(1) 4+7.5 ∴.6(2)=min0.5×2+2+2+f (2)=min 5+7 =11.5 0.5×2+2+3+f(3) 6+6.5 0.5×2+2+4+f(4) 7+6 u3（2)=1 0.5×3+0+f(1) 1.5+7.5 5(3)=minJ0.5×3+2+1+f(2) =min 4.5+7 =9 0.5X3+2+2+f(3) 5.5+6.5 0.5×3+2+3+f斤(4) 6.5+6 u3(3)=0 0.5×4+0+f(2) 2+7 5(4)=min{0.5×4+2+1+f(3)=min 5+6.5 =9 0.5×4+2+2+f（4) 6+6 3(4)=0
注意：u3≥3-x3，u3≤min｛5,6-x3｝, x3+u3-2=x4 0.5×2+2+1+f4（1） 4+7.5 ∴ f3（2）=min 0.5×2+2+2+f4（2）=min 5+7 =11.5 0.5×2+2+3+f4（3） 6+6.5 0.5×2+2+4+f4（4） 7+6 u3（2）=1 0.5×3+0+f4（1） 1.5+7.5 f3（3）=min 0.5×3+2+1+f4（2）=min 4.5+7 =9 0.5×3+2+2+f4（3） 5.5+6.5 0.5×3+2+3+f4（4） 6.5+6 u3（3）=0 0.5×4+0+f4（2） 2+7 f3（4）=min 0.5×4+2+1+f4（3）=min 5+6.5 =9 0.5×4+2+2+f4（4） 6+6 u3（4）=0
k=2 x2=0,1,2,3,4 注意：0≤X2u2d2x3≤4，而d2=3, ∴.3-x2≤u2≤min{5,7-x2} 于是有： 0.5×0+2+3+5(0) 5+12.5 五(0)=min0.5×0+2+4+5(1)=min6+12 =17.5 0.5×0+2+5+5(2) 7+11.5 2(0)=3 0.5×1+2+2+f6(0) 4.5+12.5 ￡(1)=min 0.5×1+2+3+5(1) =min 5.5+12 =16.5 0.5×1+2+4+5(2) 6.5+11.5 0.5×1+2+5+5(3) 7.5+9 u2(1)=5 0.5×2+2+1+5 (0) 4+12.5 0.5×2+2+2+5(1) 5+12 龙(2)=min{0.5×2+2+3+5(2) =min 6+11.5=16 0.5×2+2+4+5(3) 7+9 0.5×2+2+5+5 (4) 8+9 山(2)=4
k=2 x2 =0,1,2,3,4 注意：0≤x2+u2-d2=x3≤4,而d2=3， ∴3-x2≤u2≤min｛5,7-x2｝ 于是有： 0.5×0+2+3+f3（0） 5+12.5 f2（0）=min 0.5×0+2+4+f3（1）=min 6+12 =17.5 0.5×0+2+5+f3（2） 7+11.5 u2（0）=3 0.5×1+2+2+f3（0） 4.5+12.5 f2（1）=min 0.5×1+2+3+f3（1）=min 5.5+12 =16.5 0.5×1+2+4+f3（2） 6.5+11.5 0.5×1+2+5+f3（3） 7.5+9 u2（1）=5 0.5×2+2+1+f3（0） 4+12.5 0.5×2+2+2+f3（1） 5+12 f2（2）=min 0.5×2+2+3+f3（2）=min 6+11.5 =16 0.5×2+2+4+f3（3） 7+9 0.5×2+2+5+f3（4） 8+9 u2（2）=4