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

核心觀念

本題評量線性規劃（Linear Programming, LP）中最核心的演算法——單形法（Simplex Method），屬於工業工程技師「作業研究」必考之基礎計算題型。其涉及之核心觀念與定義如下：

1. 標準型（Standard Form）轉換：

• 極大化問題中，若限制式為「$\leq$」不等式，且右端值（Right-Hand Side, $\text{RHS} \geq 0$），需引入差額變數（Slack Variables）​轉換為等式。
• 所有變數（包含決策變數與差額變數）皆須滿足非負限制（$x_j \geq 0$）。

2. 基本可行解（Basic Feasible Solution, BFS）：

• 令非基底變數（Non-Basic Variables）為 $0$，解出基底變數（Basic Variables），對應可行解空間之極點（Extreme Point）。

3. 單形法疊代判斷準則：

• 進基準則（Entering Rule / Optimality Condition）：在目標列（Row 0）中，選取負係數絕對值最大者（即能使目標值增長最快之非基底變數）作為進基變數。
• 出基準則（Leaving Rule / Feasibility Condition）：利用最小比值測試（Minimum Ratio Test, MRT），在樞紐行元素嚴格大於 $0$（$a_{ij} > 0$）之列中，計算 $\frac{\text{RHS}}{a_{ij}}$，選取比值最小者對應之基底變數出基，確保新解仍維持非負可行性。
• 樞紐消去（Pivot Operation）：利用高斯-約當列運算（Gauss-Jordan Row Operations），使樞紐元素化為 $1$，該行其餘元素均化為 $0$。
• 最適性條件（Optimality Criterion）：當目標列中所有變數之係數皆大於或等於 $0$（無任何負檢定數）時，即獲得唯一或多重最適解。

解題方法

步驟一：將線性規劃模型轉換為標準型

引入差額變數 $s_1, s_2, s_3 \geq 0$，將原限制式改寫為等式系統；將目標函數移項整理至等號左側作為第 0 列（Row 0）：

起始基底變數選定為差額變數組 $(s_1, s_2, s_3)$，非基底變數為 $(x_1, x_2, x_3) = (0, 0, 0)$，起始目標函數值 $Z = 0$。

步驟二：建立起始單形表與第 1 次疊代（Iteration 1）

【起始單形表（Tableau 1）】

1. 決定進基變數：Row 0 中負值最大者為 $x_3$ 之係數（$-2$），故 $x_3$ 為進基變數。
2. 決定出基變數：計算比值，第 2 列（$s_2$ 列）之比值 $1$ 為最小，故 $s_2$ 為出基變數。樞紐元素（Pivot Element）為第 2 列、第 $x_3$ 行之數值 $1$。
3. 高斯-約當列運算：

• 新 Row 2 = 原 Row 2（樞紐元素已為 $1$）
• 新 Row 0 = 原 Row 0 $+ 2 \times$ 新 Row 2
• 新 Row 1 = 原 Row 1 $- 3 \times$ 新 Row 2
• 新 Row 3 = 原 Row 3 $- 1 \times$ 新 Row 2

步驟三：第 2 次疊代（Iteration 2）

【第 1 次疊代後單形表（Tableau 2）】

核心觀念

本題考查要徑法（Critical Path Method, CPM）與節點作業網路（Activity-on-Node, AON）。每項作業以一個節點表示，箭頭表示先後關係；若某作業有多項先行作業，必須等所有先行作業完成後才能開始。

本題以專案起始時間 $0$ 計算，使用以下公式：

• 正推：$EF=ES+\text{作業時間}$；有多項先行作業時，$ES=\max(\text{先行作業的 }EF)$。
• 逆推：$LS=LF-\text{作業時間}$；有多項後續作業時，$LF=\min(\text{後續作業的 }LS)$。
• 寬鬆時間：$ST=LS-ES=LF-EF$。$ST=0$ 的作業位於要徑上。

（一）AON 專案網路

依各作業的先行關係，網路如下：

開始 → A → B ─┬→ C → F → I ──────────┐
 ├→ D ─→ G ───────────┤
 │ └→ H ──────────┤→ J → 完成
 └→ E ─→ H ──────────┘

其中，$H$ 須等待 $D$、$E$ 完成；$J$ 須等待 $G$、$H$、$I$ 完成。

（二）ES、EF、LS、LF 與 ST

1. 正推：計算 ES 與 EF

從 $A$ 開始，$ES_A=0$，所以 $EF_A=0+6=6$。接著依序計算：

• $B$ 接在 $A$ 後：$ES_B=6$，$EF_B=6+10=16$。
• $C、D、E$ 接在 $B$ 後：三者的 $ES$ 均為 $16$。
• $F$ 接在 $C$ 後：$ES_F=20$，$EF_F=26$；$I$ 接在 $F$ 後：$ES_I=26$，$EF_I=42$。
• $G$ 接在 $D$ 後：$ES_G=20$，$EF_G=30$。
• $H$ 須等待 $D、E$：$ES_H=\max(20,24)=24$，$EF_H=30$。
• $J$ 須等待 $G、H、I$：$ES_J=\max(30,30,42)=42$，$EF_J=46$。

因此專案完成時間為 $46$ 天。

2. 逆推：計算 LS 與 LF

核心觀念

本題考「資源有限下的最佳分配」動態規劃。把 7 天視為有限資源，依序決定分配給各門課的天數；每門課至少分配 1 天，且依題目表格，每門課最多分配 4 天。

