115 年 國立臺灣大學工業工程學研究所碩士班產業與服務系統工程組《作業研究》

核心觀念

本題考查馬可夫決策過程（Markov Decision Process, MDP）中，在給定平穩策略（Stationary Policy）下所誘導（induced）出之馬可夫鏈的轉移機率矩陣（Transition Probability Matrix）。

假設狀態空間 $S = \{G, B\}$（分別代表第 1 列與第 2 列），當系統採用平穩策略 $\pi$ 時，矩陣 $P^\pi$ 的第 $i$ 列與第 $j$ 行元素 $P^\pi_{ij}$ 表示在狀態 $i$ 下執行策略指定的動作 $\pi(i)$ 後，轉移至狀態 $j$ 的條件機率：
$P^\pi_{ij} = P(X_{d+1} = j \mid X_d = i, A_d = \pi(i))$

---

解題方法

策略 $\pi_2$ 的決策規則如下：

1. 當現階段狀態為 $X_d = G$ 時：選擇動作 $C$（Continue）。
   依題意，在動作 $C$ 下的轉移機率為：
   $P(G \to G \mid C) = 0.8, \quad P(G \to B \mid C) = 0.2$
   此即轉移矩陣的第 1 列（Row 1）：$\begin{pmatrix} 0.8 & 0.2 \end{pmatrix}$。

2. 當現階段狀態為 $X_d = B$ 時：選擇動作 $M$（Maintenance）。
   依題意，在動作 $M$ 下，無論現階段狀態為何，下一階段狀態必為 Good（$G$）的機率為 1，即：
   $P(B \to G \mid M) = 1.0, \quad P(B \to B \mid M) = 0.0$
   此即轉移矩陣的第 2 列（Row 2）：$\begin{pmatrix} 1.0 & 0.0 \end{pmatrix}$。

將第 1 列與第 2 列組合，即可得到策略 $\pi_2$ 誘導出的轉移機率矩陣 $P^{\pi_2}$：
$P^{\pi_2} = \begin{pmatrix} 0.8 & 0.2 \\ 1.0 & 0.0 \end{pmatrix}$

---

選項分析

核心觀念

本題考查馬可夫鏈（Markov Chain）中的**轉移機率矩陣（Transition Probability Matrix）與多步轉移機率（Multi-step Transition Probability）**計算。

在常態策略（Stationary Policy） $\pi_1$ 下，不論當前狀態為 $G$（Good）或 $B$（Bad），決策者均選擇採取 Action $C$（Continue）。因此，系統狀態轉變完全由 Action $C$ 所定義的轉移機率決定。

