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

核心觀念

本題考查作業研究中「整數線性規劃（Integer Linear Programming, ILP）」的模式建構能力，具體應用場景為經典的「多維背包問題（Multi-dimensional Knapsack Problem, MKP）」。

在作業研究模式建構中，必須具備以下三大要素：

1. 決策變數（Decision Variables）：定義決策者所能控制的實體量，包含清楚的物理意義、指標範圍及計量單位。
2. 目標函數（Objective Function）：以數學式量化決策目標（本題為利潤極大化 $\max Z$）。
3. 限制條件（Constraints）：包含系統的外部資源限制（空間上限與重量上限）以及變數本身的數學性質（非負限制與整數限制）。

---

解題方法

題目要求以整數規劃方法建構裝載決策模型。由於題目未限制每種貨物僅有單件，預設每種貨物可裝載多件，變數屬於一般非負整數（General Integer Variables）。若實務上視為每種貨物僅有 1 件，則屬於 0-1 整數規劃；標準模式建構應以一般整數規劃為主。

(一) 決策變數之定義（5 分）

定義決策變數時，必須指明「下標意義」、「物理量」與「單位」：

• 令 $x_i$ 代表貨櫃所裝載第 $i$ 種貨物的件數（單位：件），其中 $i = 1, 2, 3, 4, 5$。

(二) 目標式之建立（10 分）

決策目標為「貨櫃裝載貨品之總利潤最大化」：

• 總利潤 $Z$ 為各貨物裝載量乘以其單位利潤的總和： $\max Z = 9x_1 + 11x_2 + 13x_3 + 14x_4 + 18x_5$ （其中 $Z$ 的單位為萬元）

(三) 限制式之建立（15 分）

系統受到「空間體積上限」、「載重上限」與「非負整數」三類限制：

1. 空間容積限制：總使用體積不可超過貨櫃容量 $300\text{ m}^3$ $4x_1 + 5x_2 + 7x_3 + 9x_4 + 10x_5 \le 300$
2. 總載重量限制：總裝載重量不可超過貨櫃耐重 $160\text{ 噸}$ $11x_1 + 14x_2 + 15x_3 + 17x_4 + 19x_5 \le 160$
3. 非負整數限制：裝載數量不能為負數且必須為不可分割之整數 $x_i \ge 0 \text{ 且 } x_i \in \mathbb{Z}, \quad \forall i \in \{1, 2, 3, 4, 5\}$

延伸求解（最佳裝載方案計算）

本題配分共 30 分，已完整對應三個子題的模式建構。若進一步求解該整數規劃：

1. 資源緊縮度分析：

• 各貨物單位重量所需體積皆在 $0.36 \sim 0.59\text{ m}^3/\text{噸}$ 之間。若重量達上限 $160\text{ 噸}$，體積最多約為 $160 \times (10/19) \approx 84.2\text{ m}^3$，遠小於空間上限 $300\text{ m}^3$。
• 因此「重量限制」為主要瓶頸限制（Binding Constraint），空間限制在最佳解處為寬鬆限制（Slack Constraint）。

2. 單位重量利潤比（Profit-to-Weight Ratio, $c_i/w_i$）：

• 貨物 1：$9 / 11 \approx 0.818$
• 貨物 2：$11 / 14 \approx 0.786$
• 貨物 3：$13 / 15 \approx 0.867$
• 貨物 4：$14 / 17 \approx 0.824$
• 貨物 5：$18 / 19 \approx 0.947$（性價比最高）

3. 整數最佳解配置：

核心觀念

本題評量線性規劃（Linear Programming, LP）中極為重要的「對偶理論（Duality Theory）」與「單形法矩陣形式（Matrix Form of Simplex Method）」，核心觀念包含：

1. 原問題與對偶問題之轉換法則（Primal-Dual Relationships）：

• 最大化（$\text{Max}$）問題轉換為最小化（$\text{Min}$）問題。
• 原問題之右端常數（RHS, $b$）轉換為對偶問題之目標函數係數。
• 原問題之目標函數係數（$c$）轉換為對偶問題之右端常數。
• 原問題限制式係數矩陣 $A$ 轉置為 $A^T$ 作為對偶限制式之係數矩陣。
• 標準對稱形式：原問題為 $\le$ 限制式且變數非負時，對偶問題之限制式為 $\ge$ 且對偶變數非負。

