加載中. ..
PDF
113年公務人員高等考試三級考試試題
類 科
：
工業工程
科 目
：
作業研究
考試時間
：
2
小時
座號
：
※注意：禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目得以本國文字或英文作答。
代號：
36940
頁次：
3
－
1
一、求解馬可夫決策過程之問題的其中一種方式是可以將此問題轉化成線
性規劃的問題來看待。考慮以下由馬可夫決策過程之問題轉化後之原始
（Primal）線性規劃問題：
Minimize
(0)(0)+(1)(1)+(2)(2)+(3)(3)+(4)(4)
Subject to:
(0)− 0.9(0) − 0.1(1) − 0(2) − 0(3) − 0(4) ≥ (0,0)
(0)− 0.1(0)− 0.9(1)− 0(2)− 0(3)− 0(4)≥(0,1)
(1)− 0.9(0)− 0(1)− 0.1(2)− 0(3)− 0(4)≥(1,0)
(1)− 0.1(0)− 0(1)− 0.9 (2)− 0(3)− 0(4)≥(1,1)
(2)− 0(0) − 0(1) − 0(2) − 0(3) − 0(4) ≥ (2,0)
(2)− 0(0)− 0(1)− 0(2)− 0(3)− 0(4)≥(2,1)
(3)− 0(0) − 0(1) − 0.9(2) − 0(3) − 0.1(4) ≥ (3,0)
(3)− 0(0)− 0(1)− 0.1(2)− 0(3)− 0.9(4)≥(3,1)
(4)− 0(0) − 0(1) − 0(2) − 0.9(3) − 0.1(4) ≥ (4,0)
(4)− 0(0)− 0(1)− 0(2)− 0.1 (3)− 0.9 (4)≥(4,1)
()≥ 0 for = 1,2,3,4。在此問題中，()為決策變數而α(∙)及r(∙,∙)為
給定常數。
假設 (,),= 0,1,2,3,4; = 0,1為上述問題相對應之對偶（Dual）線
性規劃問題之對偶決策變數（dual variable）。
請寫出對偶問題之目標式。（5分）
請寫出對偶問題之限制式。（20 分）
代號：
36940
頁次：
3
－
2
二、在每次賭局中，賭徒每次下注的上限即是他當下手中所擁有的現金。每
次贏錢的機率與輸錢的機率分別是和= 1 − 。賭徒一共可以下注 n次
而且每次下注的金額為其所擁有的現金成一固定比例，其中0 ≤ ≤ 1。
他的目標為最大化其最後所擁有現金取自然對數後之期望值。當賭徒手
上擁有現金並且還有次下注機會時，以
()來表示在此情況下賭徒
最大的期望目標值。邊際條件為
() = ()。
假設> 1/2，利用
() = ()之結果，證明
() = +()，其
中=(2) + () + ()。（15 分）
假設> 1/2，證明
() = +()，forall 皆成立而且最佳下注策
略為每次下注的金額為其當下所擁有的現金之 −比例。（10 分）
三、考慮以下線性規劃問題
max = 12+ 9
subject to ≤ 1000
≤ 1500
+≤ 1750
4+ 2≤ 4800
,≥ 0.
請將此問題轉成以標準型式（standard form）來表示，也就是將所有不
等式轉成為等式的型式。（5分）
請以單形法（Simplex method）的表格式（Tableau form）來求解最佳
解並在每回合表中列出完整之列表。（20 分）
代號：
36940
頁次：
3
－
3
四、律師事務所正準備招聘新的律師。以下是律師事務所預估未來一年新聘
律師所需要處理的案件時數：
月份 案件時數（小時） 月份 案件時數（小時）
1 650 7 750
2 450 8 900
3 600 9 800
4 500 10 650
5 700 11 700
6 650 12 500
每一位新聘的律師預期每月可以處理 150 小時的案件時數而且其聘任期
至少為一年。所有的案件時數必須在年終處理完畢。這家律師事務所想
要決定新的一年所要聘任的新律師的人數。請定義所需之決策變數並將
此問題以整數規劃的形式表示出來。（25 分）