113 年 國立臺灣大學工業工程學研究所碩士班產業與服務系統工程組《作業研究》

這是一道標準的單體法 (Simplex Method) 問題，考驗考生對線性規劃的初始解、迭代過程、以及判斷最佳解的能力。

首先，我們將線性規劃問題轉換成標準形式，並引入鬆弛變數 (slack variables)：
Maximize $z = 4x_1 + 3x_2 + 6x_3$
subject to
$3x_1 + x_2 + 3x_3 + x_4 = 30$
$2x_1 + 2x_2 + 3x_3 + x_5 = 40$
$x_1, x_2, x_3, x_4, x_5 \geq 0$

並將目標函數寫成 $z - 4x_1 - 3x_2 - 6x_3 = 0$。

初始單體表（Initial Simplex Tableau）：

Basis	$z$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	RHS
$z$	1	-4	-3	-6	0	0	0
$x_4$	0	3	1	3	1	0	30
$x_5$	0	2	2	3	0	1	40

(a) 若 $x_2$ 和 $x_3$ 是基本變數 (basic variables)，則非基本變數 (nonbasic variables) $x_1$ 必須為 0。
此時，我們將 $x_1 = 0$ 代入限制式：
$0 + x_2 + 3x_3 = 30$
$0 + 2x_2 + 3x_3 = 40$

解這個聯立方程式：
由第一個式子 $x_2 = 30 - 3x_3$ 代入第二個式子：
$2(30 - 3x_3) + 3x_3 = 40$
$60 - 6x_3 + 3x_3 = 40$
$60 - 3x_3 = 40$
$3x_3 = 20 \implies x_3 = 20/3$

將 $x_3 = 20/3$ 代回 $x_2 = 30 - 3x_3$：
$x_2 = 30 - 3(20/3) = 30 - 20 = 10$

所以，若 $x_2$ 和 $x_3$ 是基本變數，則 $x_2 = 10$ 且 $x_3 = 20/3$。
【答案】$x_2 = 10, x_3 = 20/3$

(b) 題目要求我們選擇 $x_2$ 作為進入變數 (entering variable)，並判斷其最大可行增量。
從初始單體表中，我們看到 $x_1$ 和 $x_3$ 為非基本變數（即 $x_1=0, x_3=0$）。
若 $x_2$ 進入，則 $x_4$ 或 $x_5$ 必須離開 (leaving variable)。
我們需要計算比率檢定 (ratio test)：
對於 $x_4$：$\frac{30}{1} = 30$
對於 $x_5$：$\frac{40}{2} = 20$

最小的比率是 20，對應到 $x_5$。因此，$x_5$ 是離開變數。
當 $x_2$ 增加時，它受到 $x_5$ 限制，最大可以增加到 $x_2 = 20$。
此時，原始變數 $x_2$ 可以從 0 增加到 20，而不會離開可行區域。
【答案】$x_2$ 最多可以增加到 20。

(c) 當 $x_2$ 從 0 增加到 20 時，我們從初始基本可行解 ($x_1=0, x_2=0, x_3=0, x_4=30, x_5=40$) 變為新的基本可行解。
在這個過程中，$x_2$ 進入，成為基本變數，而 $x_5$ 離開，成為非基本變數（值為 0）。
新的基本變數是 $x_4$ 和 $x_2$。
我們需要計算這些新基本變數的值。
在進行單體法的迭代前，我們需要將 $x_2$ 的行 (pivot row) 轉換成單位向量。
從初始單體表，我們知道 $x_5$ 是離開變數，其對應的限制式為 $2x_1 + 2x_2 + 3x_3 + x_5 = 40$。
當 $x_2$ 進入，我們將此行除以 pivot element 2：
$\frac{1}{2}(2x_1 + 2x_2 + 3x_3 + x_5) = \frac{1}{2}(40)$
$x_1 + x_2 + \frac{3}{2}x_3 + \frac{1}{2}x_5 = 20$
這是新的 $x_2$ 的限制式。

現在，我們需要用新的 $x_2$ 限制式來更新其他變數（包括 $x_4$ 和目標函數 $z$）。
新的 $x_4$ 限制式：
$3x_1 + x_2 + 3x_3 + x_4 = 30$
將 $x_2 = 20 - x_1 - \frac{3}{2}x_3 - \frac{1}{2}x_5$ 代入：
$3x_1 + (20 - x_1 - \frac{3}{2}x_3 - \frac{1}{2}x_5) + 3x_3 + x_4 = 30$
$2x_1 + \frac{3}{2}x_3 + x_4 - \frac{1}{2}x_5 = 10$
所以，新的基本變數 $x_4$ 的值是 10。

