110 地方特考三等 工業工程 作業研究 考古題詳解

核心觀念

本題考查線性規劃之基底矩陣、基底逆矩陣、基本解與陰影價格。

先將限制式改寫為標準型，加入差額變數 $s_1,s_2,s_3$：

$$\begin{aligned} -x_1+x_2+x_3+s_1&=2\\ 2x_1-x_2+x_3+s_2&=1\\ x_1+x_2+3x_3+s_3&=6 \end{aligned}$$

其係數矩陣為

$$A= \begin{bmatrix} -1&1&1&1&0&0\\ 2&-1&1&0&1&0\\ 1&1&3&0&0&1 \end{bmatrix},$$

變數順序為 $(x_1,x_2,x_3,s_1,s_2,s_3)$。

已知基變數為 $x_2,x_3,s_3$，因此基底矩陣 $B$ 是由 $A$ 中 $x_2,x_3,s_3$ 的欄所組成。

---

（一）建構最佳解之基底矩陣 $B$

各基變數之係數欄為

$$a_2= \begin{bmatrix} 1\\-1\\1 \end{bmatrix}, \qquad a_3= \begin{bmatrix} 1\\1\\3 \end{bmatrix}, \qquad a_{s_3}= \begin{bmatrix} 0\\0\\1 \end{bmatrix}.$$

依照基變數順序 $(x_2,x_3,s_3)$，基底矩陣為

$$\boxed{ B= \begin{bmatrix} 1&1&0\\ -1&1&0\\ 1&3&1 \end{bmatrix} }$$

---

（二）以高斯－喬登法求 $B^{-1}$

組成增廣矩陣：

$$\left[ \begin{array}{ccc|ccc} 1&1&0&1&0&0\\ -1&1&0&0&1&0\\ 1&3&1&0&0&1 \end{array} \right]$$

先進行列運算：

$$R_2\leftarrow R_2+R_1,\qquad R_3\leftarrow R_3-R_1$$

得

$$\left[ \begin{array}{ccc|ccc} 1&1&0&1&0&0\\ 0&2&0&1&1&0\\ 0&2&1&-1&0&1 \end{array} \right].$$

再進行

$$R_2\leftarrow \frac{1}{2}R_2$$

得

$$\left[ \begin{array}{ccc|ccc} 1&1&0&1&0&0\\ 0&1&0&\frac12&\frac12&0\\ 0&2&1&-1&0&1 \end{array} \right].$$

消去第一列與第三列中的第二欄：

$$R_1\leftarrow R_1-R_2,\qquad R_3\leftarrow R_3-2R_2$$

得

$$\left[ \begin{array}{ccc|ccc} 1&0&0&\frac12&-\frac12&0\\ 0&1&0&\frac12&\frac12&0\\ 0&0&1&-2&-1&1 \end{array} \right].$$

因此

$$\boxed{ B^{-1}= \begin{bmatrix} \frac12&-\frac12&0\\ \frac12&\frac12&0\\ -2&-1&1 \end{bmatrix} }$$

---

（三）利用 $B^{-1}$ 求最佳解及目標函數值

右側常數向量為

$$b= \begin{bmatrix} 2\\1\\6 \end{bmatrix}.$$

基本變數向量為

$$x_B=B^{-1}b.$$

代入所求之逆矩陣：

核心觀念

本題考查「資源分配問題」的動態規劃。有限資源為 6 個廣告時段，必須分配給 3 個地區，且每個地區至少分配 1 個時段，以使總增加銷售量最大。

設：

• $A_i(x)$：地區 $i$ 購買 $x$ 個廣告時段所增加的銷售量
• $F_j(n)$：將 $n$ 個廣告分配給前 $j$ 個地區的最大增加銷售量

動態規劃遞迴式為：

$$F_j(n)=\max_{1\leq k\leq n-j+1} \left\{F_{j-1}(n-k)+A_j(k)\right\}$$

其中 $k$ 表示分配給第 $j$ 個地區的廣告數量。

由於題目擷取文字中第 1、2 次廣告的數值缺漏，無法由題面唯一確定原始數據。以下依各地區資料呈現的整數遞增型態，採合理補值：

