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

核心觀念

本題考查：

1. 線性規劃的對偶問題建構。
2. 原問題與對偶問題的變數、限制式及目標函數之對應關係。
3. 互補鬆弛定理（Theorem of Complementary Slackness）。
4. 利用原問題的最佳解求得對偶問題的最佳解。

原問題為「最大化」、限制式為「$\le$」、變數為非負，因此其對偶為「最小化」、對偶變數非負，且對偶限制式為「$\ge$」。

---

(a) 建立對偶問題

原問題為

$$\begin{aligned} \max \quad & z=6x_1+10x_2+9x_3+20x_4\\ \text{subject to}\quad &4x_1+9x_2+7x_3+10x_4\le 600\\ &x_1+x_2+3x_3+40x_4\le 400\\ &3x_1+4x_2+2x_3+x_4\le 500\\ &x_1,x_2,x_3,x_4\ge 0 \end{aligned}$$

令三個原問題限制式分別對應對偶變數 $y_1,y_2,y_3$。

對偶目標函數

原問題每一條限制式右側常數形成對偶目標函數係數，因此：

$$\min \quad w=600y_1+400y_2+500y_3$$

對偶限制式

原問題每一個變數形成一條對偶限制式：

• $x_1$ 的係數欄為 $(4,1,3)^T$：

$$4y_1+y_2+3y_3\ge 6$$

• $x_2$ 的係數欄為 $(9,1,4)^T$：

$$9y_1+y_2+4y_3\ge 10$$

• $x_3$ 的係數欄為 $(7,3,2)^T$：

$$7y_1+3y_2+2y_3\ge 9$$

• $x_4$ 的係數欄為 $(10,40,1)^T$：

$$10y_1+40y_2+y_3\ge 20$$

由於原問題的限制式皆為 $\le$ 且為最大化問題，對偶變數皆須非負：

$$y_1,y_2,y_3\ge 0$$

因此對偶問題為

$$\begin{aligned} \min \quad & w=600y_1+400y_2+500y_3\\ \text{subject to}\quad &4y_1+y_2+3y_3\ge 6\\ &9y_1+y_2+4y_3\ge 10\\ &7y_1+3y_2+2y_3\ge 9\\ &10y_1+40y_2+y_3\ge 20\\ &y_1,y_2,y_3\ge 0 \end{aligned}$$

---

(b) 利用互補鬆弛定理求對偶最佳解

第一步：由原問題的鬆弛變數判斷對偶變數

互補鬆弛條件為：

$$y_i s_i=0,\qquad i=1,2,3$$

已知原問題最佳解的鬆弛變數為

$$(s_1,s_2,s_3)=\left(0,0,\frac{280}{3}\right)$$

因為

$$s_3=\frac{280}{3}>0$$

所以依互補鬆弛定理：

$$y_3=0$$

---

第二步：由原問題的正值變數判斷對偶限制式

另一組互補鬆弛條件為：

$$x_j\left((A^Ty)_j-c_j\right)=0$$

已知

$$x_1=\frac{400}{3}>0$$

因此 $x_1$ 所對應的對偶限制式必須取等號：

$$4y_1+y_2+3y_3=6$$

代入 $y_3=0$：

$$4y_1+y_2=6$$

目前得到

$$y_3=0,\qquad 4y_1+y_2=6$$

---

第三步：利用最佳目標值相等求出 $y_1,y_2$

原問題與對偶問題若皆達最佳解，依強對偶定理，兩者最佳目標值相等：

$$w^*=z^*=\frac{2800}{3}$$

因此

$$600y_1+400y_2+500y_3=\frac{2800}{3}$$

代入 $y_3=0$：

$$600y_1+400y_2=\frac{2800}{3}$$

搭配

$$4y_1+y_2=6$$

由第二式得

$$y_2=6-4y_1$$

代入目標值方程式：

$$600y_1+400(6-4y_1)=\frac{2800}{3}$$

核心觀念

本題考查「指派問題的運輸問題模型」以及兩種不同的最佳化目標：

1. 最小化專案總工時：將四項工作的執行時間加總，目標是最小化所有學生投入的時間總和。
2. 最小化專案完成時間：兩位學生可同時工作，因此專案完成時間取決於兩人中較晚完成者，即最小化兩位學生工作時間的最大值（minimax）。

每項工作必須且只能分配給一位學生；每位學生恰好負責兩項工作。

令

• $x_{ij}=1$：學生 $i$ 負責工作 $j$；
• $x_{ij}=0$：否則。