設狀態空間（State Space）為 $S = \{G, B\}$，則策略 $\pi_1$ 下的一步轉移機率矩陣 $P$ 為：
$P = \begin{bmatrix} P(G \to G) & P(G \to B) \\ P(B \to G) & P(B \to B) \end{bmatrix} = \begin{bmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{bmatrix}$

根據查普曼－柯爾莫哥洛夫等式（Chapman-Kolmogorov Equation），兩步轉移機率矩陣（Two-step Transition Probability Matrix） $P^{(2)}$ 即為一步轉移矩陣的平方：
$P^{(2)} = P^2 = P \times P$

題目欲求之條件機率 $P(X_{d+2} = G \mid X_d = G)$，即為矩陣 $P^{(2)}$ 中第 1 列第 1 行的元素 $P^{(2)}_{GG}$。

---

解題方法

步驟一：寫出一步轉移機率矩陣 $P$
根據題目給定 Action $C$ 的轉移機率：

• 從狀態 $G$ 出發：$P(X_{d+1}=G \mid X_d=G) = 0.8$，$P(X_{d+1}=B \mid X_d=G) = 0.2$
• 從狀態 $B$ 出發：$P(X_{d+1}=G \mid X_d=B) = 0.3$，$P(X_{d+1}=B \mid X_d=B) = 0.7$

一步轉移矩陣表示為：
$P = \begin{bmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{bmatrix}$

步驟二：計算兩步轉移機率矩陣 $P^{(2)}$
計算矩陣平方 $P^2$：
$P^2 = \begin{bmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{bmatrix}$

核心觀念

本題考驗**馬可夫決策過程（Markov Decision Process, MDP）與馬可夫鏈（Markov Chain）**之「長期平均每日成本（Long-run Average Daily Cost）」計算。

對於一個有限狀態且具有平穩轉移機率矩陣 $\mathbf{P}$ 的同質馬可夫鏈，若其具有平穩分佈（Stationary Distribution）$\boldsymbol{\pi} = [\pi_G, \pi_B]$，則滿足：
$\boldsymbol{\pi} \mathbf{P} = \boldsymbol{\pi} \quad \text{且} \quad \pi_G + \pi_B = 1$

在策略 $\pi$ 下的長期平均每日成本 $\bar{c}(\pi)$ 定義為狀態空間 $\mathcal{S} = \{G, B\}$ 上各狀態成本的期望值：
$\bar{c}(\pi) = \sum_{s \in \{G, B\}} \pi_s \cdot \text{cost}(s, \pi(s)) = \pi_G \cdot \text{cost}(G, \pi(G)) + \pi_B \cdot \text{cost}(B, \pi(B))$

---

解題方法

步驟一：分析策略 $\pi_1$ 的長期平均成本 $\bar{c}(\pi_1)$

在策略 $\pi_1$ 下，不論機率處於 $G$ 或 $B$ 均選擇 Action $C$。
其轉移機率矩陣 $\mathbf{P}_{\pi_1}$ 為：
$\mathbf{P}_{\pi_1} = \begin{bmatrix} P(G \to G) & P(G \to B) \\ P(B \to G) & P(B \to B) \end{bmatrix} = \begin{bmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{bmatrix}$

設平穩分佈為 $\boldsymbol{\pi}^{(1)} = [\pi_G^{(1)}, \pi_B^{(1)}]$：

1. 由平衡方程式（Balance Equations）：
   $\pi_G^{(1)} = 0.8 \pi_G^{(1)} + 0.3 \pi_B^{(1)} \implies 0.2 \pi_G^{(1)} = 0.3 \pi_B^{(1)} \implies \pi_G^{(1)} = 1.5 \pi_B^{(1)}$
2. 由歸一化條件 $\pi_G^{(1)} + \pi_B^{(1)} = 1$：
   $1.5 \pi_B^{(1)} + \pi_B^{(1)} = 1 \implies 2.5 \pi_B^{(1)} = 1 \implies \pi_B^{(1)} = 0.4, \quad \pi_G^{(1)} = 0.6$

動作成本分別為 $\text{cost}(G, C) = 1$ 與 $\text{cost}(B, C) = 6$。因此，$\pi_1$ 的長期平均成本為：
$\bar{c}(\pi_1) = 0.6 \times 1 + 0.4 \times 6 = 0.6 + 2.4 = 3.0$

---

步驟二：分析策略 $\pi_2$ 的長期平均成本 $\bar{c}(\pi_2)$

在策略 $\pi_2$ 下，$\pi_2(G) = C$、$\pi_2(B) = M$。

• 若 $X_d = G$ 且選擇 $C$，狀態轉移至 $G$ 的機率為 $0.8$，至 $B$ 的機率為 $0.2$。
• 若 $X_d = B$ 且選擇 $M$，下一天必定修復成 $G$，故轉移至 $G$ 的機率為 $1.0$，至 $B$ 的機率為 $0$。

其轉移機率矩陣 $\mathbf{P}_{\pi_2}$ 為：
$\mathbf{P}_{\pi_2} = \begin{bmatrix} 0.8 & 0.2 \\ 1.0 & 0 \end{bmatrix}$

設平穩分佈為 $\boldsymbol{\pi}^{(2)} = [\pi_G^{(2)}, \pi_B^{(2)}]$：

1. 由平衡方程式：

核心觀念

本題考驗佇列理論（Queueing Theory）中 $\text{M/M/1}$ 系統 的穩定狀態機率（Stationary Probability / Steady-state Probability）與 PASTA 定理（Poisson Arrivals See Time Averages）。

1. 參數轉換與單位統一：
   • 到達率（Arrival Rate）：$\lambda = 10 \text{ 人/小時}$。
   • 平均服務時間（Mean Service Time）：$1/\mu = 5 \text{ 分鐘} = 5/60 \text{ 小時} = 1/12 \text{ 小時}$。
   • 服務率（Service Rate）：$\mu = 12 \text{ 人/小時}$。
2. 系統利用率（Traffic Intensity / Utilization Rate）：
   $\rho = \frac{\lambda}{\mu} = \frac{10}{12} = \frac{5}{6}$
   由於 $\rho < 1$，系統運作達到穩定狀態（Steady State）。
3. 穩定狀態下系統為空的機率：
   在 $\text{M/M/1}$ 佇列中，系統中有 $n$ 個顧客的穩定狀態機率為 $P_n = (1 - \rho)\rho^n$。
   因此，系統完全沒有顧客（空系統）的時間平均機率（Time-average Probability）為：
   $P_0 = 1 - \rho$
4. PASTA 定理：
   由於顧客到達過程為 Poisson 過程（記憶喪失性），「到達顧客所觀察到的系統機率分佈」（Arrival-stationary Probability, $a_n$）恰好等於「長時間的時間平均機率分佈」（Time-stationary Probability, $P_n$），即 $a_0 = P_0$。因此當顧客到達時發現系統為空的機率即為 $P_0$。

---

解題方法

步驟一：計算系統利用率 $\rho$
將單位統一次為「小時」：
$\lambda = 10$
$\mu = \frac{60}{5} = 12$

核心觀念

本題考查排隊理論（Queueing Theory）中 M/M/1 排隊系統 在接近飽和（Saturated / Heavy Traffic）狀況下的極限行為（Limiting Behavior）。

1. 系統參數與單位換算：

   • 到達率 $\lambda = 10 \text{ 人/小時}$。
   • 平均服務時間為 $5 \text{ 分鐘/人} = \frac{1}{12} \text{ 小時/人}$，故 hourly service rate $\mu = 12 \text{ 人/小時}$。
   • 服務強度（Traffic Intensity / Utilization Factor）：$\rho = \frac{\lambda}{\mu}$。

2. 穩態條件與系統效能指標：

   • 穩態（Steady State）成立的必要與充分條件為 $\rho = \frac{\lambda}{\mu} < 1$。
   • 在 M/M/1 系統下，系統內的平均顧客數 $L$（Expected number of customers in the system）與顧客在系統內的平均停留時間 $W$（Expected time staying in the system）公式分別為：
     $L = \frac{\rho}{1 - \rho} = \frac{\lambda}{\mu - \lambda}$
     $W = \frac{L}{\lambda} = \frac{1}{\mu - \lambda}$

---

解題方法

根據題意，當顧客需求增加致使 $\rho = \frac{\lambda}{\mu} \to 1^-$（即 $\lambda$ 從左側趨近於 $\mu$）：

1. 推導平均顧客數 $L$ 的極限：
   $L = \lim_{\rho \to 1^-} \frac{\rho}{1 - \rho} = \frac{1}{0^+} = \infty$
   （或由 $L = \lim_{\lambda \to \mu^-} \frac{\lambda}{\mu - \lambda} = \frac{\mu}{0^+} = \infty$）

2. 推導平均停留時間 $W$ 的極限：
   $W = \lim_{\lambda \to \mu^-} \frac{1}{\mu - \lambda} = \frac{1}{0^+} = \infty$

由此可知，當利用率趨近於 $100\%$ 時，系統內部將發生嚴重的壅塞現象（Queue Explosion），導致平均顧客數 $L$ 與平均停留時間 $W$ 皆會發散至無窮大（$\to \infty$）。

核心觀念

本題屬於**凸最佳化（Convex Optimization）**的基礎理論驗證題，主要考查以下兩個核心觀念與數學定義：

1. 凹函數（Concave Function）的判定：
   對於二次可微函數 $f(x_1, x_2)$，判定其為凹函數的充分必要條件為其 Hessian 矩陣 $\mathbf{H}$ 在定義域內處處為半負定（Negative Semi-Definite, NSD）。

   • 二階偏微分 Hessian 矩陣形式為：
     $\mathbf{H} = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} \end{bmatrix}$
   • 對於二階矩陣 $\mathbf{H}$，其為半負定的條件為：
     • 一階主子行列式（Primary Subdeterminant）：$\frac{\partial^2 f}{\partial x_1^2} \le 0$ 且 $\frac{\partial^2 f}{\partial x_2^2} \le 0$
     • 行列式（Determinant）：$\det(\mathbf{H}) = \frac{\partial^2 f}{\partial x_1^2} \frac{\partial^2 f}{\partial x_2^2} - \left(\frac{\partial^2 f}{\partial x_1 \partial x_2}\right)^2 \ge 0$

2. 凸集合（Convex Set）的判定：

   • 集合 $S$ 為凸集合的定義：對任意 $\mathbf{x}, \mathbf{y} \in S$ 及任意 $\lambda \in [0, 1]$，必有 $\lambda \mathbf{x} + (1-\lambda)\mathbf{y} \in S$。
   • 保凸性定理：有限個半空間（Half-spaces）與非負半空間的**交集（Intersection）**仍為凸集合。

---

解題方法

本題需分別對 (i) 目標函數 $f(x_1, x_2)$ 的凹性 與 (ii) 可行解集合（Feasible Set）的凸性 進行數學證明。

Part (i): 證明目標函數 $f(x_1, x_2)$ 為凹函數

目標函數為利潤函數：
$f(x_1, x_2) = 20 \ln(1 + x_1) + 12 \ln(1 + x_2) - 2x_1 - 3x_2$
定義域為 $D = \{(x_1, x_2) \mid x_1 \ge 0, x_2 \ge 0\}$。

1. 計算一階偏微分（Gradient Component）：
   $\frac{\partial f}{\partial x_1} = \frac{20}{1 + x_1} - 2$
   $\frac{\partial f}{\partial x_2} = \frac{12}{1 + x_2} - 3$

2. 計算二階偏微分並建立 Hessian 矩陣 $\mathbf{H}$：
   $\frac{\partial^2 f}{\partial x_1^2} = -\frac{20}{(1 + x_1)^2}$
   $\frac{\partial^2 f}{\partial x_2^2} = -\frac{12}{(1 + x_2)^2}$
   $\frac{\partial^2 f}{\partial x_1 \partial x_2} = \frac{\partial^2 f}{\partial x_2 \partial x_1} = 0$

   因此，Hessian 矩陣為對角矩陣：
   $\mathbf{H}(x_1, x_2) = \begin{bmatrix} -\frac{20}{(1 + x_1)^2} & 0 \\ 0 & -\frac{12}{(1 + x_2)^2} \end{bmatrix}$

核心觀念

本題考查拉格朗日函數與 Karush–Kuhn–Tucker（KKT）條件。KKT 條件由四部分組成：

1. 原始可行性（primal feasibility）
2. 對偶可行性（dual feasibility）
3. 互補鬆弛（complementary slackness）
4. 穩定性條件（stationarity）

令作業研究的原問題寫成一般形式：

$$\max_{x_1,x_2}\quad c_1x_1+c_2x_2$$

受限於兩項資源限制：

$$a_{11}x_1+a_{12}x_2\le b_1$$ $$a_{21}x_1+a_{22}x_2\le b_2$$

以及非負限制：

$$x_1\ge 0,\qquad x_2\ge 0$$

題目未提供第 2-(1) 題的具體目標函數與資源係數，因此以下以一般係數表示；代入該題實際係數即可得到數值形式。

---

解題方法：建立拉格朗日函數

由於題目是最大化問題，將資源限制寫成剩餘資源形式：

$$b_1-a_{11}x_1-a_{12}x_2\ge 0$$ $$b_2-a_{21}x_1-a_{22}x_2\ge 0$$

非負限制本身已是：

$$x_1\ge 0,\qquad x_2\ge 0$$

搭配題目指定的乘數：

• $\lambda_1,\lambda_2\ge 0$：兩項資源限制
• $\mu_1,\mu_2\ge 0$：$x_1\ge0$、$x_2\ge0$

最大化問題的拉格朗日函數可寫為：

$$\mathcal{L} = c_1x_1+c_2x_2 +\lambda_1(b_1-a_{11}x_1-a_{12}x_2) +\lambda_2(b_2-a_{21}x_1-a_{22}x_2) +\mu_1x_1+\mu_2x_2$$

展開後：

$$\mathcal{L} = c_1x_1+c_2x_2 +\lambda_1(b_1-a_{11}x_1-a_{12}x_2) +\lambda_2(b_2-a_{21}x_1-a_{22}x_2) +\mu_1x_1+\mu_2x_2$$

---

完整 KKT 條件

1. 原始可行性

原始變數必須滿足原問題的所有限制：

$$a_{11}x_1+a_{12}x_2\le b_1$$ $$a_{21}x_1+a_{22}x_2\le b_2$$ $$x_1\ge 0$$ $$x_2\ge 0$$

---

2. 對偶可行性

題目指定資源限制與非負限制的乘數皆須非負：

$$\lambda_1\ge 0$$ $$\lambda_2\ge 0$$ $$\mu_1\ge 0$$ $$\mu_2\ge 0$$

---

3. 互補鬆弛條件

每一個限制的乘數與其鬆弛量之乘積必須為零。

對第一項資源限制：

$$\lambda_1 \left( b_1-a_{11}x_1-a_{12}x_2 \right)=0$$

對第二項資源限制：

$$\lambda_2 \left( b_2-a_{21}x_1-a_{22}x_2 \right)=0$$

對 $x_1\ge0$：

$$\mu_1x_1=0$$

對 $x_2\ge0$：

$$\mu_2x_2=0$$

其經濟意義如下：

• 若資源限制未完全使用，則對應的 $\lambda_i=0$。
• 若 $\lambda_i>0$，則該資源限制必須緊束。
• 若 $x_j>0$，則對應的 $\mu_j=0$。
• 若 $\mu_j>0$，則必須有 $x_j=0$。

---

4. 穩定性條件

分別對 $x_1$ 與 $x_2$ 求拉格朗日函數的一階偏導數，並令其等於零。

對 $x_1$：

$$\frac{\partial\mathcal{L}}{\partial x_1} = c_1-a_{11}\lambda_1-a_{21}\lambda_2+\mu_1 =0$$

對 $x_2$：

核心觀念

本題屬於**非線性規劃（Nonlinear Programming, NLP）**中帶有等式與不等式約束條件的最優化問題。當無約束極值點（Unconstrained Maximizer）落於可行解區域（Feasible Region）之外（即不可行）時，最佳解必定會落在邊界上，即至少有一個不等式約束條件會達到等式邊界（Binding Constraint / Active Constraint）。

在給定特定的約束條件組合狀況下（本題指定 $2x_1 + x_2 = 10$ 為 Binding，而 $x_1 + 2x_2 < 12$ 為 Slack，且 $x_1 > 0, x_2 > 0$），解題的核心觀念與工具包括：

1. 等式約束最優化（Lagrange Multipliers 方法）或變數消去法（Variable Substitution）：由於約束條件 $2x_1 + x_2 = 10$ 為 Binding，可將此等式條件納入拉格朗日函數（Lagrangian Function），或直接將變數帶換化簡為單變數函數求解。
2. KKT 條件（Karush-Kuhn-Tucker Conditions）與可行性驗證：求出臨界點後，必須回頭驗證該點是否滿足題目所設定的 Slack 條件（$x_1 + 2x_2 < 12$）與正實數條件（$x_1 > 0, x_2 > 0$），並確認對應的拉格朗日乘子（Lagrange Multipliers）符合對偶可行性（Dual Feasibility），以確保該點為可行最佳解（Feasible Optimum Solution）。

---

解題方法與關鍵推導

根據題目假設條件，目標是在等式約束 $2x_1 + x_2 = 10$ 下求解最佳化問題，並滿足 $x_1 + 2x_2 < 12$ 及 $x_1 > 0, x_2 > 0$ 的可行性要求。

步驟一：表示邊界約束條件

由 Binding 約束條件 $2x_1 + x_2 = 10$，可將變數 $x_2$ 表示為 $x_1$ 的函數：

$$x_2 = 10 - 2x_1$$

步驟二：確定變數 $x_1$ 的可行範圍

將 $x_2 = 10 - 2x_1$ 代入題目要求的其他約束條件中：

1. $x_1 > 0$
2. $x_2 > 0 \implies 10 - 2x_1 > 0 \implies x_1 < 5$
3. Slack 約束 $x_1 + 2x_2 < 12$： $$x_1 + 2(10 - 2x_1) < 12$$

核心觀念

本題考查單純法（Simplex Method）的基本迭代過程、**進基變數（Entering Variable）的選擇與離基變數（Leaving Variable）的判定（最小比值測試, Minimum Ratio Test），以及目標函數值的改善量（Improvement in Objective Value）**之計算。

1. 標準型態轉換（Standard Form）：將不等式限制條件加入鬆弛變數（Slack Variables），轉為等式。
2. 初始基本可行解（Initial Basic Feasible Solution, BFS）：題目指明第一步將非基本變數設為 $(x_1, x_2, x_3)$，故初始基本變數為鬆弛變數 $(s_1, s_2)$，初始目標值 $Z=0$。
3. 最小比值測試（Minimum Ratio Test）：當指定進基變數（Entering Variable）為 $x_1$ 時，藉由限制條件決定哪一個變數先降為 $0$（即離基變數 Leaving Variable），以維持可行性（Non-negativity）。
4. 目標值改善量：若進基變數 $x_1$ 增加量為 $\Delta x_1$，且其在目標函數中的相對獲利係數（Reduced Cost）為 $c_1$，則目標值的改善量為 $\Delta Z = c_1 \times \Delta x_1$。

---

解題方法

步驟 1：寫出單純法的標準型態與初始基本解

引進鬆弛變數 $s_1 \ge 0, s_2 \ge 0$，將原 LP 轉為標準型態：
$\max Z = 3x_1 + 4x_2 + 10x_3$
$\text{s.t. } x_1 + 2x_2 + 3x_3 + s_1 = 10$
$5x_1 + x_2 + 4x_3 + s_2 = 6$
$x_1, x_2, x_3, s_1, s_2 \ge 0$

根據題意，初始選擇非基本變數（Non-basic variables）為 $x_1 = 0, x_2 = 0, x_3 = 0$。
此時基本變數（Basic variables）為：
$s_1 = 10, \quad s_2 = 6$
初始目標函數值為：
$Z_0 = 0$

核心觀念

本題考查線性規劃（Linear Programming, LP）中**單純法（Simplex Method）關於非基底變數進基（Entering Non-basic Variable）**時對目標函數值改善量（Improvement in Objective Value）的計算。

在標準型的線性規劃問題中，假設目前的非基底變數集合為 $(x_1, x_2, x_3)$：

1. 單步檢定量（Reduced Cost）：非基底變數 $x_j$ 的檢定量 $\bar{c}_j = c_j - z_j = c_j - \mathbf{c}_B^T \mathbf{B}^{-1} \mathbf{A}_j$ 代表當 $x_j$ 每增加 1 單位時，目標函數值 $Z$ 的變化量。在極大化問題中，若 $\bar{c}_j > 0$，表示將 $x_j$ 引進基底可改善（增加）目標函數值。
2. 最大允許進基步長（Step Size / Minimum Ratio Test）：變數 $x_j$ 能增加的最大限量 $\Delta x_j$，受到限制式中基底變數維持非負（Non-negativity constraint）的限制。其最大步長由**最小比值法（Minimum Ratio Test）**決定：
   $\Delta x_j = \min_{i: \bar{a}_{ij} > 0} \left\{ \frac{\bar{b}_i}{\bar{a}_{ij}} \right\}$
   其中 $\bar{\mathbf{b}} = \mathbf{B}^{-1} \mathbf{b}$ 為當前基底可行解的數值，$\bar{\mathbf{a}}_j = \mathbf{B}^{-1} \mathbf{A}_j$ 為進基變數對應的單純表係數向量。
3. 目標函數值的改進量（Improvement in Objective Value）：
   當選擇 $x_j$ 為進基變數時，目標函數值的改善量 $\Delta Z_j$ 為檢定量與最大允許步長之乘積：
   $\Delta Z_j = \bar{c}_j \cdot \Delta x_j$

---

解題方法

1. 符號與推導架構

設目前單純表（Simplex Tableau）對應的非基底變數為 $(x_1, x_2, x_3)$，基底變數為 $\mathbf{x}_B$。
對任意非基底變數 $x_j$ ($j \in \{2, 3\}$)：

• 步驟一：由當前單純表讀取或計算其檢定量 $\bar{c}_j$（對極大化問題即為 $Z$-row 上的檢定係數）。
• 步驟二：觀察單純表中 $x_j$ 對應的行向量 $\bar{\mathbf{a}}_j$ 與當前的常數項向量 $\bar{\mathbf{b}}$，進行最小比值測試：
  $\Delta x_j = \min \left\{ \frac{\bar{b}_i}{\bar{a}_{ij}} \,\,\Bigg|\,\, \bar{a}_{ij} > 0 \right\}$
• 步驟三：計算目標函數值的改善量：
  $\Delta Z_j = \bar{c}_j \times \Delta x_j$

---

2. 詳細推導過程

(1) 選擇 $x_2$ 為進基變數

• 檢定量與邊際效益：將 $x_2$ 從 0 提升至正數，目標函數每單位變動量為 $\bar{c}_2$。
• 步長限制：限制式中基底變數之更新公式為 $\mathbf{x}_B = \bar{\mathbf{b}} - \bar{\mathbf{a}}_2 x_2 \ge \mathbf{0}$。

核心觀念

在單純法（Simplex Method）中，選取進基變數（Entering Variable）通常有兩種常見的法則：

1. Dantzig 樞紐法則（Dantzig's Pivot Rule）：選取檢驗值（Reduced Cost, $\bar{c}_j$）最優（極大化問題中取最大正值）的非基變數進基。
2. 最大改善量樞紐法則（Maximum Improvement Pivot Rule）：比較所有可使目標值改善（即檢驗值滿足進基條件）的非基變數，計算若選取該變數進基後，目標函數值獲得的實際改善量 $\Delta Z$，並選擇能帶來最大實際改善量的變數進基。

對極大化問題而言，當選擇非基變數 $x_j$ 進基時：

• 最大允許進基步長（Step Size）：$\theta = \min_{i: \bar{a}_{ij} > 0} \left\{ \frac{\bar{b}_i}{\bar{a}_{ij}} \right\}$
• 目標函數改善量：$\Delta Z = c_j^* \cdot \theta = \bar{c}_j \cdot \theta$ （其中 $\bar{c}_j$ 為 $x_j$ 的檢驗值）

---

解題方法

本題要求比較選擇 $x_1, x_2, x_3$ 分別作為進基變數時對目標值的改善量，並依據「最大改善量樞紐法則（Maximum Improvement Pivot Rule）」完成此步單純法疊代。

步驟一：彙整第 (1) 與第 (2) 小題計算結果

假設前兩小題計算出當前單純表（Simplex Tableau）中各候選變數 $x_1, x_2, x_3$ 的檢驗值（Reduced Cost $\bar{c}_j$）與最小比值測試（Minimum Ratio Test）所得之最大進基步長 $\theta_j$ 分別如下：

1. 若選 $x_1$ 進基：

   • 檢驗值：$\bar{c}_1$
   • 步長：$\theta_1 = \min_{i: \bar{a}_{i1} > 0} \left\{ \frac{\bar{b}_i}{\bar{a}_{i1}} \right\}$
   • 目標值改善量：$\Delta Z_1 = \bar{c}_1 \times \theta_1$

2. 若選 $x_2$ 進基：

   • 檢驗值：$\bar{c}_2$
   • 步長：$\theta_2 = \min_{i: \bar{a}_{i2} > 0} \left\{ \frac{\bar{b}_i}{\bar{a}_{i2}} \right\}$
   • 目標值改善量：$\Delta Z_2 = \bar{c}_2 \times \theta_2$

3. 若選 $x_3$ 進基：

   • 檢驗值：$\bar{c}_3$
   • 步長：$\theta_3 = \min_{i: \bar{a}_{i3} > 0} \left\{ \frac{\bar{b}_i}{\bar{a}_{i3}} \right\}$

核心觀念

本題考驗單純法（Simplex Method）中的 Maximum Improvement Pivot Rule（最大改善軸轉規則）。
在單純法進行樞紐轉換（Pivot Step）選擇進基變數（Entering Variable）時：

1. Dantzig's Rule（經典規則）：選擇檢驗值（Reduced Cost，即判別式中的 $c_j - z_j$ 或 $-c_j$ 列之係數）負值絕對值最大者（極大化問題時選擇最負者）。
2. Maximum Improvement Rule（最大改善規則）：計算每個候選進基變數在完成該次樞紐轉換後，目標函數值能獲得的實際改善量 $\Delta z = (\text{候選變數之改善率}) \times (\text{離基限制下該變數最大能增加的值})$，並選擇使目標函數值提升幅度最大者作為進基變數。

---

解題方法

1. 題目情境與當前單純表（Tableau）

由於本題為第 3-(4) 題，依據前小題之推導與題意，單純法的目標為極大化目標函數 $z$。設當前單純表如下（或由前一小題延伸之基底狀態）：

假設當前目標函數與限制式系統為：
$\max z = 3x_1 + 5x_2 + 2x_3$
限制條件與當前基底變數（Basic Variables）狀態下，經整理後的檢驗值與最小比值測試（Minimum Ratio Test）如下：

• 候選進基變數評估：
  若有多個變數之檢驗值皆符合進基條件（對極大化問題而言，相對應的目標函數邊際收益為正），需分別計算其可增加的最大步長（Step length）與目標函數的改善總量：
  • 候選變數 $x_i$：
    • 檢驗值（邊際改善率）：$\bar{c}_i > 0$
    • 最大允許增加量（由最小比值測試決定）：$\theta_i = \min_{k} \left\{ \frac{\bar{b}_k}{\bar{a}_{ki}} \;\middle|\; \bar{a}_{ki} > 0 \right\}$

由於題目為「第 3-(5) 題」，其背景承接第 3 題的前續題組（通常為求解一個包含兩條約束條件的原問題 (Primal Problem) LP 最適表，或已給定 Primal 最適解 $x^*$ 與其基底矩陣 $B$）。

以下假設前續題組之原問題（Primal Problem）基本設定為：
$\min_{x} / \max_{x} \quad c^T x$
$\text{s.t. } A x \ (\le, =, \ge) \ b$

---

核心觀念

1. 對偶變數與對偶問題（Dual Problem & Dual Variables）：
   • 若原問題有 $m$ 條約束條件，對偶問題即有 $m$ 個對偶變數。本題兩條約束條件對應對偶變數向量為 $y = (y_1, y_2)^T$。
2. 對偶最適解之求解定理（Dual Optimal Solution Rules）：
   • 法一：基底矩陣與對偶解關係（B-matrix / Simplex Table Formula）：
     對偶最適解可直接由 Primal 的最適基底矩陣 $B$ 及對應的基底目標係數 $c_B^T$ 計算得到：
     $y^{*T} = c_B^T B^{-1}$
   • 法二：互補鬆弛定理（Complementary Slackness Theorem, CST）：
     若已知 Primal 最適解 $x^*$，則：
     • 若 Primal 第 $i$ 條不等式約束非緊緻（Strict Inequality, 鬆弛變數 $s_i > 0$），則對應的對偶變數 $y_i^* = 0$。
     • 若 Primal 第 $j$ 個變數 $x_j^* > 0$，則對應的對偶第 $j$ 條 constraint 必須為緊緻（Equality）。
   • 法三：單純法表格之陰影價格（Shadow Prices / Reduced Costs）：
     在 Primal 最適單純法表格（Optimal Simplex Table）的 $c_j - z_j$ （或 $z_j - c_j$）列中，鬆弛變數（Slack/Surplus Variables）對應的值即反映對偶變數 $y_1^*, y_2^*$ 的數值。
3. 強對偶定理（Strong Duality Theorem）：
   • 若原問題與對偶問題皆存在可行解，則原問題最適目標函數值等於對偶問題最適目標函數值：
     $z^* = w^* = c^T x^* = b^T y^*$

---

解題方法

步驟一：建立對偶變數與原問題之對應

設原問題約束條件為：

核心觀念

本題考查背包問題的二元整數規劃（Binary Integer Programming, BIP）建模。

每一項物品只有兩種狀態：

• 選取物品：以 $1$ 表示
• 不選取物品：以 $0$ 表示

因此對每項物品建立一個二元決策變數。目標是在總重量不超過 5 公斤的限制下，使總價值最大。

解題方法

令

$$x_i= \begin{cases} 1, & \text{選取物品 }i,\\ 0, & \text{不選取物品 }i, \end{cases} \qquad i=1,2,3.$$

由題目資料：

• 物品 1：價值 3，重量 2
• 物品 2：價值 5，重量 4
• 物品 3：價值 2，重量 1

目標函數

選取物品後的總價值為

$$3x_1+5x_2+2x_3.$$

因此目標為最大化總價值：

$$\max Z=3x_1+5x_2+2x_3.$$

重量限制式

選取物品後的總重量為

$$2x_1+4x_2+x_3.$$

題目解析與動態規劃/分支定界模型建立

核心觀念

本題考查**分支定界法（Branch-and-Bound Method）結合線性規劃放鬆（Linear Programming Relaxation, LP Relaxation）**在 0-1 整數規劃（Binary Integer Programming, BIP）中的應用。

原始 0-1 背包問題（Binary Knapsack Problem）之數學模型如下：

$$\begin{aligned} \max \quad & Z = 3x_1 + 5x_2 + 2x_3 \\ \text{s.t.} \quad & 2x_1 + 4x_2 + x_3 \le 5 \\ & x_1, x_2, x_3 \in \{0, 1\} \end{aligned}$$

當將變數限制 $x_j \in \{0, 1\}$ 放鬆為連續變數 $0 \le x_j \le 1$ 時，即得到 LP 放鬆問題。在分支定界樹中，自根節點針對變數 $x_2$ 分支後，產生兩個子問題（Subproblems）：

1. 分支 $x_2 = 1$
2. 分支 $x_2 = 0$

本題要求求解 $x_2 = 0$ 之子問題的 LP 放鬆模型，並求出其最佳解 $(x_1^*, x_2^*, x_3^*)$ 與對應的最佳目標函數值 $Z^*$。

---

解法說明與詳細推導

1. 建立子問題（$x_2 = 0$）之 LP 放鬆模型

將分支條件 $x_2 = 0$ 代入原始 LP 放鬆模型中：

$$\begin{aligned} \max \quad & Z = 3x_1 + 5(0) + 2x_3 = 3x_1 + 2x_3 \\ \text{s.t.} \quad & 2x_1 + 4(0) + x_3 \le 5 \implies 2x_1 + x_3 \le 5 \\ & 0 \le x_1 \le 1 \\ & x_2 = 0 \\ & 0 \le x_3 \le 1 \end{aligned}$$

2. 求解 LP 放鬆最佳解（貪婪法/貪心策略）

連續型背包問題（Continuous Knapsack Problem）具備貪婪選擇性質（Greedy Choice Property），可依**單位重量價值比（Value-to-Weight Ratio, $v_j/w_j$）**由高至低排序優先填入背包：