112 年國立臺灣大學工業工程學研究所碩士班產業與服務系統工程組《作業研究》考古題與詳解

Question 1

Consider the following linear programming (LP) model:
Maximize $cx$
Subject to
$Ax \leq b$
$x \geq 0$

(a) (5 points) Let $x_1$ and $x_2$ be feasible points of the LP. Write down the convex combination of $x_1$ and $x_2$ .
(b) (5 points) Let $x'$ be a point belonging to the convex combination in (a). Show that $x'$ is also feasible.
(c) (5 points) Justify that the objective value of $x'$ is not better than the optimal objective value.

Accepted Answer

本題考查線性規劃中可行區域的凸性性質。

核心觀念：線性規劃的可行區域是一個凸集（convex set）。凸集的定義是指，若集合中任兩點的連線段上的所有點都屬於該集合，則該集合為凸集。

(a) 可行組合的定義
設 $x_1$ 和 $x_2$ 是線性規劃問題的兩個可行點。它們的凸組合（convex combination）可以表示為 $\lambda x_1 + (1-\lambda) x_2$ ，其中 $0 \leq \lambda \leq 1$ 。

(b) 證明凸組合點的可行性
線性規劃的可行區域是由一組線性不等式 $Ax \leq b$ 和非負約束 $x \geq 0$ 所定義的。我們需要證明，若 $x_1$ 和 $x_2$ 是可行點，則其凸組合 $x' = \lambda x_1 + (1-\lambda) x_2$ ( $0 \leq \lambda \leq 1$ ) 也滿足這些約束。

非負約束 $x' \geq 0$ ：
由於 $x_1 \geq 0$ 且 $x_2 \geq 0$ ，且 $\lambda \geq 0$ ， $1-\lambda \geq 0$ ，因此：
$x' = \lambda x_1 + (1-\lambda) x_2 \geq \lambda(0) + (1-\lambda)(0) = 0$ 。
所以， $x'$ 滿足非負約束。
線性約束 $Ax' \leq b$ ：
由於 $x_1$ 和 $x_2$ 是可行點，我們有 $Ax_1 \leq b$ 和 $Ax_2 \leq b$ 。
考慮 $Ax'$ ：
$Ax' = A(\lambda x_1 + (1-\lambda) x_2)$
根據矩陣運算的分配律：
$Ax' = \lambda (Ax_1) + (1-\lambda) (Ax_2)$

Question 2

A company has an order from a customer for requiring 9 CNC machines, to be delivered 3 units each month over the next three months. The CNC machines can be shipped to the customer at the end of the same month in which the machines are assembled, or the machines can be stored as inventory for delivery during later months. The inventory holding cost is $400 per machine per month. The company has no current inventory of these CNC machines and desires none after the completion of this contract. The company will determine a production schedule that minimizes the total cost. The production data of assembling the CNC machines are summarized as follows.

	Month 1	Month 2	Month 3
Regular production capacity (units)	2	2	3
Regular production cost per unit	$2500	$2900	$3000
Overtime production capacity (units)	2	2	1
Overtime production cost per unit	$2800	$3400	$3200

(a) (10 points) Construct a Transportation Tableau for the problem.
(b) (5 points) Use the Northwest Corner Method to find an initial solution.

Accepted Answer

核心觀念

本題考查「運輸問題（Transportation Problem）」的建模，以及「西北角法（Northwest Corner Method）」求初始基本可行解。

每一個生產方式視為一個供給點：
第 1、2、3 月的正常工時與加班生產。
每一個交貨月份視為一個需求點：
每月需求量均為 $3$ 台。
生產後若延後交貨，每台每月增加庫存持有成本 $400$ 。
各生產方式的供給量為其生產能力。
總供給量為

2+2+2+2+3+1=12

總需求量為

3+3+3=9

供給多於需求 $3$ 台，因此加入一個「虛擬需求點」表示未使用的生產能力，需求量為 $3$ ，其運輸成本設為 $0$ 。

生產於第 $i$ 月、供應第 $j$ 月的單位成本為

\text{生產成本}+400(j-i), \qquad j\geq i

若生產月份晚於交貨月份，則不可行，該格以 $M$ 或「—」表示。

解題方法

成本計算

例如：

第 1 月正常生產，供應第 2 月：

2900+400=3300

第 1 月加班生產，供應第 3 月：

3200+2(400)=4000

第 2 月加班生產，供應第 3 月：

3400+400=3800

虛擬需求點的成本均為 $0$ ，代表該生產能力不使用。

（a）Transportation Tableau

令供給列依序為：

$R_1$ ：第 1 月正常生產
$O_1$ ：第 1 月加班生產
$R_2$ ：第 2 月正常生產
$O_2$ ：第 2 月加班生產
$R_3$ ：第 3 月正常生產
$O_3$ ：第 3 月加班生產

