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

核心觀念

1. 對偶單形法（Dual Simplex Method）的啟動條件：

• 對偶可行性（Dual Feasibility，即最佳性條件）：目標式列之檢定數（Reduced Costs）皆滿足最佳準則（極大化問題之檢定數 $\leq 0$；若採列運算形式 $W - \sum \bar{c}_j x_j = 0$，則非基底變數係數 $\geq 0$）。
• 原問題不可行（Primal Infeasibility）：基底解中至少存在一個常數項 $b_i < 0$。

2. 對偶理論（Duality Theory）：

• 原問題（Primal）與對偶問題（Dual）具有對稱關係。原問題為極小化、限制式為「$\leq$」、變數非負時，其對偶變數為非正（$y_i \leq 0$）。為便於單形表操作，令 $u_i = -y_i \geq 0$ 轉為非負變數。
• 強對偶定理（Strong Duality Theorem）：若原問題或對偶問題任一具有有限最佳解，則另一問題亦具最佳解，且兩者最佳目標函數值相等（$Z^* = W^*$）。
• 最佳解之讀取：對偶問題最終單形表中，各差額變數（Slack Variables）在目標列（Row 0）的係數，即對應原問題各決策變數的最佳解。

解題方法

破題分析

檢視原問題（Primal Problem）：

若直接在原問題加入差額變數，常數項 $b = [4, 12]^T \geq 0$（原問題可行），但目標式含負係數（$-2, -4$），未具備對偶可行性，無法直接啟動對偶單形法（無法選取離開變數）。

將原問題轉為對偶問題（Dual Problem）​後，對偶問題之常數項自然出現負值，且目標式係數全數滿足最佳條件。因此，標準解法為：寫出對偶問題，以對偶單形法求解對偶問題，再由最終單形表直接讀出原問題最佳解。

步驟一：建立對偶問題（Dual Problem）並標準化

設對偶變數為 $y_1, y_2$。因原問題為極小化且限制式為 $\leq$，對偶變數規定為 $y_1, y_2 \leq 0$。 令非負變數 $u_1 = -y_1 \geq 0$、$u_2 = -y_2 \geq 0$，建立對偶問題：

加入差額變數 $s_1, s_2, s_3, s_4 \geq 0$，化為標準型：

步驟二：初始對偶單形表與可行性檢視

以 $\{s_1, s_2, s_3, s_4\}$ 為初始基底變數：

初始單形表（Tableau 1）

• 對偶可行性檢驗：目標列中非基底變數 $u_1, u_2$ 之係數分別為 $4 \geq 0, 12 \geq 0$，已滿足極大化問題之最佳性條件。
• 原問題可行性檢驗：$\text{RHS}$ 中 $s_2 = -2 < 0$、$s_4 = -4 < 0$，違反非負限制。符合對偶單形法條件。

步驟三：對偶單形法迭代運算

第一次迭代（Iteration 1）：

1. 決定離開變數（Leaving Variable）： $\min \{b_i \mid b_i < 0\} = \min\{-2, -4\} = -4 \quad (\text{第 4 列})$ 由 $s_4$ 離開基底。
2. 決定進入變數（Entering Variable）： 檢定第 4 列中為負之係數（$u_1$ 行為 $-1$，$u_2$ 行為 $-1$），進行比值檢定： $\theta = \min_{j: a_{4j} < 0} \left\{ \frac{\text{Row } W \text{ 係數}}{|a_{4j}|} \right\} = \min \left\{ \frac{4}{|-1|}, \frac{12}{|-1|} \right\} = \min\{4, 12\} = 4 \quad (u_1)$ 樞紐元素（Pivot）為 $a_{4, u_1} = -1$，$u_1$ 進入基底。
3. 高斯消去列運算：

• $\text{新第 4 列} = \text{原第 4 列} \div (-1)$

核心觀念

本題屬於作業研究（Operations Research）中的網路最佳化（Network Optimization）​與配銷規劃（Distribution Planning）​範疇，主要考核以下核心觀念與工具：

