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

核心觀念

本題評量線性規劃（Linear Programming, LP）中最重要的對偶理論（Duality Theory）​及其應用，包含三大核心工具：

1. 對稱對偶轉換規則（Symmetric Dual Rules）： 主要問題（Primal）為極小化（$\min$）且限制式均為「$\geq$」、變數非負時，其對偶問題（Dual）必為極大化（$\max$）、限制式為「$\leq$」、變數非負。

• 主要問題的右端項（RHS）$b$ 成為對偶問題的目標函數係數。
• 主要問題的目標函數係數 $c$ 成為對偶問題的右端項。
• 係數矩陣 $A$ 在對偶問題中轉置為 $A^T$。

2. 圖解法（Graphical Method）： 主要問題有 3 個決策變數，無法直接於二維平面圖解；對偶問題僅有 2 個決策變數（對應主要問題的 2 個限制式），可輕易於二維坐標平面繪出可行解區域並找出最佳解。
3. 互補差額定理（Complementary Slackness Theorem, CST）： 設 $X^*$ 與 $Y^*$ 分別為主要問題與對偶問題之可行解，則兩者同時為最佳解的充要條件為：

• 若對偶變數 $Y_i^* > 0$，則主要問題第 $i$ 個限制式必為等式（緊縮，Tight / Binding）。
• 若主要問題變數 $X_j^* > 0$，則對偶問題第 $j$ 個限制式必為等式；反之，若對偶問題第 $j$ 個限制式為嚴格不等式（存在鬆弛差額，Slack $> 0$），則 $X_j^* = 0$。

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

解題方法

(一) 寫出主要問題的對偶問題（Dual Problem）

令主要問題之兩道限制式對應的對偶變數分別為 $Y_1$ 與 $Y_2$。

1. 目標函數： 主要問題為極小化 $\min Z$，對偶問題為極大化 $\max W$。目標函數係數為主要問題之 RHS： $W = 3Y_1 + 5Y_2$

2. 限制式： 主要問題之各變數 $X_1, X_2, X_3$ 的技術係數行向量，構成對偶問題之各列限制式，右端值為對應之目標函數係數：

• 對應 $X_1$：$Y_1 + 2Y_2 \leq 13$
• 對應 $X_2$：$3Y_1 + 2Y_2 \leq 19$
• 對應 $X_3$：$Y_1 + Y_2 \leq 10$

3. 變數非負限制： 主要問題限制式方向均為 $\geq$ 且為極小化問題，對應之對偶變數皆為非負： $Y_1 \geq 0,\quad Y_2 \geq 0$

綜上所述，對偶問題為： $\text{極大化}\quad W = 3Y_1 + 5Y_2$ 受限於： $Y_1 + 2Y_2 \leq 13 \quad \text{--- (式 1)}$ $3Y_1 + 2Y_2 \leq 19 \quad \text{--- (式 2)}$ $Y_1 + Y_2 \leq 10 \quad \text{--- (式 3)}$ $Y_1 \geq 0,\quad Y_2 \geq 0$

(二) 利用對偶性質及圖解法求出原始問題的最佳解

本題策略：先以圖解法求出對偶問題最佳解 $(Y_1^*, Y_2^*)$，再藉由互補差額定理反求原始主要問題之最佳解 $(X_1^*, X_2^*, X_3^*)$。

步驟一：以圖解法求解對偶問題

繪製第一象限（$Y_1 \geq 0, Y_2 \geq 0$）之邊界直線：

• $L_1: Y_1 + 2Y_2 = 13 \implies$ 截距點為 $(13, 0)$ 與 $(0, 6.5)$。
• $L_2: 3Y_1 + 2Y_2 = 19 \implies$ 截距點為 $\left(\frac{19}{3}, 0\right)$ 與 $(0, 9.5)$。
• $L_3: Y_1 + Y_2 = 10 \implies$ 截距點為 $(10, 0)$ 與 $(0, 10)$。

可行解區域（Feasible Region）為由原點及各限制線朝原點側所圍成的多邊形凸集，其各極值點（Corner Points）座標如下：

