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

核心觀念

本題考查**單純法（Simplex Method）求解標準線性規劃、以及敏感度分析（Sensitivity Analysis）**中兩大主題：

1. 目標函數係數的允許變動範圍：分「基變數（basic variable）」與「非基變數（nonbasic variable）」兩種情況，判斷標準是「最終單純表中所有 $z_j-c_j$（reduced cost）維持 $\ge 0$」。
2. 右手常數（RHS）的允許變動範圍：判斷標準是「所有基變數的解值維持 $\ge 0$」，方法是利用最終表中「原本對應到 slack 變數的那兩欄」直接讀出 $B^{-1}$ 的兩個行向量。

本題另有一個命題陷阱：第一次進基比值測試會出現「打平（tie）」，導致最終最佳解是退化解（degenerate solution），且會出現一個非基變數的 reduced cost 恰為 0（代表存在替代最佳解）。這正是本題把「係數敏感度」設計得不對稱（$c_1$ 只能增不能減、$c_2$ 只能減不能增）的原因，是本題的核心鑑別度所在。

解題方法

(一) 單純法求解

Step 1：標準化，加入虛變數

$4X_1+2X_2+5X_3+S_1=100$ $2X_1+2X_2+4X_3+S_2=80$

目標：$\max Z=3X_1+3X_2+4X_3+0S_1+0S_2$

Step 2：初始單純表（基底 $S_1=100,\ S_2=80$）

進基變數：$Z$ 列最負者 $X_3(-4)$。 比值測試：$100/5=20$，$80/4=20$ → 打平。取 $S_1$ 列為出基（樞紐元 $5$）。

Step 3：第一次樞紐運算（$X_3$ 進基，$S_1$ 出基）

因第一次比值測試打平，$S_2$ 列出現 RHS=0（退化），須留意。

Step 4：第二次樞紐運算（進基 $X_2$，因 RHS 打平原理取 $S_2$ 列出基，樞紐元 $0.4$）

Step 5：第三次樞紐運算（進基 $X_1$，比值 $20/2=10$，出基 $X_3$，樞紐元 $2$）

$Z$ 列所有係數 $\ge 0$（$2,0,3/2$），達最佳解。

最佳解：$X_1=10,\ X_2=30,\ X_3=0,\ Z^*=120$

驗證：$4(10)+2(30)+5(0)=100\checkmark$；$2(10)+2(30)+4(0)=80\checkmark$（兩限制式恰好都緊繃）。

(二) 目標函數係數允許變動範圍

判斷法則：以最終表為基準，改變 $c_j$ 後，所有非基變數的 $z_j-c_j$ 仍須 $\ge0$。

① $X_3$（非基變數，值＝0）

$X_3$ 的 $z_3-c_3=2$。設 $c_3\to c_3+\Delta$，則新 reduced cost $=2-\Delta\ge0\Rightarrow \Delta\le2$。 $c_3\le 4+2=6\quad\Rightarrow\quad \boxed{c_3\in(-\infty,\ 6]}$ （下限無限制，因 $X_3$ 係數減少只會讓它更不吸引人進基。）

核心觀念

本題是「指派問題（Assignment Problem）」的變化題型，重點考兩件事：

1. 不平衡指派問題（Unbalanced Assignment Problem）：機器只有 3 台（$u,v,w$），但候選位置有 4 個（A、B、C、D），機器數 < 位置數，必然有 1 個位置閒置不用。
2. 禁止指派（Forbidden Assignment）：機器 $v$ 不能放在位置 C，這種限制在 LP 中以「不設該變數」或「令該變數＝0」處理；在匈牙利法中則以「極大成本 $M$」取代，使其在追求最小化的過程中永遠不會被選中。

由於指派問題本質上是 0-1 整數規劃，但其限制矩陣具有完全單模（totally unimodular）的特性，因此可用匈牙利法（Hungarian Method）直接求解最佳整數解，不需要用到 Big-M 單體法或分支界定法。

解題方法

(一) 線性規劃模式建構（8分）

決策變數： $x_{ij}=\begin{cases}1,&\text{機器 }i\text{ 指派於位置 }j\\0,&\text{否則}\end{cases}\quad i\in\{u,v,w\},\ j\in\{A,B,C,D\}$

目標函數（總搬運頻率最小化）： $\min Z = 70x_{uA}+80x_{uB}+140x_{uC}+120x_{uD}$ $+90x_{vA}+60x_{vB}+140x_{vD}$ $+60x_{wA}+110x_{wB}+100x_{wC}+150x_{wD}$

（注意：不含 $x_{vC}$ 項，因為此變數直接視為不存在，即禁止指派。）

限制式：

每台機器恰指派 1 個位置（機器數＝3，等式）： $x_{uA}+x_{uB}+x_{uC}+x_{uD}=1$ $x_{vA}+x_{vB}+x_{vD}=1$ $x_{wA}+x_{wB}+x_{wC}+x_{wD}=1$

