111 年 國立中央大學工業管理研究所碩士班《作業研究》

題目資訊缺漏說明

本題題幹於引言後中斷（缺少具體的目標函數與限制式數學模型，如 Maximize/Minimize Z = ... subject to ...），題目資訊確實不足。為提供符合研究所入學考試規格之「參考書等級詳解」，以下以工管所入學考試中要求「比較並使用單形法（Simplex Method）或對偶單形法（Dual-Simplex Method）」之最具代表性典型經典題進行完整演算示範：

$$\begin{aligned} \min \quad & Z = 2x_1 + 3x_2 \\ \text{s.t.} \quad & x_1 + x_2 \ge 4 \\ & x_1 + 2x_2 \ge 6 \\ & x_1, x_2 \ge 0 \end{aligned}$$

---

核心觀念

1. 標準線性規劃型態（Standard LP Form）：
   單形法在建立初始表格前，必須將不等式化為等式。對於「$\ge$」限制式，傳統原始單形法（Primal Simplex Method）須減去剩餘變數（Surplus Variable）並額外引進人工變數（Artificial Variable），搭配大 M 法（Big-M Method）或兩階段法（Two-Phase Method）求解。
2. 對偶單形法（Dual-Simplex Method）之優勢與條件：
   • 對偶可行性（Dual Feasibility / Optimality Condition）：初始目標列各變數之檢定數（Reduced Cost, 即 $c_j - z_j$ 或 $z_j - c_j$）已滿足最佳化條件。
   • 原始不可行性（Primal Infeasibility）：右端常數項（Right-Hand Side, RHS）存在負值（$b_i < 0$）。
   • 若將原最小化問題化為最大化問題：$\max W = -Z = -2x_1 - 3x_2$，並將「$\ge$」兩邊同乘 $-1$ 轉換為「$\le$」，加入鬆弛變數後即可直接構成具備對偶可行性的初始基底，完全不需引進人工變數，計算步驟大幅簡化。
3. 對偶單形法旋轉規則（Pivoting Rules）：
   • 出基變數（Leaving Variable）：選擇 RHS 中最負者所對應之基底變數出基（即 $\min_i \{b_i \mid b_i < 0\}$）。
   • 進基變數（Entering Variable）：針對出基列中係數為負（$a_{ij} < 0$）之非基底變數，進行最小比值檢定： $$\min_{j} \left\{ \frac{z_j - c_j}{a_{rj}} \ \middle|\ a_{rj} < 0 \right\} \quad \text{或} \quad \min_{j} \left\{ \left| \frac{\text{Row } 0 \text{ 係數}}{a_{rj}} \right| \ \middle|\ a_{rj} < 0 \right\}$$
   • 樞紐消去（Pivot Operation）：利用高斯—若爾當消去法（Gauss-Jordan Elimination）將樞紐元轉為 $1$，同行其餘元素化為 $0$。

---

解題方法

本題採用**對偶單形法（Dual-Simplex Method）**求解。相較於原始單形法需處理人工變數的繁複計算，對偶單形法能以極少迭代步數直接求得最佳解。

步驟一：模型轉換為對偶單形法標準型

將目標函數改為極大化形式：

$$\max \quad W = -2x_1 - 3x_2$$

將兩道「$\ge$」限制式同乘 $-1$ 變更不等號方向，並分別加入鬆弛變數 $s_1, s_2 \ge 0$：

$$\begin{aligned} -x_1 - x_2 + s_1 &= -4 \\ -x_1 - 2x_2 + s_2 &= -6 \end{aligned}$$

列出目標函數列（以 $W$ 為基底之零列方程）：

$$W + 2x_1 + 3x_2 = 0$$

步驟二：建立初始單形表（Initial Tableau）

基底變數選取鬆弛變數 $\{s_1, s_2\}$，檢視列 0 係數（非負，滿足極大化問題之最佳性條件，即對偶可行）：