2. 最佳單形表與對偶最佳解之對應關係：

• 根據線性規劃矩陣理論，若原問題在最佳基底 $B$ 下，對偶最佳解向量為 $y^* = c_B B^{-1}$。
• 在單形表中，原問題初始為單位矩陣的鬆弛變數（slack variables）$x_4, x_5, x_6$，其在最佳單形表第 0 列（$Z$ 列 / Row 0）所對應的係數即為 $c_B B^{-1} - 0 = y^*$，亦即各限制式之「影子價格（Shadow Price）」。

3. 強對偶定理（Strong Duality Theorem）與互補鬆弛定理（Complementary Slackness Theorem）：

• 原問題與對偶問題若皆有最佳解，則兩者之最佳目標函數值相等（$Z^* = W^*$）。
• 若原問題某限制式之鬆弛變數大於 0（未達緊繃），則對應之對偶變數必為 0。

---

解題方法

(一) 將原問題轉換成對偶問題（Dual Problem）

1. 定義對偶變數： 原問題共有 3 個限制式，分別指派對應的對偶變數：

• 限制式 1 對應對偶變數 $y_1$
• 限制式 2 對應對偶變數 $y_2$
• 限制式 3 對應對偶變數 $y_3$

2. 轉換目標函數： 原問題為 $\text{Max } Z$，右端項係數為 $b = \begin{bmatrix} 15 \\ 12 \\ 8 \end{bmatrix}$； 對偶問題為 $\text{Min } W$，目標函數為： $W = 15y_1 + 12y_2 + 8y_3$

3. 轉換限制式： 原問題之變數 $x_1, x_2, x_3$ 係數與目標值係數 $c = [1, 2, 2]$，轉置後形成對偶問題的 3 個限制式：

• 對應 $x_1$ 欄位：$5y_1 + y_2 + 2y_3 \geq 1$
• 對應 $x_2$ 欄位：$2y_1 + 4y_2 + 0y_3 \geq 2 \implies 2y_1 + 4y_2 \geq 2$
• 對應 $x_3$ 欄位：$3y_1 + 2y_2 + y_3 \geq 2$

4. 變數符號限制： 因原問題限制式皆為「$\leq$」且原變數皆為「$\geq 0$」，故對偶變數皆為非負： $y_1, y_2, y_3 \geq 0$

綜上所述，對偶問題之完整數學模型為：

$$\begin{aligned} \text{Minimize}\quad & W = 15y_1 + 12y_2 + 8y_3\\ \text{subject to}\quad & 5y_1 + y_2 + 2y_3 \geq 1,\\ & 2y_1 + 4y_2 \geq 2,\\ & 3y_1 + 2y_2 + y_3 \geq 2,\\ & y_1, y_2, y_3 \geq 0. \end{aligned}$$

---

(二) 由最佳單形表讀出對偶問題的最佳解

讀取對偶最佳解主要有以下兩種途徑，兩者結果完全一致：

【途徑一：直接由 Row 0 讀取影子價格】

在標準最大化線性規劃的單形表中：

• 原問題限制式 1、2、3 所加入的鬆弛變數分別為 $x_4, x_5, x_6$。
• 在最佳單形表的 $Z$ 列（Row 0）中，鬆弛變數對應的係數即為對偶變數之最佳值 $y^*$：
• $x_4$ 欄位係數為 $0.5$（即 $\frac{1}{2}$），故 $y_1^* = 0.5$
• $x_5$ 欄位係數為 $0.25$（即 $\frac{1}{4}$），故 $y_2^* = 0.25$

核心觀念

本題屬於作業研究中的**離散時間馬可夫鏈（Discrete-Time Markov Chain, DTMC）**模型，核心觀念包含以下三項：

1. 狀態空間（State Space）與狀態定義： 系統在離散時點 $t \in \{0, 1, 2, \dots\}$（以「年」為單位）處於特定狀態。設狀態空間包含三種互斥且周延的居住地狀態：

• 狀態 1（$R$）：鄉村（Rural）
• 狀態 2（$U$）：城市（Urban）
• 狀態 3（$O$）：移居海外（Overseas）

