112 高普考高考二級 工業工程 作業研究（包括線性規劃與等候理論） 考古題詳解

核心觀念

本題考線性規劃的圖解法與表格式單純法。圖解法以可行域的角點求極值；單純法則將限制式化為等式，從一個初始基本可行解出發，經樞紐運算逐步改善目標值。

各限制式的邊界為：

$$2X_1-3X_2=6,\qquad X_1+2X_2=10,\qquad X_1+X_2=6$$

由於 $X_1,X_2\geq 0$，解題時須同時考慮第一象限及各限制式所指定的不等式方向。

（一）圖解法

1. 確認可行域方向

將各限制式改寫成 $X_2$ 的形式：

$$2X_1-3X_2\leq 6 \quad\Longleftrightarrow\quad X_2\geq \frac{2X_1-6}{3}$$ $$X_1+2X_2\geq 10 \quad\Longleftrightarrow\quad X_2\geq \frac{10-X_1}{2}$$ $$X_1+X_2\geq 6 \quad\Longleftrightarrow\quad X_2\geq 6-X_1$$

可行域位於第一象限，且在三條限制線所指定的上方一側。目標函數為 $Z=3X_1+4X_2$，兩變數的係數皆為正，因此往右上方移動時 $Z$ 增加，最小值會出現在可行域靠左下側的角點。

2. 求可行角點

先求第二、第三條限制線交點：

$$\begin{aligned} X_1+2X_2&=10,\\ X_1+X_2&=6. \end{aligned}$$

相減得 $X_2=4$，代回得 $X_1=2$，故交點為 $(2,4)$。代入第一條限制式：

$$2(2)-3(4)=-8\leq 6,$$

所以此點可行。

再求第一、第二條限制線交點：

$$\begin{aligned} 2X_1-3X_2&=6,\\ X_1+2X_2&=10. \end{aligned}$$

解得 $(X_1,X_2)=(6,2)$，其目標值為 $Z=26$。第三條限制式在此點為 $6+2\geq6$，故此點亦可行。

第一、第三條限制線交點為 $(12,6)$，但不符合第二條限制式，因此不是可行角點。另，$X_1=0$ 與 $X_1+2X_2=10$ 交於 $(0,5)$，但不符合 $X_1+X_2\geq6$；$X_1=0$ 與 $X_1+X_2=6$ 交於 $(0,6)$，則符合其他限制式，也是可行角點。

3. 比較可行角點的目標值

$$\begin{array}{c|c} (X_1,X_2)&Z=3X_1+4X_2\\ \hline (0,6)&24\\ (2,4)&22\\ (6,2)&26 \end{array}$$

可行角點 $(2,4)$ 的目標值最小。

（二）表格式單純法

1. 化為標準形式

第一條限制式加上鬆弛變數 $s_1$：

$$2X_1-3X_2+s_1=6.$$

第二、第三條限制式為大於等於型態，各減去剩餘變數並加入人工變數：

$$X_1+2X_2-s_2+a_2=10,$$ $$X_1+X_2-s_3+a_3=6.$$

以兩階段法求解。第一階段令人工變數總和最小：

$$\min W=a_2+a_3.$$

核心觀念

本題考查線性規劃的對偶問題構造，以及如何運用對偶弱性質證明原始問題最佳目標值的上界。

原始問題為極大化問題，限制式為「$\leq$」型，且變數非負。其對偶問題的對應規則是：

• 每一條原始限制式對應一個對偶變數；原始限制式為「$\leq$」型，故對偶變數非負。
• 原始問題為極大化，故對偶問題為極小化。
• 原始變數非負，故對偶限制式為「$\geq$」型。
• 對偶目標式的係數取自原始限制式右側常數；對偶限制式右側係數取自原始目標式中的變數係數。

解題方法

令第一、第二條原始限制式所對應的對偶變數分別為 $Y_1$、$Y_2$。由原始限制式均為「$\leq$」型，可得

$$Y_1\geq 0,\qquad Y_2\geq 0.$$

原始限制式右側常數為 $24$ 與 $2$，因此對偶目標式為極小化 $W=24Y_1+2Y_2$。

依各原始變數的係數建立對偶限制式：

• $X_1$ 在兩條限制式中的係數為 $1,1$，其原始目標係數為 $-1$，故 $Y_1+Y_2\geq -1$。
• $X_2$ 的係數為 $1,1$，其原始目標係數為 $-2$，故 $Y_1+Y_2\geq -2$。
• $X_3$ 的係數為 $2,-1$，其原始目標係數為 $-1$，故 $2Y_1-Y_2\geq -1$。

（一）原始問題的對偶問題

核心觀念

本題考「決策分析」中的償付矩陣與赫威茲準則。每天實際可銷售數量是本性狀態，進貨數量是可行方案；各格填入該方案在相應銷售狀態下的利潤。

設進貨量為 $Q$、銷售量為 $D$。售出數量為 $\min(Q,D)$，未售出數量為 $\max(Q-D,0)$，因此：

$$\text{利潤} =100\min(Q,D)+10\max(Q-D,0)-50Q$$