1. 原點：$(0, 0)$
2. $Y_1$ 軸截點（由式 2 限制）：$\left(\frac{19}{3}, 0\right)$
3. $L_1$ 與 $L_2$ 之交點： 聯立解： $\begin{cases} Y_1 + 2Y_2 = 13 \\ 3Y_1 + 2Y_2 = 19 \end{cases}$ 兩式相減得 $2Y_1 = 6 \implies Y_1 = 3$；代回得 $2Y_2 = 10 \implies Y_2 = 5$。 檢驗第三式：$Y_1 + Y_2 = 3 + 5 = 8 \leq 10$，符合可行解要求，故交點為 $(3, 5)$。
4. $Y_2$ 軸截點（由式 1 限制）：$(0, 6.5)$

核心觀念

本題評量線性規劃（Linear Programming, LP）中單純法運算機制與主要—對偶問題（Primal-Dual Relationship）轉換法則兩大核心重點：

1. 單純法與對偶單純法的對偶本質：

• 一般單純法（Primal Simplex Method）：在滿足「主要可行性（Primal Feasibility）」的前提下開始，反覆進行樞紐運算逐步消除「對偶不可行性」，直到滿足「對偶可行性（Dual Feasibility，即最佳化條件）」為止。搜尋路徑沿著可行解區域（Feasible Region）的頂點移動，目標函數值單調遞增（極大化問題）。
• 對偶單純法（Dual Simplex Method）：在滿足「對偶可行性（Dual Feasibility，即檢驗行滿足最佳條件）」但「主要不可行（Primal Infeasible，即存在常數項 $b_i < 0$）」的狀態下開始，透過樞紐運算逐步修復主要可行性，直到所有 $b_i \ge 0$ 為止。搜尋路徑在外圍不可行區移動，目標函數值單調遞減逼近最佳解。

2. 主要問題與對偶問題的對應關係：

• 線性規劃的主要問題與對偶問題之間存在對稱性與嚴格的一對一對偶結構：
• 主要問題的第 $i$ 個限制式對應對偶問題的第 $i$ 個決策變數。
• 主要問題的第 $j$ 個決策變數對應對偶問題的第 $j$ 個限制式。
• 限制式不等號方向（$\le$、$\ge$、$=$）與變數符號限制（$\ge 0$、$\le 0$、無限制符號 URS）遵循「常態（Sensible / Normal）」、「非常態（Odd / Abnormal）」與「奇異（Bizarre）」的對偶互補法則（即 SOB 規則）。

解題方法

1. 第 (一) 子題： 針對極大化問題（$\max Z$），從起始條件、終止條件、離開變數（Pivot Row）決定原則、進入變數（Pivot Column）決定原則、比值檢定公式、搜尋路徑與幾何意義、目標函數值變化以及典型應用情境八大維度進行結構化列表比較。

2. 第 (二) 子題： 將主要問題分為「極大化」與「極小化」兩種基本形式，並各自將「限制式與變數」的全部組合（$\le$、$\ge$、$=$ 與 $\ge 0$、$\le 0$、URS）以清晰的對照表呈現，使限制式類型與對偶變數符號、主要變數符號與對偶限制式類型的雙向對應關係完全具備規範性。

選項分析

本題為申論與列表比較題，無選擇題選項。重點在於概念界定精確，不得混淆樞紐列與樞紐行選取的前後次序（一般單純法為「先選行再選列」，對偶單純法為「先選列再選行」）。

解題技巧

1. 計算程序的「鏡像」記憶訣竅：

• 一般單純法：先選進入變數（行），再選離開變數（列）。選行看檢驗列（$c_j - z_j > 0$），選列以常數項除以正係數做最小比值檢定（$\min \{b_i / a_{ij} \mid a_{ij} > 0\}$）。
• 對偶單純法：先選離開變數（列），再選進入變數（行）。選列看常數項最負者（$\min \{b_i \mid b_i < 0\}$），選行以檢驗列除以負係數取絕對值做最小比值檢定（$\min \{|(c_j - z_j) / a_{rj}| \mid a_{rj} < 0\}$）。

2. 對偶轉換 SOB 規則速記法：

