115 年高普考高考三級工業工程考古題與詳解

Question 1

以大 M 法（Big M Method）求解以下線性規劃問題。 $$ \begin{aligned} 	ext{Maximize}\quad & Z=2x1+2x2+3x3\ 	ext{Subject to}\quad &x1+3x2+3x3\le 15,\ &3x1+x2+4x3\ge 10,\ &2x1+x2+2x3=12,\ &x1,x2,x3\ge 0. \end{aligned} $$

Accepted Answer

核心觀念

本題考大 M 法的標準形轉換與單形法運算。使用大 M 法時，先將限制式改寫為等式： $\le$ 限制式加入鬆弛變數， $\ge$ 限制式減去剩餘變數並加入人工變數，等式限制式則加入人工變數。人工變數在最大化問題的目標式中給予 $-M$ 罰值，其中 $M$ 為足夠大的正數；若最適解仍有人工變數為正，表示原問題不可行。

解題方法

將三條限制式分別標準化：

\begin{aligned} x_1+3x_2+3x_3+s_1&=15,\\ 3x_1+x_2+4x_3-s_2+a_2&=10,\\ 2x_1+x_2+2x_3+a_3&=12, \end{aligned}

其中 $s_1$ 為鬆弛變數， $s_2$ 為剩餘變數， $a_2,a_3$ 為人工變數；所有變數皆非負。目標式改為

\max Z=2x_1+2x_2+3x_3-Ma_2-Ma_3.

為了得到最適解，先利用等式限制式消去 $x_1$ ：

x_1=6-\frac12x_2-x_3.

代入其餘兩條限制式及目標式：

\begin{aligned} \frac52x_2+2x_3+s_1&=9,\\ -\frac12x_2+x_3-s_2+a_2&=-8,\\ a_3&=0,\\ Z&=12+x_2+x_3-Ma_2-Ma_3. \end{aligned}

第二式右側為負，將該式乘以 $-1$ ，並以 $s_2$ 作為基底變數，得

\frac12x_2-x_3+s_2-a_2=8,

亦即

s_2=8-\frac12x_2+x_3+a_2.

由第一式與非負條件可知

Question 2

某太空中心計畫將一顆探測器送入預定軌道，只有 3 個火箭發射窗口可供使用，而每個發射窗口至多可以發射 5 枚火箭。每枚火箭成功將探測器送入預定軌道的機率為 $\frac{3}{4}$ ，失敗機率為 $\frac{1}{4}$ 。

若某一發射窗口被啟用，則需支付固定的發射準備費用 200 萬元。此外，每發射一枚火箭需額外支付 100 萬元的發射成本。只要有任意一枚火箭成功將探測器送入預定軌道，任務即宣告成功，後續發射窗口將不再使用。

若三個發射窗口全部結束後，仍未能成功將探測器送入預定軌道，則此次太空任務失敗，並造成 800 萬元的任務損失。

請利用動態規劃決定在各發射窗口中應發射多少枚火箭，使太空中心的總期望成本最小。

Accepted Answer

核心觀念 本題考驗有限期數、有限資源的隨機動態規劃。每個發射窗口都是一個階段；每階段可決定發射 $0$ 至 $5$ 枚火箭。若全部失敗，就進入下一窗口；只要有一枚成功，任務立即結束。 每枚火箭失敗率為 $1/4$，因此在同一窗口發射 $n$ 枚時，全部失敗的機率為 $$ qn=\left(\frac14\right)^n, $$ 至少一枚成功的機率則為 $1-qn$。發射 $n$ 枚火箭的當期成本為啟用窗口的準備費 $2$ 百萬元，加上每枚火箭 $1$ 百萬元，即 $2+n$ 百萬元。 解題方法 以百萬元為成本單位。令 $Vk$ 表示進入第 $k$ 個窗口、任務仍未成功時，從該時點起的最小期望總成本。三個窗口都用完仍失敗，還要承擔 $8$ 百萬元任務損失，因此 $$ V4=8. $$ 在第 $k$ 個窗口選擇發射 $n$ 枚（$n=0,1,\ldots,5$），當期支付 $2+n$；若全數失敗，機率為 $qn$，再承擔下一階段的成本 $V{k+1}$。所以遞迴式為 $$ Vk=\min{n\in\{0,1,\ldots,5\}} \left\{2+n+\left(\frac14\right)^n V{k+1}\right\}. $$ 其中 $n=0$ 表示不啟用該窗口，不支付準備費，也不發射火箭；此時任務必然未成功並進入下一窗口，故其成本為 $V{k+1}$。這也可視為把不啟用窗口的選擇納入決策。 由最後一個窗口往前計算： | 階段 | 各發射數的期望成本比較（百萬元） | 最佳決策 | |---|---|---| | 第 3 窗口，$V4=8$ | $n=0: 8$；$n=1: 3+\frac14(8)=5$；$n=2: 4+\frac1{16}(8)=4.5$；$n=3: 5+\frac1{64}(8)=5.125$；$n=4: 6+\frac1{256}(8)=6.03125$；$n=5: 7+\frac1{1024}(8)=7.0078125$ | $n3^=2$，$V3=4.5$ | | 第 2 窗口，$V3=4.5$ | $n=0: 4.5$；$n=1: 3+\frac14(4.5)=4.125$；$n=2: 4+\frac1{16}(4.5)=4.28125$；

Question 3

某校園有兩個共享單車停放點：東門與西門。一位學生每天早上從校園離開。他從東門出發的機率為 $\frac{2}{3}$ ，從西門出發的機率為 $\frac{1}{3}$ 。

若出發的停放點有共享單車，他就騎一輛單車；若該停放點沒有共享單車，他只能步行。

