问题提出

• 已知时段 $t$ 某产品的需求量为 $d_t(t=1,2,...,T)$，任意时刻或生产该产品，需付出生产准备费 $c_0$ ，且生产每单位产品的生产成本为 $k$，若满足本时段需求后有剩余，每时段每单位产品需付出存贮费 $h_0$。
• 设每时段最大生产能力为 $X_m$，最大存贮量为 $I_m$，且第1时段初有库存量 $i_1$。
• 试制定产品的生产计划，即每时段的产量，使 $T$ 个时段的总费用最小。
• 假设：
  $$\begin{gathered} T=3,d_1=2,d_2=1,d_3=2(单位), \\ {c}_0=3(千元),k=2(千元/单位),h_0=1(千元/单位\ast 时段), \\ {X}_m=4(单位),I_m=3(单位),i_1=1(单位), \end{gathered}$$

问题分析与求解

• 记时段 $t$ 的产量为 $x_t$ ：
  当 $x_t>0$ 时，生产费用为 $c(x_t)=c_0+k{x}_t=3+2x_t$；
  当 $x_t=0$ 时，生产费用为 $c(0)=0$
• 记时段 $t$ 的贮存量为 $i_t$：
  满足时段 $t$ 的需求量 $d_t$ 后，时段 $t+1$ 初（即时段 $t$ 末）的存贮量为 $i_{t+1}=i_t+x_t-d_t$
• 于是时段 $t$ 的存贮费为：
  $$h(i_t)=h_0(i_t+x_t-d_t)=i_t+x_t-d_t，且x_t\le X_m=4,i_t\le I_m=3.$$
• 为了简化这个多阶段生产计划问题，我们将它从后向前地分解为一个个单时段问题。
• 首先看最后一个时段（时段3），对于时段3初的存贮量 $i_3$，记时段3的最小费用为 $f_3(i_3)$，产量为 $x_3(i_3)$。为了使3个时段的总费用最小，时段3末的存贮量显然应为0，且时段3的产量只需满足需求 $d_3=2$ 即可，所以只需考虑 $i_3=0,1,2$ 的情况，容易计算出：
  $$\begin{gathered} f_3(0)=c(2)=3+2\times 2=7,x_3(0)=2; \\ {f}_3(1)=c(1)=5,x_3(1)=1; \\ {f}_3(2)=c(0)=0,x_3(2)=0. \end{gathered}$$
• 然后看倒数第2个时段（时段2），对于时段2初的存贮量 $i_2$，产量为 $x_2$，因为 $d_2=1$，时段2末的存贮量为 $i_2+x_2-1$，于是时段2与时段3的最小费用之和记为 $f_2(i_2)$，注意到时段3的最小费用为 $f_3(i_3)=f_3(i_2+x_2-1)$，所以：
  f2(i2)=min⁡x2{c(x2)+h(i2)+f3(i2+x2−1)} f_2(i_2)=\min_{x_2}{\left\{c(x_2)+h(i_2)+f_3(i_2+x_2-1)\right\}} f2​(i2​)=x2​min​{c(x2​)+h(i2​)+f3​(i2​+x2​−1)}
  
  
• 故最优生产计划是：3个时段的产量依次是 $x_1=2,x_2=0,x_3=2$。

最短路径问题

确定需求下多阶段生产计划的一般模型

1.根据时段 $T$ 末存贮量的要求，确定 $f_{T+1}(i_{T+1})$
2.时段从后向前地计算最小费用，按照以下公式递推：
ft(it)=min⁡xt{c(xt)+h(it)+ft+1(it+1)},it+1=it+xt−dtit≤Im,xt≤Xm,t=T,T−1,...,1. f_t(i_t)=\min_{x_t}{\left\{c(x_t)+h(i_t)+f_{t+1}(i_{t+1})\right\}}, i_{t+1}=i_t+x_t-d_t\\ i_t\le I_m,x_t\le X_m, t=T,T-1,...,1. ft​(it​)=xt​min​{c(xt​)+h(it​)+ft+1​(it+1​)},it+1​=it​+xt​−dt​it​≤Im​,xt​≤Xm​,t=T,T−1,...,1.
得到从时段 $t$ 到时段 $T$ d 最小费用 $f_t(i_t)$ 及相应的 $x_t(i_t)$
3.时段从前向后地确定最优生产计划

随机需求下的多阶段生产计划

• 如果每个时段的需求量是随机的，那么对于确定的生产量，各时段的存贮量也是随机的，于是存贮费乃至总费用都是随机的，优化问题的目标是总费用的期望值最小，这个随机优化问题可以用随机动态规划求解。
• 仍然考察 $T=3$ 个时段，设需求量 $d_t=1$ 的概率为 $1/3$，$d_t=2$ 的概率为 $2/3(t=1,2,3)$。
• 因为计划结束时（时段3末）存贮量是随机的（不一定为零），我们假定，这时剩余的存贮量能够以 1.5千元/单位 的价格出售。
• 将随机需求表示为 $P(d_t=1)=1/3,P(d_t=2)=2/3$，生产费用为 $c(x_t)=c_0+k{x}_t=3+2x_t(x_t>0),c(0)=0$，存贮量的转移仍为 $i_{t+1}=i_t+x_t-d_t$，由随机需求得到存贮费的期望值：
  $$\begin{gathered} Eh(i_t)=h_{0}E(i_t+x_t-d_t) \\ =(i_t+x_t-1)P(d_t=1)+(i_t+x_t-2)P(d_t=2) \\ =i_t+x_t-5/3 \end{gathered}$$
• 当时段3初的存贮量为 $i_3$ 时，计划结束时出售剩余量得到的回报记作 $s(i_3)$，回报的期望值为：
  $$Es(i_3)=1.5[(i_3+x_3-1)/3+2(i_3+x_3-2)/3]=1.5(i_3+x_3)-2.5$$
  产量、存贮量的限制仍然为 $x_t\le X_m=4,i_t\le I_m=3$.
• 记时段3期望费用的最小值为 $f_3(i_3)$，产量为 $x_3(i_3)$，在满足随机需求的 $d_3$ 的前提下，容易算出：
  
• 计算时段2与时段3期望费用的最小值 $f_2(i_2)$ 时， $h(i_t)$ 应改为 $Eh(i_2)$，$f_3(i_3)$ 应改为 $f_3(i_2+x_2-1)P(d_t=1)+f_3(i_2+x_2-2)P(d_t=2)$.
  -可以将随机需求下的最优计划用图2表示：
  

总结归纳

• 建立动态规划模型的主要步骤为：划分阶段，定义状态（如存贮量）和决策（产量），建立状态转移律（如 $i_{t+1}=i_t+x_t-d_t$），确定允许状态集合和允许决策集合，列出最优方程并确定终端条件（$f_{T+1}(i_{t+1})$）。