107 地方特考三等 工業工程 作業研究 考古題詳解

核心觀念

本題屬於作業研究（Operations Research）中的多期人力規劃線性規劃模型（Multi-period Workforce Planning LP Model），主要考核以下核心觀念與技巧：

1. 決策變數的設定時點：區分「具備完整獨立產能的現有技術工人」與「尚在培訓期的新聘工人」。
2. 多期人力動態平衡方程式（Workforce Balance Equations）：以離職率（耗損率）與結訓新進人員，連結相鄰月份的人力庫存關係。
3. 有效工時產能限制（Capacity Constraints）：新進人員在受訓期間非但無法獨立提供生產工時，反而需要資深技術工人投入工時輔導，故資深工人的總可用工時需扣除培訓負擔。
4. 成本極小化目標函數（Cost Minimization）：涵蓋正式員工薪資與受訓員工薪資。

解題方法

步驟一：定義時間指標與決策變數

令月份指標 $t \in \{1, 2, 3, 4\}$ 分別代表第一、二、三、四個月。

• $W_t$：第 $t$ 個月中，具備完整生產能力之正式技術工人人數（人）。
• $H_t$：第 $t$ 個月開始接受在職訓練之新聘工人人數（人）。（即於第 $t-1$ 個月底聘入、第 $t$ 個月受訓、第 $t$ 個月底結訓）。

已知初始條件：第 1 個月已有聘用之技術工人數 $W_1 = 30$。

步驟二：建立目標函數（極小化總薪資成本）

• 正式技術工人每人每月薪資為 $10,000$ 元。
• 受訓新工每人每月薪資為 $5,000$ 元。
• 未來四個月之總薪資成本為： $\min Z = \sum_{t=1}^{4} (10,000 W_t + 5,000 H_t)$

步驟三：推導限制條件

1. 工作時數需求限制（工時產能限制）：

• 每位正式技術工人每月至多可工作 $160$ 小時，共可提供 $160 W_t$ 小時。
• 每位新聘工人需接受 $40$ 小時在職輔導，該輔導工時必須由正式技術工人提供，因而佔用正式工人的生產工時 $40 H_t$ 小時。
• 各月份可用於實際生產之技術工時，必須大於或等於該月份的工時需求 $D_t$：
• 第 1 月（$D_1 = 3,000$）：$160 W_1 - 40 H_1 \ge 3,000$
• 第 2 月（$D_2 = 3,500$）：$160 W_2 - 40 H_2 \ge 3,500$
• 第 3 月（$D_3 = 5,000$）：$160 W_3 - 40 H_3 \ge 5,000$
• 第 4 月（$D_4 = 4,500$）：$160 W_4 - 40 H_4 \ge 4,500$

2. 人力動態銜接限制（動態平衡方程式）：

• 每個月底有 $10\%$ 的技術工人離職，故留下之留存率為 $1 - 10\% = 90\%$（即 $0.9 W_t$）。
• 在第 $t$ 個月受訓滿一個月的新工人 $H_t$，於第 $t$ 個月底結訓，並於第 $t+1$ 個月起正式具備完整工作能力。
• 因此，第 $t+1$ 個月的正式技術工人數等於「前一月留任之正式工人」加上「前一月結訓之新工人」：
• 第 2 月：$W_2 = 0.9 W_1 + H_1$

核心觀念

1. 原問題與對偶問題之轉換規則（Primal-Dual Relationships）： 對於極大化（$\max$）之線性規劃原問題，轉換為極小化（$\min$）對偶問題時，變數與限制式之對應規則如下：