• 目標函數方向相反：$\max \leftrightarrow \min$。
• 常態配常態（Natural / Sensible）：
• 極大化問題的常態限制式為「$\le$」，對應對偶變數「$\ge 0$」。
• 極小化問題的常態限制式為「$\ge$」，對應對偶變數「$\ge 0$」。
• 等式配無限制（Equality $\leftrightarrow$ URS）：
• 限制式為「$=$」，對應對偶變數「無限制符號（URS）」。
• 變數為「無限制符號（URS）」，對應對偶限制式「$=$」。
• 非常態方向倒轉：
• 極大化若出現「$\ge$」，對偶變數即為「$\le 0$」。
• 極小化若出現「$\le$」，對偶變數即為「$\le 0$」。

【答案】

(一) 一般單純法與對偶單純法之計算程序比較（以極大化問題為例）

以極大化問題 $\max Z = \sum c_j x_j$（檢驗行指標採 $c_j - z_j$）為例，兩者在計算程序上的差異列表比較如下：

核心觀念

本題評量作業研究（Operations Research）中經典的運輸問題（Transportation Problem）​建模與求解能力，核心觀念包含：

1. 不平衡運輸問題（Unbalanced Transportation Problem）：

• 總供給量 $\sum S_i = 50 + 85 + 65 = 200$。
• 總需求量 $\sum D_j = 40 + 90 + 60 = 190$。
• 因總供給大於總需求（$200 > 190$），在線性規劃中供給限制式為「$\le$」；在以運輸表格求解時，須增設一個需求量為 $10$、各廠運費皆為 $0$ 的「虛擬賣場（Dummy Destination）」，使供需達到平衡（$\sum S_i = \sum D_j = 200$）。

2. 禁運路徑之處理（Prohibited Routes）：

• 工廠 3 無法運送至賣場 B。在線性規劃中可直接令決策變數 $x_{3B} = 0$（或不列入模型）；在運輸表格求解時，將該格單位運費設為極大正數 $M$（Big-$M$ 法），防止其被指派。

3. 西北角法（Northwest Corner Method, NWCM）：

• 從表格左上角 $(1, 1)$ 開始依序配銷，快速求得具 $m + n - 1$ 個基本變數的初始基本可行解（Initial Basic Feasible Solution）。

4. 修正分配法（Modified Distribution Method, MODI / $u-v$ 法）：

• 利用對偶變數關係 $u_i + v_j = c_{ij}$（對所有基本格）求出列乘子 $u_i$ 與行乘子 $v_j$。
• 計算非基本格之檢驗數（Reduced Cost）：$\bar{c}_{ij} = c_{ij} - (u_i + v_j)$。
• 極小化問題中，若存在 $\bar{c}_{ij} < 0$，選取最負者為入基變數，藉由閉迴路（Closed Loop）調整指派量 $\theta$，直到所有非基本格之 $\bar{c}_{ij} \ge 0$ 為止。

解題方法

(一) 線性規劃模式（Linear Programming Model）

1. 決策變數定義

設 $x_{ij}$ 為由工廠 $i$ 運送至賣場 $j$ 之產品數量（單位：單位/週），其中 $i \in \{1, 2, 3\}$ 代表工廠 1、2、3；$j \in \{A, B, C\}$ 代表賣場 A、B、C。

2. 目標函數（極小化每週總運輸成本，單位：仟元）

$\min Z = 7x_{1A} + 8x_{1B} + 6x_{1C} + 9x_{2A} + 6x_{2B} + 6x_{2C} + 5x_{3A} + 5x_{3C}$

3. 限制條件

• 工廠生產容量限制（供給限制）： $x_{1A} + x_{1B} + x_{1C} \le 50 \quad \text{（工廠 1）}$ $x_{2A} + x_{2B} + x_{2C} \le 85 \quad \text{（工廠 2）}$ $x_{3A} + x_{3C} \le 65 \quad \text{（工廠 3）}$

• 賣場每週需求限制（需求限制）： $x_{1A} + x_{2A} + x_{3A} = 40 \quad \text{（賣場 A）}$ $x_{1B} + x_{2B} = 90 \quad \text{（賣場 B）}$ $x_{1C} + x_{2C} + x_{3C} = 60 \quad \text{（賣場 C）}$

• 禁運限制與非負限制： $x_{3B} = 0 \quad \text{（工廠 3 無法運送至賣場 B）}$ $x_{ij} \ge 0, \quad \forall i \in \{1, 2, 3\}, \; j \in \{A, B, C\}$

(二) 西北角法求起始解與修正分配法求最佳解

