112 年公務人員升官等薦任工業工程考古題與詳解

Question 1

考慮下列線性規劃問題： $$ \begin{aligned} \max\quad & z=50x1+60x2\ 	ext{subject to}\quad & 2x1+3x2\leq 180\ & 3x1+2x2\leq 150\ & x1,x2\geq 0 \end{aligned} $$ （一）請將此問題轉成以標準型式來表示，也就是所有不等式轉成為等式的型式。（5 分） （二）請以一般單形法（Simplex method）的表格式（tableau form）來求解最佳解並在每回合表中列出完整之列表。（20 分）

Accepted Answer

核心觀念 本題考查線性規劃的標準型式，以及以單形法表格式求解最大化問題。將「$\leq$」限制式加入非負鬆弛變數，使限制式改寫為等式；單形法每回合依目標列選入基變數，再以最小比值檢定選出基變數，透過樞紐運算更新表格。 採用目標列 $Cj-Zj$ 的記號：最大化問題中，若所有 $Cj-Zj\leq 0$，目前基可行解即為最佳解；若有正值，選取其中最大者作為入基變數。 （一）化為標準型式 分別在兩個限制式加入鬆弛變數 $s1,s2\geq 0$： $$ \begin{aligned} \max\quad & z=50x1+60x2\ 	ext{subject to}\quad &2x1+3x2+s1=180\ &3x1+2x2+s2=150\ &x1,x2,s1,s2\geq 0 \end{aligned} $$ 其中 $s1,s2$ 分別表示兩項資源限制中尚未使用的額度。 （二）單形法表格式求解 初始表 令 $s1,s2$ 為初始基變數，其目標係數 $CB$ 均為 $0$。初始基本可行解為 $x1=x2=0,\ s1=180,\ s2=150$。 | $CB$ | 基變數 | $x1$ | $x2$ | $s1$ | $s2$ | RHS | 比值檢定（$x2$ 欄） | |---:|:---:|---:|---:|---:|---:|---:|---:| | 0 | $s1$ | 2 | 3 | 1 | 0 | 180 | $180/3=60$ | | 0 | $s2$ | 3 | 2 | 0 | 1 | 150 | $150/2=75$ | | | $Zj$ | 0 | 0 | 0 | 0 | 0 | | | | $Cj-Zj$ | 50 | 60 | 0 | 0 | | | 因 $Cj-Zj$ 最大正值在 $x2$ 欄，故 $x2$ 入基。比值檢定取正樞紐欄係數所算比值的最小值：$\min\{60,75\}=60$，故 $s1$ 出基，樞紐元素為 $3$。 第一次樞紐運算 將第 1 列除以 $3$，得到新樞紐列；再用第 1 列消去第 2 列中的 $x2$ 係數： $$ R1\leftarrow \frac{R1}{3},\qquad R2\leftarrow R2-2R1 $$ | $CB$ | 基變數 | $x1$ | $x2$ | $s1$ | $s2$ | RHS | 比值檢定（$x1$ 欄） | |---:|:---:|---:|---:|---:|---:|---:|---:| | 60 | $x2$ | $2/3$ | 1 | $1/3$ | 0 | 60 | $60/(2/3)=90$ |

Question 2

鋼鐵廠主要產品為三米、五米以及九米長之鋼條。這些長度的鋼條是由原料十七米長的鋼條所裁切完成。目前已知需求為 25 支三米鋼條、20 支五米鋼條以及 15 支九米鋼條。鋼鐵廠希望原料十七米長的鋼條使用的數目越少越好。

請建構出整數規劃模型並定義所需之決策變數來達成此目的（無須求解）。（25 分）

Accepted Answer