其中，銷售收入為每個 $100$ 元，未售商品由供應商以每個 $10$ 元買回，全部進貨則須支付每個 $50$ 元成本。

解題方法：建立償付矩陣

列為進貨方案 $Q$，欄為本性狀態 $D$。依上述利潤公式逐格計算：

進貨量 $Q$ \ 銷售量 $D$	20 個	30 個	40 個	50 個
20 個	$1{,}000$	$1{,}000$	$1{,}000$	$1{,}000$
30 個	$600$	$1{,}500$	$1{,}500$	$1{,}500$
40 個	$200$	$1{,}100$	$2{,}000$	$2{,}000$
50 個	$-200$	$700$	$1{,}600$	$2{,}500$

例如，進貨 $40$ 個而可銷售 $20$ 個時，售出 $20$ 個，剩餘 $20$ 個以殘值買回：

$$20(100)+20(10)-40(50)=200\text{ 元}$$

進貨 $50$ 個而只能銷售 $20$ 個時：

$$20(100)+30(10)-50(50)=-200\text{ 元}$$

解題方法：赫威茲準則

赫威茲準則以樂觀指數 $\alpha$ 加權各方案的最佳與最差利潤：

$$H(Q)=\alpha(\text{該方案最大利潤})+ (1-\alpha)(\text{該方案最小利潤})$$

$\alpha=1$ 表示完全樂觀，$\alpha=0$ 表示完全悲觀。由矩陣讀出各方案的最大與最小利潤：

進貨量	最小利潤	最大利潤	赫威茲值 $H(Q)$

核心觀念

本題是平衡運輸問題。各供應商可供應的總量為 $10+15+25=50$ 公噸，各工地的需求總量為 $20+10+20=50$ 公噸，供給量等於需求量，因此不必增設虛擬供應商或虛擬工地。

每噸原料的總成本，等於「供應商售價＋該供應商至工地的運費」。令 $x_{ij}$ 表示從供應商 $i$ 運送至工地 $j$ 的公噸數，則目標是使各路線的單位總成本乘以運送量後加總最低。

（一）運輸問題參數表

先將每噸售價加上相應運費，得到各路線的單位總成本：

供應商	工地 A	工地 B	工地 C	供應量（公噸）
R	$80+40=120$	$80+70=150$	$80+60=140$	10
S	$100+70=170$	$100+40=140$	$100+50=150$	15
T	$120+60=180$	$120+70=190$	$120+55=175$	25
需求量（公噸）	20	10	20	50

各格數字的單位為元／公噸。以 $c_{ij}$ 表示供應商 $i$ 運至工地 $j$ 的每噸總成本，則線性規劃模式為：

$$\min Z= 120x_{RA}+150x_{RB}+140x_{RC} +170x_{SA}+140x_{SB}+150x_{SC} +180x_{TA}+190x_{TB}+175x_{TC}$$

供應量限制為：

$$x_{RA}+x_{RB}+x_{RC}=10$$ $$x_{SA}+x_{SB}+x_{SC}=15$$ $$x_{TA}+x_{TB}+x_{TC}=25$$

需求量限制為：

$$x_{RA}+x_{SA}+x_{TA}=20$$ $$x_{RB}+x_{SB}+x_{TB}=10$$ $$x_{RC}+x_{SC}+x_{TC}=20$$

且 $x_{ij}\geq 0$。

（二）最佳運輸規劃

1. 建立初始可行解

依單位總成本由低至高配置，並在每次配置後扣除相應供應量與需求量：

1. R 運至 A 的成本為 120 元，是最低成本路線。R 供應 10 公噸，配置 $x_{RA}=10$。R 用罄，A 尚需 10 公噸。
2. S 運至 B 的成本為 140 元。B 需求 10 公噸，配置 $x_{SB}=10$。B 滿足，S 尚餘 5 公噸。
3. T 運至 C 的成本為 175 元。T 供應 25 公噸，C 需求 20 公噸，配置 $x_{TC}=20$。C 滿足，T 尚餘 5 公噸。
4. 剩餘 A 尚需 10 公噸，S 尚餘 5 公噸、T 尚餘 5 公噸，因此配置 $x_{SA}=5$、$x_{TA}=5$。

此配置的非零運量為：

供應商	工地 A	工地 B	工地 C	供應量
R	10	0	0	10
S	5	10	0	15
T	5	0	20	25
需求量	20	10	20

2. 檢驗是否為最佳解

初始配置有 6 個正運量格，超過運輸問題基本可行解所需的 $m+n-1=3+3-1=5$ 個基底格，因此此解為退化情形。為了進行位勢檢驗，將一個目前運量為零的格視為零運量基底格；取 $x_{TA}=0$ 作為基底格。

對基底格使用 $u_i+v_j=c_{ij}$，令 $u_R=0$，依序求得：

• $x_{RA}$ 為基底格：$u_R+v_A=120$，故 $v_A=120$。
• $x_{TA}$ 為基底格：$u_T+v_A=180$，故 $u_T=60$。