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

核心觀念

本題是單一新機台的設施選址問題。三個組裝站的中心座標固定，新機台的位置為 $(x,y)$。採用直角距離（Rectilinear distance）時，新機台至第 $i$ 站的距離為

$$|x-a_i|+|y-b_i|,\qquad i=1,2,3.$$

各站的單位時間來回搬運量分別為 $5、7、2$，故目標是最小化「搬運量 × 距離」的加權總和：

$$5\bigl(|x-a_1|+|y-b_1|\bigr) +7\bigl(|x-a_2|+|y-b_2|\bigr) +2\bigl(|x-a_3|+|y-b_3|\bigr).$$

絕對值函數不是線性函數，因此必須引入輔助變數與線性限制式，才能完整改寫為線性規劃。

解題方法

令 $x,y$ 為新機台中心的 $x$、$y$ 座標。因題目允許任一象限，兩者均不設非負限制：

$$x,y\in\mathbb{R}.$$

對每個組裝站 $i$，令 $u_i$、$v_i$ 分別表示新機台與該站在 $x$ 軸、$y$ 軸上的距離。以兩條不等式線性化絕對值：

$$u_i\ge x-a_i,\qquad u_i\ge a_i-x,$$ $$v_i\ge y-b_i,\qquad v_i\ge b_i-y.$$

由於目標式以正的搬運量權重最小化 $u_i+v_i$，最適解會使 $u_i=|x-a_i|$、$v_i=|y-b_i|$。因此線性規劃模式為：

核心觀念

本題考線性規劃的互補鬆弛條件，以及如何用它檢驗原問題與對偶問題的解。互補鬆弛是線性規劃最適性的重要判準：原問題某項限制式若有剩餘量，對應的對偶變數必為零；原問題某個變數若為正，對應的對偶限制式必須緊束。

題目中的最大化問題為：

$$\begin{aligned} \max\quad & CX\\ \text{s.t.}\quad & AX\le b,\\ &X\ge 0. \end{aligned}$$

其對偶問題為：

$$\begin{aligned} \min\quad & b^TY\\ \text{s.t.}\quad & A^TY\ge C^T,\\ &Y\ge 0. \end{aligned}$$

令 $Y=(y_1,\ldots,y_m)^T$。原問題第 $i$ 個限制式的剩餘量為 $b_i-(AX)_i$；對偶問題第 $j$ 個限制式的剩餘量為 $(A^TY)_j-c_j$。

解題方法：列出互補鬆弛條件

對原問題的每一項限制式及每一個變數，互補鬆弛條件分別是：

$$y_i\bigl[b_i-(AX)_i\bigr]=0,\qquad i=1,\ldots,m,$$ $$x_j\bigl[(A^TY)_j-c_j\bigr]=0,\qquad j=1,\ldots,n.$$

第一組表示：對偶變數 $y_i$ 與原問題第 $i$ 項限制式的剩餘量，至少有一者為零。因為兩者皆非負，所以：

• 若原問題第 $i$ 項限制式有剩餘量，即 $(AX)_i<b_i$，則 $y_i=0$。
• 若 $y_i>0$，則原問題第 $i$ 項限制式必為緊束，即 $(AX)_i=b_i$。

第二組表示：原問題變數 $x_j$ 與其對偶限制式的剩餘量，至少有一者為零。因此：

• 若 $x_j>0$，則 $(A^TY)_j=c_j$，對應的對偶限制式緊束。
• 若對偶限制式有剩餘量，即 $(A^TY)_j>c_j$，則 $x_j=0$。

核心觀念

本題考查以梯度搜尋法求解無限制非線性規劃的最大化問題。每次迭代先計算目前點的梯度，沿梯度方向搜尋使目標函數最大的步長，再依停止條件判斷是否繼續。

目標函數為

$$f(x_1,x_2)=-2x_1^2-x_2^2+4x_1+2x_1x_2$$

其梯度為

