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

核心觀念

本題考查單形法與敏感度分析。先以單形法求出原問題的最適基底，再固定此基底，檢查各項資料變動後：

• 可行性：基底變數解 $x_B=B^{-1}b$ 是否仍非負。
• 最適性：最大化問題的非基底變數檢定數 $C_j-Z_j$ 是否皆小於或等於 $0$。

若基底解仍可行且所有檢定數皆不大於 $0$，原基底仍為最適基底。若只失去可行性或最適性，則分別以對偶單形法或一般單形法進行樞紐轉換。

(一) 以表格型單形法求最適解

加入差額變數 $x_4,x_5$：

$$\begin{aligned} x_1+3x_2+4x_3+x_4&=30,\\ x_1+4x_2-x_3+x_5&=10. \end{aligned}$$

初始基底為 $x_4,x_5$。先令 $x_2$ 入基，最小比值為 $10/4=5/2$，故 $x_5$ 出基。接著令 $x_1$ 入基，最小比值為 $10$，故 $x_2$ 出基。樞紐後表格如下，其中檢定數採 $C_j-Z_j$ 慣例：

基底變數	$C_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	RHS
$x_4$	0	0	$-1$	5	1	$-1$	20
$x_1$	2	1	4	$-1$	0	1	10
$C_j-Z_j$		0	$-1$	$-1$	0	$-2$

所有非基底變數的檢定數皆不大於 $0$，故此基底最適。令非基底變數 $x_2=x_3=x_5=0$，得

$$x_1=10,\qquad x_4=20,\qquad Z=2(10)=20.$$

因此原問題的最適解為

$$\boxed{(x_1,x_2,x_3)=(10,0,0),\qquad Z_{\max}=20.}$$

敏感度分析的共同基礎

原最適基底為 $(x_4,x_1)$，基底成本為 $(0,2)$。表格的兩個基底列可用來讀取 $B^{-1}A$，RHS 欄則為 $B^{-1}b$。原解的非基底變數為 $x_2,x_3,x_5$，其檢定數依序為 $-1,-1,-2$。

(二) RHS 改為 $(40,15)^T$

基底不變時，新基底解為

$$B^{-1}b_{\text{新}} = \begin{bmatrix} 1&-1\\ 0&1 \end{bmatrix} \begin{bmatrix} 40\\15 \end{bmatrix} = \begin{bmatrix} 25\\15 \end{bmatrix}.$$

因此 $x_4=25,\ x_1=15$，基底解仍非負，可行。RHS 的改變不影響檢定數，原來的檢定數仍為 $-1,-1,-2$，故原基底仍最適。

$$\boxed{(x_1,x_2,x_3)=(15,0,0),\qquad Z_{\max}=30.}$$

(三) $x_3$ 欄改為 $(c_3,a_{13},a_{23})^T=(-2,2,1)^T$

先將新 $x_3$ 欄轉換到目前表格：

$$B^{-1}a_3 = \begin{bmatrix} 1&-1\\ 0&1 \end{bmatrix} \begin{bmatrix} 2\\1 \end{bmatrix} = \begin{bmatrix} 1\\1 \end{bmatrix}.$$

新檢定數為

核心觀念

本題考查整數規劃建模。決策變數表示各機型購買架數，因此須限制為非負整數；目標是使總淨利潤最大。各限制式分別表達預算、機師人力與維修能力。

統一以「千萬元」為金額單位：15 億元等於 150 千萬元。以短程客機每架的維修需求為 1 單位，則中程與長程客機每架的維修需求分別為 $4/3$ 與 $5/3$ 單位。

解題方法

(一) 決策變數

令：

• $x_L$：增購長程客機的架數
• $x_M$：增購中程客機的架數
• $x_S$：增購短程客機的架數

因架數不可為負且必須為整數：

$$x_L,x_M,x_S\in\mathbb{Z}_{\ge 0}$$