新的基本可行解為：$x_1=0, x_3=0, x_5=0$。
$x_2 = 20$ (由 $x_1 + x_2 + \frac{3}{2}x_3 + \frac{1}{2}x_5 = 20$ 得到，因為 $x_1=0, x_3=0, x_5=0$)
$x_4 = 10$ (由 $2x_1 + \frac{3}{2}x_3 + x_4 - \frac{1}{2}x_5 = 10$ 得到，因為 $x_1=0, x_3=0, x_5=0$)

新的基本變數是 $x_4$ 和 $x_2$。
【答案】新的基本變數為 $x_4 = 10, x_2 = 20$。

(d) 我們需要計算目標函數 $z$ 的改進量。
在 (c) 中，我們從初始基本可行解 ($x_1=0, x_2=0, x_3=0$) 變為新的基本可行解 ($x_1=0, x_2=20, x_3=0$)。
初始目標函數值 $z = 4(0) + 3(0) + 6(0) = 0$。
新的目標函數值 $z = 4(0) + 3(20) + 6(0) = 60$。
改進量是 $60 - 0 = 60$。

或者，我們也可以從單體表的更新來計算：
更新 $z$ 的行：
原始 $z$ 行: $z - 4x_1 - 3x_2 - 6x_3 = 0$
新的 $x_2$ 行: $x_1 + x_2 + \frac{3}{2}x_3 + \frac{1}{2}x_5 = 20$
將新的 $x_2$ 行乘以 3 (因為原始 $z$ 行中 $x_2$ 的係數是 -3)：
$3(x_1 + x_2 + \frac{3}{2}x_3 + \frac{1}{2}x_5) = 3(20)$
$3x_1 + 3x_2 + \frac{9}{2}x_3 + \frac{3}{2}x_5 = 60$
從原始 $z$ 行減去這個式子：
$(z - 4x_1 - 3x_2 - 6x_3) - (3x_1 + 3x_2 + \frac{9}{2}x_3 + \frac{3}{2}x_5) = 0 - 60$
$z - 7x_1 - \frac{21}{2}x_3 - \frac{3}{2}x_5 = -60$
$z = 7x_1 + \frac{21}{2}x_3 + \frac{3}{2}x_5 - 60$

當 $x_1=0, x_3=0, x_5=0$ 時，新的 $z$ 值是 -60。
這表示在我們更新完 $x_2$ 行後，目標函數的 RHS 值是 -60。
這代表了新的 $z$ 的基礎解。
然而，題目問的是「改進量」。
在 (c) 中，我們從初始解 ($x_1=0, x_2=0, x_3=0$) 得到的 $z=0$。
到新的解 ($x_1=0, x_2=20, x_3=0$) 得到的 $z=60$。
所以改進量是 60。
【答案】60

(e) 我們需要完成單體法的迭代過程，直到找到最佳解。
我們從 (c) 和 (d) 的結果開始。
新的單體表，其中 $x_2$ 是進入變數，$x_5$ 是離開變數。
初始單體表：

Basis	$z$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	RHS
$z$	1	-4	-3	-6	0	0	0
$x_4$	0	3	1	3	1	0	30

核心觀念

本題考查**隨機動態規劃（Stochastic Dynamic Programming, SDP）**在多階段投資決策中的應用，主要核心概念包括：

1. 貝爾曼最佳化原理（Bellman's Principle of Optimality）：利用逆向歸納法（Backward Induction），由最後一個階段往回推導各階段的最佳決策。
2. 期望值極大化（Expected Value Maximization）：在風險中立（Risk-neutral）的假設下，目標為最大化最終期末資產的數學期望值。
3. 線性規劃之角隅解特性（Linearity and Corner Solutions）：各期期望報酬率固定且大於 0 時，目標函數相對於投資決策變數為嚴格遞增線性函數，最佳決策必為邊界解（全額投資）。

---

解題方法

1. 定義動態規劃要素

• 階段（Stage）$n$：代表第 $n$ 年的開始（$n = 1, 2, 3, 4$）。
• 狀態變數（State Variable）$s_n$：在第 $n$ 年年初時擁有的總資金（$s_n \ge 0$），初始狀態為 $s_1 =$$10,000。
• 決策變數（Decision Variable）$x_n$：在第 $n$ 年年初投入股票市場的金額，決策空間為 $0 \le x_n \le s_n$。未投資的金額為 $(s_n - x_n)$。
• 隨機報酬倍數（Random Return Multiplier）$R_n$：第 $n$ 年投資金額的期末倍數，其機率分配為： $$R_n = \begin{cases} 3, & \text{機率 } 0.4 \\ 1, & \text{機率 } 0.2 \\ 0, & \text{機率 } 0.4 \end{cases}$$ 每投入 $1 的期望期末價值為： $$\mathbb{E}[R_n] = 3 \times 0.4 + 1 \times 0.2 + 0 \times 0.4 = 1.2 + 0.2 + 0 = 1.4$$
• 狀態轉移方程式（State Transition Equation）： $$s_{n+1} = (s_n - x_n) + R_n \cdot x_n$$
• 值函數（Value Function）$f_n(s_n)$：在第 $n$ 年年初持有資金 $s_n$ 的條件下，持續執行最佳投資策略至第 4 年年末所能獲得的最大期望總金額。

