107 高普考高考二級 工業工程 作業研究(包括線性規劃與等候理論) 考古題詳解

核心觀念

1. 線性規劃標準型與輔助變數引入：

• 等式限制式（$=$）：無法直接提供起始基底可行解，須加入非負的人工變數（Artificial Variable, $A_i \geq 0$）。
• 大於等於限制式（$\geq$）：須減去剩餘變數（Surplus Variable, $e_i \geq 0$）​以化為等式；因其係數為 $-1$ 無法作為基底變數，故需再加入人工變數（$A_i \geq 0$）​以構成初始單位矩陣。
• 小於等於限制式（$\leq$）：直接加入寬限變數（Slack Variable, $s_i \geq 0$）​化為等式，可直接作為初始基底變數。

2. 大 M 法（Big-M Method）懲罰機制：

• 目的在於藉由給予人工變數極大的懲罰係數 $M$（$M > 0$ 且為充分大之正實數），迫使單形法在疊代過程中自動將人工變數驅逐出基底（即令其值為 0）。
• 對於極小化問題（Minimization），人工變數在目標函數中的懲罰項係數為 $+M$（即懲罰其增大）。

3. 單形表（Simplex Tableau）指標列之初表調整：

• 初始單形表之目標列（Row 0）必須先透過列運算消去基底變數（人工變數）的係數，使其係數化為 0，滿足單形法之正規規範型態（Canonical Form）。

4. 單形法疊代準則（以方程式型態 $z + \sum \bar{c}_j x_j = \text{RHS}$ 為例）：

• 進基變數（Entering Variable）：極小化問題中，Row 0 係數為正且最大者（代表該非基底變數增大時能最快速使 $z$ 降低）。
• 出基變數（Leaving Variable）：由最小比值檢驗（Minimum Ratio Test）​決定，取 $\min \left\{ \frac{\text{RHS}}{a_{ij}} \;\middle|\; a_{ij} > 0 \right\}$。
• 最適性條件：Row 0 中所有非基底變數之係數皆 $\leq 0$ 時即達最適解。

解題方法

步驟一：標準化並加入輔助變數

原模式為：

1. 第 1 式（等式）：加入人工變數 $A_1 \geq 0$，得 $3x_1 + x_2 + A_1 = 3$。
2. 第 2 式（$\geq$）：減去剩餘變數 $e_1 \geq 0$ 並加入人工變數 $A_2 \geq 0$，得 $4x_1 + 3x_2 - e_1 + A_2 = 6$。
3. 第 3 式（$\leq$）：加入寬限變數 $s_2 \geq 0$，得 $x_1 + 2x_2 + s_2 = 4$。
4. 目標函數加入人工變數之大 $M$ 懲罰項： $\text{Minimize}\quad z = 4x_1 + x_2 + 0e_1 + 0s_2 + M A_1 + M A_2$

步驟二：建立初始目標列（Row 0）之規範型態

將目標式整理為方程式形式： $\text{Row 0}:\quad z - 4x_1 - x_2 + 0e_1 + 0s_2 - M A_1 - M A_2 = 0$

由於初始基底變數為 $\{A_1, A_2, s_2\}$，Row 0 中 $A_1$ 與 $A_2$ 的係數必須消除為 0。 利用限制式：

• $\text{Row 1}:\quad 3x_1 + x_2 + A_1 = 3 \implies A_1 = 3 - 3x_1 - x_2$
• $\text{Row 2}:\quad 4x_1 + 3x_2 - e_1 + A_2 = 6 \implies A_2 = 6 - 4x_1 - 3x_2 + e_1$

進行列運算：$\text{New Row 0} = \text{Old Row 0} + M \times (\text{Row 1}) + M \times (\text{Row 2})$

步驟三：單形表疊代運算

【初始單形表（Initial Tableau）】

