系列文章

【管理运筹学】第 8 章 | 动态规划（1，多阶段决策过程与动态规划基本概念）
【管理运筹学】第 8 章 | 动态规划（2，动态规划的基本思想与模型求解）
【管理运筹学】第 8 章 | 动态规划（3，资源分配问题）
【管理运筹学】第 8 章 | 动态规划（4，生产与储存问题）
【管理运筹学】第 8 章 | 动态规划（5，设备更新问题）

---

引言

在生产和经营管理中，经常遇到要合理安排生产（或购买）与库存的问题，达到既要满足社会的需要，又要尽量降低成本费用。因此，正确制定生产（或采购）策略，确定不同时期的生产量（或购买量）和库存量，以使得总生产成本费用和库存费用之和最小，这就是生产与储存问题的最优化目标。

---

四、生产与储存问题

4.1 生产计划问题

设某公司要对某种产品要制定一项 $n$ 个阶段的生产（或购买）目标。已知它的初始库存量为 0 ，每阶段生产（或购买）该产品的数量有上限 $m$ 的限制；每阶段社会对该产品的需求量 $d_k$ 是已知的，公司保证供应；在 $n$ 阶段末的终结库存量为 0 。问该公司如何制定每个阶段的生产（或采购）计划，从而使总成本最小。

用动态规划方法来求解，把它看作一个 $n$ 阶段决策问题。令 $s_k$ 为状态变量，表示第 $k$ 阶段开始时的库存量；$x_k$ 为决策变量，表示第 $k$ 阶段的生产量。状态转移方程为 $s_{k+1}=s_k+x_k-d_k.$