學生集合為 $i\in\{A,B\}$，工作集合為

$j\in\{F,I,N,R\}$

其中 $F$、$I$、$N$、$R$ 分別代表 formulation、implementation、numerical study、reporting。

---

解題方法

先將資料整理如下：

學生／工作	$F$	$I$	$N$	$R$
A	5	7.3	3.2	4.6
B	5.4	6.7	3.8	4.9

由於每位學生必須做兩項工作，可將學生視為供給點，每位學生供給量為 $2$；四項工作視為需求點，每項需求量為 $1$。

---

(a) 最小化專案總工時

運輸問題模型

目標函數為所有指派工作所需時間的總和：

$$\min Z = 5x_{AF}+7.3x_{AI}+3.2x_{AN}+4.6x_{AR} +5.4x_{BF}+6.7x_{BI}+3.8x_{BN}+4.9x_{BR}$$

每位學生恰好負責兩項工作：

$$x_{AF}+x_{AI}+x_{AN}+x_{AR}=2$$ $$x_{BF}+x_{BI}+x_{BN}+x_{BR}=2$$

每項工作恰好分配給一位學生：

$$x_{AF}+x_{BF}=1$$ $$x_{AI}+x_{BI}=1$$ $$x_{AN}+x_{BN}=1$$ $$x_{AR}+x_{BR}=1$$

且

$$x_{ij}\in\{0,1\}$$

求解

只要決定 A 負責哪兩項工作，B 就負責另外兩項。逐一比較：

A 負責工作	A 工時	B 負責工作	B 工時	總工時
$F,I$	$12.3$	$N,R$	$8.7$	$21.0$
$F,N$	$8.2$	$I,R$	$11.6$	$19.8$
$F,R$	$9.6$	$I,N$	$10.5$	$20.1$
$I,N$	$10.5$	$F,R$	$10.3$	$20.8$
$I,R$	$11.9$	$F,N$	$9.2$	$21.1$
$N,R$	$7.8$	$F,I$	$12.1$	$19.9$

因此最適指派為：

• A：formulation、numerical study；
• B：implementation、reporting。

最小總工時為

$$Z^*=5+3.2+6.7+4.9=19.8$$

---

(b) 最小化每位學生的工作時間

此處的「time spent for each student」應理解為：兩位學生可以平行工作，專案完成時間由工作較久的學生決定。因此要最小化兩位學生工作時間的最大值。

定義每位學生的總工作時間：

$$T_A= 5x_{AF}+7.3x_{AI}+3.2x_{AN}+4.6x_{AR}$$ $$T_B= 5.4x_{BF}+6.7x_{BI}+3.8x_{BN}+4.9x_{BR}$$

再令 $T$ 表示專案完成時間，要求兩位學生的工作時間都不超過 $T$：

$$\min T$$

subject to

$$T_A\le T$$ $$T_B\le T$$

以及與 (a) 相同的指派限制：

$$x_{AF}+x_{AI}+x_{AN}+x_{AR}=2$$ $$x_{BF}+x_{BI}+x_{BN}+x_{BR}=2$$ $$x_{AF}+x_{BF}=1$$ $$x_{AI}+x_{BI}=1$$ $$x_{AN}+x_{BN}=1$$

本題考查動態規劃或網路流模型在設備更新問題中的應用，具體來說是使用最短路徑問題來決定設備（拖拉機）的更新策略，以最小化總成本。

核心觀念：

1. 設備更新問題的決策點與狀態。
2. 將時間序列問題轉換為網路圖模型。
3. 最短路徑問題的應用。
4. 線性規劃的建立。

解題過程：

此問題是在 3 年的時間跨度內，決定何時購買新拖拉機並何時賣掉舊拖拉機，以最小化總的折現成本。

** (a) What network optimization model can be used to solve this problem so that the total cost over 3 years can be minimized? Also draw the corresponding network graph. **

這個問題可以被看作是一個尋找最短路徑的問題。
我們從「現在」（第 0 年）開始，目標是在第 3 年結束時，總成本最低。
我們可以將時間點視為圖中的節點（Nodes）。
節點代表時間點：0, 1, 2, 3。
從一個時間點 $i$ 到另一個時間點 $j$ 的弧（Arc）代表在時間點 $i$ 購買新拖拉機，並在時間點 $j$ 將其賣掉。這個弧的權重（Cost）就是表格中給出的費用。
我們希望從節點 0 出發，經過一系列的購買和賣出決策，最終到達第 3 年結束時，總成本最低。

