动态规划解生产存储问题

动态规划解生产存储问题"/>

动态规划解生产存储问题

某工厂调查了解市场情况，估计在今后四个月内，市场对其产品的需求量如下表所示。

已知：对每个月来讲，生产一批产品的固定成本费为3 (千元)，若不生产，则为零。每生产单位产品的成本费为1(千元)。同时，在任何一个月内，生产能力所允许的最大生产批量为不超过6个单位。又知每单位产品的库存费用为每月0.5(千元)，同时要求在第一个月开始之初， 及在第四个月末，均无产品库存。问：在满足上述条件下，该厂应如何安排各个时期的生产与库存，使所花的总成本费用最低？

设第k月的需求量为Nk(k=1,2,3,4)

状态变量Xk：第k月初的库存量，X1=X5=0，0≤Xk≤Nk+…+N4

决策变量Uk：第k月的生产量，max{0，Nk-Xk}≤Uk≤min{6，Nk+…+N4 - Xk}

状态转移方程：X_k+1 = Uk + Xk – Nk

第k月的成本Vk = 0.5*(Xk - Nk)                 Uk=0

                 3 + Uk + 0.5*(Uk + Xk - Nk)      Uk≠0

设F_k(Xk)是由第k月初的库存量Xk开始到第4月份结束这段时间的最优成本

则F_k(Xk) = min{Vk + F_k+1(X_k+1)}        1≤k≤4

= min{ 3 + Uk + 0.5*(Uk + Xk - Nk) + F_k+1(Uk+ Xk - Nk) }  Uk≠0

 min{ 0.5*(Xk - Nk) + F_k+1(Xk - Nk) }                  Uk=0

F₅(X5)=0

四个月内的最优成本为F₁(X1)=F₁(0)

详细计算步骤如下：

（1）k=4时

0≤X4≤4，max{0，4 - X4}≤U4≤min{6，4-X4}

即对于状态X4的每个取值，都有唯一确定的决策变量U4使得F₄(X4)最优

（2）k=3时

0≤X3≤6，max{0，2 - X3}≤U3≤min{6，6-X3}

（3）k=2时

0≤X2≤9，max{0，3 - X2}≤U2≤min{6，9-X2}

（4）k=1时

X1=0，max{0，2}≤U1≤min{6，11}

由以上计算可得，4个月的总最优成本为F₁(0) = 20.5(千元)

从k=1回溯，可得最优结果中各阶段的状态变量Xk和决策变量Uk如下表：