第 $k$ 阶段的成本费用包括生产成本和存储费用两项：$c_k(x_k)+h_k(x_k)$ ，其中 $c_k(x_k)$ 表示第 $k$ 阶段生产产品 $x_k$ 时的成本费用，一般包括生产准备成本 $K$ 和产品成本 $a{x}_k$ （其中 $a$ 是单位产品成本）两项费用。有 $$c_k(x_k)=\{\begin{array}{ll}0& ,x_k=0\\ K+a{x}_k& ,x_k=1,2,\cdots ,m\\ \infty & ,x_k>m\end{array}$$ $K,a$ 为已知参数，$h_k(x_k)$ 表示在第 $k$ 阶段结束有库存量时所需的储存费用。其实第 $k$ 阶段结束时库存量就等于下一阶段开始的库存量，即 $x_{k+1}$ 。

最优值函数 $f_k(s_k)$ 表示从第 $k$ 阶段初库存量为 $s_k$ 到第 $n$ 阶段库存量为 0 时的最小总费用，其基本方程为 { f k ( s k ) = min ⁡ σ k ′ ≤ x k ≤ σ k { c k ( x k ) + h k ( x k ) + f k + 1 ( x k + s k − d k ) } , k = n , n − 1 , ⋯   , 1 f n + 1 ( s n + 1 ) = 0 \begin{cases} f_k(s_k)=\min_{\sigma_k'\leq x_k \leq \sigma_k} \{c_k(x_k)+h_k(x_k)+f_{k+1}(x_k+s_k-d_k)\} ,k=n,n-1,\cdots,1 \\ f_{n+1}(s_{n+1})=0 \end{cases} {fk​(sk​)=minσk′​≤xk​≤σk​​{ck​(xk​)+hk​(xk​)+fk+1​(xk​+sk​−dk​)},k=n,n−1,⋯,1fn+1​(sn+1​)=0​ 其中， σ k = min ⁡ { ∑ i = k n d i − s k , m } \sigma_k=\min\{\sum_{i=k}^nd_i-s_k,m\} σk​=min{∑i=kn​di​−sk​,m} ，一方面每阶段生产上限为 $m$ ，另一方面需保证 $n$ 阶段结束时库存量能取 0 。 σ k ′ = max ⁡ { d k − s k , 0 } \sigma'_k=\max\{d_k-s_k,0\} σk′​=max{dk​−sk​,0} ，这是为了保证第 $k$ 阶段的生产量能满足市场需求。

4.2 不确定性的采购问题

在实际问题中，还会遇到某些多阶段决策过程，与前面所讨论的确定性不同，出现了随机性因素，状态转移不能完全确定，是按照某种已知的概率分布取值的。具有这种性质的多阶段决策过程称为随机性的决策过程。下面举一个例子。

（采购问题） 某厂生产上需要在近 5 周内采购一批原料，而估计在未来 5 周内价格会有波动，单价为 500 的概率为 0.3 ，为 600 的概率为 0.3 ，为700 的概率为 0.4 。试求在哪一周以什么价格购入，能使得其采购价格的数学期望最小？并求出期望值。

我感觉这类题目还可以改成求采购价格的最大可能、最小可能等等。

按采购期限，分为 5 个阶段，设

$y_k$ —— 状态变量，表示第 $k$ 周的实际价格。

$x_k$ —— 决策变量，表示第 $k$ 周是否决定采购，当取值为 1 时，表示第 $k$ 周采购；取值为 0 时，表示第 $k$ 周决定等待。

$y_{kE}$ —— 第 $k$ 周决定等待，而在以后采取最优决策时的采购价格平均值。

$f_k(y_k)$ —— 第 $k$ 周实际价格为 $y_k$ 时，从第 $k$ 周至第 5 周采取最优决策所得的最小期望值。

则逆序递推关系为 { f k ( y k ) = min ⁡ { y k , y k E } , y k ∈ s k f 5 ( y k ) = y 5 , y 5 ∈ s 5 \begin{cases} f_k(y_k)=\min\{y_k,y_{kE}\},&y_k \in s_k \\ f_5(y_k)=y_5,&y_5\in s_5 \end{cases} {fk​(yk​)=min{yk​,ykE​},f5​(yk​)=y5​,​yk​∈sk​y5​∈s5​​ 其中， s k = { 500 , 600 , 700 } , k = 1 , 2 , 3 , 4 , 5. s_k=\{500,600,700\},k=1,2,3,4,5. sk​={500,600,700},k=1,2,3,4,5.

当第 $k$ 周实际价格为 $y_k$ 时，若选择等待，则 $y_{kE}=E[f_{k+1}(y_{k+1})]=0.3f_{k+1}(500)+0.3f_{k+1}(600)+0.4f_{k+1}(700)$ 。如果 $f_k(y_k)=y_{kE}$ ，则第 $k$ 周应选择等待，即 $x_k=0$ ；如果 $f_k(y_k)=y_k$ ，则第 $k$ 周应选择购入，即 $x_k=1$ ；

第一步： $k=5$ ，此时必须购入，则 $x_5=1,f_5(500)=500,f_5(600)=600,f_5(700)=700.$

第二步： $k=4$ ，$y_{4E}=0.3f_5(500)+0.3f_5(600)+0.4f_5(700)=0.3\times 500+0.3\times 600+0.4\times 700=610$ ，则 f 4 ( y 4 ) = min ⁡ { y 4 , y 4 E } = { 500 , y 4 = 500 600 , y 4 = 600 610 , y 4 = 700 f_4(y_4)=\min\{y_4,y_{4E}\}=\begin{cases} 500,&y_4=500 \\ 600,&y_4=600 \\ 610,&y_4=700 \end{cases} f4​(y4​)=min{y4​,y4E​}=⎩ ⎨ ⎧​500,600,610,​y4​=500y4​=600y4​=700​ 可知，当第 4 周实际价格为 500 或 600 时，可以选择购入；当实际价格为 700 时，应等待。

第三、四、五步： 同理，可计算得到， f 3 ( y 3 ) = min ⁡ { y 3 , y 3 E = 574 } = { 500 , y 3 = 500 574 , y 3 = 600 574 , y 3 = 700 , x 3 = { 1 , y 3 = 500 0 , y 3 = 600 , 700 ; f_3(y_3)=\min\{y_3,y_{3E}=574\}=\begin{cases} 500,&y_3=500 \\ 574,&y_3=600 \\ 574,&y_3=700 \end{cases},x_3=\begin{cases} 1,&y_3=500 \\ 0,&y_3=600,700 \end{cases}; f3​(y3​)=min{y3​,y3E​=574}=⎩ ⎨ ⎧​500,574,574,​y3​=500y3​=600y3​=700​,x3​={1,0,​y3​=500y3​=600,700​; f 2 ( y 2 ) = min ⁡ { y 2 , y 2 E = 551.8 } = { 500 , y 2 = 500 551.8 , y 2 = 600 551.8 , y 2 = 700 , x 2 = { 1 , y 2 = 500 0 , y 2 = 600 , 700 ; f_2(y_2)=\min\{y_2,y_{2E}=551.8\}=\begin{cases} 500,&y_2=500 \\ 551.8,&y_2=600 \\ 551.8,&y_2=700 \end{cases},x_2=\begin{cases} 1,&y_2=500 \\ 0,&y_2=600,700 \end{cases}; f2​(y2​)=min{y2​,y2E​=551.8}=⎩ ⎨ ⎧​500,551.8,551.8,​y2​=500y2​=600y2​=700​,x2​={1,0,​y2​=500y2​=600,700​; f 1 ( y 1 ) = min ⁡ { y 1 , y 1 E = 536.26 } = { 500 , y 1 = 500 536.26 , y 1 = 600 536.26 , y 1 = 700 , x 1 = { 1 , y 1 = 500 0 , y 1 = 600 , 700 ; f_1(y_1)=\min\{y_1,y_{1E}=536.26\}=\begin{cases} 500,&y_1=500 \\ 536.26,&y_1=600 \\ 536.26,&y_1=700 \end{cases},x_1=\begin{cases} 1,&y_1=500 \\ 0,&y_1=600,700 \end{cases}; f1​(y1​)=min{y1​,y1E​=536.26}=⎩ ⎨ ⎧​500,536.26,536.26,​y1​=500y1​=600y1​=700​,x1​={1,0,​y1​=500y1​=600,700​; 综上，最优采购策略为：前三周，价格为 500 就购入，否则等待；第 4 周时，如果还没购入，价格为 500 或 600 时就购入，否则等待；第 5 周时，如果还没购入，不管怎么样都应该购入。

按照上述策略进行采购时，采购价格的数学期望计算如下：$$E=500\times (0.3+0.7\times 0.3+0.7^2\times 0.3+0.7^3\times 0.3+0.7^3\times 0.4\times 0.3)+$$ $$600\times (0.7^3\times 0.3+0.7^3\times 0.4\times 0.3)+700\times (0.7^3\times 0.4\times 0.4)=\mathrm{525.382.}$$

还好前几天复习了下概率论，要不这个数学期望还真不太好理解。

---

写在最后

对于确定型生产计划问题，其实和资源分配问题有点像，只是多加了一部分回收的费用；而对于不确定型采购问题，则有点难以理解，建模难度较高，不过求解方法和前面类似。