網路模型：最短路徑問題 (Shortest Path Problem)

• 節點 (Nodes): 代表時間點。我們有節點 $0, 1, 2, 3$。
• 弧 (Arcs): 代表在某個時間點購買新拖拉機，並在之後的某個時間點賣掉。
  • 從節點 $i$ 到節點 $j$ 的弧，表示在時間點 $i$ 購買新拖拉機，並在時間點 $j$ 賣掉。
  • 弧的權重（Cost）是從表格中讀取的對應 $i$ 和 $j$ 的總折現成本。
• 起始節點 (Source): 節點 0。
• 目標： 找到從節點 0 到達節點 3 的最短路徑。

網路圖的繪製：

節點：

• $N_0$: 現在 (Year 0)
• $N_1$: Year 1
• $N_2$: Year 2
• $N_3$: Year 3 (結束點)

弧及其權重：

• 從 $N_0$ 到 $N_1$: 成本 $10000$
• 從 $N_0$ 到 $N_2$: 成本 $20000$
• 從 $N_0$ 到 $N_3$: 成本 $33000$
• 從 $N_1$ 到 $N_2$: 成本 $12000$
• 從 $N_1$ 到 $N_3$: 成本 $23000$
• 從 $N_2$ 到 $N_3$: 成本 $14000$

圖示：

graph LR
    N0(Year 0) -->|10000| N1(Year 1)
    N0 -->|20000| N2(Year 2)
    N0 -->|33000| N3(Year 3)
    N1 -->|12000| N2
    N1 -->|23000| N3
    N2 -->|14000| N3

說明：
這個圖代表了所有的可能決策。例如，從 $N_0$ 到 $N_1$ 的弧代表在第 0 年購買拖拉機，並在第 1 年結束時賣掉。從 $N_1$ 到 $N_2$ 的弧代表在第 1 年購買（或繼續使用），並在第 2 年結束時賣掉。
我們需要找到一條從 $N_0$ 到 $N_3$ 的路徑，使得路徑上所有弧的權重之和最小。這條路徑的選擇就代表了最佳的拖拉機購買和更換策略。
例如，一條路徑 $N_0 \to N_1 \to N_3$ 代表在第 0 年購買，在第 1 年賣掉，然後在第 1 年再購買，在第 3 年賣掉。總成本是 $10000 + 23000 = 33000$。
另一條路徑 $N_0 \to N_2 \to N_3$ 代表在第 0 年購買，在第 2 年賣掉，然後在第 2 年再購買，在第 3 年賣掉。總成本是 $20000 + 14000 = 34000$。
還有一條路徑 $N_0 \to N_3$ 代表在第 0 年購買，並一直使用到第 3 年結束才賣掉。總成本是 $33000$。

這個模型假設我們必須在第 3 年結束時賣掉拖拉機（或其殘值計入總成本）。
如果我們需要從節點 0 到達節點 3，則我們必須選擇一條路徑。
例如，如果我們選擇 $N_0 \to N_1$，則我們在第 1 年結束時需要做出新的決策：是繼續持有到第 2 年 ($N_1 \to N_2$)，還是持有到第 3 年 ($N_1 \to N_3$)。
這是一個典型的動態規劃問題，可以用最短路徑演算法（如 Dijkstra 演算法）來求解。

【答案】
網路優化模型：最短路徑問題。
對應的網路圖：
節點代表時間點：0, 1, 2, 3。
弧代表購買新拖拉機並持有至賣出的決策，弧的權重為該決策的總折現成本。
圖示如下：

graph LR
    N0(Year 0) -->|10000| N1(Year 1)
    N0 -->|20000| N2(Year 2)
    N0 -->|33000| N3(Year 3)
    N1 -->|12000| N2
    N1 -->|23000| N3
    N2 -->|14000| N3

** (b) Based on (a), formulate the corresponding linear programming model. **

我們將使用決策變數來表示是否選擇某條弧（即某個時間段的購買/持有策略）。
設 $x_{ij}$ 為一個二元變數，表示是否在時間點 $i$ 購買新拖拉機，並在時間點 $j$ 賣掉。
$x_{ij} = 1$ 如果選擇在 $i$ 購買並在 $j$ 賣掉，否則 $x_{ij} = 0$。
這裡的 $i$ 和 $j$ 是購買和賣出的時間點。
根據表格，可能的 $(i, j)$ 組合有：
(0, 1), (0, 2), (0, 3)
(1, 2), (1, 3)
(2, 3)