核心觀念 本題考查一維切割問題（cutting stock problem）的整數規劃建模。每支 17 米原料鋼條可依不同切割方式，製成若干支 3 米、5 米及 9 米鋼條；決策重點是各切割方式使用幾次，並使原料鋼條總數最少。 切割時不得超過原料長度，因此每種切割方式都須符合長度限制；各成品數量則須滿足需求。 解題方法 令 $x{ijk}$ 表示使用 $i$ 支 3 米鋼條、$j$ 支 5 米鋼條及 $k$ 支 9 米鋼條的切割方式，裁切 17 米原料鋼條的次數。其索引集合為： $$ \mathcal{P}=\{(i,j,k)\in\mathbb{Z}{\ge 0}^3:3i+5j+9k\le 17\}. $$ 因此，$x{ijk}$ 是非負整數變數。每一種列入 $\mathcal{P}$ 的切割方式都不會超過 17 米；未用完的長度視為裁切餘料。 目標為使使用的原料鋼條總數最少： $$ \min \sum{(i,j,k)\in\mathcal{P}}x{ijk}. $$ 三種成品的總產量須分別滿足需求： $$ \sum{(i,j,k)\in\mathcal{P}} i\,x{ijk}\ge 25, $$ $$ \sum{(i,j,k)\in\mathcal{P}} j\,x{ijk}\ge 20, $$ $$ \sum{(i,j,k)\in\mathcal{P}} k\,x{ijk}\ge 15. $$ 整數與非負限制為：

Question 3

考慮下列最佳化問題以動態規劃的方式求解： $$ \begin{aligned} \max\quad & z=2x1+x2^2\ 	ext{subject to}\quad & x1^2+x2^2\leq 4\ & x1,x2\geq 0 \end{aligned} $$ （一）請定義動態規劃所需之階段（stage）以及狀態（state）。（5 分） （二）請以動態規劃的方式分階段求出最佳解。（10 分）

Accepted Answer

核心觀念 本題考查資源配置型動態規劃。將限制式中的總資源 $4$ 視為可分配資源；選擇 $x1$、$x2$ 時，分別耗用 $x1^2$、$x2^2$ 單位資源，而目標函數的兩項收益分別為 $2x1$、$x2^2$。 動態規劃的核心是定義階段與狀態，並以遞迴關係逐步求得最佳值。狀態需記錄足以描述後續決策條件的資訊；本題以「剩餘可用資源」作為狀態。 （一）階段與狀態 - 階段（stage）：共兩個階段。第 $1$ 階段決定 $x1$，第 $2$ 階段決定 $x2$。 - 狀態（state）：令 $s$ 表示進入某階段時剩餘的可用資源，初始狀態為 $s=4$。決定 $xi$ 後，剩餘資源減少 $xi^2$，因此必須滿足 $0\leq xi^2\leq s$。 （二）分階段求最佳解 令 $Fi(s)$ 表示從第 $i$ 階段起，在剩餘資源為 $s$ 時可取得的最大收益。 第 1 階段 只需決定 $x1$，且 $x1^2\leq s$、$x1\geq 0$，因此： $$ F1(s)=\max{0\leq x1\leq\sqrt{s}}2x1=2\sqrt{s}. $$ 第 2 階段 決定 $x2$ 後，耗用資源 $x2^2$，將剩餘資源 $s-x2^2$ 留給第 1 階段。依遞迴關係： $$ F2(s)=\max{0\leq x2\leq\sqrt{s}} \left\{x2^2+F1(s-x2^2)\right\}. $$ 代入 $F1(s)=2\sqrt{s}$，並令 $t=x2^2$，可得：

Question 4

請以逆變換法（inverse transform method）來產生機率密度函數為 $$ f(x)=\frac{e^x}{e-1},\quad 0\leq x\leq 1 $$ 的隨機樣本。（15 分）

Accepted Answer

核心觀念 逆變換法（inverse transform method）利用均勻分配隨機變數來產生目標分配的樣本。若目標隨機變數 $X$ 的累積分配函數為 $FX(x)$，取 $U\sim \mathrm{Uniform}(0,1)$，則 $$ X=FX^{-1}(U) $$ 具有累積分配函數 $FX$。因此，本題先由機率密度函數積分求出累積分配函數，再解出反函數。 解題方法 題目給定 $$ f(x)=\frac{e^x}{e-1},\qquad 0\le x\le 1. $$ 先確認其為合法的機率密度函數： $$ \int0^1 \frac{e^x}{e-1}\,dx =\frac{e-1}{e-1}=1. $$ 累積分配函數分段為 $$ FX(x)= \begin{cases} 0, & x<0,\[4pt] \displaystyle \int0^x \frac{e^t}{e-1}\,dt =\frac{e^x-1}{e-1}, & 0\le x\le 1,\[8pt] 1, & x1. \end{cases} $$ 令 $U\sim \mathrm{Uniform}(0,1)$，並令 $U=FX(x)$。在 $0\le x\le 1$ 上， $$ U=\frac{e^x-1}{e-1}. $$ 解出 $x$：