• 進基變數：因 $M$ 為極大正數，$7M - 4 > 4M - 1 > 0$，故選 $x_1$ 進基。
• 出基變數：比值最小者為 Row 1，故 $A_1$ 出基。樞紐元素（Pivot）為 $3$。
• 高斯消去列運算：
• $\text{New } R_1 = R_1 / 3$
• $\text{New } R_2 = R_2 - 4 \times (\text{New } R_1)$
• $\text{New } R_3 = R_3 - 1 \times (\text{New } R_1)$
• $\text{New } R_0 = R_0 - (7M - 4) \times (\text{New } R_1)$

【第一次疊代單形表（Tableau 1）】

核心觀念

本題為線性規劃（Linear Programming, LP）的經典「敏感度分析（Sensitivity Analysis）」與「對偶理論（Duality Theory）」考題，核心觀念包含：

1. 對偶價格（Dual Price / Shadow Price，又稱影子價格）： 在極大化問題中，各限制式右側常數（RHS, Resource Availability）每增加 1 單位時，目標函數值（總收益）的邊際增加量。在最適單形表中，對應各限制式差額變數（Slack Variables）於 $z$ 列（Row 0）的係數即為該資源之對偶價格 $y_i$。
2. 可行性範圍（Range of Feasibility / Allowable Range of RHS）： 在維持當前最適基底變數組合不變（即基底可行解維持非負 $x_B \geq 0$）的前提下，右側常數向量 $b$ 所允許的變動範圍。在此範圍內，各資源之對偶價格保持固定不變。
3. 基底反矩陣 $B^{-1}$ 的判讀： 在標準單形表中，初始基底為差額變數矩陣 $I$ 時，最適單形表中差額變數（$s_1, s_2, s_3$）所在的行向量，即為最適基底矩陣之反矩陣 $B^{-1}$。
4. 超出可行性範圍的經濟決策： 當資源擴充量超過允許範圍時，現有基底會改變，對偶價格亦會隨之遞減。進行外購決策時，必須重新評估新瓶頸所產生的最大總收益，扣除購買總成本後檢視淨收益是否增加。

解題方法

由考卷原頁與最適單形表資訊可知：

• 基底變數向量為 $x_B = \begin{bmatrix} x_1 \\ s_3 \\ x_2 \end{bmatrix}$，其對應的解向量為 $x_B = \begin{bmatrix} 450 \\ 400 \\ 100 \end{bmatrix}$。
• 差額變數 $s_1, s_2, s_3$ 欄位所構成的基底反矩陣為： $B^{-1} = \begin{bmatrix} -\frac{1}{4} & \frac{3}{4} & 0 \\ -2 & 2 & 1 \\ \frac{1}{2} & -\frac{1}{2} & 0 \end{bmatrix}$
• 最適目標函數值 $z = 1750$ 美元。

（一）每一資源之對偶價格及其有效正確範圍

1. 每一資源之對偶價格 在最適單形表的 $z$ 列中，差額變數之係數即為各資源之對偶價格（$y_1, y_2, y_3$）：

• 電阻器（對應 $s_1$）：$y_1 = \frac{5}{4} = 1.25$ 美元／單位。
• 電容器（對應 $s_2$）：$y_2 = \frac{1}{4} = 0.25$ 美元／單位。
• 芯片（對應 $s_3$）：$y_3 = 0$ 美元／單位（芯片尚有剩餘 400 單位，為非緊縮資源，影子價格為 0）。

2. 有效正確範圍（允許變動範圍） 設資源可用量由 $b$ 變動為 $b + \Delta b$，為維持當前基底可行性，必須滿足： $x_B' = B^{-1}(b + \Delta b) = x_B + B^{-1}\Delta b \geq 0$