需求欄依序為第 1、2、3 月交貨，以及虛擬需求點。

生產來源	第1月交貨	第2月交貨	第3月交貨	未使用能力	供給量
第1月正常 $R_1$	$2500$	$2900+400=3300$	$3000+800=3800$	$0$	$2$
第1月加班 $O_1$	$2800$	$3400+400=3800$	$3200+800=4000$	$0$	$2$
第2月正常 $R_2$	$M$	$2900$	$3000+400=3400$	$0$	$2$
第2月加班 $O_2$	$M$	$3400$	$3400+400=3800$	$0$	$2$
第3月正常 $R_3$	$M$	$M$	$3000$	$0$	$3$
第3月加班 $O_3$	$M$	$M$	$3200$	$0$	$1$
需求量	3	3	3	3	12

其中：

$M$ 表示生產時間晚於交貨時間，不允許運輸。
「未使用能力」欄的需求量為 $3$ ，用來平衡供需。
$0$ 成本表示該生產能力不使用，不代表真的生產後免費保存。

（b）西北角法初始解

依照西北角法，從左上角開始分配。

第一步： $R_1$ 配給第 1 月

x_{R_1,1}=\min(2,3)=2

第 1 月尚餘需求 $1$ ， $R_1$ 生產能力用罄。

第二步： $O_1$ 配給第 1 月

x_{O_1,1}=\min(2,1)=1

第 1 月需求滿足， $O_1$ 尚餘能力 $1$ 。

第三步： $O_1$ 配給第 2 月

x_{O_1,2}=\min(1,3)=1

Question 3

NTUIIE has four teachers to offer the following courses each semester: Operations Research (OR), Production Planning (PP), Quality Control (QC), and Data Analysis (DA). The effectiveness of each teacher in teaching each class is shown in the following table. Each teacher can teach one course during the semester, and all these four courses are provided.

	OR	PP	QC	DA
Teacher A	9	8	5	5
Teacher B	9	5	6	8
Teacher C	5	8	8	6
Teacher D	7	5	8	9

(a) (10 points) Use the Hungarian Method to solve the teaching assignment problem that maximizes the total effectiveness.
(b) (10 points) Assume that a goal of achieving effectiveness level of about 7 in each course is set by the school, and deviations from this goal in any courses have equal weight. Formulate a goal programming model that determines the teaching assignment.

Accepted Answer

核心觀念 本題考查兩個主題： 1. 指派問題（assignment problem）：四位教師各教一門課，且每門課恰由一位教師教授。目標是使總教學效果最大。 2. 目標規劃（goal programming）：以各課程教學效果 $7$ 為目標，最小化各課程偏離目標的總偏差。 令 $$ x{ij}= \begin{cases} 1,&	ext{教師 }i	ext{ 教授課程 }j,\ 0,&	ext{否則。} \end{cases} $$ --- （a）以匈牙利法求最大總教學效果 步驟一：將最大化問題轉成最小化問題 表中最大效果值為 $9$，令成本矩陣為 $$ c{ij}=9-e{ij}, $$ 其中 $e{ij}$ 為原始教學效果。如此一來，總成本越小，總教學效果越大，因為四位教師各分配一門課： $$ \sum c{ij}=4(9)-\sum e{ij}=36-\sum e{ij}. $$ 因此，原問題等價於最小化下列成本矩陣： | | OR | PP | QC | DA | |------|---:|---:|---:|---:| | A | 0 | 1 | 4 | 4 | | B | 0 | 4 | 3 | 1 | | C | 4 | 1 | 1 | 3 | | D | 2 | 4 | 1 | 0 | 步驟二：列減法 每列最小值皆為 $0$，因此列減法後矩陣不變。 步驟三：欄減法 各欄最小值為： - OR 欄：$0$ - PP 欄：$1$ - QC 欄：$1$ - DA 欄：$0$ 將 PP 欄與 QC 欄各減去 $1$，得到： | | OR | PP | QC | DA | |------|---:|---:|---:|---:| | A | 0 | 0 | 3 | 4 | | B | 0 | 3 | 2 | 1 | | C | 4 | 0 | 0 | 3 | | D | 2 | 3 | 0 | 0 | 步驟四：選取互不衝突的零元素 選取下列四個互不位於同列、同欄的零元素： - A–PP - B–OR - C–QC - D–DA 因此指派結果為： | 教師 | 課程 | 原始教學效果 | |------|------|---:| | A | PP | 8 | | B | OR | 9 | | C | QC | 8 | | D | DA | 9 | 總教學效果為 $$ 8+9+8+9=34. $$ 由於已找到四個互不衝突的零元素，匈牙利法可停止；此指派即為最佳指派。 --- （b）目標規劃模型 變數定義 令： - $x{ij}=1$：教師 $i$ 教授課程 $j$ - $x{ij}=0$：否則 - $dj^-$：課程 $j$ 的效果低於目標 $7$ 的不足偏差 - $dj^+$：課程 $j$ 的效果超過目標 $7$ 的超額偏差 其中 $$ dj^…