2. 建立動態規劃遞迴關係式（DP Recurrence Relation）

邊界條件（第 4 年年末／第 5 年年初）：

$$f_5(s_5) = s_5$$

遞迴關係式（$n = 4, 3, 2, 1$）：

$$f_n(s_n) = \max_{0 \le x_n \le s_n} \mathbb{E} \left[ f_{n+1}\Big((s_n - x_n) + R_n \cdot x_n\Big) \right]$$

---

3. 逆向歸納推導（Backward Induction）

• 階段 4（$n = 4$）： $$f_4(s_4) = \max_{0 \le x_4 \le s_4} \mathbb{E} \left[ f_5(s_4 - x_4 + R_4 x_4) \right]$$ $$= \max_{0 \le x_4 \le s_4} \left[ (s_4 - x_4) + \mathbb{E}[R_4] \cdot x_4 \right]$$ $$= \max_{0 \le x_4 \le s_4} \left[ s_4 - x_4 + 1.4 x_4 \right] = \max_{0 \le x_4 \le s_4} \left[ s_4 + 0.4 x_4 \right]$$ 因為係數 $0.4 > 0$，此目標式為 $x_4$ 的嚴格遞增函數，極大值發生在上限 $x_4^* = s_4$： $$f_4(s_4) = s_4 + 0.4 s_4 = 1.4 s_4$$

這是一道關於隨機過程和機率的題目，特別是關於指數分佈的性質。

核心觀念：

1. 指數分佈的記憶性 (Memoryless Property)：對於任何時間 $t \ge 0$ 和 $s > 0$，若隨機變數 $X \sim \text{Exp}(\lambda)$，則 $P(X > t+s | X > t) = P(X > s)$。這意味著過去的等待時間對未來的剩餘時間沒有影響。
2. 指數分佈的最小值的性質：兩個獨立的指數分佈隨機變數的最小值，其分佈仍然是指數分佈，其速率為兩個速率之和。若 $X \sim \text{Exp}(\lambda_1)$ 且 $Y \sim \text{Exp}(\lambda_2)$ 獨立，則 $\min(X, Y) \sim \text{Exp}(\lambda_1 + \lambda_2)$。

已知：
John 由 clerk 1 服務，服務時間 $T_J \sim \text{Exp}(\mu_1)$。
Mary 由 clerk 2 服務，服務時間 $T_M \sim \text{Exp}(\mu_2)$。
John 開始服務時間：8:00。
Mary 開始服務時間：8:10。

(a) Mary 在 8:10 到達，約翰在 8:00 開始由 clerk 1 服務。約翰的服務時間是 $T_J$。
我們想知道 Mary 看見 John 仍然在接受 clerk 1 服務的機率。這意味著 John 的服務時間 $T_J$ 必須大於 John 在 8:10 時已經服務的時間。
John 從 8:00 開始服務，到 8:10，他已經服務了 10 分鐘。
所以，我們需要計算 $P(T_J > 10 \text{ minutes})$。
由於服務時間是指數分佈，我們需要確定速率 $\mu_1$ 的單位。題目中未明確給出 $\mu_1$ 和 $\mu_2$ 的單位，但通常情況下，速率會與時間單位相關聯（例如，每小時幾位顧客）。假設 $\mu_1$ 和 $\mu_2$ 的單位是 "每分鐘服務人數"。
則 $T_J$ 的單位是分鐘。
$P(T_J > 10) = e^{-\mu_1 \times 10}$。
如果 $\mu_1$ 的單位是 "每小時服務人數"，則 10 分鐘是 $10/60 = 1/6$ 小時。
$P(T_J > 1/6) = e^{-\mu_1 \times (1/6)}$。

假設 $\mu_1$ 的單位是 "每分鐘" (即每分鐘完成服務的平均數)。
那麼，John 服務時間超過 10 分鐘的機率是：
$P(T_J > 10) = e^{-10\mu_1}$。

【答案】$e^{-10\mu_1}$ (假設 $\mu_1$ 的單位是每分鐘)。

核心觀念

本題考查馬可夫鏈的「首次再訪」與「永不再訪」機率。由於題目說明「不計初始狀態」，因此即使初始狀態為 2，也只禁止時間 $t\geq 1$ 再次進入狀態 2。

先指出：題目所列矩陣第 4 列總和為

$$1+0.2+0.3+0.5=2,$$