基底 (Basis)	$W$	$x_1$	$x_2$	$s_1$	$s_2$	RHS
$W$ (Row 0)	$1$	$2$	$3$	$0$	$0$	$0$
$s_1$ (Row 1)	$0$	$-1$	$-1$	$1$	$0$	$-4$
$s_2$ (Row 2)	$0$	$-1$	-2	$0$	$1$	$-6$

• 出基變數判定：$\min\{-4, -6\} = -6$，由 $s_2$ 出基（Row 2 為樞紐列）。
• 進基變數判定：檢驗 Row 2 中係數為負之變數（$x_1, x_2$）：
  • 對於 $x_1$：$\left| \frac{2}{-1} \right| = 2$
  • 對於 $x_2$：$\left| \frac{3}{-2} \right| = 1.5$
  • 最小比值為 $1.5$，由 $x_2$ 進基。
• 樞紐元（Pivot Element）：Row 2 的 $x_2$ 係數，即 $-2$。

核心觀念

本題評量線性規劃（Linear Programming, LP）之**單形法（Simplex Method）求解流程與無界解（Unbounded Solution）**之判定準則：

1. 標準型態轉換（Standard Form）：
   • 限制式為「$\le$」時，加入未知的寬限變數（Slack Variable, $s_i \ge 0$）。
   • 限制式為「$\ge$」時，減去剩餘變數（Excess Variable, $e_i \ge 0$），並引入人工變數（Artificial Variable, $A_i \ge 0$）以構成初始可行基底。
2. 兩階段單形法（Two-Phase Simplex Method）：
   • 第一階段（Phase I）：最小化人工變數總和（$\min W = \sum A_i$ 或 $\max -W = -\sum A_i$）。若人工變數順利歸零並移出基底，即獲得原問題的一個初始基可行解（Initial Basic Feasible Solution, BFS）。
   • 第二階段（Phase II）：自第一階段求得之 BFS 出發，放回原目標函數進行單形法疊代，直至滿足最佳化準則或判定為無界解。
3. 無界解判定準則（Unboundedness Criterion）：
   • 在最大化問題的單形表（Row 0 為 $z - \sum c_j x_j$ 形式）中，若存在某非基變數 $x_k$ 的檢定數（Reduced Cost）小於 0（即目標列係數為負，表示增加 $x_k$ 可使目標函數值 $z$ 繼續增大）；
   • 且該變數所在行向量之所有限制式係數皆小於或等於零（$a_{ik} \le 0, \, \forall i$），導致比值測試（Minimum Ratio Test）無法選出離開變數（Leaving Variable）；
   • 則該非基變數可無限制增大而不違反任何限制式，使目標函數值趨向 $+\infty$，判定原問題具有無界解，不存在有限最佳解。

---

解題方法

原線性規劃模型為：

$$\begin{aligned} \text{maximize} \quad & z = x_1 + 2x_2 - 3x_3 - 3x_4 \\ \text{subject to} \quad & 2x_1 - 11x_2 + 12x_3 - 10x_4 \le 50 \\ & 2x_1 - 15x_2 + 4x_3 - 5x_4 \ge 10 \\ & x_1, x_2, x_3, x_4 \ge 0 \end{aligned}$$

因為第二個限制式為 $\ge 10$，無法直接以寬限變數作為初始可行基底，故採用結構最清晰、不易混淆符號的**兩階段單形法（Two-Phase Simplex Method）**求解。

步驟一：引進變數並建立標準型

• 對限制式 (1) 加入寬限變數 $s_1 \ge 0$。
• 對限制式 (2) 減去剩餘變數 $e_2 \ge 0$，並加入人工變數 $A_2 \ge 0$。

等式限制條件為：

$$\begin{aligned} 2x_1 - 11x_2 + 12x_3 - 10x_4 + s_1 &= 50 \\ 2x_1 - 15x_2 + 4x_3 - 5x_4 - e_2 + A_2 &= 10 \end{aligned}$$

---

步驟二：第一階段（Phase I）求解初始可行解

第一階段目標為驅除人工變數 $A_2$：