• 原問題之目標函數係數向量 $\mathbf{c}$ 轉為對偶問題之右端常數項（RHS）。
• 原問題之右端常數項 $\mathbf{b}$ 轉為對偶問題之目標函數係數向量。
• 原問題之係數矩陣 $\mathbf{A}$ 轉置為 $\mathbf{A}^T$。
• 限制式與對偶變數符號對應：
• 原問題第 $i$ 個限制式為「$=$」$\iff$ 對偶變數 $y_i$ 為「無符號限制（URS, unrestricted in sign）」。
• 原問題第 $i$ 個限制式為「$\leq$」$\iff$ 對偶變數 $y_i \geq 0$。
• 原問題變數符號與對偶限制式對應：
• 原問題變數 $x_j \leq 0 \iff$ 對偶問題第 $j$ 個限制式為「$\leq$」。
• 原問題變數 $x_j \geq 0 \iff$ 對偶問題第 $j$ 個限制式為「$\geq$」。
• 原問題變數 $x_j$ 為「無符號限制（URS）」$\iff$ 對偶問題第 $j$ 個限制式為「$=$」。

2. 互補差額定理（Complementary Slackness Theorem）： 設 $\mathbf{x}^*$ 為原問題可行解，$\mathbf{y}^*$ 為對偶問題可行解，則 $\mathbf{x}^*$ 與 $\mathbf{y}^*$ 分別為兩問題最佳解之充分且必要條件為：

• 若對偶變數 $y_i^* > 0$，則原問題第 $i$ 個限制式必成立等式（無差額）。
• 若對偶問題第 $j$ 個限制式為嚴格不等式（存在非零差額），則對應之原問題變數必為邊界值 $x_j^* = 0$。

3. 強對偶定理（Strong Duality Theorem）： 若原問題與對偶問題皆有可行解，則兩者皆存在最佳解，且最佳目標函數值相等，即 $Z^* = W^*$。

解題方法

(一) 建構並求解此問題之對偶問題

1. 對偶變數設定：

• 令 $y_1$ 對應原問題第 1 個限制式（等式「$=$」），故 $y_1$ 為無符號限制（unrestricted in sign, URS）。
• 令 $y_2$ 對應原問題第 2 個限制式（「$\leq$」），故 $y_2 \geq 0$。

2. 建構對偶限制式：

• 對應變數 $x_1 \leq 0$：第 1 個對偶限制式為「$\leq$」 $-y_1 - y_2 \leq 3$
• 對應變數 $x_2 \geq 0$：第 2 個對偶限制式為「$\geq$」 $y_1 + y_2 \geq 4$
• 對應變數 $x_3$（題目未特別規範，為無符號限制 URS）：第 3 個對偶限制式為「$=$」 $y_1 - y_2 = 2$

3. 完整對偶問題數學模型： 極小化 $W = 4y_1 + 6y_2$ 受限於 $-y_1 - y_2 \leq 3 \quad \text{（即 } y_1 + y_2 \geq -3 \text{）}$ $y_1 + y_2 \geq 4$ $y_1 - y_2 = 2$ $y_1 \text{ 無符號限制 (URS)},\quad y_2 \geq 0$

4. 求解對偶問題： 利用代入消去法與可行域分析：

• 由第 3 式等式限制得： $y_1 = y_2 + 2$
• 將 $y_1 = y_2 + 2$ 代入第 2 式 $y_1 + y_2 \geq 4$： $(y_2 + 2) + y_2 \geq 4 \implies 2y_2 \geq 2 \implies y_2 \geq 1$
• 將 $y_1 = y_2 + 2$ 代入第 1 式 $-y_1 - y_2 \leq 3$： $-(y_2 + 2) - y_2 \leq 3 \implies -2y_2 \leq 5 \implies y_2 \geq -2.5$
• 綜合變數限制 $y_2 \geq 0$ 與上述條件，對偶問題之可行解集合為： $y_2 \geq 1,\quad y_1 = y_2 + 2$

核心觀念