步驟一：建立標準平衡運輸表

1. 總供給 $50 + 85 + 65 = 200$，總需求 $40 + 90 + 60 = 190$。
2. 增設「虛擬賣場 D」，需求量為 $200 - 190 = 10$，各廠至 D 的運費均為 $0$。
3. 工廠 3 至賣場 B 為禁運格，設單位運費為極大值 $M$。

步驟二：以西北角法（NWCM）求起始基本可行解

1. 由最左上角 $(1, A)$ 開始： $x_{1A} = \min(50, 40) = 40$。賣場 A 滿足；工廠 1 剩餘 $10$。
2. 向右移至 $(1, B)$： $x_{1B} = \min(10, 90) = 10$。工廠 1 耗盡；賣場 B 剩餘 $80$。
3. 向下移至 $(2, B)$： $x_{2B} = \min(85, 80) = 80$。賣場 B 滿足；工廠 2 剩餘 $5$。
4. 向右移至 $(2, C)$： $x_{2C} = \min(5, 60) = 5$。工廠 2 耗盡；賣場 C 剩餘 $55$。
5. 向下移至 $(3, C)$： $x_{3C} = \min(65, 55) = 55$。賣場 C 滿足；工廠 3 剩餘 $10$。
6. 向右移至 $(3, D)$： $x_{3D} = \min(10, 10) = 10$。工廠 3 與虛擬賣場 D 同時耗盡。

基本變數個數為 $m + n - 1 = 3 + 4 - 1 = 6$ 個，無退化現象。

初始配銷表（括號內為單位運費）：

起始解總運輸成本： $Z_0 = 40 \times 7 + 10 \times 8 + 80 \times 6 + 5 \times 6 + 55 \times 5 + 10 \times 0 = 280 + 80 + 480 + 30 + 275 + 0 = 1145 \text{ 仟元}$

步驟三：以修正分配法（MODI）迭代求解

【第 1 次迭代】

1. 計算乘子（基本格滿足 $u_i + v_j = c_{ij}$，令 $u_1 = 0$）：

• $(1, A): u_1 + v_A = 7 \implies v_A = 7$
• $(1, B): u_1 + v_B = 8 \implies v_B = 8$
• $(2, B): u_2 + v_B = 6 \implies u_2 + 8 = 6 \implies u_2 = -2$
• $(2, C): u_2 + v_C = 6 \implies -2 + v_C = 6 \implies v_C = 8$
• $(3, C): u_3 + v_C = 5 \implies u_3 + 8 = 5 \implies u_3 = -3$
• $(3, D): u_3 + v_D = 0 \implies -3 + v_D = 0 \implies v_D = 3$

2. 計算非基本格檢驗數 $\bar{c}_{ij} = c_{ij} - (u_i + v_j)$：

• $\bar{c}_{1C} = 6 - (0 + 8) = -2$
• $\bar{c}_{1D} = 0 - (0 + 3) = -3$ （最負）
• $\bar{c}_{2A} = 9 - (-2 + 7) = 4$
• $\bar{c}_{2D} = 0 - (-2 + 3) = -1$
• $\bar{c}_{3A} = 5 - (-3 + 7) = 1$
• $\bar{c}_{3B} = M - (-3 + 8) = M - 5 > 0$

3. 入基與出基調整：

• 最負檢驗數為 $\bar{c}_{1D} = -3$，選 $(1, D)$ 為入基變數。
• 閉迴路：$(1, D) \to (3, D) \to (3, C) \to (2, C) \to (2, B) \to (1, B) \to (1, D)$。
• 符號與指派：
• $(1, D): +\theta$
• $(3, D): 10 - \theta$
• $(3, C): 55 + \theta$
• $(2, C): 5 - \theta$
• $(2, B): 80 + \theta$
• $(1, B): 10 - \theta$
• 決定步長：$\theta = \min(10, 5, 10) = 5$。
• 出基變數：$(2, C)$ 配銷量降為 $0$，退出基底。

第 1 次調整後配銷表：

總成本：$Z_1 = 1145 + 5 \times (-3) = 1130$ 仟元。

【第 2 次迭代】

1. 計算乘子（令 $u_1 = 0$）：