1. 最大流量問題（Maximum Flow Problem）與最大流最小割定理（Max-Flow Min-Cut Theorem）：題目目標為「盡可能滿足各品牌商的需求」，在未給定單位運送成本的情況下，問題本質為最大化總配送量（即網路最大流）。最大可供應總量受限於源點至各工廠的供給容量割集（Capacity Cut）。
2. 具上下界限制之流量平衡（Flow with Lower and Upper Bounds）：特定弧帶有等式限制（$x_{12} = 40$）與下界限制（$x_{23} \ge 30$），可透過「預先指派基準量」將限制扣除後，轉化為標準流量分配問題。
3. 不平衡運輸問題（Unbalanced Transportation Problem）與虛擬工廠（Dummy Factory）：總供給（275 萬台）小於總需求（305 萬台），透過加入「虛擬工廠」吸收未滿足的 30 萬台缺額，使系統達成供需平衡。
4. 多重最佳解（Alternative Optimal Solutions）：由於缺乏成本與懲罰權重參數，只要產能全開且滿足上下界約束，即達最大可能之總供應量（275 萬台）。

解題方法

步驟一：定義決策變數與建立線性規劃模式

令 $x_{ij}$ 為工廠 $P_i$ 每月供應給品牌商 $C_j$ 的相機模組數量（單位：萬台），其中 $i \in \{1, 2, 3\}$、$j \in \{1, 2, 3, 4\}$。

• 目標函數（最大化總滿足需求量／總出貨量）： $\max Z = \sum_{i=1}^3 \sum_{j=1}^4 x_{ij}$

• 限制條件：

1. 工廠產能限制（供給上限）： $x_{11} + x_{12} + x_{13} + x_{14} \le 90 \quad (P_1)$ $x_{21} + x_{22} + x_{23} + x_{24} \le 75 \quad (P_2)$ $x_{31} + x_{32} + x_{33} + x_{34} \le 110 \quad (P_3)$
2. 客戶需求限制（需求上限，不可超額供應）： $x_{11} + x_{21} + x_{31} \le 90 \quad (C_1)$ $x_{12} + x_{22} + x_{32} \le 80 \quad (C_2)$ $x_{13} + x_{23} + x_{33} \le 70 \quad (C_3)$ $x_{14} + x_{24} + x_{34} \le 65 \quad (C_4)$
3. 特殊供應限制： $x_{12} = 40$ $x_{23} \ge 30$
4. 非負限制： $x_{ij} \ge 0, \quad \forall i \in \{1, 2, 3\}, j \in \{1, 2, 3, 4\}$

步驟二：總供應量極限分析

• 總產能 $= 90 + 75 + 110 = 275$ 萬台。
• 總需求 $= 90 + 80 + 70 + 65 = 305$ 萬台。
• 依據最大流最小割定理，由於總產能（275 萬台）小於總需求（305 萬台），且所有工廠的剩餘配額均有暢通的供應途徑，最大出貨量必定受限於工廠端的總產能。因此，最大總滿足需求量為 275 萬台，全系統必然存在 $305 - 275 = 30$ 萬台的未滿足需求（缺額）。

步驟三：轉化為平衡運輸表求解（扣除基準量法）

為求得具體且系統化的整數指派方案，先滿足固定與下界約束：

1. 固定 $x_{12} = 40$：$P_1$ 剩餘產能為 $90 - 40 = 50$ 萬台；$C_2$ 剩餘需求為 $80 - 40 = 40$ 萬台。
2. 基準指派 $x_{23} = 30$：$P_2$ 剩餘產能為 $75 - 30 = 45$ 萬台；$C_3$ 剩餘需求為 $70 - 30 = 40$ 萬台。
3. 加入產能為 30 萬台的虛擬工廠 $P_D$（代表未滿足之需求缺額），形成供需皆為 235 萬台的平衡運輸問題。

剩餘供需矩陣（單位：萬台）：

