111 專技高考高等考試 工業工程技師 作業研究 考古題詳解

核心觀念

本題旨在評量線性規劃（Linear Programming, LP）中處理「大於等於（$\geq$）」限制式時的標準求解技巧——大 $M$ 法（Big-$M$ Method），以及對單形法終表特殊狀態的判讀能力。

1. 標準型轉換與變數引入：

• 「$\leq$」型限制式：加入**鬆弛變數（Slack Variable, $s_i \geq 0$）**以構成初始基底變數。
• 「$\geq$」型限制式：減去**剩餘變數（Surplus Variable, $e_i \geq 0$）後，因剩餘變數係數為 $-1$，無法直接作為初始基底變數，必須再加入人工變數（Artificial Variable, $R_i \geq 0$）**提供初始單位基底向量。

2. 大 $M$ 懲罰機制：

• 在極大化問題中，目標函數須對人工變數給予極大的負懲罰項（$-M R_i$，其中 $M$ 為任意大的正數），迫使人工變數在單形法迭代中離開基底或變為 $0$。

3. 無可行解（Infeasible Solution）判定準則：

• 當單形表已滿足最佳性準則（極大化問題的第 $0$ 列所有非基底變數檢驗數皆 $\geq 0$），但基底中仍有人工變數存在且其值大於零（$R_i > 0$），代表原始限制式彼此矛盾，原問題無可行解。

---

解題方法

步驟一：轉換為標準型（Standard Form）

原始問題為： 極大化

$$Z = 4x_1 + 5x_2 + 3x_3$$

受限於

$$x_1 + x_2 + 2x_3 \geq 10$$ $$15x_1 + 6x_2 - 5x_3 \leq 25$$ $$x_1 + 3x_2 + 5x_3 \leq 15$$ $$x_1, x_2, x_3 \geq 0$$

依序引入剩餘變數 $e_1$、人工變數 $R_1$ 以及鬆弛變數 $s_2, s_3$：

1. 第一式（$\geq 10$）：$x_1 + x_2 + 2x_3 - e_1 + R_1 = 10$
2. 第二式（$\leq 25$）：$15x_1 + 6x_2 - 5x_3 + s_2 = 25$
3. 第三式（$\leq 15$）：$x_1 + 3x_2 + 5x_3 + s_3 = 15$ 所有變數非負：$x_1, x_2, x_3, e_1, R_1, s_2, s_3 \geq 0$。

目標函數加入人工變數懲罰項後為：

$$\text{Max } Z = 4x_1 + 5x_2 + 3x_3 - M R_1$$

移項整理得第 $0$ 列方程式（Row 0）：

$$Z - 4x_1 - 5x_2 - 3x_3 + M R_1 = 0$$

---

步驟二：建立初始單形表與第 $0$ 列修正

初始基底變數（Basic Variables, BV）取為 $\{R_1, s_2, s_3\}$。 由於人工變數 $R_1$ 為基底變數，其在 Row 0 的係數必須透過初等列運算化為 $0$： 由第一式可知 $R_1 = 10 - x_1 - x_2 - 2x_3 + e_1$，將其代入 Row 0：

$$\text{Row 0} \leftarrow \text{Row 0} - M \times (\text{Row 1})$$

計算得：

$$Z + (-M - 4)x_1 + (-M - 5)x_2 + (-2M - 3)x_3 + M e_1 = -10M$$

初始單形表（Iteration 0）：

基本變數	$Z$	$x_1$	$x_2$	$x_3$	$e_1$	$R_1$	$s_2$	$s_3$	常數項（RHS）	比值檢定（Ratio）
$Z$	$1$	$-M-4$	$-M-5$	$-2M-3$	$M$	$0$	$0$	$0$	$-10M$	—
$R_1$	$0$	$1$	$1$	$2$	$-1$	$1$	$0$	$0$	$10$	$10 / 2 = 5$
$s_2$	$0$	$15$	$6$	$-5$	$0$	$0$	$1$	$0$	$25$	係數 $\leq 0$（不適用）
$s_3$	$0$	$1$	$3$	$5$	$0$	$0$	$0$	$1$	$15$	$15 / 5 = 3$（最小）