Question 4

A mysterious disease is spreading on a small island, where the population is n. In any single period, two random people from the population meet and interact. If one of the two is infected and the other is not, the disease is transmitted to the healthy person with probability p; otherwise, no disease transmission takes place.

(a) (6 points) Setup a Markov chain model and determine the transition probability matrix.
(b) (9 points) Assuming that the process starts at time 0 with a single person infected, n = 5, and p = 0.1, what is the mean time that the disease takes to infect the whole population?
(You might need:
r -1 0 1 2]
| 0 0 1 0]
| 3 3 3 3]
| 0 0 1 0]
| 0 0 0 1]
| 0 0 0 1]
LO 0 0 1]

Accepted Answer

核心觀念 令 $Xt$ 表示第 $t$ 期結束後，島上已感染的人數。由於下一期的感染情形只取決於目前感染人數 $Xt$，與過去感染歷程無關，因此 $\{Xt\}$ 是馬可夫鏈。 狀態空間為 $$ \mathcal{S}=\{0,1,2,\ldots,n\}. $$ 其中： - $0$：沒有感染者； - $n$：全體人口皆感染。 狀態 $0$ 與 $n$ 都是吸收狀態。疾病只會新增感染者，不會自行痊癒，因此每一期感染人數最多增加 $1$。 --- (a) 轉移機率矩陣 假設目前有 $i$ 人感染，則有 $n-i$ 人尚未感染。 從全體人口中任選兩人，兩人一感染、一未感染的配對數為 $$ i(n-i). $$ 全體任選兩人的配對數為 $$ \binom{n}{2}=\frac{n(n-1)}{2}. $$ 因此，選到「一人感染、一人健康」配對的機率為 $$ \frac{i(n-i)}{\binom{n}{2}} = \frac{2i(n-i)}{n(n-1)}. $$ 在此情況下，疾病以機率 $p$ 傳給健康者，所以 $$ P{i,i+1} = p\frac{i(n-i)}{\binom{n}{2}} = \frac{2pi(n-i)}{n(n-1)}. $$ 若沒有成功傳染，感染人數維持為 $i$，故 $$ P{i,i} = 1-\frac{2pi(n-i)}{n(n-1)}. $$ 其餘轉移皆不可能，因此 $$ P{i,j}=0 \quad	ext{若 }j
otin\{i,i+1\}. $$ 特別地，$0$ 與 $n$ 為吸收狀態： $$ P{0,0}=1,\qquad P{n,n}=1. $$ 若依狀態順序 $0,1,\ldots,n$ 排列，轉移矩陣為 $$ P= \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & 0\ 0 & 1-q1 & q1 & \cdots & 0 & 0\ 0 & 0 & 1-q2 & \ddots & 0 & 0\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots\ 0 & 0 & 0 & \cdots & 1-q{n-1} & q{n-1}\ 0 & 0 & 0 & \cdots & 0 & 1 \end{bmatrix}, $$ 其中 $$ qi=\frac{2pi(n-i)}{n(n-1)},\qquad i=1,2,\ldots,n-1. $$ --- (b) 感染全體人口的平均時間

Question 5

The NTU mobile shop is now selling the newest ePhone and managing its own inventory. In the morning of day $(i + 1)$ when the shop opens, it has $Si + Ai$ ePhones on hands, where $Si$ is the stock level and $Ai$ is the ordered quantity at the end of day $i$. The ordered $Ai$ phones will always arrive before the shop opens on day $(i + 1)$. The demand of ePhone on day $i$, expressed as $Di$, occurs during business hours and follows a probability distribution. The inventory control and ordering criteria of the shop are summarized below. The shop can only hold 0 to 2 phones at the beginning of the day, i.e., $0 \leq Si + Ai \leq 2$. The shop doesn't allow backorders, i.e., $Si \geq 0$. The penalty cost of unsatisfied demand is 3 per phone. Each order issued at the end of the day yields an ord…

Accepted Answer