• 剩餘供給：$P_1': 50$、$P_2': 45$、$P_3': 110$、$P_D: 30$。
• 剩餘需求：$C_1': 90$、$C_2': 40$、$C_3': 40$、$C_4': 65$。

依據西北角法（Northwest Corner Rule）​依序分配剩餘量：

• 指派 $(P_1, C_1) = 50$ $\implies P_1$ 產能全數耗盡，$C_1$ 尚缺 40。

核心觀念

本題屬於作業研究中「有限期界確定型動態規劃」（Finite-Horizon Deterministic Dynamic Programming）之經典題型——人力規劃與平滑化問題（Workforce Planning / Smoothing Problem），在數學結構上亦與動態批量規模模型（如 Wagner-Whitin 模型）具對偶相似性。

其核心考點包括：

1. 動態規劃五大要素之定義：階段（Stage）、狀態（State）、決策變數（Decision Variable）、狀態轉移方程式（State Transition Equation）與單期成本函數（Stage Cost Function）。
2. 貝爾曼最適性原理（Bellman's Principle of Optimality）：建立逆向動態規劃（Backward DP）的遞迴關係式（Recursive Equation）。
3. 固定成本與線性持有成本之權衡（Trade-off Analysis）：

• 每多僱一位兼職人員每月產生超額閒置成本 $c_h = \text{\char36}20,000$。
• 新聘兼職人員不論人數多寡，均需支付固定的職前培訓成本 $K = \text{\char36}42,000$（未新聘則為 $0$）。
• 解僱成本為 $0$。
• 決策本質在於衡量「保留超額人力所衍生之閒置成本」與「解僱後重新招募所衍生之固定培訓成本」之間的損益平衡。

解題方法

(一) 動態規劃模式建立（10 分）

本問題可建立為一逆向動態規劃（Backward Dynamic Programming）模式：

1. 階段（Stage）$t$： 代表專案執行的月份，$t \in \{1, 2, 3, 4, 5, 6\}$。

2. 狀態變數（State Variable）$s_t$： 代表進入第 $t$ 個月月初時（即第 $t-1$ 個月結束時）的在職兼職人數。

• 初始狀態：$s_1 = 0$（專案開始前未僱用兼職人員）。

3. 決策變數（Decision Variable）$x_t$： 代表第 $t$ 個月的在職兼職總人數。

• 可行決策集合限制：$x_t \ge d_t$，其中 $d_t$ 為第 $t$ 個月的人力需求量。 即 $(d_1, d_2, d_3, d_4, d_5, d_6) = (7, 5, 4, 5, 6, 8)$。
• 第 $t$ 個月的新聘人數為 $\max(0, x_t - s_t)$。

4. 狀態轉移方程式（State Transition Equation）： $s_{t+1} = x_t \quad (t = 1, 2, \dots, 5)$

5. 單期成本函數（Stage Cost Function）$C_t(s_t, x_t)$： 第 $t$ 個月的成本包含「超額僱用成本」與「新聘培訓固定成本」： $C_t(s_t, x_t) = 20000 \cdot (x_t - d_t) + K(x_t - s_t)$ 其中培訓成本函數 $K(\Delta)$ 為： $K(\Delta) = \begin{cases} 42000, & \text{若 } \Delta > 0 \\ 0, & \text{若 } \Delta \le 0 \end{cases}$ （若 $x_t < s_t$，表示該月解僱 $s_t - x_t$ 人，依題意解僱成本為 $0$）。

6. 遞迴關係式（Recursive Equation）： 定義 $f_t(s_t)$ 為在第 $t$ 個月期初在職人數為 $s_t$ 的條件下，自第 $t$ 個月至第 $6$ 個月的「最低總累計成本」： $f_t(s_t) = \min_{x_t \ge d_t} \left\{ 20000(x_t - d_t) + K(x_t - s_t) + f_{t+1}(x_t) \right\}$ 邊界條件（Boundary Condition）： $f_7(s_7) = 0$ 求解目標：求 $f_1(s_1) = f_1(0)$ 以及達成該最低成本之各階段最佳決策序列 $(x_1^*, x_2^*, \dots, x_6^*)$。

