运筹学 / 习题/考试 / 作业 / 4

迁移来源

• 旧站标题：4
• 新站标题：运筹学 / 习题/考试 / 作业 / 4
• 旧站路径：/math/课程/运筹学/exams/作业/4/
• 旧页面 ID：638

Homework 4 #

姓名: 刘欣楠 班级: 数学强基 2301 学号: 2233310237

解：

设单件样品合格的概率为

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

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

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

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

(1) #

将三次试制视作三个阶段 $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.

### (2) 把“第三次试制结束后”的时刻记为阶段 $k=4$。 令 $f_k(s)$ 表示在第 $k$ 阶段开始、系统处于状态 $s$ 时， 从该阶段起到合同结束的最小期望总费用。 终端阶段（$k=4$）： $ f_4(1)=0, \qquad f_4(0)=2000. $ 对 $k=1,2,3$： $ f_k(1)=0 $ 当 $s_k=0$ 时要作决策 $x_k=n$，有 $$\begin{aligned} f_k(0) &=\min_{1\le n\le 5}\Big\{ \underbrace{C(n)} +\underbrace{(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}$$ 因为 $f_{k+1}(1)=0$。 \medskip **向后递推计算：** **阶段 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$。 \medskip **结论：** 该随机动态规划模型的最优策略为： $$\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{元}。

$$$$