• 入基變數：Row 0 中負得最多者（$M$ 為極大正數），$-2M - 3 < -M - 5 < -M - 4$，選取 $x_3$ 入基。
• 出基變數：由最小比值檢定 $\min(5, 3) = 3$，選取 $s_3$ 出基。樞紐元素（Pivot）為第 3 列之 $5$。

---

步驟三：第一次迭代（Iteration 1）

對樞紐列與其餘各列實施高斯消去法：

1. $\text{新 Row 3} = \text{Row 3} / 5$
2. $\text{新 Row 1} = \text{Row 1} - 2 \times \text{新 Row 3}$
3. $\text{新 Row 2} = \text{Row 2} + 5 \times \text{新 Row 3}$
4. $\text{新 Row 0} = \text{Row 0} + (2M + 3) \times \text{新 Row 3}$

第一次迭代單形表（Iteration 1）：

基本變數	$Z$	$x_1$	$x_2$	$x_3$	$e_1$	$R_1$	$s_2$	$s_3$	常數項（RHS）	比值檢定（Ratio）
$Z$	$1$	$-\frac{3}{5}M - \frac{17}{5}$	$\frac{1}{5}M - \frac{16}{5}$	$0$	$M$	$0$	$0$	$\frac{2}{5}M + \frac{3}{5}$	$-4M + 9$	—

核心觀念

本題考查動態規劃（Dynamic Programming, DP）在離散型資源分配問題（Resource Allocation Problem）之應用。其核心理論基於貝爾曼最適性原理（Bellman's Principle of Optimality），將多階段決策過程分解為一系列單階段問題逐步求解。

本題之整數規劃數學模型如下：

• 目標函數：極大化招生總人數 $\max Z = \sum_{i=1}^{3} p_i(x_i)$
• 限制條件：

1. 教師總數限制：$\sum_{i=1}^{3} x_i = 4$
2. 每區至少指派一人：$x_i \ge 1, \quad \forall i \in \{1, 2, 3\}$
3. 整數限制：$x_i \in \mathbb{Z}^+$

其中 $x_i$ 代表指派至地區 $i$ 的教師人數，$p_i(x_i)$ 代表指派 $x_i$ 位教師至地區 $i$ 所招收之新生人數。

---

解題方法

本題要求使用動態規劃求解。採逆向動態規劃（Backward Dynamic Programming），將 3 個地區視為 3 個決策階段，依序由後向前推導。

一、動態規劃要素定義

1. 階段（Stage $n$）：$n = 1, 2, 3$，分別對應地區 1、地區 2、地區 3。
2. 狀態變數（State $s_n$）：進入階段 $n$ 時，尚可用於分配至地區 $n$ 至地區 3 的教師總人數。
3. 決策變數（Decision $x_n$）：分配至地區 $n$ 的教師人數。
4. 立即效益（Return $p_n(x_n)$）：地區 $n$ 分配 $x_n$ 名教師時招收之新生人數。
5. 遞迴關係式（Recurrence Relation）： $f_n^*(s_n) = \max_{x_n} \left\{ p_n(x_n) + f_{n+1}^*(s_n - x_n) \right\}, \quad n = 1, 2$ 邊界條件為最後階段： $f_3^*(s_3) = p_3(s_3)$
6. 決策變數可行範圍： 因每個地區至少分配 1 位教師，後續階段亦須保留至少足夠之教師數：

• 階段 1：後續尚有 2 個地區，故 $1 \le x_1 \le s_1 - 2$
• 階段 2：後續尚有 1 個地區，故 $1 \le x_2 \le s_2 - 1$
• 階段 3：所有剩餘教師皆須分配至地區 3，故 $x_3 = s_3$

---

二、各階段反向計算推導

【階段 3：地區 3】

