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

114 年・高普考・高考三級・工業工程
試題代碼 作業研究

第 一 題25 分

考慮一個雙人零和賽局（Two-person Zero-sum Game），其收益表（Payoff Table）如下。表中數值為參賽者 A 的收益；若參賽者 A 採取策略 a1a_1，而參賽者 B 採取策略 b1b_1，參賽者 A 之收益為 88，相對地，參賽者 B 之收益為 −8-8，餘此類推。

策略\multicolumn3c參賽者 B\cline3−5\multicolumn2c∣b1b2b3\multirow3∗參賽者 Aa1805a2951a33107\begin{array}{c|c|ccc} & \text{策略} & \multicolumn{3}{c}{\text{參賽者 B}} \\ \cline{3-5} \multicolumn{2}{c|}{} & b_1 & b_2 & b_3 \\ \hline \multirow{3}{*}{\text{參賽者 A}} & a_1 & 8 & 0 & 5 \\ & a_2 & 9 & 5 & 1 \\ & a_3 & 3 & 10 & 7 \\ \end{array}

（一）若雙方均採取最大損失最小化原則來選取單一策略，雙方所選取之策略為何？（10 分）

（二）此問題是否有鞍點（Saddle Point）？原因為何？（5 分）

（三）若參賽者 A 考慮採取混合策略，請寫出一個線性規劃（Linear Programming）以幫助參賽者 A 決定最佳的混合策略（無需求解）。（10 分）

🖼️ 本題原卷含圖表。基於試題來源之版權考量，本站不轉載原卷影像； 題目文字已完整轉錄，圖表請自行參閱考選部公告之試題原檔。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查雙人零和賽局中的：

  1. 最大損失最小化原則（Minimax）。
  2. 鞍點（Saddle Point）的判斷。
  3. 以線性規劃求參賽者 A 的最佳混合策略。

表中數值均為參賽者 A 的收益，因此：

  • 參賽者 A 希望使收益最大。
  • 參賽者 B 希望使參賽者 A 的收益最小。

（一）雙方採取單一策略

1. 參賽者 A：最大損失最小化

對參賽者 A 而言，每一列代表一種策略。A 應先找出各列中的最小收益，再選擇其中最大的值。

b1b2b3列最小值a18050a29511a331073\begin{array}{c|ccc|c} & b_1 & b_2 & b_3 & \text{列最小值}\\ \hline a_1 & 8 & 0 & 5 & 0\\ a_2 & 9 & 5 & 1 & 1\\ a_3 & 3 & 10 & 7 & 3 \end{array}

因此：

max⁡{0,1,3}=3\max\{0,1,3\}=3

參賽者 A 應選擇：

a3\boxed{a_3}

其保證收益為 33。

2. 參賽者 B：最大損失最小化

對參賽者 B 而言，B 希望降低 A 的收益，因此先找出每一欄中的最大收益，再選擇其中最小的值。

B 的策略欄最大值b1max⁡{8,9,3}=9b2max⁡{0,5,10}=10b3max⁡{5,1,7}=7\begin{array}{c|c} \text{B 的策略} & \text{欄最大值}\\ \hline b_1 & \max\{8,9,3\}=9\\ b_2 & \max\{0,5,10\}=10\\ b_3 & \max\{5,1,7\}=7 \end{array}

因此：

min⁡{9,10,7}=7\min\{9,10,7\}=7

參賽者 B 應選擇：

b3\boxed{b_3}

此時 B 將 A 的最大可能收益壓低至 77。

（二）鞍點判斷

鞍點存在的條件為：

最大列最小值=最小欄最大值\text{最大列最小值}=\text{最小欄最大值}

本題中：

Maximin=3\text{Maximin}=3 Minimax=7\text{Minimax}=7

由於：

3≠73\neq 7

因此本題沒有鞍點。

也可直接觀察：A 的單一策略選擇為 a3a_3，B 的單一策略選擇為 b3b_3，交會收益為：

a3∩b3=7a_3\cap b_3=7

但 a3a_3 列的最小值為 33，故該位置不是列最小值；同時 b3b_3 欄的最大值為 77，雖為欄最大值，但不符合列最小值與欄最大值相等的鞍點條件。

（三）參賽者 A 的混合策略線性規劃

1. 設定變數

令：

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 二 題25 分

請使用分枝界限法（Branch-and-Bound）求解下列背包問題（Knapsack Problem），以將所有整數變數放鬆為實數變數的方式，求取搜尋樹（Search Tree）中各節點所需之上限值（Upper Bound）。請畫出搜尋樹，並標示各節點所對應的完整實數解及上限值。（25 分）

Max⁡z=10x1+3x2+x3+8x4+5x5+3x6s.t.8x1+x2+3x3+5x4+2x5+2x6≤15xi=0 or 1,i=1,2,…,6\begin{aligned} \operatorname{Max}\quad z &= 10x_1+3x_2+x_3+8x_4+5x_5+3x_6 \\ \text{s.t.}\quad &8x_1+x_2+3x_3+5x_4+2x_5+2x_6\leq 15 \\ &x_i=0\text{ or }1,\quad i=1,2,\ldots,6 \end{aligned}

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