不符合轉移機率矩陣每列總和必須為 $1$ 的條件。以下採用合理修正：第 4 列第一個元素應為 $0$，即

$$P_{4\cdot}=(0,0.2,0.3,0.5).$$

解題方法

令

$$h_i=P(\text{從目前狀態 }i\text{ 出發，未來永遠不再訪問狀態 }2).$$

由於狀態 1 與狀態 3 都是吸收狀態，且不是狀態 2，因此

$$h_1=h_3=1.$$

由初始狀態 2 出發

雖然一開始位於狀態 2，但不計初始狀態。從狀態 2 出發，下一步：

• 以機率 $0.8$ 留在狀態 2，立即違反條件；
• 以機率 $0.2$ 轉移至狀態 3，之後永遠不會再到狀態 2。

因此

$$h_2=0.8\times 0+0.2\times h_3 =0.2.$$

由初始狀態 4 出發

依修正後的第 4 列：

核心觀念

本題是「無等待空間、兩服務台」的連續時間馬可夫鏈（Continuous-Time Markov Chain, CTMC）。

• 一般櫃檯服務率為 $\mu_1$。
• 冰淇淋櫃檯服務率為 $\mu_2$。
• 冰淇淋客偏好冰淇淋櫃檯；冰淇淋櫃檯忙碌且一般櫃檯空閒時，才改至一般櫃檯。
• 漢堡客只能使用一般櫃檯。
• 沒有排隊，因此每個櫃檯只有「忙碌」或「空閒」兩種狀態。

令長期穩態機率為 $p_{ij}$，其中：

• $i=0,1$ 表示一般櫃檯空閒、忙碌；
• $j=0,1$ 表示冰淇淋櫃檯空閒、忙碌。

因此共有四個狀態：

$(0,0),\quad (1,0),\quad (0,1),\quad (1,1)$

---

解題方法：狀態轉移

各狀態的轉移如下：

$$(0,0)\xrightarrow{\lambda_2}(1,0),\qquad (0,0)\xrightarrow{\lambda_1}(0,1)$$ $$(1,0)\xrightarrow{\lambda_1}(1,1),\qquad (1,0)\xrightarrow{\mu_1}(0,0)$$

當處於 $(0,1)$ 時，冰淇淋櫃檯忙碌、一般櫃檯空閒：

• 漢堡客以速率 $\lambda_2$ 使用一般櫃檯；
• 冰淇淋客也以速率 $\lambda_1$ 改至一般櫃檯。

所以：

$$(0,1)\xrightarrow{\lambda_1+\lambda_2}(1,1),\qquad (0,1)\xrightarrow{\mu_2}(0,0)$$

最後，在 $(1,1)$ 中兩個櫃檯皆忙碌，新客無法進入，只會離開：

$$(1,1)\xrightarrow{\mu_1}(0,1),\qquad (1,1)\xrightarrow{\mu_2}(1,0)$$

---

(a) 必要狀態

四個必要狀態為：

$\boxed{(0,0),(1,0),(0,1),(1,1)}$

分別代表：

狀態	一般櫃檯	冰淇淋櫃檯
$(0,0)$	空閒	空閒
$(1,0)$	忙碌	空閒
$(0,1)$	空閒	忙碌
$(1,1)$	忙碌	忙碌

---

(b) 平衡方程式

對每一個狀態列出「流出率 × 該狀態機率 = 流入率」：

對 $(0,0)$：

$$(\lambda_1+\lambda_2)p_{00} = \mu_1p_{10}+\mu_2p_{01}$$

對 $(1,0)$：

$$(\lambda_1+\mu_1)p_{10} = \lambda_2p_{00}+\mu_2p_{11}$$

對 $(0,1)$：

$$(\lambda_1+\lambda_2+\mu_2)p_{01} = \lambda_1p_{00}+\mu_1p_{11}$$

對 $(1,1)$：

$$(\mu_1+\mu_2)p_{11} = \lambda_1p_{10}+(\lambda_1+\lambda_2)p_{01}$$

再加上正規化條件：

$p_{00}+p_{10}+p_{01}+p_{11}=1$

其中四條平衡方程式中有一條可由其他方程式與正規化條件推出，因此實際求解時使用其中三條搭配正規化條件即可。

---

(c) 店內平均顧客數

狀態 $(0,0)$ 有 $0$ 位顧客，$(1,0)$ 與 $(0,1)$ 各有 $1$ 位，$(1,1)$ 有 $2$ 位。因此：

$$\boxed{ L=p_{10}+p_{01}+2p_{11} }$$

這裡的 $L$ 是長期平均店內顧客數。

---

(d) 顧客平均停留時間

由於沒有排隊，進入店內的顧客會立即接受服務。必須先計算實際成功進入店內的有效到達率。