目標函數是最小化總成本：
$\min \quad z = 10000 x_{01} + 20000 x_{02} + 33000 x_{03} + 12000 x_{12} + 23000 x_{13} + 14000 x_{23}$

現在考慮約束條件。
我們需要確保從第 0 年開始，並且在第 3 年結束時，我們已經完成了一個完整的購買-使用-賣出週期。

本題考查動態規劃（Dynamic Programming, DP）在資源分配問題中的應用，特別是多維度資源分配問題。

核心觀念：

1. 動態規劃的要素：階段（Stages）、狀態（States）、決策（Decisions）、遞迴關係（Recurrence Relation）。
2. 將問題分解為子問題。
3. 利用表格法（Tabulation）或遞迴法（Recursion with memoization）求解。

解題過程：

我們有 5 盒冰淇淋（總資源）需要分配給 3 個商店（決策對象）。每個商店可以獲得 0 到 5 盒冰淇淋，但總分配量不能超過 5 盒。每個商店獲得不同數量的冰淇淋所產生的利潤是給定的。目標是最大化總利潤。

這是一個典型的資源分配問題，可以使用動態規劃來解決。我們可以將問題分解為：

• 階段：考慮分配給商店的順序，例如，先決定商店 1 的分配，然後是商店 2，最後是商店 3。
• 狀態：在每個階段，狀態需要包含剩餘的資源（冰淇淋盒數）以及之前階段已經分配的資源。
• 決策：在每個階段，決定當前商店分配多少盒冰淇淋。
• 遞迴關係：計算當前階段的總最大利潤，基於之前階段的最大利潤和當前階段的決策。

我們採用一個從左到右（從商店 1 到商店 3）的動態規劃方法。

定義：
令 $DP(k, b)$ 表示將 $b$ 盒冰淇淋分配給從商店 $k$ 到商店 $N$（這裡 $N=3$）的最大總利潤。
我們的目標是計算 $DP(1, 5)$。

階段： $k = 1, 2, 3$ (代表商店 1, 2, 3)
狀態： $b$ (剩餘可分配的冰淇淋盒數)，$b$ 的範圍是 $0$ 到 $5$。
決策： 在階段 $k$，決定分配 $x$ 盒冰淇淋給商店 $k$。$x$ 的範圍是 $0$ 到 $b$。

遞迴關係：
$DP(k, b) = \max_{0 \le x \le b} \{ \text{Profit}(k, x) + DP(k+1, b-x) \}$
其中 $\text{Profit}(k, x)$ 是商店 $k$ 獲得 $x$ 盒冰淇淋的利潤。
基本情況（Base Case）：當 $k = N+1 = 4$ 時，表示沒有更多商店需要分配，所以 $DP(4, b) = 0$ 對於所有 $b \ge 0$。

具體計算：

我們需要一個表格來儲存 DP 值。表格的行代表商店 (k)，列代表可分配的冰淇淋盒數 (b)。
我們從最後一階段 (k=3) 開始向前計算。

商店 3 (k=3)：
$DP(3, b) = \max_{0 \le x \le b} \{ \text{Profit}(3, x) + DP(4, b-x) \}$
由於 $DP(4, \cdot) = 0$，所以 $DP(3, b) = \max_{0 \le x \le b} \{ \text{Profit}(3, x) \}$。
這裡 $\text{Profit}(3, x)$ 是表格中「NTUShop Store 3」的利潤。

b	Profit(3, x) for x=0..b	DP(3, b)
0	Profit(3, 0) = 0	0
1	Profit(3, 0)=0, Profit(3, 1)=4	4
2	Profit(3, 0)=0, Profit(3, 1)=4, Profit(3, 2)=9	9
3	Profit(3, 0)=0, Profit(3, 1)=4, Profit(3, 2)=9, Profit(3, 3)=13	13
4	Profit(3, 0)=0, ..., Profit(3, 4)=18	18
5	Profit(3, 0)=0, ..., Profit(3, 5)=20	20

商店 2 (k=2)：
$DP(2, b) = \max_{0 \le x \le b} \{ \text{Profit}(2, x) + DP(3, b-x) \}$
這裡 $\text{Profit}(2, x)$ 是表格中「NTUShop Store 2」的利潤。

b	x	Profit(2, x)	b-x	DP(3, b-x)	Profit(2, x) + DP(3, b-x)	DP(2, b) (max)
0	0	0	0	0	0	0
1	0	0	1	4	4
	1	6	0	0	6	6