核心觀念 本題考查有限狀態存貨控制的庫存平衡式、馬可夫轉移機率，以及含缺貨罰款的期望成本。 訂貨量 $a$ 到貨後，隔日營業開始時的可用庫存為 $s+a$。由於不允許欠單，需求超過庫存的部分視為未滿足需求，期末庫存不會低於 $0$。因此，下一期庫存為 $$ S{i+1}=\max\{Si+Ai-D{i+1},\,0\}. $$ 其中 $0\leq Si+Ai\leq 2$，且訂貨量為非負整數。 解題方法 先依可用庫存 $x=s+a$ 計算下一期庫存的機率分布，再以訂貨成本加上期望缺貨罰款，計算各狀態與行動的期望成本。政策的長期平均成本則以其穩態機率加權各狀態成本。 (a) 庫存平衡式 $$ S{i+1}=\max\{Si+Ai-D{i+1},\,0\}. $$ 等價地，也可寫成 $S{i+1}=\max\{Si+Ai-D{i+1},0\}$；需求超過可用庫存時，未滿足的數量不會形成欠單。 (b) 完整轉移機率 令 $x=s+a$。當 $x=0$ 時，下一期庫存必為 $0$；當 $x=1$ 時，需求為 $0$ 才留下 $1$ 支；當 $x=2$ 時，需求為 $0、1、2$ 時分別留下 $2、1、0$ 支。 下表列出所有可行的 $(s,a)$，欄位為下一期庫存 $s{i+1}$： | 目前庫存 $s$ | 訂貨量 $a$ | $p{s,0}(a)$ | $p{s,1}(a)$ | $p{s,2}(a)$ | |---:|---:|---:|---:|---:| | 0 | 0 | 1.0 | 0 | 0 | | 0 | 1 | 0.6 | 0.4 | 0 | | 0 | 2 | 0.3 | 0.3 | 0.4 | | 1 | 0 | 0.6 | 0.4 | 0 | | 1 | 1 | 0.3 | 0.3 | 0.4 | | 2 | 0 | 0.3 | 0.3 | 0.4 | 例如 $(s,a)=(1,0)$ 時，可用庫存為 $1$；需求 $0$ 的機率為 $0.4$，隔日庫存為 $1$；需求 $1$ 或 $2$ 的總機率為 $0.6$，隔日庫存為 $0$。 (c) 各狀態與行動的期望成本 令 $x=s+a$。每次下單的固定處理成本為 \$2，變動成本為每支 \$4；若 $a=0$，則沒有訂單處理成本。當日未滿足需求的期望量為 $$ \mathbb{E}[(D-x)^+] =\sum{d=0}^{2}p(D=d)\max\{d-x,0\}. $$ 因此，採取行動後的期望成本為 $$ c(s,a)= \begin{cases} 0, & a=0,\ 2+4a, & a0 \end{cases} +3\mathbb{E}[(D-x)^+]. $$ 可用庫存 $x=0$ 時，期望未滿足需求量為 $0.3(1)+0.3(2)=0.9$，缺貨罰款期望為 \$2.70；$x…

112 年國立臺灣大學工業工程學研究所碩士班產業與服務系統工程組《作業研究》

第 1 題15 分

第 2 題15 分

核心觀念

解題方法

成本計算

（a）Transportation Tableau

（b）西北角法初始解

第一步： $R_1$ 配給第 1 月

第二步： $O_1$ 配給第 1 月

第三步： $O_1$ 配給第 2 月

第 3 題20 分

（a）以匈牙利法求最大總教學效果

步驟一：將最大化問題轉成最小化問題

步驟二：列減法

步驟三：欄減法

步驟四：選取互不衝突的零元素

（b）目標規劃模型

變數定義

目標函數

目標限制式

第 4 題15 分

第 5 題35 分

核心觀念

解題方法

(a) 庫存平衡式

(b) 完整轉移機率

(c) 各狀態與行動的期望成本

其他考古題

112 年臺灣大學的其他科目

臺灣大學《作業研究》其他年度

112 年 國立臺灣大學工業工程學研究所碩士班產業與服務系統工程組《作業研究》

第 1 題15 分

第 2 題15 分

核心觀念

解題方法

成本計算

（a）Transportation Tableau

（b）西北角法初始解

第一步：R1R_1R1​ 配給第 1 月

第二步：O1O_1O1​ 配給第 1 月

第三步：O1O_1O1​ 配給第 2 月

第 3 題20 分

（a）以匈牙利法求最大總教學效果

步驟一：將最大化問題轉成最小化問題

步驟二：列減法

步驟三：欄減法

步驟四：選取互不衝突的零元素

（b）目標規劃模型

變數定義

目標函數

目標限制式

第 4 題15 分

第 5 題35 分

核心觀念

解題方法

(a) 庫存平衡式

(b) 完整轉移機率

(c) 各狀態與行動的期望成本

其他考古題

112 年臺灣大學的其他科目

臺灣大學《作業研究》其他年度

112 年國立臺灣大學工業工程學研究所碩士班產業與服務系統工程組《作業研究》

第一步： $R_1$ 配給第 1 月

第二步： $O_1$ 配給第 1 月

第三步： $O_1$ 配給第 2 月