• $(1, A): v_A = 7$
• $(1, B): v_B = 8$
• $(1, D): v_D = 0$
• $(2, B): u_2 + v_B = 6 \implies u_2 = 6 - 8 = -2$
• $(3, D): u_3 + v_D = 0 \implies u_3 = 0 - 0 = 0$

核心觀念

本題評量專案管理（Project Management）中要徑法（Critical Path Method, CPM）​與專案趕工（Project Crashing）​之核心理論，主要涵蓋三大觀念：

1. AOA（Activity on Arc，箭線圖法）網路繪製規則：

• 節點（Node / Event）代表事件狀態，箭線（Arc / Branch）代表作業活動。
• 專案僅能有單一起點節點與單一終點節點。
• 任兩節點間至多只能有一條實體箭線；若有多個先行或後續限制，須檢驗是否需要引入長度與成本皆為零的「虛作業」（Dummy Activity）。

2. 要徑（Critical Path）與專案完工期：

• 要徑為專案網路中耗時最長的路徑，決定了整個專案的最早完工時間（Project Duration）。
• 要徑上的作業稱為要徑作業，其總浮時（Total Float / Slack）為 0。

3. 專案趕工與邊際成本分析法（Marginal Cost Analysis）：

• 作業單位時間趕工成本（又稱成本斜率，Cost Slope）公式為： $S = \frac{\text{趕工成本 } (C_C) - \text{正常成本 } (C_N)}{\text{正常時間 } (T_N) - \text{趕工時間 } (T_C)}$
• 邊際成本分析決策準則：在欲縮短專案工期時，必須針對「要徑」上的作業進行趕工；若有多項要徑作業可供選擇，優先選擇成本斜率 $S$ 最小者，逐步壓縮工期，直至該作業達趕工上限或要徑移轉，以達成追加成本最小化。

解題方法

(一) 繪製此專案的 AOA 網路圖

依據題目表一之先行關係：

• 作業 A、B、D 無先行作業，自專案起點開始。
• 作業 C、F、G 以 B 為先行作業。
• 作業 E 以 A、C 為先行作業。
• 作業 H 以 D、E、F 為先行作業。
• 作業 G、H 無後續作業，匯流至專案終點。

定義事件節點如下：

• 節點 1：專案開始（作業 A、B、D 之起點）。
• 節點 2：作業 B 完成（作業 C、F、G 之起點）。
• 節點 3：作業 A 與 C 完成（作業 E 之起點）。
• 節點 4：作業 D、E、F 完成（作業 H 之起點）。
• 節點 5：專案完成（作業 G 與 H 之終點）。

作業箭線對照（始節點 $\to$ 終節點）：

• 作業 A：$1 \to 3$
• 作業 B：$1 \to 2$
• 作業 C：$2 \to 3$
• 作業 D：$1 \to 4$
• 作業 E：$3 \to 4$
• 作業 F：$2 \to 4$
• 作業 G：$2 \to 5$
• 作業 H：$4 \to 5$

本題各作業之起始與結束節點皆各自獨立，未出現「兩作業具有完全相同之始節點與終節點」，因此不需要使用任何虛作業（Dummy Activity）​即可完整且精確地表達邏輯關係。

AOA 網路拓撲結構如下：

 +----------------------- D ------------------------+
 | |
 | +-------- A --------+ v
 ( 1 ) | v ( 4 ) ----- H -----> ( 5 )
 | ( 2 ) ----- C ----> ( 3 ) ----- E -------> ^ ^
 | | | |
 +--- B ---+---------------- F ---------------------+ |
 | |
 +---------------------------- G -----------------------------+

(二) 正常時間下之要徑與總時間

將所有路徑自起點（節點 1）至終點（節點 5）展開，計算正常時間下的各路徑長度：

1. 路徑 1（$\text{A} \to \text{E} \to \text{H}$）： $T_1 = 8 + 11 + 7 = 26 \text{ 週}$
2. 路徑 2（$\text{B} \to \text{C} \to \text{E} \to \text{H}$）： $T_2 = 10 + 6 + 11 + 7 = 34 \text{ 週}$
3. 路徑 3（$\text{B} \to \text{F} \to \text{H}$）： $T_3 = 10 + 9 + 7 = 26 \text{ 週}$
4. 路徑 4（$\text{B} \to \text{G}$）： $T_4 = 10 + 6 = 16 \text{ 週}$
5. 路徑 5（$\text{D} \to \text{H}$）： $T_5 = 6 + 7 = 13 \text{ 週}$