(二) 動態規劃模式求解（20 分）

採用逆向求解法（由第 $6$ 個月往第 $1$ 個月回推）：

【階段 6】$t = 6$，$d_6 = 8$

專案於第 6 個月結束，超額僱用無任何未來效益，故最佳決策必為 $x_6^* = 8$。 $f_6(s_6) = 20000(8 - 8) + K(8 - s_6) = K(8 - s_6)$

• 若 $s_6 = 8$：$x_6^* = 8$，$f_6(8) = 0$
• 若 $s_6 < 8$：$x_6^* = 8$，$f_6(s_6) = 42,000$

【階段 5】$t = 5$，$d_5 = 6$

決策限制 $x_5 \ge 6$。合理的候選決策為 $x_5 \in \{6, 8\}$（僱用 7 位將衍生 1 位超額成本 $\text{\char36}20,000$，且第 6 個月仍需支付培訓費 $\text{\char36}42,000$，成本為 $\text{\char36}62,000$，劣於 $x_5 = 6$ 之 $\text{\char36}42,000$）：

• 若選 $x_5 = 6$：期後成本為 $20000(6 - 6) + f_6(6) = 0 + 42000 = 42,000$
• 若選 $x_5 = 8$：期後成本為 $20000(8 - 6) + f_6(8) = 40000 + 0 = 40,000$

評估不同進入狀態 $s_5$：

1. 若 $s_5 = 5$：

• $x_5 = 6 \implies K(6 - 5) + 42000 = 42000 + 42000 = 84,000$
• $x_5 = 8 \implies K(8 - 5) + 40000 = 42000 + 40000 = 82,000$ $\implies x_5^* = 8$，$f_5(5) = 82,000$。

2. 若 $s_5 \ge 6$（例如 $s_5 = 6$）：

• $x_5 = 6 \implies K(6 - 6) + 42000 = 0 + 42000 = 42,000$
• $x_5 = 8 \implies K(8 - 6) + 40000 = 42000 + 40000 = 82,000$ $\implies x_5^* = 6$，$f_5(6) = 42,000$。

【階段 4】$t = 4$，$d_4 = 5$

決策限制 $x_4 \ge 5$。候選決策為 $x_4 \in \{5, 6\}$：

• 若選 $x_4 = 5$：期後成本為 $20000(5 - 5) + f_5(5) = 0 + 82000 = 82,000$
• 若選 $x_4 = 6$：期後成本為 $20000(6 - 5) + f_5(6) = 20000 + 42000 = 62,000$

評估不同進入狀態 $s_4$：

1. 若 $s_4 = 4$：

• $x_4 = 5 \implies K(5 - 4) + 82000 = 42000 + 82000 = 124,000$
• $x_4 = 6 \implies K(6 - 4) + 62000 = 42000 + 62000 = 104,000$ $\implies x_4^* = 6$，$f_4(4) = 104,000$。

2. 若 $s_4 = 5$：

• $x_4 = 5 \implies K(5 - 5) + 82000 = 0 + 82000 = 82,000$
• $x_4 = 6 \implies K(6 - 5) + 62000 = 42000 + 62000 = 104,000$ $\implies x_4^* = 5$，$f_4(5) = 82,000$。

3. 若 $s_4 = 6$：

• $x_4 = 5 \implies K(5 - 6) + 82000 = 0 + 82000 = 82,000$
• $x_4 = 6 \implies K(6 - 6) + 62000 = 0 + 62000 = 62,000$ $\implies x_4^* = 6$，$f_4(6) = 62,000$。

【階段 3】$t = 3$，$d_3 = 4$

決策限制 $x_3 \ge 4$。候選決策為 $x_3 \in \{4, 5, 6\}$：

核心觀念

本題評量離散時間馬可夫鏈（Discrete-Time Markov Chain, DTMC）在市場佔有率預測與收益分析之經典應用，核心觀念涵蓋：