$$\text{minimize} \quad W = A_2 \iff \text{maximize} \quad -W = -A_2$$

將 $A_2 = 10 - 2x_1 + 15x_2 - 4x_3 + 5x_4 + e_2$ 代入目標式，寫成標準單形表目標列（Row 0）：

$$-W + A_2 = 0 \implies -W - 2x_1 + 15x_2 - 4x_3 + 5x_4 + e_2 = -10$$

建立第一階段初始單形表：

基底變數	$-W$	$x_1$	$x_2$	$x_3$	$x_4$	$s_1$	$e_2$	$A_2$	RHS	比值測試（Ratio Test）
$-W$	1	$-2$	15	$-4$	5	0	1	0	$-10$	—
$s_1$	0	2	$-11$	12	$-10$	1	0	0	50	$50 / 2 = 25$
$A_2$	0	[2]	$-15$	4	$-5$	0	$-1$	1	10	$10 / 2 = 5$（最小比值）

• 樞紐選擇：選取 $x_1$ 行為進基變數（係數 $-2 < 0$）。經比值測試，最小正比值為 $10/2 = 5$，故 $A_2$ 離基，樞紐元素為 Row 2 的 $2$。
• 列運算：
  1. $\text{New Row 2} = \text{Row 2} / 2$
  2. $\text{New Row 1} = \text{Row 1} - 2 \times \text{New Row 2}$
  3. $\text{New Row 0} = \text{Row 0} + 2 \times \text{New Row 2}$

運算後單形表：

基底變數	$-W$	$x_1$	$x_2$	$x_3$	$x_4$	$s_1$	$e_2$	$A_2$	RHS
$-W$	1	0	0	0	0	0	0	1	0
$s_1$	0	0	4	8	$-5$	1	1	$-1$	40
$x_1$	0	1	$-7.5$	2	$-2.5$	0	$-0.5$	0.5	5

此時 $W = 0$，人工變數 $A_2$ 已成功離開基底，獲得原問題之初始 BFS：

$$(x_1, x_2, x_3, x_4, s_1, e_2) = (5, 0, 0, 0, 40, 0)$$

---

步驟三：第二階段（Phase II）原問題求解

移除人工變數 $A_2$ 欄位，還原原問題目標函數：

核心觀念

本題考查旅行推銷員問題（Traveling Salesman Problem, TSP）的整數線性規劃（ILP）經典模型——DFJ 模式（Dantzig-Fulkerson-Johnson Formulation）中的子迴圈消除限制式（Subtour Elimination Constraints, SEC）。

1. 基本定義：
   • 給定城市集合 $V = \{1, 2, \dots, S\}$。
   • 前兩組限制式為出入度限制式（亦即指派問題 Assignment Problem 的限制式）：
     • 每一城市出度為 $1$：$\sum_{j \ne i} x_{ij} = 1, \quad \forall i$
     • 每一城市入度為 $1$：$\sum_{i \ne j} x_{ij} = 1, \quad \forall j$
   • 第三組限制式即為 DFJ 子迴圈消除限制式：
     對於任意非空真子集合 $\mathbf{K} \subset \{1, 2, \dots, S\}$ 且 $2 \le |\mathbf{K}| \le S - 1$： $$\sum_{i \in \mathbf{K}} \sum_{\substack{j \in \mathbf{K} \\ j \ne i}} x_{ij} \le |\mathbf{K}| - 1$$
2. 圖論性質：
   在包含 $|\mathbf{K}|$ 個節點的子圖中，若節點間選擇的有向邊數達到 $|\mathbf{K}|$ 條，且每個節點的出入度皆為 $1$，則該子圖內部必然形成一個封閉的獨立迴圈（Subtour）。若要破壞此獨立迴圈，子圖內部的邊數上限必為 $|\mathbf{K}| - 1$。

---

解題方法

2.a 說明第三限制式的含意（What is this constraint ensuring?）