$$\nabla f(x_1,x_2)= \begin{bmatrix} \dfrac{\partial f}{\partial x_1}\\[2pt] \dfrac{\partial f}{\partial x_2} \end{bmatrix} = \begin{bmatrix} -4x_1+4+2x_2\\ -2x_2+2x_1 \end{bmatrix}$$

梯度指出函數值增加最快的方向。對最大化問題，在目前點 $X^{(k)}$ 沿 $\nabla f(X^{(k)})$ 前進，並以一維搜尋決定步長 $\lambda_k$：

$$X^{(k+1)}=X^{(k)}+\lambda_k\nabla f(X^{(k)})$$

本題依停止條件 $\varepsilon=1$，以梯度長度 $\|\nabla f(X^{(k)})\|\leq 1$ 作為停止判準。

解題方法

起始點為

$$X^{(0)}=(0,0)$$

第 1 次迭代

在 $X^{(0)}=(0,0)$ 計算梯度：

$$\nabla f(0,0)= \begin{bmatrix} 4\\ 0 \end{bmatrix}$$

沿此方向搜尋，令

$$X(\lambda)=(0,0)+\lambda(4,0)=(4\lambda,0)$$

代入目標函數：

$$f(4\lambda,0)=-2(4\lambda)^2+4(4\lambda) =-32\lambda^2+16\lambda$$

對 $\lambda$ 微分並令其為零：

$$\frac{d}{d\lambda}f(4\lambda,0)=-64\lambda+16=0$$

因此 $\lambda_0=\dfrac14$，更新點為

$$X^{(1)}=(0,0)+\frac14(4,0)=(1,0)$$

函數值為

$$f(1,0)=-2+4=2$$

此點的梯度為

$$\nabla f(1,0)= \begin{bmatrix} 0\\ 2 \end{bmatrix}, \qquad \|\nabla f(1,0)\|=2>1$$

尚未符合停止條件，繼續迭代。

第 2 次迭代

沿 $X^{(1)}=(1,0)$ 的梯度方向搜尋：

$$X(\lambda)=(1,0)+\lambda(0,2)=(1,2\lambda)$$

代入目標函數：

$$f(1,2\lambda) =-2-(2\lambda)^2+4+2(1)(2\lambda) =2-4\lambda^2+4\lambda$$

對 $\lambda$ 微分並令其為零：

$$\frac{d}{d\lambda}f(1,2\lambda)=-8\lambda+4=0$$

因此 $\lambda_1=\dfrac12$，更新點為

$$X^{(2)}=(1,0)+\frac12(0,2)=(1,1)$$

函數值為

$$f(1,1)=-2-1+4+2=3$$

在此點計算梯度：

核心觀念

本題考普瓦松過程的稀疏化：若事件在一年內的發生次數服從普瓦松分配，而每次事件獨立地以固定機率 $p$ 成為某一類事件，則該類事件的次數仍服從普瓦松分配，其平均率為原平均率乘上 $p$。

設 $N$ 為一年內侵襲該島國的颱風總數，題目給定

$$N\sim\operatorname{Poisson}(30).$$

每次颱風不登陸的機率為 $2/3$，所以登陸機率為

$$p=1-\frac{2}{3}=\frac{1}{3}.$$

解題方法與推導

令 $X$ 為一年內登陸該國的颱風次數。給定總颱風數 $N=n$ 時，每次颱風以機率 $1/3$ 登陸，因此

$$X\mid N=n\sim\operatorname{Binomial}\left(n,\frac{1}{3}\right).$$

對任意 $k=0,1,2,\ldots$，利用條件機率與全機率公式：

$$\begin{aligned} P(X=k) &=\sum_{n=k}^{\infty}P(X=k\mid N=n)P(N=n)\\ &=\sum_{n=k}^{\infty} \binom{n}{k}\left(\frac13\right)^k \left(\frac23\right)^{n-k} \frac{e^{-30}30^n}{n!}. \end{aligned}$$

令 $m=n-k$，整理後得