• 電阻器（資源 1，$\Delta b = [\Delta b_1, 0, 0]^T$）： $\begin{bmatrix} 450 \\ 400 \\ 100 \end{bmatrix} + \begin{bmatrix} -\frac{1}{4} \\ -2 \\ \frac{1}{2} \end{bmatrix} \Delta b_1 \geq \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$ 聯立求解不等式： $450 - \frac{1}{4}\Delta b_1 \geq 0 \implies \Delta b_1 \leq 1800$ $400 - 2\Delta b_1 \geq 0 \implies \Delta b_1 \leq 200$ $100 + \frac{1}{2}\Delta b_1 \geq 0 \implies \Delta b_1 \geq -200$ 取交集得：$-200 \leq \Delta b_1 \leq 200$。 因為原始可用量 $b_1 = 1200$，故電阻器的有效正確範圍為： $1200 - 200 \leq b_1 \leq 1200 + 200 \implies 1000 \leq b_1 \leq 1400\text{ 單位}$

• 電容器（資源 2，$\Delta b = [0, \Delta b_2, 0]^T$）： $\begin{bmatrix} 450 \\ 400 \\ 100 \end{bmatrix} + \begin{bmatrix} \frac{3}{4} \\ 2 \\ -\frac{1}{2} \end{bmatrix} \Delta b_2 \geq \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$ 聯立求解不等式： $450 + \frac{3}{4}\Delta b_2 \geq 0 \implies \Delta b_2 \geq -600$ $400 + 2\Delta b_2 \geq 0 \implies \Delta b_2 \geq -200$ $100 - \frac{1}{2}\Delta b_2 \geq 0 \implies \Delta b_2 \leq 200$ 取交集得：$-200 \leq \Delta b_2 \leq 200$。 因為原始可用量 $b_2 = 1000$，故電容器的有效正確範圍為： $1000 - 200 \leq b_2 \leq 1000 + 200 \implies 800 \leq b_2 \leq 1200\text{ 單位}$

• 芯片（資源 3，$\Delta b = [0, 0, \Delta b_3]^T$）： $\begin{bmatrix} 450 \\ 400 \\ 100 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} \Delta b_3 \geq \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$ 聯立求解不等式： $400 + \Delta b_3 \geq 0 \implies \Delta b_3 \geq -400$ 上限無限制（增加芯片不會影響可行性）。 因為原始可用量 $b_3 = 800$，故芯片的有效正確範圍為： $b_3 \geq 400\text{ 單位（即 } 400 \leq b_3 < \infty\text{）}$

（二）若電阻器的可用數量增加為 1300 單位，最佳解為何？

1. 檢驗可行性： 電阻器可用量由 1200 增至 1300，變動量 $\Delta b_1 = 1300 - 1200 = 100$ 單位。 因為 $\Delta b_1 = 100$ 介於允許變動區間 $[-200, 200]$ 內，現有基底維持最適。
2. 計算新的變數值： $\begin{bmatrix} x_1^* \\ s_3^* \\ x_2^* \end{bmatrix} = \begin{bmatrix} 450 \\ 400 \\ 100 \end{bmatrix} + \begin{bmatrix} -\frac{1}{4} \\ -2 \\ \frac{1}{2} \end{bmatrix}(100) = \begin{bmatrix} 450 - 25 \\ 400 - 200 \\ 100 + 50 \end{bmatrix} = \begin{bmatrix} 425 \\ 200 \\ 150 \end{bmatrix}$ 非基底變數仍為 $s_1^* = 0, s_2^* = 0$。
3. 計算新的最適收益：

• 利用對偶價格計算：

核心觀念

本題屬於作業研究中經典的時變需求動態批量問題（Dynamic Lot-Sizing Problem），在學術上亦稱為 Wagner-Whitin 模型。其核心概念為：

1. 零存貨訂購特性（Zero-Inventory Property）： 在不允許缺貨且持有成本為正的前提下，最適決策必定滿足「唯有當期初存貨降至零時，才會進行訂購/採購」。因此，任一次採購的數量，必恰好等於未來連續若干個月的需求總和。
2. 最短路徑問題（Shortest Path Problem, SPP）網路轉化：