此限制式稱為子迴圈消除限制式（Subtour Elimination Constraint, SEC），其主要含意在於：限制推銷員在任何城市的真子集合內部，所走過的路徑邊數不得形成封閉的區域小迴圈（Subtour），確保最終解只包含一個走遍所有 $S$ 個城市的單一完整大巡迴（Single Grand Tour / Hamiltonian Cycle）。

• 數學意義推導：
  考慮城市集合 $\{1, \dots, S\}$ 的任一真子集合 $\mathbf{K}$（其中 $2 \le |\mathbf{K}| \le S-1$）：
  • 若在子集合 $\mathbf{K}$ 內部的城市之間形成了自成一格的封閉迴圈，則這些城市彼此相連的邊數總和必定恰好等於節點數，即： $$\sum_{i \in \mathbf{K}} \sum_{\substack{j \in \mathbf{K} \\ j \ne i}} x_{ij} = |\mathbf{K}|$$
  • 第三限制式強制規定該內部邊數總和最多只能為 $|\mathbf{K}| - 1$： $$\sum_{i \in \mathbf{K}} \sum_{\substack{j \in \mathbf{K} \\ j \ne i}} x_{ij} \le |\mathbf{K}| - 1$$
  • 此限制迫使推銷員在拜訪子集合 $\mathbf{K}$ 內的城市時，至少必須有一條邊是由 $\mathbf{K}$ 外部連入，或由 $\mathbf{K}$ 內部連出到外部城市，從而阻斷任何在真子集 $\mathbf{K}$ 內部自行封閉成環的可能性。

---

2.b 為何需要第三限制式？（Why is this constraint needed?）

需要加入第三限制式的核心原因為：前兩組限制式不足以保證解為單一連通的 TSP 巡迴路徑，容易產生「多個不相連子迴圈」的不合理可行解。

核心觀念

本題評量**等候理論（Queueing Theory）**中具有容量限制的單一服務員模型——$M/M/1/k$ 系統：

1. 連續時間馬可夫鏈（CTMC）與生滅過程（Birth-Death Process）：系統狀態以系統內顧客數 $n$（$n = 0, 1, \dots, k$）表示。到達率與服務率分別為：
   $\lambda_n = \begin{cases} \lambda, & 0 \le n < k \\ 0, & n \ge k \end{cases}$
   $\mu_n = \mu, \quad 1 \le n \le k$
2. 細緻平衡方程式（Detailed Balance Equations）：
   $\lambda p_{n-1} = \mu p_n \implies p_n = u p_{n-1} = u^n p_0, \quad \text{其中 } u = \frac{\lambda}{\mu}$
3. 全機率公理（Normalization Condition）：
   $\sum_{n=0}^k p_n = 1$
4. 有限等比級數求和公式與微分技巧：
   • 級數和：$\sum_{n=0}^k u^n = \frac{1 - u^{k+1}}{1 - u}$（當 $u \neq 1$）
   • 期望值 $L = \sum_{n=0}^k n p_n = p_0 \sum_{n=1}^k n u^n$：可利用微積分技巧 $\sum_{n=1}^k n u^n = u \frac{d}{du}\left(\sum_{n=0}^k u^n\right)$ 快速展開。

---

解題方法與詳細推導

(a) 求穩態機率分佈 $p_n$ ($n = 0, 1, \dots, k$)

1. 建立狀態轉移平衡式：
   根據生滅過程的相鄰狀態平衡條件：
   $\lambda p_{n-1} = \mu p_n \implies p_n = \left(\frac{\lambda}{\mu}\right) p_{n-1} = u p_{n-1}, \quad \forall n = 1, 2, \dots, k$
   遞迴展開可得：
   $p_n = u^n p_0, \quad n = 0, 1, \dots, k$