1. 轉移機率矩陣（Transition Probability Matrix）之性質：單階轉移機率矩陣 $P$ 為隨機矩陣（Stochastic Matrix），其元素滿足 $0 \le P_{ij} \le 1$，且各列（Row）機率總和恆等於 1（即 $\sum_{j} P_{ij} = 1$）。
2. 查普曼—柯莫哥洛夫方程式（Chapman-Kolmogorov Equation）：$n$ 階轉移機率矩陣為單階矩陣的 $n$ 次方，即 $P^{(n)} = P^n$。其元素 $P_{ij}^{(n)}$ 代表由狀態 $i$ 經過 $n$ 期後轉移至狀態 $j$ 的條件機率。
3. 瞬態分佈（Transient Distribution）：若第 0 期的起始狀態機率向量為 $\pi^{(0)}$，則第 $n$ 期的狀態機率向量（市場佔有率）為： $\pi^{(n)} = \pi^{(0)} P^n$
4. 穩定狀態機率（Steady-State Probabilities）：對於不可約（Irreducible）且非週期（Aperiodic）的齊次馬可夫鏈，長期狀態機率向量 $\pi = [\pi_A, \pi_B, \pi_C]$ 存在且唯一，並滿足聯立方程： $\pi P = \pi \quad \text{且} \quad \sum_{i} \pi_i = 1$
5. 長期期望總銷售額：長期穩定狀態下，顧客購買各品牌的機率收斂至 $\pi$。年總銷售額等於總需求量乘上穩定狀態下的加權平均單價。

解題方法

(一) 計算 $P^2$ 及 $P^3$

已知單階轉移機率矩陣：

1. 計算 $P^2 = P \times P$：

• 第一列元素：
• $P_{11}^{(2)} = (0.6)(0.6) + (0.3)(0.3) + (0.1)(0.1) = 0.36 + 0.09 + 0.01 = 0.46$
• $P_{12}^{(2)} = (0.6)(0.3) + (0.3)(0.5) + (0.1)(0.7) = 0.18 + 0.15 + 0.07 = 0.40$
• $P_{13}^{(2)} = (0.6)(0.1) + (0.3)(0.2) + (0.1)(0.2) = 0.06 + 0.06 + 0.02 = 0.14$
• 第二列元素：
• $P_{21}^{(2)} = (0.3)(0.6) + (0.5)(0.3) + (0.2)(0.1) = 0.18 + 0.15 + 0.02 = 0.35$
• $P_{22}^{(2)} = (0.3)(0.3) + (0.5)(0.5) + (0.2)(0.7) = 0.09 + 0.25 + 0.14 = 0.48$
• $P_{23}^{(2)} = (0.3)(0.1) + (0.5)(0.2) + (0.2)(0.2) = 0.03 + 0.10 + 0.04 = 0.17$
• 第三列元素：
• $P_{31}^{(2)} = (0.1)(0.6) + (0.7)(0.3) + (0.2)(0.1) = 0.06 + 0.21 + 0.02 = 0.29$
• $P_{32}^{(2)} = (0.1)(0.3) + (0.7)(0.5) + (0.2)(0.7) = 0.03 + 0.35 + 0.14 = 0.52$
• $P_{33}^{(2)} = (0.1)(0.1) + (0.7)(0.2) + (0.2)(0.2) = 0.01 + 0.14 + 0.04 = 0.19$

故兩階轉移機率矩陣為：

2. 計算 $P^3 = P^2 \times P$：