2	0	0	2	9	9
	1	6	1	4	10
	2	11	0	0	11	11
3	0	0	3	13	13
	1	6	2	9	15
	2	11	1	4	15
	3	15	0	0	15	15
4	0	0	4	18	18
	1	6	3	13	19
	2	11	2	9	20
	3	15	1	4	19

核心觀念

本題考馬可夫鏈（Markov chain）。狀態代表外送員完成一趟後所在的區域；轉移機率只與目前所在區域有關。轉移矩陣的第 $i$ 列、第 $j$ 欄，表示目前在狀態 $i$ 時，下一趟結束後位於狀態 $j$ 的機率。

以下依序以「市中心、北區、南區」排列狀態，並採用每列總和為 $1$ 的列隨機矩陣。

解題方法與推導

(a) 轉移矩陣

將題目給的各區去向機率依狀態順序填入矩陣：

$$P= \begin{bmatrix} 0.4 & 0.1 & 0.5\\ 0.2 & 0.5 & 0.3\\ 0.3 & 0.3 & 0.4 \end{bmatrix}$$

例如第一列表示外送員目前在市中心時，下一趟後有 $0.4$ 的機率留在市中心、$0.1$ 的機率到北區、$0.5$ 的機率到南區。每列機率總和皆為 $1$。

(b) 從市中心出發，完成第 3 趟後位於市中心的機率

經過 $n$ 趟後的轉移機率由 $P^n$ 表示，因此所求為 $P^3$ 的「市中心列、市中心欄」元素。

先計算 $P^2$ 的市中心列：

$$(0.4,\,0.1,\,0.5)P=(0.33,\,0.24,\,0.43)$$

再與 $P$ 的市中心欄相乘：

$$\Pr(X_3=\text{市中心}\mid X_0=\text{市中心}) =0.33(0.4)+0.24(0.2)+0.43(0.3) =0.309$$

因此，完成第 3 趟後在市中心的機率為 $0.309$，也就是 $30.9\%$。

(c) 一個月的期望總收入

本題未指定月初所在區域；以下依長期穩態區域比例估計。穩態分布 $\boldsymbol{\pi}=(\pi_D,\pi_N,\pi_S)$ 滿足

本題考查無約束非線性規劃的優化方法，包括梯度、Hessian 矩陣的計算、Hessian 矩陣的定性分析，以及求解非線性規劃。

核心觀念：

1. 梯度（Gradient）的定義與計算。
2. Hessian 矩陣（Hessian Matrix）的定義與計算。
3. Hessian 矩陣的定性分析（正定性）。
4. 無約束非線性規劃的最優條件。

解題過程：

給定的非線性規劃函數為：
$f(x_1, x_2) = (x_1 - 1)^2 + x_2^2 + 1$

** (a) What is the gradient of this problem? **

梯度是函數對每個變數的偏導數組成的向量。
$\nabla f(x_1, x_2) = \left[ \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2} \right]^T$

計算偏導數：
$\frac{\partial f}{\partial x_1} = \frac{\partial}{\partial x_1} [(x_1 - 1)^2 + x_2^2 + 1] = 2(x_1 - 1) \cdot 1 + 0 + 0 = 2(x_1 - 1)$
$\frac{\partial f}{\partial x_2} = \frac{\partial}{\partial x_2} [(x_1 - 1)^2 + x_2^2 + 1] = 0 + 2x_2 + 0 = 2x_2$

所以，梯度為：
$\nabla f(x_1, x_2) = \begin{bmatrix} 2(x_1 - 1) \\ 2x_2 \end{bmatrix}$

【答案】
$\nabla f(x_1, x_2) = \begin{bmatrix} 2(x_1 - 1) \\ 2x_2 \end{bmatrix}$

** (b) What is the Hessian matrix of this problem? **

Hessian 矩陣是函數的二階偏導數組成的矩陣。

$$H(x_1, x_2) = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} \end{bmatrix}$$

計算二階偏導數：
$\frac{\partial^2 f}{\partial x_1^2} = \frac{\partial}{\partial x_1} [2(x_1 - 1)] = 2$
$\frac{\partial^2 f}{\partial x_1 \partial x_2} = \frac{\partial}{\partial x_2} [2(x_1 - 1)] = 0$
$\frac{\partial^2 f}{\partial x_2 \partial x_1} = \frac{\partial}{\partial x_1} [2x_2] = 0$
$\frac{\partial^2 f}{\partial x_2^2} = \frac{\partial}{\partial x_2} [2x_2] = 2$