2. 利用全機率公理求 $p_0$：
   所有狀態機率總和為 1：
   $\sum_{n=0}^k p_n = \sum_{n=0}^k u^n p_0 = p_0 \sum_{n=0}^k u^n = 1$
   由於題目給定 $\frac{\lambda}{\mu} < 1$（即 $u \neq 1$），套用有限等比級數求和公式：
   $\sum_{n=0}^k u^n = \frac{1 - u^{k+1}}{1 - u}$
   因此：
   $p_0 \left(\frac{1 - u^{k+1}}{1 - u}\right) = 1 \implies p_0 = \frac{1 - u}{1 - u^{k+1}}$

3. 求得穩態機率 $p_n$：
   $p_n = u^n p_0 = \frac{(1 - u)u^n}{1 - u^{k+1}}, \quad n = 0, 1, \dots, k$

---

(b) 證明系統內平均顧客數 $L$ 為指定形式

系統內平均顧客數 $L$ 定義為：
$L = E[N] = \sum_{n=0}^k n p_n = p_0 \sum_{n=1}^k n u^n$

步驟一：計算關鍵求和項 $S = \sum_{n=1}^k n u^n$

核心觀念

本題評量離散時間馬可夫鏈（Discrete-Time Markov Chain, DTMC）之核心分析能力，涵蓋兩大主題：

1. 有限期多步轉移機率分佈（Multi-step Transition Probability Distribution）：
   若系統在時刻 $n$ 的狀態機率分佈為列向量 $\pi^{(n)}$，轉移機率矩陣為 $P$，則由 Chapman-Kolmogorov 方程可知，第 $n+k$ 期的狀態機率分佈為：
   $\pi^{(n+k)} = \pi^{(n)} P^k$
   本題給定第 1 週（$n=1$）選擇品牌 $A$，求第 4 週（$n=4$）的機率分佈，即為經過 $3$ 步轉移後的分佈 $\pi^{(4)} = \pi^{(1)} P^3$（亦即 $P^3$ 的第一列）。

2. 極限分佈／穩態分佈（Limiting Distribution / Stationary Distribution）：
   此馬可夫鏈具有有限狀態空間 $\{A, B, C\}$，且轉移矩陣 $P$ 的所有元素皆大於 0（$P > 0$，為嚴格正矩陣），因此此鏈為不可約（Irreducible）、**非週期（Aperiodic）且常態（Recurrent）**之正復現遍歷鏈（Ergodic Chain）。
   其極限分佈 $\pi = [\pi_A, \pi_B, \pi_C]$ 存在、唯一，且與初始狀態無關，滿足穩態方程式與全機率公理：
   $\pi P = \pi \quad \text{且} \quad \sum_{i} \pi_i = 1, \quad \pi_i \ge 0$

---

解題方法

(a) 第 4 週的品牌機率分佈

• 定義初始分佈：
  在第 1 週使用品牌 $A$，初始機率向量為：
  $\pi^{(1)} = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix}$
  經過 $4 - 1 = 3$ 次轉移到達第 4 週，其狀態分佈為：
  $\pi^{(4)} = \pi^{(1)} P^3$
  其值剛好等於矩陣 $P^3$ 的第一列向量。為減少計算量，無須計算完整的 $P^3$ 矩陣，僅需遞推計算第 1 列的轉移向量：

1. 計算第 2 週的分佈 $\pi^{(2)} = \pi^{(1)} P$：
   $\pi^{(2)} = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0.1 & 0.2 & 0.7 \\ 0.1 & 0.5 & 0.4 \\ 0.3 & 0.2 & 0.5 \end{bmatrix} = \begin{bmatrix} 0.1 & 0.2 & 0.7 \end{bmatrix}$

2. 計算第 3 週的分佈 $\pi^{(3)} = \pi^{(2)} P$：
   $\pi_A^{(3)} = 0.1(0.1) + 0.2(0.1) + 0.7(0.3) = 0.01 + 0.02 + 0.21 = 0.24$
   $\pi_B^{(3)} = 0.1(0.2) + 0.2(0.5) + 0.7(0.2) = 0.02 + 0.10 + 0.14 = 0.26$
   $\pi_C^{(3)} = 0.1(0.7) + 0.2(0.4) + 0.7(0.5) = 0.07 + 0.08 + 0.35 = 0.50$
   因此：
   $\pi^{(3)} = \begin{bmatrix} 0.24 & 0.26 & 0.50 \end{bmatrix}$