因總人數為 4 人，且地區 1 與地區 2 各至少需 1 人，故到達地區 3 時，可用人數 $s_3$ 僅可能為 $4 - 1 - 1 = 2$ 或 $4 - 2 - 1 = 1$。 剩餘人數必須全數指派至地區 3，即 $x_3 = s_3$。

狀態 $s_3$	決策 $x_3$	效益 $p_3(x_3)$	最優值 $f_3^*(s_3)$	最優決策 $x_3^*$
1	1	40	40	1
2	2	50	50	2

---

【階段 2：地區 2】

地區 1 至少分配 1 人、最多 2 人（因地區 2、3 各至少需 1 人），因此進入階段 2 時的可用人數 $s_2 \in \{2, 3\}$。

• 當 $s_2 = 2$ 時：地區 3 至少需 1 人，故 $x_2$ 只能取 1。
• 當 $s_2 = 3$ 時：地區 3 至少需 1 人，故 $x_2 \in \{1, 2\}$。

遞迴式計算：$f_2(s_2, x_2) = p_2(x_2) + f_3^*(s_2 - x_2)$

狀態 $s_2$	$x_2 = 1$	$x_2 = 2$	最優值 $f_2^*(s_2)$	最優決策 $x_2^*$

核心觀念

本題屬於作業研究（Operations Research）中的**混合整數線性規劃（Mixed Integer Linear Programming, MILP）**模式建構題，主要測驗以下四大核心觀念：

1. 固定成本問題（Fixed-Charge Problem）：產線開工需先支付「設置成本（固定成本）」，每生產一件產品需支付「單位生產成本（變動成本）」。需引進 0-1 二元變數（Binary Variable）與連續／整數生產量變數相互連動。
2. 產能與開工連動限制（Capacity Linking Constraint）：利用緊緻上界（Tight Upper Bound）建立關係式 $x_i \le C_i y_i$，當產線未開工（$y_i = 0$）時，產量強制為 0；開工（$y_i = 1$）時，產量不超過該產線上限 $C_i$。
3. 互斥與條件相依之邏輯限制（Logical Constraints）：

• 總選擇數量上限（$k$-out-of-$n$）：$\sum y_i \le k$。
• 蘊含條件（If-Then）：若啟用產線 1 則必啟用產線 2（$y_1 \le y_2$）。
• 至少選擇其一（At-least-one）：產線 3 與產線 4 至少開一條（$y_3 + y_4 \ge 1$）。

4. 滿足總需求限制（Demand Constraint）：各產線生產總量必須剛好滿足（或至少等於）客戶訂單需求 500 件。

---

解題方法

步驟一：定義決策變數（Decision Variables）

設 $i$ 為產線編號，$i \in \{1, 2, 3, 4\}$：

• 產量變數： 令 $x_i$ 表示產線 $i$ 實際生產該產品的數量（件）。
• 啟用指示變數（0-1 變數）： 令 $y_i$ 表示產線 $i$ 是否被啟用進行生產： $y_i = \begin{cases} 1, & \text{若產線 } i \text{ 被啟用生產} \\ 0, & \text{若產線 } i \text{ 未被啟用} \end{cases}, \quad \forall i \in \{1, 2, 3, 4\}$

步驟二：建構目標函數（Objective Function）

公司目標為「最小化總生產成本」，總成本由「固定設置成本」與「變動生產成本」兩部分構成：

• 固定設置成本：$1000 y_1 + 2500 y_2 + 2000 y_3 + 1500 y_4$
• 變動生產成本：$55 x_1 + 30 x_2 + 45 x_3 + 62 x_4$

目標函數為： $\min Z = 1000 y_1 + 2500 y_2 + 2000 y_3 + 1500 y_4 + 55 x_1 + 30 x_2 + 45 x_3 + 62 x_4$

步驟三：推導限制式（Constraints）

