109 高普考高考三級 工業工程 作業研究 考古題詳解

核心觀念

本題考查單形法最佳基底下的對偶價格（影子價格）、減少成本與目標係數可允許範圍。

最佳解為 $x_2=10,\ x_4=10$，其餘產品產量為 0。代入限制式可得：

• 資源 1、2 用量分別為 $30、20$，兩者緊束。
• 資源 3、4 用量分別為 $30、30$，故 $x_7=10,\ x_8=30$。

因此一組最佳基底為 $(x_2,x_4,x_7,x_8)$。其基底矩陣及反矩陣為：

$$B= \begin{bmatrix} 1&2&0&0\\ 1&1&0&0\\ 2&1&1&0\\ 1&2&0&1 \end{bmatrix}, \qquad B^{-1}= \begin{bmatrix} 0&0&\frac23&-\frac13\\ 0&0&-\frac13&\frac23\\ 1&0&0&-1\\ 0&1&-\frac13&-\frac13 \end{bmatrix}.$$

基底變數的目標係數向量為 $c_B=(60,100,0,0)$。影子價格向量為

$$y^T=c_B^TB^{-1} =(0,\ 0,\ 20,\ \tfrac{140}{3}).$$

對最大化問題，非基底變數 $x_j$ 的減少成本為 $c_j-y^Ta_j$；基底保持最適的條件是所有非基底變數的減少成本皆不大於 0。

（一）四個資源的影子價格

影子價格依序為：

$$\boxed{y_1=0,\quad y_2=0,\quad y_3=20,\quad y_4=\frac{140}{3}}.$$

每單位資源 1、2 的邊際價值為 0；每增加一單位資源 3，最佳收入的邊際增加額為 20；每增加一單位資源 4，邊際增加額為 $\frac{140}{3}$。

（二）資源 1 增加 1 單位

最佳收入增加額為影子價格乘上資源增量：

$$\Delta Z=y_1\Delta b_1=0\times1=0.$$

所以新最佳收入增加 0。理由是資源 1 的影子價格為 0；在目前基底下，資源 1 增加不會提高最佳目標值。原最佳收入為

$$60(10)+100(10)=1600.$$

因此增加後的最佳收入仍為 $1600$。

（三）加購資源 2 的最高價格

資源 2 的影子價格為 $y_2=0$，表示增加一單位資源 2 對最佳收入沒有邊際貢獻。因此最高購買價格為

$$\boxed{0}.$$

若購買價格大於 0，增加資源 2 所帶來的收入增益不足以抵銷成本。

（四）產品 3 的價格門檻

產品 3 的單位資源需求向量為 $a_3=(2,2,2,1)^T$。在目前影子價格下，生產一單位產品 3 所耗用資源的機會成本為

$$y^Ta_3 =2(0)+2(0)+2(20)+\frac{140}{3} =\frac{260}{3}.$$

產品 3 的目標係數提高到其機會成本時，減少成本恰為 0；超過該值後，產品 3 才會進入最適基底。因此門檻價格為

$$\boxed{\frac{260}{3}\approx86.67}.$$

也就是產品 3 的價格須由 20 提高至 $\frac{260}{3}$；達到門檻時已具備進入基底的條件，若要嚴格說「開始生產正數產量」，價格需高於此門檻。

（五）四個產品價格的可允許範圍

以下每次只改變一個產品價格，其餘價格維持原值；範圍端點包含在內時，原基底仍為最適基底。

產品 1 價格 $C_1$

產品 1 為非基底變數，其最適條件為

$$C_1-y^Ta_1\le 0.$$

其中 $a_1=(1,1,1,1)^T$，故

$$y^Ta_1=0+0+20+\frac{140}{3}=\frac{200}{3}.$$

因此

$$\boxed{C_1\in(-\infty,\tfrac{200}{3}]}.$$

產品 2 價格 $C_2$

核心觀念