1. 0-1 整數線性規劃（Binary Integer Linear Programming, BILP）： 本題屬於資源配置問題。由於各產品的銷售利潤隨廣告時段數之變化呈非線性、非凹（邊際報酬非遞減，例如產品 2 由 1 增至 2 時段之邊際利潤為 $0$，由 2 增至 3 時段之邊際利潤為 $2$），無法直接以單一整數變數乘上固定單價建立線性目標函數。因此，必須引入 0-1 二元變數（Binary Variables）將離散決策與跳躍利潤進行「線性化」。
2. 多重互斥選擇限制（Multiple-Choice Constraints）： 每種產品只能被指定一種廣告時段數量（包含分配 0 個時段），各狀態彼此互斥，限制式總和必須為 1（或若不定義 0 時段變數時，其和小於等於 1）。
3. 背包容量限制（Knapsack Constraint）： 各產品實際消耗的廣告時段總量受限於總購買量上限 5 個時段。

解題方法

1. 定義決策變數

令二元決策變數 $x_{ij} \in \{0, 1\}$ 表示產品 $i$ 是否分配 $j$ 個電視廣告時段： $x_{ij} = \begin{cases} 1, & \text{若產品 } i \text{ 分配 } j \text{ 個電視廣告時段} \\ 0, & \text{其他} \end{cases}$ 其中：

• 產品編號 $i \in \{1, 2, 3\}$
• 時段數量 $j \in \{0, 1, 2, 3\}$

令 $P_{ij}$ 為產品 $i$ 分配 $j$ 個時段所獲得的利潤（百萬元）。由題意表格可知：

• 產品 1：$P_{10} = 0,\; P_{11} = 2,\; P_{12} = 3,\; P_{13} = 3$
• 產品 2：$P_{20} = 0,\; P_{21} = 2,\; P_{22} = 2,\; P_{23} = 4$
• 產品 3：$P_{30} = 0,\; P_{31} = 1,\; P_{32} = 3,\; P_{33} = 4$

2. 建立目標函數

最大化 3 種產品的總利潤 $Z$（百萬元）： $\text{Max } Z = \sum_{i=1}^3 \sum_{j=0}^3 P_{ij} x_{ij}$ 將利潤係數展開代入（$P_{i0} = 0$ 項省略）： $\text{Max } Z = 2x_{11} + 3x_{12} + 3x_{13} + 2x_{21} + 2x_{22} + 4x_{23} + 1x_{31} + 3x_{32} + 4x_{33}$

3. 建立限制條件

• 互斥選擇限制（每種產品恰好分配一種時段數量狀態）： $\sum_{j=0}^3 x_{ij} = 1, \quad \forall i \in \{1, 2, 3\}$ 展開如下： $x_{10} + x_{11} + x_{12} + x_{13} = 1$ $x_{20} + x_{21} + x_{22} + x_{23} = 1$ $x_{30} + x_{31} + x_{32} + x_{33} = 1$

• 總廣告時段限制（總使用時段數不得超過 5 個）： $\sum_{i=1}^3 \sum_{j=1}^3 j \cdot x_{ij} \le 5$ 展開如下： $(x_{11} + 2x_{12} + 3x_{13}) + (x_{21} + 2x_{22} + 3x_{23}) + (x_{31} + 2x_{32} + 3x_{33}) \le 5$

• 變數整數與二元限制： $x_{ij} \in \{0, 1\}, \quad \forall i \in \{1, 2, 3\}, \; j \in \{0, 1, 2, 3\}$

選項分析

本題為非選擇題（計算建模題），針對考生作答時常見的模型設定方式進行比較分析：

1. 二元指標變數法（本解法採用，標準解答）： 定義 $x_{ij} \in \{0, 1\}$ 表示「產品 $i$ 是否配置 $j$ 個時段」。

核心觀念

本題評量離散時間馬可夫鏈（Discrete-Time Markov Chain, DTMC）之「長期穩態機率」（Steady-State Probabilities / Stationary Distribution）。