當他返回校園時，他從東門進入的機率為 $\frac{1}{3}$ ，從西門進入的機率為 $\frac{2}{3}$ ，並將共享單車停放在進入的停放點。

假設校園共有兩輛共享單車，長期而言，該學生必須步行的比例是多少？

Accepted Answer

核心觀念

本題是有限狀態的馬可夫鏈長期比例問題。每一天的狀態可用「東門停放點的單車數」表示；校園共有兩輛車，因此東門車數可能為 $0、1、2$ ，西門車數則由 $2$ 減去東門車數決定。

需先依出發與返回的機率建立狀態轉移，再求穩態機率。學生必須步行的情況是：他選擇出發的停放點沒有車。

解題方法

令 $X_n$ 為第 $n$ 天早上出發前，東門停放的單車數，狀態空間為 $\{0,1,2\}$ 。

學生出發時，東門機率為 $\frac23$ ，西門機率為 $\frac13$ ；返回時，東門機率為 $\frac13$ ，西門機率為 $\frac23$ 。每天結束後，車輛所在位置由「出發點」移至「返回點」；若出發點無車，學生步行，但停車點仍按題目給定的返回機率決定。

由各狀態逐一列出轉移：

狀態 $0$ ：東門無車、西門有兩輛。若從東門出發（機率 $\frac23$ ），步行後依返回機率停車；若從西門出發（機率 $\frac13$ ），騎車後同樣依返回機率停車。兩種情況下，東門車數增加一輛的機率都是 $\frac13$ ，故

P_{00}=\frac23,\qquad P_{01}=\frac13,\qquad P_{02}=0.

狀態 $1$ ：兩個停放點各有一輛。從東門出發，東門有車；返回東門的機率為 $\frac13$ ，使東門車數回到 $1$ ，返回西門的機率為 $\frac23$ ，使東門車數變為 $0$ 。從西門出發則反之。因此

P_{10}=\frac23\cdot\frac23=\frac49,\qquad P_{11}=\frac23\cdot\frac13+\frac13\cdot\frac23=\frac49,\qquad P_{12}=\frac13\cdot\frac13=\frac19.

狀態 $2$ ：東門有兩輛、西門無車。若從東門出發，東門車數在返回東門時維持 $2$ ，在返回西門時降為 $1$ ；若從西門出發，學生步行，返回東門後東門車數為 $2$ ，返回西門後為 $1$ 。故

P_{20} = 0,\qquad P_{21}=\frac23,\qquad P_{22}=\frac13.

Question 4

某消防局將配置 8 輛消防車到 4 個地區，每個地區必須配置 1 至 4 輛消防車，且每輛消防車只能配置到一個地區。配置不同數量的消防車到各地區時，預估可增加的成功救災件數如下表：

消防車數量	地區 1	地區 2	地區 3	地區 4
0	0	0	0	0
1	0	0	0	0
2	16	14	18	12
3	30	27	32	24
4	41	37	43	33
5	49	46	51	40

建構一個整數規劃模型，以決定 8 輛消防車於 4 個地區之配置方式，使成功救災總件數的增加量最大。

Accepted Answer

核心觀念

本題考「資源配置」的整數規劃建模。決策變數表示各地區配置的消防車數量；目標是最大化四區預估成功救災件數增加量的總和，並滿足消防車總數及各區配置數量限制。

解題方法

令 $x_i$ 為配置至地區 $i$ 的消防車數量， $i=1,2,3,4$ 。令 $y_{ik}$ 為二元變數：若地區 $i$ 配置 $k$ 輛消防車，則 $y_{ik}=1$ ；否則為 $0$ 。其中 $k=1,2,3,4$ 。

表中各地區配置 $0$ 輛或 $1$ 輛時，增加件數皆為 $0$ ；題目又要求每區配置 $1$ 至 $4$ 輛，因此每區可選的配置數量為 $1,2,3,4$ 。雖然表格另列 $5$ 輛的效益，但本題每區上限為 $4$ 輛，故不納入模型。

依各地區的效益，目標式為：

\max Z = 16y_{12}+30y_{13}+41y_{14} +14y_{22}+27y_{23}+37y_{24} +18y_{32}+32y_{33}+43y_{34} +12y_{42}+24y_{43}+33y_{44}

每個地區必須選擇一種配置數量：

階段	各發射數的期望成本比較（百萬元）	最佳決策
第 3 窗口， $V_4=8$	$n=0: 8$ ； $n=1: 3+\frac14(8)=5$ ； $n=2: 4+\frac1{16}(8)=4.5$ ； $n=3: 5+\frac1{64}(8)=5.125$ ； $n=4: 6+\frac1{256}(8)=6.03125$ ； $n=5: 7+\frac1{1024}(8)=7.0078125$	$n_3^*=2$ ， $V_3=4.5$
第 2 窗口， $V_3=4.5$	$n=0: 4.5$ ； $n=1: 3+\frac14(4.5)=4.125$ ； $n=2: 4+\frac1{16}(4.5)=4.28125$ ；

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

第一題30 分

核心觀念

解題方法

第二題25 分

核心觀念

解題方法

第三題25 分

核心觀念

解題方法

第四題20 分

核心觀念

解題方法

其他考古題

115 年工業工程的其他科目

工業工程《作業研究》其他年度

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

第 一 題30 分

核心觀念

解題方法

第 二 題25 分

核心觀念

解題方法

第 三 題25 分

核心觀念

解題方法

第 四 題20 分

核心觀念

解題方法

其他考古題

115 年工業工程的其他科目

工業工程《作業研究》其他年度

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

第一題30 分

第二題25 分

第三題25 分

第四題20 分