本題考馬可夫鍊的狀態設定、轉移矩陣、穩態機率，以及由穩態機率計算欠單發生率與平均間隔。

以每日結束營業後的淨庫存量作為狀態：欠單以負數表示。例如狀態 $-1$ 代表欠單 $1$ 支。每日需求 $D$ 為 $0、1、2$，各以 $1/3$ 的機率發生。

解題方法

（一）狀態空間與補貨量

若當日結束時庫存量大於 $0$，不補貨，隔日開店庫存維持原數量。若結束時庫存量小於或等於 $0$，則補貨，供貨於隔日開店前到達。

各狀態的補貨決策如下：

• 狀態 $-1$：欠單 $1$ 支，並希望補足 $S=2$ 支庫存，合計需要 $3$ 支，因此補 $R_2=3$ 支。
• 狀態 $0$：沒有欠單，希望補至 $2$ 支。$R_1=1$ 與 $R_2=3$ 均無法恰好補至 $2$；選 $R_1=1$ 後庫存為 $1$，不超過上限且可儘量補足庫存。
• 狀態 $1、2$：庫存大於 $s=0$，不補貨。

補貨後隔日開店的庫存為：

前一日結束狀態	補貨量	隔日開店庫存
$-1$	$3$	$2$
$0$	$1$	$1$
$1$	$0$	$1$
$2$	$0$	$2$

因此狀態空間為

$$\mathcal S=\{-1,0,1,2\}.$$

狀態 $-1$ 是可能出現的最低值：隔日開店庫存至少為 $1$，而單日需求最多為 $2$，最多只會欠單 $1$ 支。

（二）轉移矩陣

依狀態順序 $(-1,0,1,2)$，逐列計算：

• 從 $-1$ 出發，隔日開店庫存為 $2$；需求 $0、1、2$ 後，結束狀態分別為 $2、1、0$。
• 從 $0$ 或 $1$ 出發，隔日開店庫存為 $1$；需求 $0、1、2$ 後，結束狀態分別為 $1、0、-1$。
• 從 $2$ 出發，隔日開店庫存為 $2$；結束狀態分別為 $2、1、0$。

每種需求的機率均為 $1/3$，故轉移矩陣為

$$P= \begin{pmatrix} 0&\frac13&\frac13&\frac13\\ \frac13&\frac13&\frac13&0\\ \frac13&\frac13&\frac13&0\\ 0&\frac13&\frac13&\frac13 \end{pmatrix}.$$

列代表當日結束狀態，欄代表隔日結束狀態；每列總和均為 $1$。

（三）穩態機率

令穩態機率向量為

$$\boldsymbol{\pi}=(\pi_{-1},\pi_0,\pi_1,\pi_2),$$

滿足

核心觀念

本題考有限期程的資源分配問題，使用動態規劃逐一決定三種產品各分配幾天，使總成本最低。階段代表依序處理的產品；狀態記錄目前尚可分配的天數；決定是本階段產品分配的天數。

令 $f_i(t)$ 表示產品 $i$ 分配 $t$ 天的製造成本。總天數必須恰為 7 天，且符合各產品的天數限制：

• 產品 1：1 至 4 天。
• 產品 2：2 至 4 天。
• 產品 3：1 至 3 天。

（一）階段、狀態與決定

• 階段（stage）：依產品順序分為 3 個階段，第 $i$ 階段處理產品 $i$。
• 狀態（state）：進入第 $i$ 階段時，尚未分配的生產天數，記為 $s$。
• 決定（decision）：第 $i$ 階段分配給產品 $i$ 的天數，記為 $x_i$；決定後進入下一階段的狀態為 $s-x_i$。

（二）動態規劃求解與決策樹

遞迴式

令 $F_i(s)$ 為從第 $i$ 個產品開始，將剩餘 $s$ 天分配給產品 $i$ 至產品 3 的最低成本。則