2. 單步轉換機率矩陣（One-Step Transition Probability Matrix, $P$）： 定義 $P_{ij} = P(X_{t+1} = j \mid X_t = i)$ 為由狀態 $i$ 轉移至狀態 $j$ 的條件機率。轉移矩陣具有隨機矩陣（Stochastic Matrix）之特性：

• 非負性：對所有 $i, j$，$P_{ij} \ge 0$
• 列和為 1（Row Sum = 1）：對所有狀態 $i$，$\sum_{j} P_{ij} = 1$

3. 查普曼－柯爾莫哥洛夫方程式（Chapman-Kolmogorov Equations）與狀態分佈演變：

• $n$ 步轉移機率矩陣可由單步矩陣相乘求得：$P^{(n)} = P^n$。由狀態 $i$ 出發，經過 $n$ 期到達狀態 $j$ 之機率即為 $P^n$ 的第 $i$ 列第 $j$ 行元素 $P_{ij}^{(n)}$。
• 若期初（$t = 0$）的無條件狀態機率分佈行（或列）向量為 $\pi(0) = [\pi_1(0), \pi_2(0), \pi_3(0)]$，則經過 $n$ 年後的狀態分佈向量為： $\pi(n) = \pi(0) P^n = \pi(n-1) P$

---

解題方法

(一) 求轉換機率矩陣（Transition Matrix）

依題意逐列建立各居住地的單步轉移機率：

1. 由鄉村出發（第 1 列）：

• 留鄉村：$P_{11} = 60\% = 0.60$
• 遷往城市：$P_{12} = 20\% = 0.20$
• 移居海外：$P_{13} = 20\% = 0.20$
• 驗算列和：$0.60 + 0.20 + 0.20 = 1.00$

2. 由城市出發（第 2 列）：

• 遷往鄉村：$P_{21} = 3\% = 0.03$
• 留城市：$P_{22} = 90\% = 0.90$
• 移居海外：$P_{23} = 7\% = 0.07$
• 驗算列和：$0.03 + 0.90 + 0.07 = 1.00$

3. 由海外出發（第 3 列）：

• 遷往鄉村：題意未提及回鄉村定居，故 $P_{31} = 0\% = 0.00$
• 返國定居城市：$P_{32} = 5\% = 0.05$
• 留海外：其餘即 $100\% - 5\% = 95\%$，故 $P_{33} = 0.95$
• 驗算列和：$0.00 + 0.05 + 0.95 = 1.00$

以狀態順序［鄉村, 城市, 海外］表示，其轉換機率矩陣為： $P = \begin{bmatrix} 0.60 & 0.20 & 0.20 \\ 0.03 & 0.90 & 0.07 \\ 0.00 & 0.05 & 0.95 \end{bmatrix}$

---

(二) 小邱兩年後遷往城市的機率

小邱目前居住在鄉村，初始狀態為狀態 1（鄉村）。兩年後他遷往城市的機率，即為兩步轉移機率 $P_{12}^{(2)}$。

利用查普曼－柯爾莫哥洛夫展開式（矩陣第 1 列與第 2 行的內積）： $P_{12}^{(2)} = \sum_{k=1}^{3} P_{1k} P_{k2} = P_{11} P_{12} + P_{12} P_{22} + P_{13} P_{32}$

代入數值計算： $P_{12}^{(2)} = (0.60 \times 0.20) + (0.20 \times 0.90) + (0.20 \times 0.05)$ $P_{12}^{(2)} = 0.12 + 0.18 + 0.01 = 0.31$

因此，小邱兩年後遷往城市的機率為 $0.31$（即 $31\%$）。

---

(三) 三年後居住在各地的百分比

設期初（$t = 0$）的人口分佈列向量為： $\pi(0) = [\pi_1(0), \pi_2(0), \pi_3(0)] = [0.20, 0.65, 0.15]$

採逐年遞推方式計算 $\pi(t) = \pi(t-1) P$：

1. 一年後的人口分佈 $\pi(1) = \pi(0) P$：

• $\pi_1(1) = 0.20(0.60) + 0.65(0.03) + 0.15(0.00) = 0.12 + 0.0195 + 0 = 0.1395$
• $\pi_2(1) = 0.20(0.20) + 0.65(0.90) + 0.15(0.05) = 0.04 + 0.585 + 0.0075 = 0.6325$
• $\pi_3(1) = 0.20(0.20) + 0.65(0.07) + 0.15(0.95) = 0.04 + 0.0455 + 0.1425 = 0.2280$
• 驗算：$0.1395 + 0.6325 + 0.2280 = 1.0000$