結論： 專案工期由耗時最長之路徑決定，最長路徑為路徑 2。

• 要徑（Critical Path）：$\text{B}-\text{C}-\text{E}-\text{H}$（或寫為 $\text{B} \to \text{C} \to \text{E} \to \text{H}$）
• 要徑總時間：$34$ 週

(三) 專案最快完成時間

當專案內所有作業皆趕工至其最短極限（即趕工時間）​時，各路徑的極限時間如下：

1. 路徑 1（$\text{A} \to \text{E} \to \text{H}$）： $T_{1,\text{crash}} = 6 + 9 + 6 = 21 \text{ 週}$
2. 路徑 2（$\text{B} \to \text{C} \to \text{E} \to \text{H}$）： $T_{2,\text{crash}} = 7 + 4 + 9 + 6 = 26 \text{ 週}$
3. 路徑 3（$\text{B} \to \text{F} \to \text{H}$）： $T_{3,\text{crash}} = 7 + 8 + 6 = 21 \text{ 週}$
4. 路徑 4（$\text{B} \to \text{G}$）： $T_{4,\text{crash}} = 7 + 4 = 11 \text{ 週}$
5. 路徑 5（$\text{D} \to \text{H}$）： $T_{5,\text{crash}} = 3 + 6 = 9 \text{ 週}$

結論： 在所有作業皆已趕工至極限的情況下，路徑 2 仍然需要 $26$ 週方能完工。因此，本專案之最快完成時間為 $26$ 週。

(四) 以邊際成本分析法縮短至 26 週之趕工分析與總成本

1. 計算各作業之可趕工週數與成本斜率（Cost Slope）

核心觀念

本題考查動態規劃（Dynamic Programming, DP）​於經典整數背包問題／貨櫃裝載問題（Integer Knapsack / Cargo-Loading Problem）​之應用，其理論基礎為貝爾曼最佳化原理（Bellman's Principle of Optimality）。

建立動態規劃模型時，需明確定義下列關鍵要素：

1. 階段（Stage $i$）：按貨物種類劃分決策階段，本題共有 3 種貨物，對應 $i = 1, 2, 3$。
2. 狀態變數（State $s_i$）：進入階段 $i$ 時，貨櫃尚可供貨物 $i, \dots, 3$ 使用的剩餘載重容量。
3. 決策變數（Decision $x_i$）：在階段 $i$ 決定裝載貨物 $i$ 的件數（非負整數）。
4. 最佳值函數（Optimal Value Function $f_i(s_i)$）：在剩餘載重為 $s_i$ 的狀態下，分配給貨物 $i, \dots, 3$ 所能獲得的最大累積利潤。
5. 遞迴關係式（Recursive Relation）：連結階段 $i$ 與階段 $i+1$ 之狀態轉移與效益累積方程式。
6. 邊界條件（Boundary Condition）：終止階段（所有貨物決策完成後）之初值條件。

解題方法

一、動態規劃模型建立

1. 基本參數設定：

• 貨櫃最大載重容量：$W = 20$ 公噸。
• 各貨物單位利潤：$c_1 = 6, c_2 = 8, c_3 = 5$（萬元）。
• 各貨物單位重量：$w_1 = 5, w_2 = 6, w_3 = 4$（公噸）。

2. 階段（Stage）：

• 令階段 $i \in \{1, 2, 3\}$ 分別代表針對貨物 1、貨物 2、貨物 3 進行裝載件數之決策。

3. 狀態變數（State）：

• 令 $s_i$ 代表進入階段 $i$ 時，貨櫃剩餘之可用載重容量（$0 \le s_i \le 20$）。
• 狀態轉移方程式為：$s_{i+1} = s_i - w_i x_i$。

4. 決策變數（Decision Variable）：

• 令 $x_i$ 代表裝載貨物 $i$ 之單位數，可行決策集合為： $x_i \in \left\{ 0, 1, 2, \dots, \left\lfloor \frac{s_i}{w_i} \right\rfloor \right\}$

5. 最佳值函數（Optimal Value Function）：