$$F_i(s)=\min_{x_i\in A_i}\left\{f_i(x_i)+F_{i+1}(s-x_i)\right\}$$

其中 $A_1=\{1,2,3,4\}$、$A_2=\{2,3,4\}$、$A_3=\{1,2,3\}$，並且各產品天數總和須恰為 7。終端條件為 $F_4(0)=0$；若剩餘天數不為 0，則該分配不可行。

由後往前計算

第 3 階段：產品 3

產品 3 至少 1 天、最多 3 天，且須恰好用完剩餘天數：

$$F_3(1)=90,\qquad F_3(2)=60,\qquad F_3(3)=50$$

第 2 階段：產品 2

產品 2 至少 2 天。逐一考慮可行的剩餘天數：

• 剩 3 天：只能分配產品 2 為 2 天、產品 3 為 1 天，成本 $50+90=140$。
• 剩 4 天：
• 產品 2 分 2 天、產品 3 分 2 天：$50+60=110$。
• 產品 2 分 3 天、產品 3 分 1 天：$30+90=120$。

故 $F_2(4)=110$。

• 剩 5 天：
• 產品 2 分 2 天、產品 3 分 3 天：$50+50=100$。
• 產品 2 分 3 天、產品 3 分 2 天：$30+60=90$。
• 產品 2 分 4 天、產品 3 分 1 天：$20+90=110$。

故 $F_2(5)=90$。

• 剩 6 天：
• 產品 2 分 3 天、產品 3 分 3 天：$30+50=80$。
• 產品 2 分 4 天、產品 3 分 2 天：$20+60=80$。

故 $F_2(6)=80$。

第 1 階段：產品 1

總共有 7 天，產品 1 可分配 1 至 4 天：

核心觀念

本題是排隊理論的 $M/M/1$ 與 $M/M/2$ 系統。訂單到達間隔為指數分配，且相互獨立，因此到達過程為卜瓦松過程；每筆訂單的生產時間亦為獨立指數分配。

令：

• 訂單到達率 $\lambda=1/2.5=0.4$ 件／天。
• 單台機台服務率 $\mu=6/5=1.2$ 件／天。
• $W$：訂單從到達至完成生產的回應時間。
• $W_q$：訂單從到達至開始生產的等候時間。

注意回應時間包含等候與生產：$W=W_q+S$。

解題方法

（一）單機系統中，回應時間在 2 天內的比例

單台機台的利用率為

$$\rho=\frac{\lambda}{\mu}=\frac{0.4}{1.2}=\frac13<1$$

因此 $M/M/1$ 系統穩定。其回應時間分配為指數分配，參數為 $\mu-\lambda$，所以

$$P(W\le t)=1-e^{-(\mu-\lambda)t}$$

代入 $t=2$：

$$P(W\le2)=1-e^{-(1.2-0.4)(2)} =1-e^{-1.6} \approx 0.7981$$

故約 79.81% 的客戶能在 2 天內取得產品。

（二）單機系統中，1 天內開始生產的比例

此小題問的是等候時間 $W_q$，不包含生產時間。$M/M/1$ 中，訂單必須等候的機率為系統忙碌機率 $\rho$；在等待的條件下，等候時間的尾端機率為 $e^{-(\mu-\lambda)t}$。因此

$$P(W_q>t)=\rho e^{-(\mu-\lambda)t}$$

所以 1 天內開始生產的機率為

$$P(W_q\le1)=1-\rho e^{-(\mu-\lambda)} =1-\frac13e^{-0.8} \approx 0.8504$$

故約 85.04% 的訂單能在下單後 1 天內開始生產。

（三）增加一台機台後，訂單需要等候的比例

現在有兩台相同機台，形成 $M/M/2$ 系統。兩台機台的總服務能力為 $2\mu=2.4$ 件／天，且 $\lambda<2\mu$，系統穩定。

令 $a=\lambda/\mu=1/3$，則 Erlang C 等候機率為