廣告次數	地區 1	地區 2	地區 3
1	9	3	6
2	15	9	12
3	21	12	18
4	30	24	27
5	42	33	39
6	51	42	45

---

解題方法

第一步：只考慮地區 1

因為每個地區至少要有 1 個廣告，所以：

$$F_1(n)=A_1(n)$$

因此：

$n$	$F_1(n)$
1	9
2	15
3	21
4	30
5	42
6	51

第二步：分配給地區 1、2

$$F_2(n)=\max_{1\leq k\leq n-1} \{F_1(n-k)+A_2(k)\}$$

其中 $k$ 為分配給地區 2 的廣告數量。

總廣告數 $n$	各種分配計算	$F_2(n)$
2	$9+3=12$	12
3	$\max(15+3,\;9+9)=18$	18
4	$\max(21+3,\;15+9,\;9+12)=24$	24
5	$\max(30+3,\;21+9,\;15+12,\;9+24)=33$	33
6	$\max(42+3,\;30+9,\;21+12,\;15+24,\;9+33)=45$	45

例如：

核心觀念

本題考查兩個重點：

1. 不平衡運輸問題的平衡化、Vogel 近似法與運輸單形法。
2. 具有最小需求量與最大需求量限制之運輸問題轉換。

原題供應總量為

$$240+190+170=600$$

需求總量為

$$100+130+190=420$$

供應量超過需求量 $180$，因此須增設「虛擬倉庫」作為剩餘供應量的去處，需求量為 $180$，各工廠運至虛擬倉庫的成本設為 $0$。

---

（一）利用 Vogel 近似法求初始可行基解

1. 增設虛擬倉庫

	倉庫1	倉庫2	倉庫3	虛擬倉庫	供應量
工廠1	50	100	110	0	240
工廠2	90	80	120	0	190
工廠3	60	70	210	0	170
需求量	100	130	190	180	600

Vogel 近似法每次計算各列、各欄中最小成本與次小成本之差，稱為罰數：

$$\text{罰數}=\text{次小成本}-\text{最小成本}$$

2. 第一次分配

各列罰數：

• 工廠1：$50-0=50$
• 工廠2：$80-0=80$
• 工廠3：$60-0=60$

各欄罰數：

• 倉庫1：$60-50=10$
• 倉庫2：$80-70=10$
• 倉庫3：$120-110=10$
• 虛擬倉庫：$0$

最大罰數為工廠2之 $80$，選該列最小成本格，即虛擬倉庫：

$$x_{24}=\min(190,180)=180$$

工廠2剩餘供應量為 $10$，虛擬倉庫需求已滿足。

3. 第二次分配

剩餘問題中，工廠3的罰數為：

$$210-60=150$$

選工廠3之最小成本格，運至倉庫1：

$$x_{31}=\min(170,100)=100$$

倉庫1需求已滿足，工廠3剩餘供應量為 $70$。

4. 第三次分配

剩餘倉庫為倉庫2與倉庫3。工廠3之罰數為：

$$210-70=140$$

因此分配至倉庫2：

$$x_{32}=\min(70,130)=70$$

工廠3供應量用罄，倉庫2剩餘需求量為 $60$。

5. 第四次分配

工廠2剩餘供應量為 $10$，其最小成本為倉庫2，因此：

$$x_{22}=\min(10,60)=10$$

倉庫2剩餘需求量為 $50$。

6. 完成分配

工廠1供應量為 $240$，剩餘倉庫2需求 $50$、倉庫3需求 $190$：

$$x_{12}=50,\qquad x_{13}=190$$

因此，Vogel 近似法所得初始可行基解為：

	倉庫1	倉庫2	倉庫3	虛擬倉庫	供應量
工廠1	0	50	190	0	240
工廠2	0	10	0	180	190
工廠3	100	70	0	0	170
需求量	100	130	190	180	600

共有 $m+n-1=3+4-1=6$ 個基變數，故為非退化初始基解。

初始總成本為：

$$Z=50(100)+70(70)+80(10)+100(50)+110(190)$$ $$Z=6000+4900+800+5000+20900=37600$$

---

（二）利用運輸單形法求最佳解

第一次迭代

對初始基解求位勢 $u_i,v_j$，使所有基變數滿足：

$$u_i+v_j=c_{ij}$$