• 定義 $f_i(s_i)$ 為「當進入階段 $i$ 且剩餘可用載重容量為 $s_i$ 時，自階段 $i$ 至階段 3（裝載貨物 $i, \dots, 3$）所能獲得之最大總利潤（萬元）」。

6. 遞迴關係式（Recursive Relation）：

• 對於階段 $i = 1, 2$： $f_i(s_i) = \max_{x_i \in \left\{ 0, 1, \dots, \left\lfloor \frac{s_i}{w_i} \right\rfloor \right\}} \left\{ c_i x_i + f_{i+1}(s_i - w_i x_i) \right\}$

7. 邊界條件（Boundary Condition）：

• 當所有貨物均考慮完畢時，無額外利潤： $f_4(s_4) = 0, \quad \forall s_4 \ge 0$
• 亦即在最終階段 3（$c_3 = 5, w_3 = 4$），最佳值函數可直接表示為： $f_3(s_3) = \max_{x_3 \in \left\{ 0, 1, \dots, \left\lfloor \frac{s_3}{4} \right\rfloor \right\}} \{ 5 x_3 \} = 5 \left\lfloor \frac{s_3}{4} \right\rfloor$ 對應之最佳決策為 $x_3^*(s_3) = \left\lfloor \frac{s_3}{4} \right\rfloor$。

二、逆向逐步求算（Backward Recursion）

本題初始可用容量為 $s_1 = 20$ 公噸。為求算效率，僅需針對後續階段可能出現之可行狀態進行計算。

【階段 3：貨物 3】（$c_3 = 5, w_3 = 4$）

由 $f_3(s_3) = 5 \lfloor s_3 / 4 \rfloor$ 及 $x_3^*(s_3) = \lfloor s_3 / 4 \rfloor$，各可能容量之值如下：

• $s_3 \in \{0, 2, 3\} \implies f_3(s_3) = 0, \quad x_3^* = 0$
• $s_3 \in \{4, 5\} \implies f_3(s_3) = 5, \quad x_3^* = 1$
• $s_3 \in \{8, 9, 10\} \implies f_3(s_3) = 10, \quad x_3^* = 2$
• $s_3 \in \{14, 15\} \implies f_3(s_3) = 15, \quad x_3^* = 3$
• $s_3 = 20 \implies f_3(20) = 25, \quad x_3^* = 5$

【階段 2：貨物 2】（$c_2 = 8, w_2 = 6$）

在階段 1 中，$x_1 \in \{0, 1, 2, 3, 4\}$，其占用重量為 $5x_1$，因此進入階段 2 之可能狀態為： $s_2 = 20 - 5x_1 \in \{20, 15, 10, 5, 0\}$

針對各 $s_2$ 應用遞迴式 $f_2(s_2) = \max_{x_2} \{ 8x_2 + f_3(s_2 - 6x_2) \}$ 計算：

1. $s_2 = 0$：

• $x_2 = 0 \implies 8(0) + f_3(0) = 0$
• 故 $f_2(0) = 0, x_2^*(0) = 0$

2. $s_2 = 5$：

• $x_2 = 0 \implies 8(0) + f_3(5) = 0 + 5 = 5$
• 故 $f_2(5) = 5, x_2^*(5) = 0$

3. $s_2 = 10$：

• $x_2 = 0 \implies 8(0) + f_3(10) = 0 + 10 = 10$
• $x_2 = 1 \implies 8(1) + f_3(10 - 6) = 8 + f_3(4) = 8 + 5 = 13$
• 故 $f_2(10) = 13, x_2^*(10) = 1$

4. $s_2 = 15$：

• $x_2 = 0 \implies 8(0) + f_3(15) = 0 + 15 = 15$
• $x_2 = 1 \implies 8(1) + f_3(15 - 6) = 8 + f_3(9) = 8 + 10 = 18$
• $x_2 = 2 \implies 8(2) + f_3(15 - 12) = 16 + f_3(3) = 16 + 0 = 16$
• 故 $f_2(15) = 18, x_2^*(15) = 1$

5. $s_2 = 20$：

• $x_2 = 0 \implies 8(0) + f_3(20) = 0 + 25 = 25$

核心觀念

本題屬於作業研究（Operations Research）中的二人零和競賽（Two-Person Zero-Sum Game）。核心觀念包含：