• 節點定義：設立節點 $1, 2, 3, 4, 5$。節點 $i$（$i \in \{1, 2, 3, 4\}$）代表「第 $i$ 個月初且手頭存貨恰好為零」的時間點；節點 $5$ 代表「第 4 個月底（即規劃期末）完成所有需求且庫存歸零」的終點。
• 弧（Arc）定義：由節點 $i$ 指向節點 $j$（$1 \le i < j \le 5$）的有向弧 $(i, j)$，代表「在第 $i$ 個月初下單採購，一次滿足第 $i$ 月至第 $j-1$ 月的所有需求」。
• 弧權重（Cost）：弧 $(i, j)$ 的成本 $C_{ij}$ 即為該次下單所發生的「設置成本（Setup Cost）＋採購成本（Purchase Cost）＋庫存持有成本（Holding Cost）」。
• 目標：求由節點 $1$ 至節點 $5$ 的最短路徑（即最小總成本路徑）。

解題方法

步驟一：整理各期基本參數

• 需求量：$d_1 = 100,\; d_2 = 140,\; d_3 = 210,\; d_4 = 180$（單位）。
• 採購單價：$c_1 = 15,\; c_2 = 12,\; c_3 = 10,\; c_4 = 14$（美元/單位）。
• 每次設置成本：$K = 200$ 美元。
• 單位持有成本：$h = 1.20$ 美元/（單位 $\cdot$ 月）。

步驟二：推導各月份需求若於第 $i$ 個月採購的有效單位成本

若第 $k$ 個月（$k \ge i$）的需求 $d_k$ 決定提前在第 $i$ 個月購買，則每單位除了購買價格 $c_i$ 之外，尚須支付存放在倉庫 $(k - i)$ 個月的持有成本。其有效單位成本 $u_{ik}$ 定義為： $u_{ik} = c_i + (k - i) \cdot h$

各組合之有效單位成本計算如下：

• 第 1 個月下單（$i = 1$）：
• 供應第 1 個月（$k=1$）：$u_{11} = 15 + 0 = 15.00$
• 供應第 2 個月（$k=2$）：$u_{12} = 15 + 1 \times 1.20 = 16.20$
• 供應第 3 個月（$k=3$）：$u_{13} = 15 + 2 \times 1.20 = 17.40$
• 供應第 4 個月（$k=4$）：$u_{14} = 15 + 3 \times 1.20 = 18.60$
• 第 2 個月下單（$i = 2$）：
• 供應第 2 個月（$k=2$）：$u_{22} = 12 + 0 = 12.00$
• 供應第 3 個月（$k=3$）：$u_{23} = 12 + 1 \times 1.20 = 13.20$
• 供應第 4 個月（$k=4$）：$u_{24} = 12 + 2 \times 1.20 = 14.40$
• 第 3 個月下單（$i = 3$）：
• 供應第 3 個月（$k=3$）：$u_{33} = 10 + 0 = 10.00$
• 供應第 4 個月（$k=4$）：$u_{34} = 10 + 1 \times 1.20 = 11.20$
• 第 4 個月下單（$i = 4$）：
• 供應第 4 個月（$k=4$）：$u_{44} = 14 + 0 = 14.00$

步驟三：計算所有可能弧 $(i, j)$ 的成本 $C_{ij}$

弧成本公式為： $C_{ij} = K + \sum_{k=i}^{j-1} u_{ik} \cdot d_k$

1. 從節點 1 出發的弧：

• $C_{12} = 200 + 15.00 \times 100 = 200 + 1500 = 1700$
• $C_{13} = C_{12} + 16.20 \times 140 = 1700 + 2268 = 3968$
• $C_{14} = C_{13} + 17.40 \times 210 = 3968 + 3654 = 7622$
• $C_{15} = C_{14} + 18.60 \times 180 = 7622 + 3348 = 10970$

2. 從節點 2 出發的弧：