分枝界限法（Branch-and-Bound）將原問題分成若干子問題：

  • 分枝：選一個尚未固定的 00–11 變數，分成 xj=0x_j=0 與 xj=1x_j=1 兩個子問題。
  • 上限值（Upper Bound, UB）：把尚未固定的整數變數放鬆為 0≤xi≤10\leq x_i\leq1，求解線性鬆弛問題。最大化問題的鬆弛解值是該節點的上限值。
  • 剪枝：若節點的上限值不大於目前最佳整數可行解值，該節點不可能改善目前解，可停止搜尋。

背包線性鬆弛可依「單位重量價值」由高至低裝入物品，最後一件物品可取分數。

解題方法

各物品的單位重量價值如下：

物品x1x_1x2x_2x3x_3x4x_4x5x_5x6x_6
價值／重量10/8=1.2510/8=1.253/1=33/1=31/31/38/5=1.68/5=1.65/2=2.55/2=2.53/2=1.53/2=1.5

依比值由高至低的裝入順序為

x2, x5, x4, x6, x1, x3.x_2,\ x_5,\ x_4,\ x_6,\ x_1,\ x_3.

根節點的鬆弛解先取 x2=x5=x4=x6=1x_2=x_5=x_4=x_6=1，使用重量 1+2+5+2=101+2+5+2=10，剩餘重量 55，再取 x1=5/8x_1=5/8。因此根節點的完整實數解（依原變數順序）為

(x1,x2,x3,x4,x5,x6)=(58,1,0,1,1,1),(x_1,x_2,x_3,x_4,x_5,x_6) =\left(\frac58,1,0,1,1,1\right), UB=10(58)+3+0+8+5+3=1014=25.25.UB=10\left(\frac58\right)+3+0+8+5+3 =\frac{101}{4}=25.25.

根節點唯一的分數變數是 x1x_1，以 x1x_1 分枝。

節點 x1=0x_1=0

固定 x1=0x_1=0 後，其餘物品全部取 11 的重量為 1+3+5+2+2=13≤151+3+5+2+2=13\leq15。完整實數解為

(x1,x2,x3,x4,x5,x6)=(0,1,1,1,1,1),(x_1,x_2,x_3,x_4,x_5,x_6)=(0,1,1,1,1,1), UB=z=3+1+8+5+3=20.UB=z=3+1+8+5+3=20.

此解已是整數可行解，可作為目前最佳解。

節點 x1=1x_1=1

固定 x1=1x_1=1 後，剩餘容量為 15−8=715-8=7。依比值順序取 x2=x5=x4=1x_2=x_5=x_4=1，使用重量 1+2+5=81+2+5=8，超過剩餘容量；

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 三 題25 分

考慮下列線性規劃問題：

Max⁡z=x1−x2+2x3s.t.x1+x2+3x3≤15（限制式 1）2x1−x2+x3≤3（限制式 2）−x1+x2+x3≤4（限制式 3）x1≥0,x2≥0,x3≥0\begin{aligned} \operatorname{Max}\quad z&=x_1-x_2+2x_3 \\ \text{s.t.}\quad &x_1+x_2+3x_3\leq 15 \qquad \text{（限制式 1）}\\ &2x_1-x_2+x_3\leq 3 \qquad \text{（限制式 2）}\\ &-x_1+x_2+x_3\leq 4 \qquad \text{（限制式 3）}\\ &x_1\geq 0,\quad x_2\geq 0,\quad x_3\geq 0 \end{aligned}

令 x4,x5,x6x_4,x_5,x_6 分別代表限制式 1、2、3 的寬裕變數（Slack Variable）。考慮一個基本解（Basic Solution）XB=(x1,x3,x2)X_B=(x_1,x_3,x_2)，此基本解所對應的反矩陣（Inverse）為：

B−1=[1−1−2−1213232−2−52]B^{-1}= \begin{bmatrix} 1 & -1 & -2 \\ -\frac{1}{2} & 1 & \frac{3}{2} \\ \frac{3}{2} & -2 & -\frac{5}{2} \end{bmatrix}

（一）請計算此基本解所對應的目標函數值。（5 分）

（二）請建構此基本解所對應的完整單形表（Simplex Tableau）。（10 分）

（三）請判斷此基本解是否為最佳解？若否，由此基本解開始，利用單形法（Simplex Method）求取最佳解。（10 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

單形表以目前的基底變數表示各限制式。若基底矩陣為 BB，則

xB=B−1b−B−1NxNx_B=B^{-1}b-B^{-1}N x_N

其中 xBx_B 是基底變數，xNx_N 是非基底變數。最大化問題的檢定數採用 Cj−ZjC_j-Z_j；若所有非基底變數的檢定數皆不大於 00，目前解即為最佳解。若有正檢定數，可選其對應變數進入基底，再以最小比值檢定決定離基變數。