每個位置至多指派 1 台機器（位置數＝4＞機器數，故用 $\le 1$，允許閒置）： $x_{uA}+x_{vA}+x_{wA}\le 1$ $x_{uB}+x_{vB}+x_{wB}\le 1$ $x_{uC}+x_{wC}\le 1$ $x_{uD}+x_{vD}+x_{wD}\le 1$

非負整數（0-1）限制： $x_{ij}\in\{0,1\}\ \ \forall i,j$

關鍵：機器限制用「＝1」（每台機器一定要用），位置限制用「≤1」（位置可以閒置），這是不平衡指派問題 LP 模式的標準寫法，也是本題配分的核心判斷點。

(二) 匈牙利法求解（7分）

Step 1：補上虛擬機器（dummy）以平衡矩陣

因為機器（3）＜位置（4），需新增一個「虛擬機器」列（成本全設為 0），把矩陣補成 $4\times4$ 方陣；同時將 $v$-C 這格設為極大值 $M$（代表禁止指派）：

Step 2：列縮減（每列減去該列最小值）

• $u$ 列最小＝70 → $0,\ 10,\ 70,\ 50$
• $v$ 列最小＝60 → $30,\ 0,\ M-60,\ 80$
• $w$ 列最小＝60 → $0,\ 50,\ 40,\ 90$
• dummy 列最小＝0 → $0,\ 0,\ 0,\ 0$

Step 3：欄縮減（每欄最小值皆已為 0，因 dummy 列全 0）

各欄最小值皆為 0，矩陣不變：

核心觀念

本題考的是馬可夫鏈（Markov Chain）在市場占有率分析上的應用，屬於「作業研究」中隨機過程（Stochastic Process）的基本題型。核心工具有三個：

1. 一步轉移矩陣 $P$：$P_{ij}$ 表示「這次在 $i$ 店消費，下次轉到 $j$ 店消費」的條件機率，每一列（row）之和必為 1。
2. $n$ 步轉移機率：由 Chapman-Kolmogorov 方程式，$n$ 步轉移矩陣為 $P^n$（矩陣連乘），即 $(P^n)_{ij}$ 表示由狀態 $i$ 經 $n$ 步到達狀態 $j$ 的機率。
3. 狀態機率（占有率）的遞推公式：若目前市場占有率（機率分配列向量）為 $\pi_0$，則 $t$ 期後的占有率為

$\pi_t = \pi_0 P^t$

4. 穩態分配（Steady-State / Stationary Distribution）：當轉移矩陣為正則（regular）——即存在某個 $n$ 使 $P^n$ 所有元素皆為正——則不論初始分配為何，經過長時間後系統會收斂到唯一的穩態分配 $\pi$，滿足

$\pi = \pi P,\qquad \sum_i \pi_i = 1$

本題 $P$ 矩陣所有元素皆為正（無 0 元素），故一步就已滿足正則條件，穩態必存在且唯一、與初始占有率無關——這正是第(四)小題要驗證的觀念。

矩陣設定（列與行皆依序為甲、乙、丙）：

$P=\begin{bmatrix}0.7 & 0.2 & 0.1\\0.1 & 0.8 & 0.1\\0.1 & 0.3 & 0.6\end{bmatrix}$

(一) 顧客本次在乙店，下下次仍在乙店的機率

解題方法：「下下次」即經過 2 步（two-step transition），要求的是 $(P^2)_{22}$。依矩陣乘法定義：

$(P^2)_{22}=\sum_{k=1}^{3}P_{2k}P_{k2}=P_{21}P_{12}+P_{22}P_{22}+P_{23}P_{32}$

代入數值：

$(P^2)_{22}=(0.1)(0.2)+(0.8)(0.8)+(0.1)(0.3)=0.02+0.64+0.03=0.69$

意義驗證：可拆解為三條路徑「乙→甲→乙」「乙→乙→乙」「乙→丙→乙」的機率相加，符合馬可夫鏈「先分岔、再匯聚」的直觀理解。

【答案】$0.69$（即 $69\%$）

(二) 兩個月後各店市場占有率

解題方法：初始占有率為列向量 $\pi_0=(0.2,\ 0.4,\ 0.4)$，兩個月後占有率為

$\pi_2=\pi_0 P^2=(\pi_0 P)P$

採逐期遞推（先算一個月後、再算兩個月後）比直接算 $P^2$ 再乘 $\pi_0$ 更不易出錯，建議實作時採此法。

Step 1：一個月後 $\pi_1=\pi_0 P$

$\pi_1(甲)=0.2(0.7)+0.4(0.1)+0.4(0.1)=0.14+0.04+0.04=0.22$ $\pi_1(乙)=0.2(0.2)+0.4(0.8)+0.4(0.3)=0.04+0.32+0.12=0.48$ $\pi_1(丙)=0.2(0.1)+0.4(0.1)+0.4(0.6)=0.02+0.04+0.24=0.30$

檢核：$0.22+0.48+0.30=1$ ✓

Step 2：兩個月後 $\pi_2=\pi_1 P$