1. 遍歷馬可夫鏈（Ergodic Markov Chain）： 本題狀態空間有限，且所有狀態彼此互通（不可約，Irreducible），亦無固定週期循環（非週期性，Aperiodic），因此必存在唯一的長期穩態機率向量 $\pi$。
2. 平衡方程式（Balance Equations）： 設狀態轉移機率矩陣為 $P$，穩態機率列向量為 $\pi = [\pi_1, \pi_2, \pi_3]$，長期動態平衡滿足： $\pi P = \pi$
3. 正規化條件（Normalizing Condition）： 依全機率公理，所有互斥狀態的長期機率總和必為 1： $\sum_{i} \pi_i = 1 \quad (\pi_i \ge 0)$

解題方法

步驟一：定義狀態與轉移機率矩陣

定義系統的三個互斥狀態：

• 狀態 1：良
• 狀態 2：普通
• 狀態 3：差

依題目之每日轉移機率表，列（第 $n$ 日）為出發狀態，行（第 $n+1$ 日）為到達狀態，建構一步轉移機率矩陣 $P$： $P = \begin{bmatrix} 0.3 & 0.5 & 0.2 \\ 0.4 & 0.5 & 0.1 \\ 0.2 & 0.6 & 0.2 \end{bmatrix}$

步驟二：建立聯立方程式

設長期穩態機率向量為 $\pi = [\pi_1, \pi_2, \pi_3]$，其中 $\pi_1$ 代表空氣品質為「良」之天數所占比例。 根據 $\pi P = \pi$ 展開各行之方程式：

1. 由第 1 行（良）： $0.3\pi_1 + 0.4\pi_2 + 0.2\pi_3 = \pi_1 \implies 7\pi_1 - 4\pi_2 - 2\pi_3 = 0$
2. 由第 2 行（普通）： $0.5\pi_1 + 0.5\pi_2 + 0.6\pi_3 = \pi_2 \implies 5\pi_1 - 5\pi_2 + 6\pi_3 = 0$
3. 由第 3 行（差）： $0.2\pi_1 + 0.1\pi_2 + 0.2\pi_3 = \pi_3 \implies 2\pi_1 + \pi_2 - 8\pi_3 = 0$

由於轉移機率矩陣各列之和為 1，上述三式彼此線性相依（必有一式為冗餘方程式）。解題時取其中任意兩式，並結合正規化條件： $\pi_1 + \pi_2 + \pi_3 = 1$

步驟三：代入消去求解

由第 3 行方程式可得 $\pi_2$ 與 $\pi_1, \pi_3$ 之關係式： $\pi_2 = 8\pi_3 - 2\pi_1$

核心觀念

本題評量網路最佳化（Network Optimization）​的兩大核心主題：

1. 最大流量問題（Maximum Flow Problem, MFP）轉化為最小成本流量問題（Minimum Cost Flow Problem, MCFP）：

• 最大流量問題旨在將源點（source）$s$ 到匯點（sink）$t$ 的總流量最大化。
• 最小成本流量問題是網路規劃的一般化模型，其標準形式要求所有節點滿足流量守恆，且每條弧具有單位成本、流量下限與上限。
• 轉換標準手法：新增一條由匯點 $F$ 指回源點 $A$ 的虛擬回流弧 $(F, A)$，設定其單位成本為 $-1$、容量為 $\infty$；所有原始網路弧的單位成本設為 $0$；所有節點的淨供給量皆設為 $0$（滿足流入等於流出）。透過最小化總成本 $\min Z = -x_{FA}$，等價於最大化流經網路的總流量 $x_{FA}$。

2. 有界變數之網路單形法（Network Simplex Method with Bounded Variables）：