1. 純策略鞍點檢驗（Saddle Point Test）：

• 甲方為收益極大化者（Maximizer），其保守準則為求「每列最小值之最大值」（Maximin）。
• 乙方為損失極小化者（Minimizer），其保守準則為求「每行最大值之最小值」（Minimax）。
• 當 $\text{Maximin} = \text{Minimax}$ 時，存在純策略鞍點（Saddle Point）；若不相等，則無純策略解，雙方必採用混合策略（Mixed Strategy）。

2. 優勢原則（Principle of Dominance）：

• 對甲方（列）而言，若策略 $A_i$ 的每一項收益皆大於或等於策略 $A_k$，則稱 $A_i$ 優勢支配 $A_k$，$A_k$ 為劣勢策略，甲方絕不會採行（機率為 0），可直接自矩陣刪除。

3. 混合策略與互補差額條件（Complementary Slackness）：

• 將收益矩陣降階後，利用圖解法或期望值聯立方程求解。
• 若某策略之期望收益未達邊界（對乙方而言，給予甲方的收益大於競賽值 $v$），則該策略被採用的機率必為 0。

解題方法

步驟一：檢驗純策略鞍點

列示甲方各策略在最差情況下的最小收益（Row Min），以及乙方在最差情況下的最大損失（Col Max）：

• 甲方各列最小值（Row Minimum）：

• 策略 $A_1$：$\min(3, -3, -1) = -3$

• 策略 $A_2$：$\min(0, 3, 1) = 0$

• 策略 $A_3$：$\min(-2, 1, 1) = -2$

• 最大列最小值 $\text{Maximin} = \max(-3, 0, -2) = 0$（對應策略 $A_2$）

• 乙方各行最大值（Column Maximum）：

• 策略 $B_1$：$\max(3, 0, -2) = 3$

• 策略 $B_2$：$\max(-3, 3, 1) = 3$

• 策略 $B_3$：$\max(-1, 1, 1) = 1$

• 最小行最大值 $\text{Minimax} = \min(3, 3, 1) = 1$（對應策略 $B_3$）

因為 $\text{Maximin} = 0 \neq \text{Minimax} = 1$，故本競賽不存在純策略鞍點，雙方均須採行混合策略。

步驟二：利用優勢原則（Dominance Principle）簡化矩陣

比較甲方策略 $A_2$ 與 $A_3$ 的各項收益：

• 面對 $B_1$：$A_2 = 0 > -2 = A_3$
• 面對 $B_2$：$A_2 = 3 > 1 = A_3$
• 面對 $B_3$：$A_2 = 1 \ge 1 = A_3$

策略 $A_2$ 在面對乙方所有策略時的收益均不低於 $A_3$，且在面對 $B_1$ 及 $B_2$ 時嚴格更佳。因此，策略 $A_2$ 優勢支配策略 $A_3$，策略 $A_3$ 為劣勢策略，甲方採行機率必為 $0$（即 $p_3 = 0$）。

刪除 $A_3$ 後，收益矩陣縮減為 $2 \times 3$：

步驟三：求算甲方最佳策略機率與競賽值

設甲方採行策略 $A_1$ 的機率為 $p_1 = p$，採行 $A_2$ 的機率為 $p_2 = 1 - p$，其中 $0 \le p \le 1$。 針對乙方採行之純策略，甲方的期望收益分別為：

• 面對 $B_1$：$E(B_1) = 3p + 0(1 - p) = 3p$
• 面對 $B_2$：$E(B_2) = -3p + 3(1 - p) = 3 - 6p$
• 面對 $B_3$：$E(B_3) = -1p + 1(1 - p) = 1 - 2p$

甲方之目標為極大化其最小期望收益： $v = \max_{0 \le p \le 1} \min \{ 3p,\, 3 - 6p,\, 1 - 2p \}$

求直線交點以決定下界包絡線（Lower Envelope）之最高點：

• 聯立 $E(B_1)$ 與 $E(B_3)$： $3p = 1 - 2p \implies 5p = 1 \implies p = \frac{1}{5} = 0.2$
• 代入求得競賽值： $v = 3 \times \frac{1}{5} = \frac{3}{5} = 0.6$
• 檢驗此時 $E(B_2)$ 之值：