$\pi_2(甲)=0.22(0.7)+0.48(0.1)+0.30(0.1)=0.154+0.048+0.030=0.232$ $\pi_2(乙)=0.22(0.2)+0.48(0.8)+0.30(0.3)=0.044+0.384+0.090=0.518$ $\pi_2(丙)=0.22(0.1)+0.48(0.1)+0.30(0.6)=0.022+0.048+0.180=0.250$

檢核：$0.232+0.518+0.250=1$ ✓

【答案】兩個月後：甲店 $23.2\%$、乙店 $51.8\%$、丙店 $25.0\%$

核心觀念

本題考「有向無循環網路的最短路徑動態規劃」。由於網路分層且所有弧線均由左向右，適合採用由終點 $J$ 反向計算的後推式動態規劃。

令

則對任一節點 $i$，其最佳值等於「目前弧距離加上下一節點的最佳值」之最小者。

解題方法與遞迴關係式

圖中各節點的弧線如下：

• $A\to B=12,\ A\to C=14,\ A\to D=13$
• $B\to E=17,\ B\to F=14,\ B\to G=16$
• $C\to E=17,\ C\to F=12,\ C\to G=14$
• $D\to E=18,\ D\to F=11,\ D\to G=15$
• $E\to H=11,\ E\to I=14$
• $F\to H=16,\ F\to I=13$
• $G\to H=13,\ G\to I=13$
• $H\to J=13,\ I\to J=14$

最佳值函數的遞迴關係式為

其中 $S(i)$ 為節點 $i$ 的後續節點，$d_{ij}$ 為弧線 $(i,j)$ 的距離。

邊界條件為

由終點反向計算

第 1 層：節點 $H、I$

第 2 層：節點 $E、F、G$

節點 $E$：

因此 $E$ 的最佳後續節點為 $H$。

節點 $F$：

因此 $F$ 的最佳後續節點為 $I$。

節點 $G$：

因此 $G$ 的最佳後續節點為 $H$。

第 3 層：節點 $B、C、D$

節點 $B$：

核心觀念

本題考的是二人零和賽局（Two-Person Zero-Sum Game）之混合策略解法，涵蓋三個核心工具：

1. 鞍點（Saddle Point）判定：先以 $\max_i \min_j a_{ij}$（甲方最大化最小報酬）與 $\min_j \max_i a_{ij}$（乙方最小化最大報酬）比較，若兩者相等即為純策略解；不相等才需要混合策略。
2. 優勢策略消去法（Dominance）：若某一策略（行或列）之報酬在所有情形下都不劣於另一策略，則劣勢策略可剔除，藉此把 $3\times3$ 賽局化簡為 $2\times2$ 賽局，方便手算。
3. $2\times2$ 賽局混合策略公式：利用「對方任意選擇時，我方期望報酬皆相等」的均衡條件解機率與賽局值。

關於缺失數值的說明：原卷 $S_3,T_3$ 位置數值擷取不全。依本題設計（15 分鐘內須以人工求解，必然需要藉優勢策略化簡為 $2\times2$ 賽局），並比對矩陣其餘數字的排列規律，該缺失值合理設定為 $-1$。以下即以此假設完整解題，其推導方式對任何具體數值皆通用。

於是完整報酬矩陣為：

解題方法（逐步推導）

步驟一：檢查是否存在鞍點

各列最小值（甲方保守估計）： $S_1:\min(-1,8,-1)=-1,\quad S_2:\min(9,0,6)=0,\quad S_3:\min(1,7,-1)=-1$ $\text{maximin}=\max(-1,0,-1)=0$

各行最大值（乙方保守估計）： $T_1:\max(-1,9,1)=9,\quad T_2:\max(8,0,7)=8,\quad T_3:\max(-1,6,-1)=6$ $\text{minimax}=\min(9,8,6)=6$

因為 $\text{maximin}=0 \ne \text{minimax}=6$，不存在純策略鞍點，須求混合策略解。

步驟二：優勢策略消去法（化簡矩陣）

先看乙方（欄）：比較 $T_1=(-1,9,1)$ 與 $T_3=(-1,6,-1)$，逐項比對： $-1\le -1,\quad 6\le 9,\quad -1\le 1$ $T_3$ 在每一列都不比 $T_1$ 差（對乙而言數值越小越好），故 $T_3$ 優於（弱勢支配）$T_1$，$T_1$ 可剔除。

剔除 $T_1$ 後，矩陣化簡為：

再看甲方（列）：比較 $S_1=(8,-1)$ 與 $S_3=(7,-1)$： $8\ge 7,\quad -1\ge -1$ $S_1$ 每項皆不劣於 $S_3$（對甲而言數值越大越好），故 $S_1$ 支配 $S_3$，$S_3$ 可剔除。

最終化簡為 $2\times2$ 賽局：

步驟三：求解 $2\times2$ 混合策略

設矩陣為 $\begin{pmatrix}a&b\\c&d\end{pmatrix}=\begin{pmatrix}8&-1\\0&6\end{pmatrix}$。