运筹学：第 4 次作业

随机动态规划解答 #

内容状态：解答存档。 当前资料仅包含解答，原始题面尚待补录。以下保留能够确认的参数与计算过程。

设单件样品合格的概率为

p=0.4,\qquad 1-p=0.6.

每次试制一批 $n$ 件样品时的费用为

C(n)=200+100n,\qquad n=1,2,\dots,5.

其中 $200$ 元为每批装配费， $100n$ 元为本批 $n$ 件样品的制造费。三个月内未能交出合格样品时，需支付违约金 $2000$ 元。

将三次试制视作三个阶段 $k=1,2,3$ 。在第 $k$ 次试制前，状态变量记为

s_k= \begin{cases} 0, & \text{到目前为止尚未制出合格样品},\\[2mm] 1, & \text{到目前为止已经制出至少一件合格样品}. \end{cases}

第 $k$ 阶段的决策变量为

x_k=n\in\{1,2,3,4,5\},

表示在本批中生产 $n$ 件样品。

若在状态 $s_k=0$ 时选择 $x_k=n$ ，本批中至少出现一件合格样品的概率为

1-(1-p)^n=1-0.6^n,

全部不合格的概率为 $0.6^n$ 。因此

\begin{aligned} P(s_{k+1}=1\mid s_k=0,x_k=n)&=1-0.6^n,\\ P(s_{k+1}=0\mid s_k=0,x_k=n)&=0.6^n. \end{aligned}

若某阶段开始前已经有合格品，即 $s_k=1$ ，则以后保持该状态且不再生产：

P(s_{k+1}=1\mid s_k=1)=1,\qquad P(s_{k+1}=0\mid s_k=1)=0.

把第三次试制结束后的时刻记为阶段 $k=4$ 。令 $f_k(s)$ 表示第 $k$ 阶段开始时系统处于状态 $s$ ，从当前阶段到合同结束的最小期望总费用。

终端条件为

f_4(1)=0,\qquad f_4(0)=2000.

对 $k=1,2,3$ ，已有合格品时不再发生试制费用，因此

f_k(1)=0.

当 $s_k=0$ 时选择 $x_k=n$ ，Bellman 方程为

\begin{aligned} f_k(0) &=\min_{1\le n\le 5}\Big\{ C(n)+(1-0.6^n)f_{k+1}(1)+0.6^n f_{k+1}(0) \Big\}\\ &=\min_{1\le n\le 5}\big\{200+100n+0.6^n f_{k+1}(0)\big\}. \end{aligned}

阶段 3

由 $f_4(0)=2000$ ，得到

\begin{aligned} f_3(0) &=\min_{1\le n\le 5}\{200+100n+0.6^n\cdot2000\}\\ &=\min\{1500,\ 1120,\ 932,\ 859.2,\ 855.52\}. \end{aligned}

因此 $f_3(0)=855.52$ ，最优决策为 $n_3^*=5$ 。

阶段 2

\begin{aligned} f_2(0) &=\min_{1\le n\le 5}\{200+100n+0.6^n f_3(0)\}\\ &=\min\{813.312,\ 707.9872,\ 684.79232,\ 710.875392,\ 766.5252352\}. \end{aligned}

因此 $f_2(0)=684.79232$ ，最优决策为 $n_2^*=3$ 。

阶段 1

\begin{aligned} f_1(0) &=\min_{1\le n\le 5}\{200+100n+0.6^n f_2(0)\}\\ &=\min\{710.875392,\ 646.5252352,\ 647.91514112,\ 688.749084672,\ 753.2494508032\}. \end{aligned}

因此 $f_1(0)=646.5252352$ ，最优决策为 $n_1^*=2$ 。

最优策略为：

\begin{cases} \text{第 1 批生产 }2\text{ 件样品};\\ \text{若尚无合格品，第 2 批生产 }3\text{ 件样品};\\ \text{若仍无合格品，第 3 批生产 }5\text{ 件样品}. \end{cases}

从初始状态 $s_1=0$ 出发，最小期望总费用为

f_1(0)\approx 646.53\ \text{元}.