（一）計算基本解與目標函數值

基底變數順序為 XB=(x1,x3,x2)X_B=(x_1,x_3,x_2)，因此

XB=B−1b=[1−1−2−1213232−2−52][1534]=[432132].X_B=B^{-1}b = \begin{bmatrix} 1 & -1 & -2\\ -\frac12 & 1 & \frac32\\ \frac32 & -2 & -\frac52 \end{bmatrix} \begin{bmatrix} 15\\3\\4 \end{bmatrix} = \begin{bmatrix} 4\\[2pt] \frac32\\[2pt] \frac{13}{2} \end{bmatrix}.

所以 x1=4, x3=32, x2=132x_1=4,\ x_3=\frac32,\ x_2=\frac{13}{2}，且非基底變數 x4=x5=x6=0x_4=x_5=x_6=0。目標函數值為

z=x1−x2+2x3=4−132+2(32)=12.z=x_1-x_2+2x_3 =4-\frac{13}{2}+2\left(\frac32\right) =\frac12.

（二）建構完整單形表

目標函數係數為 (1,−1,2,0,0,0)(1,-1,2,0,0,0)，基底變數順序 (x1,x3,x2)(x_1,x_3,x_2) 的係數為 (1,2,−1)(1,2,-1)。非基底欄的轉換係數為

B−1A4=[1−1232],B−1A5=[−11−2],B−1A6=[−232−52].B^{-1}A_4= \begin{bmatrix}1\\-\frac12\\\frac32\end{bmatrix},\qquad B^{-1}A_5= \begin{bmatrix}-1\\1\\-2\end{bmatrix},\qquad B^{-1}A_6= \begin{bmatrix}-2\\\frac32\\-\frac52\end{bmatrix}.

目標列的 ZjZ_j 由 cBTB−1Ajc_B^TB^{-1}A_j 計算，故 Cj−ZjC_j-Z_j 列如下。完整單形表為：

基底變數CBC_Bx1x_1x2x_2x3x_3x4x_4x5x_5x6x_6右端值
x1x_11111000011−1-1−2-244
x3x_322000011−12-\frac121132\frac3232\frac32
x2x_2−1-100110032\frac32−2-2−52-\frac52132\frac{13}{2}
🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 四 題25 分

一名玩家擲一對骰子。如果點數總和為 77 或 1010，則他贏了；如果總和為 33 或 1111，則他輸了；如果總和為其他數字，他將繼續擲骰，直到遊戲結束（他贏或輸）為止。設 XX 為遊戲結束（他贏或輸）所需的擲骰次數。

（一）求他最終贏的機率。（10 分）

（二）求 XX 的動差母函數（Moment Generating Function），即 M(t)=E[etX]M(t)=E[e^{tX}]。（10 分）

（三）求 XX 的期望值 E[X]E[X]。（5 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

這題考雙骰遊戲的吸收型過程與幾何級數。遊戲每次擲骰後有三種結果：

  • 直接獲勝：總和為 77 或 1010。
  • 直接落敗：總和為 33 或 1111。
  • 遊戲繼續：總和為其他數字。

骰子共有 6×6=366\times 6=36 種等可能結果。每次擲骰彼此獨立，因此可先計算單次獲勝、落敗與繼續的機率，再求整場遊戲的結果。

解題方法

兩顆骰子的點數和及其組合數如下：

點數和組合數
2211
3322
4433
5544
6655
7766
8855
9944
101033
111122
121211

所以單次擲骰的獲勝、落敗與繼續機率分別為

p=6+336=14,q=2+236=19,r=1−p−q=2336.p=\frac{6+3}{36}=\frac14,\qquad q=\frac{2+2}{36}=\frac19,\qquad r=1-p-q=\frac{23}{36}.

（一）最終贏的機率

玩家可以在第 nn 次擲骰才獲勝：前 n−1n-1 次都要繼續，最後一次獲勝。因此

P(X 場在第 n 次獲勝)=rn−1p.P(X\text{ 場在第 }n\text{ 次獲勝})=r^{n-1}p.

對所有 n≥1n\geq 1 加總：

P(最終獲勝)=∑n=1∞rn−1p=p∑k=0∞rk=p1−r.P(\text{最終獲勝}) =\sum_{n=1}^{\infty}r^{n-1}p =p\sum_{k=0}^{\infty}r^k =\frac{p}{1-r}.

又因為 1−r=p+q=14+19=13361-r=p+q=\frac14+\frac19=\frac{13}{36}，故

P(最終獲勝)=141336=913.P(\text{最終獲勝}) =\frac{\frac14}{\frac{13}{36}} =\boxed{\frac9{13}}.

（二）XX 的動差母函數

遊戲在第 nn 次結束的機率，是前 n−1n-1 次繼續，且第 nn 次獲勝或落敗：

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

其他考古題

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

115113112111110109