1. 滿足訂單需求限制： 四條產線的生產總量須等於客戶訂購的 500 件： $x_1 + x_2 + x_3 + x_4 = 500$
2. 產能與開工連動限制（緊緻 Big-$M$）： 各產線產量不可超過該產線上限，且未開工時產量必為 0： $x_1 \le 250 y_1$ $x_2 \le 210 y_2$ $x_3 \le 180 y_3$ $x_4 \le 210 y_4$
3. 最多使用 3 條產線限制： 啟用的產線總數上限為 3： $y_1 + y_2 + y_3 + y_4 \le 3$
4. 條件相依限制（若用產線 1 則必用產線 2）： 若 $y_1 = 1 \implies y_2 = 1$。化簡為線性不等式： $y_1 \le y_2 \quad (\text{或寫為 } y_1 - y_2 \le 0)$
5. 至少使用產線 3 或產線 4 限制： 產線 3 與產線 4 啟用的總和至少為 1： $y_3 + y_4 \ge 1$
6. 變數性質與非負限制： 產品以件計數，故 $x_i$ 應為非負整數；$y_i$ 為二元變數： $x_i \ge 0 \text{ 且為整數}, \quad \forall i \in \{1, 2, 3, 4\}$ $y_i \in \{0, 1\}, \quad \forall i \in \{1, 2, 3, 4\}$

---

題目各項邏輯條件分析

本題為非選擇題的建模題，題目所給之四項核心敘述轉換為數學條件的剖析如下：

• 「實際用來生產的產線需要先經過設置才能開始生產」： 若無此條件，直接解線性規劃即可；

核心觀念

本題屬於作業研究（Operations Research）等候理論中經典的有限母體機器修護模式（Machine Repair Problem / Finite Calling Population Model），在 Kendall 記號中可表示為 $M/M/1/\infty/2$（呼叫母體數 $K = 2$，修護人員數 $c = 1$）。

本題涵蓋以下核心理論與公式：

1. 生死過程（Birth-Death Process）：系統狀態以「故障中的伺服器數量」定義。由於母體有限，機器故障率（出生率 $\lambda_n$）會隨著正常運作的機器數減少而遞減；修護人員僅 1 人，故修護率（死亡率 $\mu_n$）受限於 1 人的產能。
2. 穩態平衡方程式（Balance Equations）：利用局部平衡切面法（Rate In = Rate Out），推導相鄰狀態之穩態機率關係，並搭配正規化條件 $\sum P_n = 1$ 求得穩態機率分配。
3. 利特爾法則（Little's Law）與到達定理（Arrival Theorem）：

• 平均在系統內的故障機器數：$L = \sum_{n=0}^{K} n P_n$
• 有效到達率（Effective Arrival Rate）：$\lambda_{\text{eff}} = \sum_{n=0}^{K-1} \lambda_n P_n$
• 平均停機修護週期（停留時間）：$W = \frac{L}{\lambda_{\text{eff}}}$

4. 交替再生過程（Alternating Renewal Process）與個別伺服器妥善率（Availability）：單一機器長期運作時間比例等於其平均正常運作時間除以一個運作與修護之完整循環時間： $\text{Availability} = \frac{MTTF}{MTTF + W}$

---

解題方法

(一) 狀態定義與轉移速率圖（Rate Diagram）

1. 基本參數設定：

• 伺服器台數：$K = 2$ 台。
• 單台伺服器平均故障時間 $MTTF = 20$ 小時 $\implies$ 每台故障率 $\lambda = \frac{1}{20} = 0.05 \text{ (台/小時)}$。
• 該職員平均修護時間 $MTTR = 5$ 小時 $\implies$ 修護率 $\mu = \frac{1}{5} = 0.2 \text{ (台/小時)}$。
• 修護人員數：$c = 1$ 人。

2. 狀態定義：

• 定義系統狀態 $n$ 為「系統中處於故障（等待修護或正在修護）的伺服器數量」，則狀態空間為 $S = \{0, 1, 2\}$。
• $n = 0$：2 台正常運作，0 台故障。
• $n = 1$：1 台正常運作，1 台在修護中。
• $n = 2$：0 台正常運作，1 台在修護中、1 台在排隊等待修護。