• 網路節點數為 $n = 6$，基底對應於一棵包含 $n - 1 = 5$ 條樹弧的生成樹（Spanning Tree, $T$）。
• 非樹弧（非基變數）分為兩類：處於流量下限 $0$ 者（記為 $L$）與處於流量上限 $u_{ij}$ 者（記為 $U$）。
• 節點位能（對偶變數）：任選一根節點（如 $y_A = 0$），對所有樹弧 $(i, j) \in T$，滿足互補鬆弛條件 $y_i - y_j = c_{ij}$。
• 折減成本（Reduced Cost）：非樹弧 $(i, j)$ 之折減成本為 $\bar{c}_{ij} = c_{ij} - (y_i - y_j)$。
• 最適性條件：
• 若 $(i, j) \in L$（$x_{ij} = 0$），需 $\bar{c}_{ij} \ge 0$。
• 若 $(i, j) \in U$（$x_{ij} = u_{ij}$），需 $\bar{c}_{ij} \le 0$。
• 樞紐變換（Pivoting）：選取違反最適性條件的非樹弧為進基弧，與樹弧形成唯一環路，計算最大可調整流量 $\theta$ 更新流量，並將達到界限的弧作為出基弧移出生成樹。

解題方法

(一) 將最大流量問題轉換成最小成本流量問題

轉換步驟：

1. 節點淨供給量設定： 令節點集合 $V = \{A, B, C, D, E, F\}$。所有節點之淨供給量（Net Supply）均設為 $0$，即： $b_i = 0, \quad \forall i \in V$ 這表示網路內部每一節點皆維持嚴格的流量守恆（總流出量等於總流入量）。

2. 原有弧參數設定： 原網路中每條有向弧 $(i, j)$：

• 單位運送成本：$c_{ij} = 0$。
• 流量下限：$l_{ij} = 0$。
• 流量上限（容量）：維持原容量 $u_{ij}$。 即 $u_{AB}=9, u_{AC}=7, u_{CB}=6, u_{BD}=7, u_{BE}=3, u_{CE}=8, u_{DF}=2, u_{EF}=5$。

3. 新增虛擬回流弧： 由匯點 $F$ 連結回源點 $A$ 增設一條有向弧 $(F, A)$：

• 單位運送成本：$c_{FA} = -1$。
• 流量下限：$l_{FA} = 0$。
• 流量上限：$u_{FA} = \infty$（或設為上界 $M \ge 16$）。

4. 數學規劃模型：

• 目標函數： $\min Z = \sum_{(i,j)} c_{ij} x_{ij} = - x_{FA}$ （最小化 $-x_{FA}$ 即等價於最大化自 $A$ 至 $F$ 之淨流量 $x_{FA}$）
• 限制條件： $\sum_{\{j:(i,j) \in A\}} x_{ij} - \sum_{\{k:(k,i) \in A\}} x_{ki} = 0, \quad \forall i \in \{A, B, C, D, E, F\}$ $0 \le x_{ij} \le u_{ij}, \quad \forall (i, j) \in \text{原網路弧}$ $0 \le x_{FA} < \infty$

(二) 以網路單形法求解最小成本流量問題

網路中節點數 $n = 6$，生成樹需包含 $5$ 條樹弧。

【初始基可行解設定（Iteration 0）】

• 選定初始生成樹 $T_0$： 選取原網路弧中無環且連通所有節點的 5 條弧作為樹弧： $T_0 = \{ (A, B), (A, C), (B, D), (B, E), (D, F) \}$
• 非樹弧集合：
• 處於下限集合 $L = \{ (C, B), (C, E), (E, F), (F, A) \}$，流量均為 $0$。
• 處於上限集合 $U = \emptyset$。
• 初始樹弧流量： 由流量守恆條件（因所有非樹弧流量為 0 且 $b_i = 0$），所有樹弧流量均為 $0$： $x_{AB} = 0, \quad x_{AC} = 0, \quad x_{BD} = 0, \quad x_{BE} = 0, \quad x_{DF} = 0$ 所有變數皆滿足 $0 \le x_{ij} \le u_{ij}$，為一可行的初始基可行解，總成本 $Z = 0$。

【第 1 次疊代（Iteration 1）】