核心觀念

本題評量**決策分析（Decision Analysis）中的決策樹（Decision Trees）建構與期望值準則（Expected Monetary Value, EMV）**之計算。

1. 決策樹基本構成要素：

• 決策節點（Decision Node）：以方形 $\square$ 表示，代表決策者可主動選擇的行動方案（如：玩或不玩）。
• 機會節點（Chance Node）：以圓形 $\bigcirc$ 表示，代表不受決策者控制的隨機事件狀態（如：投擲銅板之正反面）。
• 終端節點（Terminal Node / Leaf）：以三角形 $\triangle$ 或直接標註數值表示，代表路徑之最終結果（報酬或損失）。

2. 機率獨立性與樣本空間：

• 假設為公正銅板，每次投擲正面（$H$）與反面（$T$）之機率皆為 $P(H) = P(T) = 0.5$。
• 連續投擲三次之樣本空間包含 $2^3 = 8$ 種基本事件，各事件機率均為 $(0.5)^3 = \frac{1}{8} = 0.125$。

3. 期望收益（Expected Value）評估：

• 期望值計算公式：$E(X) = \sum_{i} x_i \cdot P(x_i)$。
• 決策評估通常使用逆向歸納法（Backward Induction / Rollback Procedure），由右至左計算各節點之期望值。

---

解題方法

(一) 建立決策樹

1. 基本假設與參數設定：

• 銅板為公正銅板，每次出現正面（$H$）與反面（$T$）之機率各為 $0.5$。
• 參賽成本：支付 $200。
• 獲勝條件：連續三次相同（即 $HHH$ 或 $TTT$），獲得彩金 $400。
• 未獲勝條件：其餘 $6$ 種情況，獲得彩金 $0。
• 終端淨收益（Net Payoff）＝ 獲得彩金 $-$ 參賽成本 $200。

2. 決策樹結構繪製：

• 起始為決策節點 $\square$，分為兩個決策分支：「玩遊戲」與「不玩遊戲」。
• 若選擇「不玩遊戲」：淨收益為 $0。
• 若選擇「玩遊戲」：進入連續三次丟銅板之隨機事件，以三階段機會節點 $\bigcirc$ 展開。

決策樹展開架構如下圖所示：

[決策節點] [第一次投擲] [第二次投擲] [第三次投擲] 結果 (路徑) 路徑機率 獲得彩金 終端淨收益
 ┌─ 正 (0.5) ─→ HHH 1/8 $400 +$200
 ┌─ 正 (0.5) ─○ (N4) ─┤
 │ └─ 反 (0.5) ─→ HHT 1/8 $0 -$200
 ┌─ 正 (0.5) ─○ (N2) ─┤
 │ │ ┌─ 正 (0.5) ─→ HTH 1/8 $0 -$200
 │ └─ 反 (0.5) ─○ (N5) ─┤
 │ └─ 反 (0.5) ─→ HTT 1/8 $0 -$200
 ┌─ 玩 (支付 $200) ─○ (N1)
 │ [EMV = -$100] │ ┌─ 正 (0.5) ─→ THH 1/8 $0 -$200
 │ │ ┌─ 正 (0.5) ─○ (N6) ─┤
 │ │ │ └─ 反 (0.5) ─→ THT 1/8 $0 -$200
 │ └─ 反 (0.5) ─○ (N3) ─┤
 ───□ │ │ ┌─ 正 (0.5) ─→ TTH 1/8 $0 -$200
 │ └─ 反 (0.5) ─○ (N7) ─┤
 │ └─ 反 (0.5) ─→ TTT 1/8 $400 +$200
 │
 └─ 不玩 ───────────────────────────────────────────────────────────────→ 不玩 1 $0 $0
 [EMV = $0]

3. 逆向歸納數值推導（Rollback）：

• 節點 $N_4$ 期望淨收益：$0.5 \times (+200) + 0.5 \times (-200) = 0$
• 節點 $N_5$ 期望淨收益：$0.5 \times (-200) + 0.5 \times (-200) = -200$
• 節點 $N_6$ 期望淨收益：$0.5 \times (-200) + 0.5 \times (-200) = -200