• 第一列元素：
• $P_{11}^{(3)} = (0.46)(0.6) + (0.40)(0.3) + (0.14)(0.1) = 0.276 + 0.120 + 0.014 = 0.410$
• $P_{12}^{(3)} = (0.46)(0.3) + (0.40)(0.5) + (0.14)(0.7) = 0.138 + 0.200 + 0.098 = 0.436$
• $P_{13}^{(3)} = (0.46)(0.1) + (0.40)(0.2) + (0.14)(0.2) = 0.046 + 0.080 + 0.028 = 0.154$
• 第二列元素：
• $P_{21}^{(3)} = (0.35)(0.6) + (0.48)(0.3) + (0.17)(0.1) = 0.210 + 0.144 + 0.017 = 0.371$
• $P_{22}^{(3)} = (0.35)(0.3) + (0.48)(0.5) + (0.17)(0.7) = 0.105 + 0.240 + 0.119 = 0.464$
• $P_{23}^{(3)} = (0.35)(0.1) + (0.48)(0.2) + (0.17)(0.2) = 0.035 + 0.096 + 0.034 = 0.165$
• 第三列元素：
• $P_{31}^{(3)} = (0.29)(0.6) + (0.52)(0.3) + (0.19)(0.1) = 0.174 + 0.156 + 0.019 = 0.349$
• $P_{32}^{(3)} = (0.29)(0.3) + (0.52)(0.5) + (0.19)(0.7) = 0.087 + 0.260 + 0.133 = 0.480$
• $P_{33}^{(3)} = (0.29)(0.1) + (0.52)(0.2) + (0.19)(0.2) = 0.029 + 0.104 + 0.038 = 0.171$

故三階轉移機率矩陣為：

(二) 計算穩定狀態機率

設長期穩定狀態機率向量為 $\pi = [\pi_A, \pi_B, \pi_C]$。 由平衡方程式 $\pi P = \pi$ 展開得：

分別對應各欄展開並整理為齊次方程式：

1. $0.6 \pi_A + 0.3 \pi_B + 0.1 \pi_C = \pi_A \implies -0.4 \pi_A + 0.3 \pi_B + 0.1 \pi_C = 0$ 同乘以 10 得： $-4 \pi_A + 3 \pi_B + \pi_C = 0 \implies \pi_C = 4 \pi_A - 3 \pi_B \quad \cdots \text{(式 1)}$

2. $0.3 \pi_A + 0.5 \pi_B + 0.7 \pi_C = \pi_B \implies 0.3 \pi_A - 0.5 \pi_B + 0.7 \pi_C = 0$ 同乘以 10 得： $3 \pi_A - 5 \pi_B + 7 \pi_C = 0 \quad \cdots \text{(式 2)}$

將 (式 1) 代入 (式 2)： $3 \pi_A - 5 \pi_B + 7(4 \pi_A - 3 \pi_B) = 0$ $3 \pi_A - 5 \pi_B + 28 \pi_A - 21 \pi_B = 0$ $31 \pi_A - 26 \pi_B = 0 \implies \pi_B = \frac{31}{26} \pi_A$

再代回 (式 1) 求 $\pi_C$： $\pi_C = 4 \pi_A - 3 \left(\frac{31}{26} \pi_A\right) = \left(4 - \frac{93}{26}\right) \pi_A = \frac{11}{26} \pi_A$

利用全機率條件 $\pi_A + \pi_B + \pi_C = 1$： $\pi_A + \frac{31}{26} \pi_A + \frac{11}{26} \pi_A = 1$ $\frac{26 + 31 + 11}{26} \pi_A = 1 \implies \frac{68}{26} \pi_A = 1 \implies \pi_A = \frac{26}{68} = \frac{13}{34}$

解得各狀態穩定機率之精確分數與小數值（四捨五入至小數點後第四位）：

• $\pi_A = \frac{13}{34} \approx 0.3824$（即 $38.24\%$）
• $\pi_B = \frac{31}{26} \times \frac{26}{68} = \frac{31}{68} \approx 0.4559$（即 $45.59\%$）
• $\pi_C = \frac{11}{26} \times \frac{26}{68} = \frac{11}{68} \approx 0.1618$（即 $16.18\%$）

(三) 計算兩個月後、三個月後及長期的市場佔有率

給定目前（第 0 個月）市場佔有率向量： $\pi^{(0)} = [0.4, 0.5, 0.1]$