令 $u_1=0$，由基變數得到：

$$v_2=100,\quad v_3=110,\quad u_2=-20,\quad v_4=20,\quad u_3=-30,\quad v_1=90$$

非基變數的相對成本為：

$$\bar c_{ij}=c_{ij}-(u_i+v_j)$$

其中：

$\bar c_{11}=50-(0+90)=-40$

$\bar c_{21}=90-(-20+90)=20$

$\bar c_{23}=120-(-20+110)=30$

$\bar c_{33}=210-(-30+110)=130$

$\bar c_{34}=0-(-30+20)=10$

因為 $\bar c_{11}=-40<0$，故 $x_{11}$ 進入基底。

形成閉迴路：

$$(1,1)^+\rightarrow(1,2)^-\rightarrow(3,2)^+ \rightarrow(3,1)^-\rightarrow(1,1)$$

可調整量為：

$$\theta=\min(x_{12},x_{31})=\min(50,100)=50$$

更新後：

$x_{11}=50,\quad x_{12}=0,\quad x_{31}=50,\quad x_{32}=120$

其他變數維持不變。新成本為：

$$Z=37600-40(50)=35600$$

---

第二次迭代

目前基變數為：

$$x_{11},x_{13},x_{22},x_{24},x_{31},x_{32}$$

令 $u_1=0$，由基變數求得：

$$v_1=50,\quad v_3=110,\quad u_3=10,\quad v_2=60,$$ $$u_2=20,\quad v_4=-20$$

非基變數相對成本：

$\bar c_{12}=100-(0+60)=40$

$\bar c_{21}=90-(20+50)=20$

$\bar c_{23}=120-(20+110)=-10$

$\bar c_{33}=210-(10+110)=90$

$\bar c_{34}=0-(10-20)=10$

核心觀念

本題考查有限狀態馬可夫鏈（Markov chain）。

以乘客上車地點作為狀態，設：

• $K$：基隆市
• $T$：臺北市
• $N$：新北市

由題目資料，轉移機率矩陣為

$$P= \begin{bmatrix} 0.6&0.3&0.1\\ 0.2&0.5&0.3\\ 0.1&0.4&0.5 \end{bmatrix},$$

其中每一列表示「目前上車地點」，每一欄表示「下一位乘客上車地點」。

司機在某地送客下車後，下一位乘客即在該地下車地點上車，因此可用馬可夫鏈描述地點變化。

---

（一）第三位乘客下車時位於新北市的機率

解題方法

司機一開始在臺北市工作，因此第一位乘客的上車地點視為臺北市，初始狀態向量為

$$\boldsymbol{p}_0= \begin{bmatrix} 0&1&0 \end{bmatrix}.$$

第三位乘客下車時的位置，相當於從臺北市經過三次地點轉移後的狀態，因此要求

$$\boldsymbol{p}_0P^3$$

中的新北市分量。

先計算兩次轉移後的分布：

$$\boldsymbol{p}_0P^2 = \begin{bmatrix} 0.23&0.43&0.32 \end{bmatrix}.$$

再轉移一次：

$$\boldsymbol{p}_0P^3 = \begin{bmatrix} 0.23&0.43&0.32 \end{bmatrix} \begin{bmatrix} 0.6&0.3&0.1\\ 0.2&0.5&0.3\\ 0.1&0.4&0.5 \end{bmatrix}.$$

新北市分量為

$$0.23(0.1)+0.43(0.3)+0.32(0.5) =0.023+0.129+0.160 =0.312.$$

因此，

$$\boxed{P(\text{第三位乘客下車時位於新北市})=0.312}$$

即為

$$\boxed{31.2\%}.$$

---

（二）每月期望收入

解題方法

每位乘客的平均車資取決於其上車地點：

$$\boldsymbol{r}= \begin{bmatrix} 230\\ 100\\ 200 \end{bmatrix}.$$

司機第一位乘客在臺北市上車，因此第一位乘客的上車地點分布為

$$\boldsymbol{p}_0= \begin{bmatrix} 0&1&0 \end{bmatrix}.$$

第 $n+1$ 位乘客的上車地點分布為

$$\boldsymbol{p}_0P^n.$$

所以每天服務 $23$ 位乘客時，每日總期望收入為