令 $F_i(t)$ 表示前 $i$ 門課合計分配 $t$ 天時，可得到的最高總分；令 $s_i(x)$ 表示第 $i$ 門課複習 $x$ 天的估計分數。遞迴式為：

只計算使前 $i-1$ 門課可行的 $t-x$；初始狀態為 $F_1(t)=s_1(t)$。

解題方法

先計算前兩門課的最佳分數，再逐門加入第 3、4 門課。下表括號內為達到該分數時，第 2 門課分配的天數。

例如，$F_2(4)=\max\{10+80,\;30+60,\;60+50\}=110$，所以前兩門課分配 $(3,1)$ 天時得分最高。

接著加入第 3 門課：

核心觀念

本題屬於作業研究（Operations Research）中的離散時間馬可夫鏈（Discrete-Time Markov Chain, DTMC）​應用題型，主要測驗以下核心觀念：

1. 狀態空間定義（State Space Formulation）：利用系統的物理守恆性（外套總數固定為 2 件），選取單一關鍵變數定義出具備「無記憶性（Markovian Property）」的系統狀態。
2. 單步轉移機率矩陣（One-Step Transition Probability Matrix）：依據出門與回家的路徑獨立性，結合條件判斷（門上有無外套）推導轉移機率。
3. 長期穩態分佈（Stationary / Steady-State Distribution）：求解馬可夫鏈的極限平衡機率向量 $\boldsymbol{\pi}$。
4. 全機率公式（Law of Total Probability）：結合穩態機率與各狀態下「穿外套出門」的條件機率，計算長期時間比例（Long-Run Proportion）。

解題方法

步驟一：定義系統狀態

設此人每天出門散步為一個時間步（Step $n$）。 令隨機變數 $X_n$ 代表第 $n$ 天出門前掛在「前門」的外套數量。 由於外套總數固定為 $2$ 件，後門的外套數量即為 $2 - X_n$。 因此狀態空間為： $S = \{0, 1, 2\}$

• 狀態 $0$：前門有 $0$ 件外套（後門有 $2$ 件）。
• 狀態 $1$：前門有 $1$ 件外套（後門有 $1$ 件）。
• 狀態 $2$：前門有 $2$ 件外套（後門有 $0$ 件）。

步驟二：分析每天的出門與進門路徑機率

設出門選擇為 $D_{\text{out}} \in \{F, B\}$（$F$ 為前門，$B$ 為後門），回家選擇為 $D_{\text{in}} \in \{F, B\}$。 依題意，出門與進門的選擇彼此獨立，且各門機率均等（均為 $1/2$），故四種可能路徑之組合機率皆為： $P(D_{\text{out}}, D_{\text{in}}) = \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$

步驟三：推導單步轉移機率矩陣 $P$

針對當前狀態 $X_n = i$，推導次日狀態 $X_{n+1} = j$ 的機率 $P_{ij}$：

1. 當當前狀態為 $0$（前門 $0$ 件，後門 $2$ 件）時：

• 若由前門出（機率 $1/2$）：前門無外套，不穿外套出門。回家時無論走前門或後門，都沒有外套可掛，前門仍維持 $0$ 件。此情境涵蓋 $(F, F)$ 與 $(F, B)$，機率合計為 $\frac{1}{4} + \frac{1}{4} = \frac{1}{2}$，轉移至狀態 $0$。
• 若由後門出（機率 $1/2$）：後門有外套，穿走 $1$ 件（此時後門剩 $1$ 件，前門 $0$ 件）。
• 若由前門進 $(B, F)$（機率 $1/4$）：將外套掛於前門，前門變為 $1$ 件，轉移至狀態 $1$。
• 若由後門進 $(B, B)$（機率 $1/4$）：將外套掛於後門，後門變回 $2$ 件，前門仍為 $0$ 件，轉移至狀態 $0$。
• 故轉移機率為： $P_{00} = \frac{1}{2} + \frac{1}{4} = \frac{3}{4}, \quad P_{01} = \frac{1}{4}, \quad P_{02} = 0$

2. 當當前狀態為 $1$（前門 $1$ 件，後門 $1$ 件）時：

• 兩扇門皆有外套，因此無論從哪扇門出門，必會穿一件外套出門。
• 若由前門出（前門剩 $0$ 件，後門 $1$ 件）：
• 由前門進 $(F, F)$（機率 $1/4$）：外套掛回前門，前門維持 $1$ 件，轉移至狀態 $1$。
• 由後門進 $(F, B)$（機率 $1/4$）：外套掛於後門，前門為 $0$ 件，轉移至狀態 $0$。
• 若由後門出（前門 $1$ 件，後門剩 $0$ 件）：
• 由前門進 $(B, F)$（機率 $1/4$）：外套掛於前門，前門變為 $2$ 件，轉移至狀態 $2$。
• 由後門進 $(B, B)$（機率 $1/4$）：外套掛回後門，前門維持 $1$ 件，轉移至狀態 $1$。
• 故轉移機率為： $P_{10} = \frac{1}{4}, \quad P_{11} = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}, \quad P_{12} = \frac{1}{4}$

3. 當當前狀態為 $2$（前門 $2$ 件，後門 $0$ 件）時：

• 依系統對稱性（前門與後門角色互換），推導結果與狀態 $0$ 對稱： $P_{20} = 0, \quad P_{21} = \frac{1}{4}, \quad P_{22} = \frac{3}{4}$

綜合以上，單步轉移機率矩陣為：