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

Question 1

求解馬可夫決策過程之問題的其中一種方式，是可以將此問題轉化成線性規劃的問題來看待。考慮以下由馬可夫決策過程之問題轉化後之原始（Primal）線性規劃問題：

Minimize

\alpha(0)v(0)+\alpha(1)v(1)+\alpha(2)v(2)+\alpha(3)v(3)+\alpha(4)v(4)

Subject to:

v(0)-0.9v(0)-0.1v(1)-0v(2)-0v(3)-0v(4)\geq r(0,0)

v(0)-0.1v(0)-0.9v(1)-0v(2)-0v(3)-0v(4)\geq r(0,1)

v(1)-0.9v(0)-0v(1)-0.1v(2)-0v(3)-0v(4)\geq r(1,0)

v(1)-0.1v(0)-0v(1)-0.9v(2)-0v(3)-0v(4)\geq r(1,1)

v(2)-0v(0)-0v(1)-0v(2)-0v(3)-0v(4)\geq r(2,0)

v(2)-0v(0)-0v(1)-0v(2)-0v(3)-0v(4)\geq r(2,1)

v(3)-0v(0)-0v(1)-0.9v(2)-0v(3)-0.1v(4)\geq r(3,0)

v(3)-0v(0)-0v(1)-0.1v(2)-0v(3)-0.9v(4)\geq r(3,1)

v(4)-0v(0)-0v(1)-0v(2)-0.9v(3)-0.1v(4)\geq r(4,0)

v(4)-0v(0)-0v(1)-0v(2)-0.1v(3)-0.9v(4)\geq r(4,1)

v(s)\geq 0\quad\text{for }s=1,2,3,4。

在此問題中， $v(s)$ 為決策變數，而 $\alpha(\cdot)$ 與 $r(\cdot,\cdot)$ 為給定常數。

假設 $x(s,a)$ ， $s=0,1,2,3,4$ ； $a=0,1$ 為上述問題相對應之對偶（Dual）線性規劃問題之對偶決策變數。

(一) 請寫出對偶問題之目標式。

(二) 請寫出對偶問題之限制式。

Accepted Answer

核心觀念

此題考馬可夫決策過程（MDP）的價值函數線性規劃與其對偶。原始問題是最小化狀態價值的加權和，對偶變數 $x(s,a)$ 對應原始問題中狀態 $s$ 、動作 $a$ 的 Bellman 不等式。

原始問題中 $v(0),\ldots,v(4)$ 都是自由變數；題目只對 $v(1),\ldots,v(4)$ 加上非負限制。因此，對偶中：

每一條原始限制式對應一個非負對偶變數 $x(s,a)\geq 0$ 。
原始變數若自由，對應的對偶限制式為等式；若原始變數非負，對應的對偶限制式為「 $\leq$ 」。

解題方法

先把每條原始限制式整理成「本期價值減去折現後的下一期價值」：