3. 計算第 4 週的分佈 $\pi^{(4)} = \pi^{(3)} P$：
   $\pi_A^{(4)} = 0.24(0.1) + 0.26(0.1) + 0.50(0.3) = 0.024 + 0.026 + 0.150 = 0.200$
   $\pi_B^{(4)} = 0.24(0.2) + 0.26(0.5) + 0.50(0.2) = 0.048 + 0.130 + 0.100 = 0.278$
   $\pi_C^{(4)} = 0.24(0.7) + 0.26(0.4) + 0.50(0.5) = 0.168 + 0.104 + 0.250 = 0.522$

經檢驗：$0.200 + 0.278 + 0.522 = 1.000$。

---

(b) 品牌的極限分佈

設極限分佈為列向量 $\pi = \begin{bmatrix} \pi_A & \pi_B & \pi_C \end{bmatrix}$，滿足平衡方程式 $\pi P = \pi$：

核心觀念

本題屬於隨機過程（Stochastic Processes）中的離散時間馬可夫鏈（Discrete-Time Markov Chain, DTMC）與極限定理（Limiting Distribution / Stationary Distribution）。

涉及的重要定義與定理如下：

1. 狀態空間定義：利用同餘（Modulo Arithmetic）將無限增長的累加和 $X_n$ 投影至有限狀態空間。令狀態為 $S_n = X_n \bmod 5$，則狀態空間為： $$S = \{0, 1, 2, 3, 4\}$$ 其中 $S_n = 0$ 代表 $X_n$ 可被 5 整除。
2. 馬可夫性質（Markov Property）：下一期的餘數僅取決於當期的餘數與下一顆骰子的點數，滿足無記憶性。
3. 極限機率存在條件（Ergodicity）：有限狀態的馬可夫鏈若滿足不可約（Irreducible）與非週期性（Aperiodic），則存在唯一的極限分佈（穩態分佈）$\boldsymbol{\pi} = [\pi_0, \pi_1, \pi_2, \pi_3, \pi_4]$，且獨立於初始狀態： $$\lim_{n\to\infty} P(S_n = j) = \pi_j$$
4. 雙隨機矩陣（Doubly Stochastic Matrix）性質：轉移機率矩陣 $P$ 若各行（Row）總和為 1 且各列（Column）總和亦為 1，則其穩態分佈必為離散均勻分佈（Discrete Uniform Distribution）： $$\pi_j = \frac{1}{|S|}, \quad \forall j \in S$$

---

解題方法

步驟一：建立馬可夫鏈模型

設第 $i$ 次投擲骰子的結果為 $Y_i$。依題意，$Y_i$ 為獨立且同分佈（i.i.d.）的隨機變數，其機率質量函數為：

$$P(Y_i = k) = \frac{1}{4}, \quad k \in \{1, 2, 3, 4\}$$

累積和為 $X_n = \sum_{i=1}^n Y_i$。定義隨機過程 $\{S_n, n \ge 1\}$ 為累積和除以 5 的餘數：

$$S_n = X_n \bmod 5$$

其狀態轉移關係式為：

$$S_n = (S_{n-1} + Y_n) \bmod 5$$

因為 $Y_n$ 只能取值 $1, 2, 3, 4$（無法取 0），這表示在任一狀態 $i \in \{0, 1, 2, 3, 4\}$ 下：

• 轉移到自身的機率為 $P(S_n = i \mid S_{n-1} = i) = 0$
• 轉移到其他任一狀態 $j \neq i$ 的機率均為 $\frac{1}{4}$

步驟二：寫出單步轉移機率矩陣 $P$

狀態依序為 $\{0, 1, 2, 3, 4\}$，其一步轉移機率矩陣 $P$ 為：

$$P = \begin{pmatrix} 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 \end{pmatrix}$$