加載中. ..
PDF
114年公務人員高等考試三級考試試題
類 科
：
工業工程
科 目
：
作業研究
考試時間
：
2
小時
座號
：
※注意：可以使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
2
7240
頁次：
2
－
1
一、考慮一個雙人零和賽局（Two-person Zero-sum Game），其收益表（Payoff
Table）如下： 參賽者 B
策略 b1 b2 b3
參賽者 Aa1 8 0 5
a2 9 5 1
a3 3 10 7
若參賽者A採取策略a1，而參賽者B採取策略 b1，參賽者A之收益為8，
相對地，參賽者 B之收益為−8，餘此類推。
若雙方均採取最大損失最小化原則來選取單一策略，雙方所選取之策
略為何？（10 分）
此問題是否有鞍點（Saddle Point）？原因為何？（5分）
若參賽者 A考慮採取混合策略，請寫出一個線性規劃（Linear
Programming）以幫助參賽者A決定最佳的混合策略（無需求解）。（10 分）
二、請使用分枝界限（Branch-and-Bound）法求解下列背包問題（Knapsack
Problem），以將所有整數變數放鬆為實數變數的方式求取搜尋樹（Search
Tree）中各節點所需之上限值（Upper Bound），請畫出搜尋樹，並標示各
節點所對應的完整實數解及上限值：（25 分）
1 2 3 4 5 6
1 2 3 4 5 6
Max 10 3 8 5 3
s.t. 8 3 5 2 2 15
0 1, 1,2,...,6
i
z x x x x x x
x x x x x x
x or i
代號：
27240
頁次：
2
－
2
三、考慮下列線性規劃問題：
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
Max 2
s.t. 3 15
2 3
4
0, 0, 0
z x x x
x x x
x x x
x x x
x x x
令
4 5 6
, ,
x x x
分別代表限制式 1, 2, 3 的寬裕變數（Slack Variable），考慮一
個基本解（Basic Solution）
B
X
=（
1 3 2
, ,
x x x
），此基本解所對應的反矩陣
（Inverse）為
1
1 1 2
1/ 2 1 3/ 2
3/ 2 2 5/ 2
B
請計算此基本解所對應的目標函數值。（5分）
請建構此基本解所對應的完整單形表（Simplex Tableau）。（10 分）
請判斷此基本解是否為最佳解？若否，由此基本解開始，利用單形法
（Simplex Method）求取最佳解。（10 分）
四、一名玩家擲一對骰子，如果點數總和為 7或10，則他贏了；如果總和為
3或11，則他輸了；如果總和為其他數字，他將繼續擲骰，直到遊戲結
束（他贏或輸）為止。設 X為遊戲結束（他贏或輸）所需的擲骰次數。
注意：若
X 3
，指的是擲一對骰子 3次。請回答以下問題：
求他最終贏的機率。（10 分）
求X的動差母函數（MomentGeneratingFunction），即M(t)=E[
tX
e
]。（10分）
求X的期望值 E[X]。（5分）
（限制式
1
）
（限制式
2
）
（限制式
3
）