• $C_{23} = 200 + 12.00 \times 140 = 200 + 1680 = 1880$
• $C_{24} = C_{23} + 13.20 \times 210 = 1880 + 2772 = 4652$
• $C_{25} = C_{24} + 14.40 \times 180 = 4652 + 2592 = 7244$

3. 從節點 3 出發的弧：

• $C_{34} = 200 + 10.00 \times 210 = 200 + 2100 = 2300$
• $C_{35} = C_{34} + 11.20 \times 180 = 2300 + 2016 = 4316$

核心觀念

本題屬於等候理論（Queueing Theory）中最經典的 $M/M/1/\infty/\text{FCFS}$ 模型（簡稱 $M/M/1$ 模型）。

1. 符號與假設判定：

• 到達過程為卜瓦松過程（Poisson Process），到達間隔時間服從參數為 $\lambda$ 的指數分配。
• 題目敘述「離去為卜瓦松分配」，即單位時間內服務完成離去的顧客數服從卜瓦松分配，意味服務時間服從參數為 $\mu$ 的指數分配。
• 單一櫃台（單一服務台，通道數 $s = 1$）。
• 系統容量無限制（可容納無限多人），服務法則為先到先服務（First-Come, First-Served, FCFS），且顧客無中途放棄（reneging）或不排隊離開（balking）之行為。

2. 關鍵參數與公式：

• 到達率 $\lambda$：平均每單位時間到達的顧客數。
• 服務率 $\mu$：平均每單位時間櫃台能服務的顧客數。
• 服務台利用率（Traffic Intensity / Utilization Factor）：$\rho = \frac{\lambda}{\mu}$。
• 穩態條件（Steady-State Condition）：$\rho < 1$。
• 系統閒置機率（系統內為 0 人之機率）：$P_0 = 1 - \rho$。
• 系統中平均顧客數：$L = \frac{\rho}{1 - \rho} = \frac{\lambda}{\mu - \lambda}$。
• 等候線中平均顧客數：$L_q = \frac{\rho^2}{1 - \rho} = \frac{\lambda^2}{\mu(\mu - \lambda)} = L - \rho$。
• 利特爾法則（Little's Law）：$L = \lambda W$、$L_q = \lambda W_q$。
• 平均停留時間關係式：$W = W_q + \frac{1}{\mu}$。
• PASTA 特性（Poisson Arrivals See Time Averages）：因到達符合卜瓦松過程，到達者觀察到系統處於特定狀態的機率等於系統長期的時間平均機率。

解題方法

步驟一：統一單位並計算基本參數

以「分鐘」為時間基準單位：

• 到達率 $\lambda$： $\lambda = \frac{3 \text{ 人}}{20 \text{ 分鐘}} = 0.15 \text{（人／分鐘）}$
• 服務率 $\mu$：每位顧客平均服務時間為 5 分鐘，即平均服務時間 $\frac{1}{\mu} = 5$ 分鐘： $\mu = \frac{1}{5} = 0.20 \text{（人／分鐘）}$
• 計算服務台利用率 $\rho$： $\rho = \frac{\lambda}{\mu} = \frac{0.15}{0.20} = 0.75$
• 檢驗穩態條件：$\rho = 0.75 < 1$，系統可達到長期穩態。

（一）系統閒置的機率

系統閒置表示系統內完全沒有顧客（$n = 0$），即求 $P_0$： $P_0 = 1 - \rho = 1 - 0.75 = 0.25$

（二）系統中平均顧客數？等候線平均顧客數？

1. 系統中平均顧客數（$L$）： 包含正在接受服務的顧客與正在排隊等候的顧客總和： $L = \frac{\rho}{1 - \rho} = \frac{0.75}{1 - 0.75} = \frac{0.75}{0.25} = 3 \text{（人）}$

2. 等候線平均顧客數（$L_q$）： 僅計算正在排隊、尚未進入櫃台接受服務的顧客：