1. 計算節點位能 $y_i$： 對樹弧 $(i, j) \in T_0$，滿足 $y_i - y_j = c_{ij} = 0$。 令根節點位能 $y_A = 0$：

• $(A, B) \in T_0 \implies y_B = y_A = 0$
• $(A, C) \in T_0 \implies y_C = y_A = 0$
• $(B, D) \in T_0 \implies y_D = y_B = 0$
• $(B, E) \in T_0 \implies y_E = y_B = 0$
• $(D, F) \in T_0 \implies y_F = y_D = 0$ 節點位能為：$(y_A, y_B, y_C, y_D, y_E, y_F) = (0, 0, 0, 0, 0, 0)$。

2. 檢驗非樹弧之折減成本 $\bar{c}_{ij} = c_{ij} - (y_i - y_j)$：

• $(C, B) \in L$：$\bar{c}_{CB} = 0 - (0 - 0) = 0 \ge 0$
• $(C, E) \in L$：$\bar{c}_{CE} = 0 - (0 - 0) = 0 \ge 0$
• $(E, F) \in L$：$\bar{c}_{EF} = 0 - (0 - 0) = 0 \ge 0$
• $(F, A) \in L$：$\bar{c}_{FA} = -1 - (y_F - y_A) = -1 - (0 - 0) = -1 < 0$（違反最適性）

3. 樞紐變換：

• 進基弧：$(F, A)$。
• 形成環路：加入 $(F, A)$ 後，與樹弧構成有向環路 $F \rightarrow A \rightarrow B \rightarrow D \rightarrow F$。 環路弧方向皆為正向：$(F, A), (A, B), (B, D), (D, F)$。
• 決定最大增流量 $\theta_1$： $\theta_1 = \min \{ u_{FA} - x_{FA}, u_{AB} - x_{AB}, u_{BD} - x_{BD}, u_{DF} - x_{DF} \}$ $\theta_1 = \min \{ \infty - 0, 9 - 0, 7 - 0, 2 - 0 \} = 2$
• 更新流量：
• $x_{FA} = 0 + 2 = 2$
• $x_{AB} = 0 + 2 = 2$
• $x_{BD} = 0 + 2 = 2$
• $x_{DF} = 0 + 2 = 2 = u_{DF}$（達到容量上限）
• 出基弧：$(D, F)$ 達到容量上限，離開樹弧集合並進入 $U$。
• 新生成樹：$T_1 = \{ (A, B), (A, C), (B, D), (B, E), (F, A) \}$。
• 目前目標函數值 $Z = -1 \times 2 = -2$。

【第 2 次疊代（Iteration 2）】

1. 計算節點位能 $y_i$： 令 $y_A = 0$：

• $(F, A) \in T_1 \implies y_F - y_A = c_{FA} = -1 \implies y_F = -1$
• $(A, B) \in T_1 \implies y_B = y_A = 0$
• $(A, C) \in T_1 \implies y_C = y_A = 0$
• $(B, D) \in T_1 \implies y_D = y_B = 0$
• $(B, E) \in T_1 \implies y_E = y_B = 0$ 節點位能為：$(y_A, y_B, y_C, y_D, y_E, y_F) = (0, 0, 0, 0, 0, -1)$。

2. 檢驗非樹弧之折減成本：

• $(D, F) \in U$：$\bar{c}_{DF} = 0 - (y_D - y_F) = 0 - (0 - (-1)) = -1 \le 0$（符合上限條件）
• $(C, B) \in L$：$\bar{c}_{CB} = 0 - (0 - 0) = 0 \ge 0$
• $(C, E) \in L$：$\bar{c}_{CE} = 0 - (0 - 0) = 0 \ge 0$
• $(E, F) \in L$：$\bar{c}_{EF} = 0 - (y_E - y_F) = 0 - (0 - (-1)) = -1 < 0$（違反最適性）