(二) 目標式與限制式

目標式：最大化總淨利潤

三型客機每架淨利潤分別為 4.2、3、2.3 千萬元，因此：

$$\max Z=4.2x_L+3x_M+2.3x_S$$

預算限制

三型客機每架價格分別為 67、50、35 千萬元，總預算為 150 千萬元：

$$67x_L+50x_M+35x_S\le 150$$

機師人力限制

題目指出增購 30 架時現有機師仍足敷執行任務，因此總購買架數不得超過 30：

$$x_L+x_M+x_S\le 30$$

核心觀念

本題考兩人零和賽局的清償矩陣建構。工會與公司分別選擇一個整數時薪增額；仲裁人會接受讓步較多的一方所提的方案。若雙方讓步相同，或都維持原先的最終底線，仲裁結果為兩個底線的中間值 $13.5$。

將工會的利益設為正、公司的利益設為負，以「實際核定增額減 $13.5$」表示工會的清償值。這樣兩方清償值互為相反數，符合零和賽局設定。

解題方法

以 $x$ 表示工會提出的增額，以 $y$ 表示公司提出的增額。兩方可提出的整數方案為：

• 工會：$11,12,13,14,15,16$
• 公司：$11,12,13,14,15,16$

工會的最終底線是 $11$，因此提出 $x$ 的讓步量為 $x-11$。公司的最終底線是 $16$，因此提出 $y$ 的讓步量為 $16-y$。依題意，仲裁人接受讓步較多一方所提的方案：

• 若 $x-11>16-y$，工會讓步較多，採用工會方案 $x$，工會清償值為 $x-13.5$。
• 若 $x-11<16-y$，公司讓步較多，採用公司方案 $y$，工會清償值為 $y-13.5$。
• 若雙方讓步相等，採用中間值 $13.5$，工會清償值為 $0$。

讓步相等的條件為：

$$x-11=16-y \quad\Longleftrightarrow\quad x+y=27$$

若雙方都維持最終底線，即 $x=11,\ y=16$，也依題意採用 $13.5$，清償值為 $0$。

清償矩陣

下表各格為工會的清償值；公司的清償值為該格數值的相反數。列為工會方案，欄為公司方案。

工會方案 \ 公司方案	$11$	$12$	$13$	$14$	$15$	$16$
$11$	$-2.5$	$-1.5$	$-0.5$	$0.5$	$1.5$	$0$

核心觀念

馬可夫鍊的狀態分類以「互通」為準：若狀態 $i$ 可以在有限步內以正機率到達狀態 $j$，且 $j$ 也可以在有限步內以正機率回到 $i$，則 $i$ 與 $j$ 互通，記為 $i\leftrightarrow j$。互通關係將狀態集合分成若干個互斥的分類（class）。

若某分類中的狀態轉移後仍不會離開該分類，稱為封閉分類。有限狀態馬可夫鍊中，封閉分類內的狀態皆為重現狀態；非封閉分類則為中轉分類。

解題方法

依轉移矩陣的列判讀各狀態的一步轉移可能性，再檢查狀態間是否互通，以及分類是否封閉。矩陣中的零元素表示該一步轉移不可能；正元素表示該一步轉移具有正機率。

• 狀態 $0$ 與狀態 $1$ 彼此一步可達：$p_{01}=p_{10}=\frac34>0$。兩者轉移後仍只會留在 $\{0,1\}$，因此形成封閉分類 $\{0,1\}$。
• 狀態 $2$ 可以一步到達狀態 $0$、$1$、$2$，但狀態 $0$、$1$ 都不能到達狀態 $2$，因為矩陣中第 $0$、$1$ 列的第 $2$ 欄皆為 $0$。因此狀態 $2$ 不與 $0$ 或 $1$ 互通，只能自成一類 $\{2\}$。此類可以離開至 $\{0,1\}$，且離開後不能返回，故不是封閉分類。