v(s)-\sum_{s'=0}^{4}p(s'|s,a)v(s')\geq r(s,a).

因此對偶目標式以原始限制式右側的獎酬為係數，並最大化：

\max \sum_{s=0}^{4}\sum_{a=0}^{1}r(s,a)x(s,a).

接著，逐一看每個 $v(s)$ 在所有原始限制式中的係數。若 $v(s)$ 自由，該欄係數加總須等於目標式係數 $\alpha(s)$ ；若 $v(s)\geq0$ ，該欄係數加總須小於或等於 $\alpha(s)$ 。

題目中每個限制式裡， $v(s)$ 的正係數是 $1$ ，其餘係數是轉移機率的負值。因此 $v(s)$ 欄係數加總為：

\sum_{a=0}^{1}x(s,a)-\sum_{i=0}^{4}\sum_{a=0}^{1}p(s|i,a)x(i,a).

令其符合原始目標式的係數，即得到對偶限制式。

對偶限制式推導

由於 $v(0)$ 未受符號限制，對應等式：

\sum_{a=0}^{1}x(0,a) -\sum_{i=0}^{4}\sum_{a=0}^{1}p(0|i,a)x(i,a) =\alpha(0).

由題目轉移機率，只有從狀態 $0$ 、 $1$ 轉移至狀態 $0$ 的機率非零，故：

x(0,0)+x(0,1) -0.9x(0,0)-0.1x(0,1) -0.9x(1,0)-0.1x(1,1) =\alpha(0).

同理，由於 $v(1)$ 至 $v(4)$ 均非負，對應不等式。逐欄整理如下：

Question 2

在每次賭局中，賭徒每次下注的上限即是他當下手中所擁有的現金。每次贏錢的機率與輸錢的機率分別是 $p$ 和 $q=1-p$ 。賭徒一共可以下注 $n$ 次，而且每次下注的金額為其所擁有的現金成一固定比例 $\alpha$ ，其中 $0\leq\alpha\leq1$ 。他的目標為最大化其最後所擁有現金取自然對數後之期望值。

當賭徒手上擁有現金 $x$ 且還有 $n$ 次下注機會時，以 $V_n(x)$ 來表示在此情況下賭徒最大的期望目標值。邊界條件為

V_0(x)=\ln(x)。

(一) 假設 $p>\frac{1}{2}$ ，利用 $V_0(x)=\ln(x)$ 之結果，證明

V_1(x)=c+\ln(x)，

其中

c=\ln(2)+p\ln(p)+q\ln(q)。

(二) 假設 $p>\frac{1}{2}$ ，證明

V_n(x)=nc+\ln(x)，\quad\text{for all }n

皆成立，而且最佳下注策略為每次下注的金額為其當下所擁有的現金之 $p-q$ 比例。

Accepted Answer

核心觀念 這題考有限期動態規劃與對數效用的可加性。若下注比例為 $\alpha$，贏時現金變成 $x(1+\alpha)$，輸時變成 $x(1-\alpha)$。因此，給定下注策略後的期望目標值可由兩種結果的對數效用加權計算。 解題方法 令 $Vn(x)$ 表示手上有現金 $x$、尚有 $n$ 次下注機會時可達到的最大期望對數效用。下注比例 $\alpha$ 必須介於 $0$ 與 $1$ 之間。對 $n\geq 1$，Bellman 方程為 $$ Vn(x)=\max{0\leq\alpha\leq 1} \left\{ pV{n-1}\bigl(x(1+\alpha)\bigr) +qV{n-1}\bigl(x(1-\alpha)\bigr) ight\}. $$ 由於 $q=1-p$ 且 $p\frac12$，可知 $p0$、$q0$。當 $\alpha=1$ 且輸掉時，現金歸零，$\ln 0$ 不存在；此策略的期望效用視為負無窮，因此不會是最佳策略。 （一）證明 $V1(x)=c+\ln(x)$ 使用邊界條件 $V0(y)=\ln(y)$： $$ \begin{aligned} V1(x) &=\max{0\leq\alpha<1} \left\{ p\ln\bigl(x(1+\alpha)\bigr) +q\ln\bigl(x(1-\alpha)\bigr) ight\}\ &=\ln(x)+\max{0\leq\alpha<1} \left\{ p\ln(1+\alpha)+q\ln(1-\alpha) ight\}. \end{aligned} $$ 設 $f(\alpha)=p\ln(1+\alpha)+q\ln(1-\alpha)$。其一階導數為 $$ f'(\alpha)=\frac{p}{1+\alpha}-\frac{q}{1-\alpha}. $$ 令 $f'(\alpha)=0$，得到 $$ p(1-\alpha)=q(1+\alpha) \quad\Longrightarrow\quad \alpha=\frac{p-q}{p+q}=p-q, $$ 其中 $p+q=1$。又因為 $$ f''(\alpha)=-\frac{p}{(1+\alpha)^2}-\frac{q}{(1-\alpha)^2}<0, $$ 所以 $f$ 為嚴格凹函數，該臨界點即為唯一最大點。將 $\alpha=p-q$ 代入，可得

Question 3

考慮以下線性規劃問題： Max $$ z=12x1+9x2 $$ subject to $$ x1\leq1000 $$ $$ x2\leq1500 $$ $$ x1+x2\leq1750 $$ $$ 4x1+2x2\leq4800 $$ $$ x1,x2\geq0。 $$ (一) 請將此問題轉成以標準型式（standard form）來表示，也就是將所有不等式轉成為等式的型式。 (二) 請以單形法（Simplex method）的表格式（Tableau form）來求解最佳解，並在每回合表中列出完整之列表。

Accepted Answer

核心觀念

本題考查線性規劃的標準型式轉換，以及以單形法（Simplex method）逐次換基求最大值。將「 $\leq$ 」限制式加入非負鬆弛變數，即可轉為等式；單形表中依目標列選入基變數，再依最小正比值選出基變數。

（一）轉換為標準型式

各限制式加入鬆弛變數 $s_1,s_2,s_3,s_4\geq0$ ：

\begin{aligned} x_1+s_1&=1000,\\ x_2+s_2&=1500,\\ x_1+x_2+s_3&=1750,\\ 4x_1+2x_2+s_4&=4800. \end{aligned}

目標式寫成

z-12x_1-9x_2=0,

且

x_1,x_2,s_1,s_2,s_3,s_4\geq0.

初始基底為 $s_1,s_2,s_3,s_4$ ，初始基本可行解為 $x_1=x_2=0$ 、 $s_1=1000$ 、 $s_2=1500$ 、 $s_3=1750$ 、 $s_4=4800$ 。

（二）單形法表格式求解

採用目標列為 $z-12x_1-9x_2=0$ 的表法。每一回合選目標列中最負係數所對應的變數入基；比值測試只計算入基欄正係數列的「右端值 ÷ 入基欄係數」，最小非負比值所在列的基變數出基。

初始表

$x_1$ 、 $x_2$ 的目標列係數分別為 $-12$ 、 $-9$ ，故 $x_1$ 入基。比值為 $1000/1=1000$ 、 $1750/1=1750$ 、 $4800/4=1200$ ；最小比值為 $1000$ ，故 $s_1$ 出基。樞紐元素為 $1$ 。

基變數	$C_B$	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	$s_4$	RHS
$s_1$	0	1	0	1	0	0	0	1000
$s_2$	0	0	1	0	1	0	0	1500
$s_3$	0	1	1	0	0	1	0	1750
$s_4$	0	4	2	0	0	0	1	4800
$z$ 列		-12	-9	0	0	0	0	0

第一次換基後

以樞紐列為基準消去其他列的 $x_1$ 係數，基底變為 $x_1,s_2,s_3,s_4$ 。目標列的 $x_2$ 係數為 $-9$ ，故 $x_2$ 入基。比值為 $1500/1=1500$ 、 $750/1=750$ 、 $800/2=400$ ；最小比值為 $400$ ，故 $s_4$ 出基。樞紐元素為 $2$ 。

基變數	$C_B$	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	$s_4$	RHS
$x_1$	12	1	0	1	0	0	0	1000
$s_2$	0	0	1	0	1	0	0	1500
$s_3$	0	0	1	-1	0	1	0	750
$s_4$	0	0	2	-4	0	0	1	800
$z$ 列		0	-9	12	0	0	0	12000

第二次換基後

Question 4

律師事務所正準備招聘新的律師。以下是律師事務所預估未來一年新聘律師所需要處理的案件時數：

月份	案件時數（小時）	月份	案件時數（小時）
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 小時的案件時數，而且其聘任期至少為一年。所有的案件時數必須在年終處理完畢。這家律師事務所想要決定新的一年所要聘任的新律師的人數。請定義所需之決策變數並將此問題以整數規劃的形式表示出來。

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

Accepted Answer

核心觀念 本題考的是「整數規劃」中的人力配置問題： - 決策變數為新聘律師人數。 - 每位律師每月可處理 $150$ 小時。 - 聘任期間至少一年，因此每位律師全年可提供： $$ 150 	imes 12=1,800	ext{ 小時} $$ - 律師人數必須為非負整數。 - 所有案件只要求在年終前完成，因此以全年總案件時數與全年總處理能力比較。 解題方法 設： $$ x=	ext{新聘律師人數} $$ 其中： $$ x\in\mathbb{Z}{\geq 0} $$ 全年案件總時數為： $$ 650+450+600+500+700+650+750+900+800+650+700+500 =7,850	ext{ 小時} $$ 每位律師全年可處理 $1,800$ 小時，因此 $x$ 位律師全年總處理能力為： $$ 1,800x $$ 為確保全年案件均能處理完畢，須滿足： $$ 1,800x\geq 7,850 $$ 若以成本相同且希望聘任人數最少為目標，整數規劃模型為： $$ \begin{aligned} \min\quad & Z=x\ 	ext{s.t.}\quad & 1,800x\geq 7,850\ & x\in\mathbb{Z}{\geq 0} \end{aligned} $$ 求得：

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

第一題25 分

核心觀念

解題方法

對偶限制式推導

第二題25 分

第三題25 分

核心觀念

（一）轉換為標準型式

（二）單形法表格式求解

初始表

第一次換基後

第二次換基後

第四題25 分

其他考古題

113 年工業工程的其他科目

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

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

第 一 題25 分

核心觀念

解題方法

對偶限制式推導

第 二 題25 分

第 三 題25 分

核心觀念

（一）轉換為標準型式

（二）單形法表格式求解

初始表

第一次換基後

第二次換基後

第 四 題25 分

其他考古題

113 年工業工程的其他科目

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

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

第一題25 分

第二題25 分

第三題25 分

第四題25 分