3. 轉移速率分析：

• 出生率（故障轉移率 $\lambda_n$）：
• $\lambda_0 = (2 - 0)\lambda = 2 \times 0.05 = 0.1 \text{ (台/小時)}$
• $\lambda_1 = (2 - 1)\lambda = 1 \times 0.05 = 0.05 \text{ (台/小時)}$
• $\lambda_2 = 0$（無正常運作之伺服器可再發生故障）
• 死亡率（修護完成轉移率 $\mu_n$）：
• $\mu_1 = 1 \times \mu = 0.2 \text{ (台/小時)}$
• $\mu_2 = \min(2, 1) \times \mu = 0.2 \text{ (台/小時)}$（因僅有 1 名職員，修護率不變）

4. 轉移速率圖（Rate Diagram）：

 λ₀ = 0.1 λ₁ = 0.05
 ----------> ---------->
( 0 ) ( 1 ) ( 2 )
 <---------- <----------
 μ₁ = 0.2 μ₂ = 0.2

---

(二) 平衡方程式與穩態機率求解

1. 建立平衡方程式（利用相鄰狀態切面平衡）：

• 切面 $(0, 1)$： $\lambda_0 P_0 = \mu_1 P_1 \implies 0.1 P_0 = 0.2 P_1 \implies P_1 = \frac{0.1}{0.2} P_0 = \frac{1}{2} P_0$
• 切面 $(1, 2)$： $\lambda_1 P_1 = \mu_2 P_2 \implies 0.05 P_1 = 0.2 P_2 \implies P_2 = \frac{0.05}{0.2} P_1 = \frac{1}{4} P_1 = \frac{1}{8} P_0$

2. 利用全機率條件（正規化方程式）求解： $\sum_{n=0}^{2} P_n = P_0 + P_1 + P_2 = 1$ $P_0 + \frac{1}{2} P_0 + \frac{1}{8} P_0 = 1 \implies \left(\frac{8 + 4 + 1}{8}\right) P_0 = 1 \implies \frac{13}{8} P_0 = 1$ 解得各狀態穩態機率為：

• $P_0 = \frac{8}{13} \approx 0.6154$
• $P_1 = \frac{1}{2} P_0 = \frac{4}{13} \approx 0.3077$
• $P_2 = \frac{1}{8} P_0 = \frac{1}{13} \approx 0.0769$

---

(三) 伺服器故障後，預期需要修理多久？

在等候理論與維護工程中，伺服器故障後的「預期修理時間」即為伺服器進入修護系統的平均停留時間（Mean Sojourn Time / Downtime, $W$），包含「排隊等待修理時間 $W_q$」與「實際修理服務時間 $E[S]$」。

1. 計算系統內平均故障伺服器數 $L$： $L = \sum_{n=0}^{2} n P_n = 0 \cdot P_0 + 1 \cdot P_1 + 2 \cdot P_2 = 0 + 1 \left(\frac{4}{13}\right) + 2 \left(\frac{1}{13}\right) = \frac{6}{13} \text{ (台)}$

2. 計算系統平均有效故障到達率 $\lambda_{\text{eff}}$： $\lambda_{\text{eff}} = \sum_{n=0}^{2} \lambda_n P_n = \lambda_0 P_0 + \lambda_1 P_1 + 0 \cdot P_2$ $\lambda_{\text{eff}} = (0.1)\left(\frac{8}{13}\right) + (0.05)\left(\frac{4}{13}\right) = \frac{0.8 + 0.2}{13} = \frac{1}{13} \text{ (台/小時)}$

3. 依據利特爾法則（Little's Law）求解停留時間 $W$： $W = \frac{L}{\lambda_{\text{eff}}} = \frac{\frac{6}{13}}{\frac{1}{13}} = 6 \text{ 小時}$

*(補充說明：若出題評分若採字面最狹義之「單純由職員動手修理的服務時間」，則為題目直接給定之平均修護時間 $E[S] = \frac{1}{\mu} = 5$ 小時；