Question 5

考慮下圖最短路徑問題：（每小題 10 分，共 20 分）

🖼️【此處有附圖，請對照原卷】

（一）以 Dijkstra 法求解由節點 1 出發至各節點最短路徑問題之最佳解。

（二）請建構以目標式為最小化由節點 1 出發至節點 6 所需距離之最佳化模型並定義所需之決策變數。

Accepted Answer

核心觀念 本題考查有向網路的最短路徑問題。Dijkstra 法適用於弧長非負的網路：每一步從尚未確定的節點中，選出目前暫定距離最小者，確定其最短距離，再更新其相鄰節點的暫定距離。 圖中的弧長為 $$ (1,2):4,\quad (1,3):3,\quad (2,4):3,\quad (2,5):2,\quad (3,5):3,\quad (4,6):2,\quad (5,6):2. $$ （一）以 Dijkstra 法求由節點 1 至各節點的最短距離 令 $dj$ 表示由節點 1 至節點 $j$ 的目前最短距離。初始化 $d1=0$，其餘距離設為無限大，再依序確定暫定距離最小的節點： | 步驟 | 確定節點 | 更新結果 | |---|---:|---| | 初始化 | 1 | $d2=4,\ d3=3$ | | 1 | 3（距離 3） | 經 $3	o5$ 得 $d5=3+3=6$ | | 2 | 2（距離 4） | 經 $2	o4$ 得 $d4=4+3=7$；經 $2	o5$ 得 $d5=4+2=6$，與原值相同 | | 3 | 5（距離 6） | 經 $5	o6$ 得 $d6=6+2=8$ | | 4 | 4（距離 7） | 經 $4	o6$ 得距離 $7+2=9$，不優於 $d6=8$ | | 5 | 6（距離 8） | 完成 | 節點 5 有兩條同長最短路徑：$1	o2	o5$ 與 $1	o3	o5$，距離均為 $6$。因此節點 6 也有兩條同長最短路徑： $$ 1	o2	o5	o6,\qquad 1	o3	o5	o6, $$ 總距離均為 $8$。各節點由節點 1 出發的最短距離為

$C_B$	基變數	$x_1$	$x_2$	$s_1$	$s_2$	RHS	比值檢定（ $x_2$ 欄）
0	$s_1$	2	3	1	0	180	$180/3=60$
0	$s_2$	3	2	0	1	150	$150/2=75$
	$Z_j$	0	0	0	0	0
	$C_j-Z_j$	50	60	0	0

112 公務人員升官等薦任工業工程作業研究考古題詳解

第一題25 分

核心觀念

（一）化為標準型式

（二）單形法表格式求解

初始表

第一次樞紐運算

第二題25 分

核心觀念

解題方法

第三題15 分

核心觀念

（一）階段與狀態

（二）分階段求最佳解

第四題15 分

第五題20 分

其他考古題

112 年工業工程的其他科目

112 公務人員升官等薦任 工業工程 作業研究 考古題詳解

第 一 題25 分

核心觀念

（一）化為標準型式

（二）單形法表格式求解

初始表

第一次樞紐運算

第 二 題25 分

核心觀念

解題方法

第 三 題15 分

核心觀念

（一）階段與狀態

（二）分階段求最佳解

第 四 題15 分

第 五 題20 分

其他考古題

112 年工業工程的其他科目

112 公務人員升官等薦任工業工程作業研究考古題詳解

第一題25 分

第二題25 分

第三題15 分

第四題15 分

第五題20 分