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

核心觀念

本題整合線性規劃的幾項核心技巧：

• 兩階段法 Phase-I：先加入人工變數，求得原問題的可行基底解。
• 單純形法 Simplex Method：由可行基底解判斷是否仍有可改善的非基底變數。
• 對偶問題 Dual Problem：依照原問題的最小化形式、等式限制與非負變數建立對偶。
• 對偶單純形法 Dual Simplex Method：由「對偶可行但原始不可行」的基底解出發。
• 目標係數允許範圍：保持目前基底解最適，必須使所有非基底變數的 reduced cost 維持最適條件。

---

(a) 使用 Phase-I 求初始可行解

原問題第一條限制式的右側為負，先將其乘以 $-1$：

$$2x_1+x_2-x_3=6$$

加入人工變數 $a_1$：

$$2x_1+x_2-x_3+a_1=6$$

第二條限制式為：

$$x_1+2x_2+x_4=6$$

Phase-I 的目標為最小化人工變數：

$$\min w=a_1$$

令 $a_1,x_4$ 為基底變數，其他變數設為 $0$：

$$a_1=6,\qquad x_4=6$$

此時 $x_1=x_2=x_3=0$，故初始 Phase-I 解為：

$$(x_1,x_2,x_3,x_4,a_1)=(0,0,0,0,6)$$

由第一式可得：

$$a_1=6-2x_1-x_2+x_3$$

當 $x_1$ 進入基底時，$a_1$ 會先降至 $0$；由第二式可知 $x_4$ 尚未先變成負值，因此令 $a_1$ 離開基底。

由

$$2x_1+x_2-x_3=6$$

解出：

$$x_1=3-\frac{1}{2}x_2+\frac{1}{2}x_3$$

再代入第二式：

$$x_4=6-x_1-2x_2 =3-\frac{3}{2}x_2-\frac{1}{2}x_3$$

令非基底變數 $x_2=x_3=0$，得到：

$$x_1=3,\qquad x_4=3$$

且人工變數 $a_1=0$，因此原問題的一組初始可行解為：

$$\boxed{(x_1,x_2,x_3,x_4)=(3,0,0,3)}$$

---

(b) 使用單純形法求最適解

當 $c_1=1$ 時，目標函數為：

$$\min z=x_1+x_2$$

沿用 (a) 所得到的基底 $x_1,x_4$，將限制式寫成字典形式：

$$x_1=3-\frac{1}{2}x_2+\frac{1}{2}x_3$$ $$x_4=3-\frac{3}{2}x_2-\frac{1}{2}x_3$$

代入目標函數：

$$\begin{aligned} z &=x_1+x_2\\ &=3-\frac{1}{2}x_2+\frac{1}{2}x_3+x_2\\ &=3+\frac{1}{2}x_2+\frac{1}{2}x_3 \end{aligned}$$

由於 $x_2,x_3\ge 0$，且目標函數中兩者的係數均為正值，因此增加任一非基底變數都會使 $z$ 增加。最小值在：

$$x_2=x_3=0$$

時取得。

因此：

$$x_1=3,\qquad x_4=3$$

最適解為：

$$\boxed{(x_1,x_2,x_3,x_4)=(3,0,0,3)}$$

最適目標值為：

$$\boxed{z^*=3}$$

---

(c) 建立對偶問題

原問題為：

$$\begin{aligned} \min\quad & c_1x_1+x_2\\ \text{s.t.}\quad &-2x_1-x_2+x_3=-6\\ &x_1+2x_2+x_4=6\\ &x_1,x_2,x_3,x_4\ge 0 \end{aligned}$$

兩條限制式都是等式，因此先令對偶變數 $y_1,y_2$ 不受符號限制。

因為原問題是最小化問題，且所有原始變數均為非負，因此對偶限制式為「小於等於」。

對偶目標函數為：

$$\max\ -6y_1+6y_2$$

逐一依照原始變數建立對偶限制式：

• $x_1$ 對應第一欄 $(-2,1)$：

$$-2y_1+y_2\le c_1$$

• $x_2$ 對應第二欄 $(-1,2)$：

$$-y_1+2y_2\le 1$$

• $x_3$ 對應第三欄 $(1,0)$，其成本為 $0$：

$$y_1\le 0$$

• $x_4$ 對應第四欄 $(0,1)$，其成本為 $0$：

$$y_2\le 0$$

故對偶問題為：

$$\boxed{ \begin{aligned} \max\quad & -6y_1+6y_2\\ \text{s.t.}\quad &-2y_1+y_2\le c_1\\ &-y_1+2y_2\le 1\\ &y_1\le 0\\ &y_2\le 0 \end{aligned} }$$

---

(d) $c_1=1$ 時對偶問題的最適解

由 (b) 的原問題最適解：

$$(x_1,x_2,x_3,x_4)=(3,0,0,3)$$

使用互補鬆弛條件。

因為 $x_4=3>0$，其對偶限制式必須為等式：

$$y_2=0$$

因為 $x_1=3>0$，其對偶限制式也必須為等式：

$$-2y_1+y_2=1$$

代入 $y_2=0$：

$$-2y_1=1$$

因此：

$$y_1=-\frac{1}{2}$$

對偶最適解為：

$$\boxed{(y_1,y_2)=\left(-\frac{1}{2},0\right)}$$

對偶目標值為：

核心觀念

本題考查動態規劃的階段、狀態與遞迴關係。將四種餐點依序分配菜色，每種至少選一道，且各種類的營養分數依所選數量查表。目標是使四種類的營養分數總和最大。

設 $f_i(x)$ 為第 $i$ 種餐點選 $x$ 道時的營養分數，則總分為四種餐點分數的加總。

(a) 階段與狀態

• 階段：每個階段處理一種餐點，依序為豬肉、牛肉、蔬菜、穀類。
• 狀態：已分配給目前及先前餐點的菜色總數。
• 決策：在目前階段所處理的餐點選幾道；每種至少一道。

令 $D_i(t)$ 表示前 $i$ 種餐點共分配 $t$ 道菜時可得到的最高營養分數。初始條件為：

$$D_1(t)=f_1(t), \qquad t\ge 1$$

對 $i\ge 2$，遞迴式為：

$$D_i(t)=\max_{1\le x\le t-(i-1)} \left\{D_{i-1}(t-x)+f_i(x)\right\}$$

其中 $x$ 是第 $i$ 種餐點的菜數；上限 $t-(i-1)$ 確保前 $i-1$ 種餐點各至少有一道。最後求 $D_4(10)$。

(b) 動態規劃求解

先合併豬肉與牛肉，計算 $D_2(t)$。表中的配置欄列出達到最高分的一組豬肉、牛肉菜數。

總菜數 $t$	$D_2(t)$	最佳配置（豬肉、牛肉）
2	45	$(1,1)$
3	95	$(1,2)$
4	120	$(2,2)$
5	140	$(2,3)$
6	150	$(2,4)$
7	170	$(4,3)$
8	190	$(5,3)$
9	200	$(5,4)$

例如，兩種餐點合計選 $5$ 道時：

$$D_2(5)=\max\{25+100,\ 50+90,\ 60+70,\ 80+20\}=140$$

此時豬肉選 $2$ 道、牛肉選 $3$ 道。

接著加入蔬菜，依遞迴式計算 $D_3(t)$：

本題考驗凸優化理論，包含凸函數判定、KKT 条件、约束最优化中的正規性条件 (LICQ) 以及寻找全局最优解。

(a) 證明 $f(x, y)$ 是凸函數:
一個二次函數 $f(\mathbf{x}) = \mathbf{x}^T Q \mathbf{x} + L^T \mathbf{x} + c$ 是凸函數，若且唯若其 Hessian 矩陣 $Q$ 是半正定的 (positive semi-definite)。
對於 $f(x, y) = x^2 + 2xy + 2y^2 + 4x + 6y + 5$，我們可以寫成向量形式。
$\mathbf{x} = \begin{pmatrix} x \\ y \end{pmatrix}$
$f(x, y) = \begin{pmatrix} x & y \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} + \begin{pmatrix} 4 & 6 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} + 5$
Hessian 矩陣為 $H = \begin{pmatrix} \frac{\partial^2 f}{\partial x^2} & \frac{\partial^2 f}{\partial x \partial y} \\ \frac{\partial^2 f}{\partial y \partial x} & \frac{\partial^2 f}{\partial y^2} \end{pmatrix}$。
$\frac{\partial f}{\partial x} = 2x + 2y + 4$
$\frac{\partial f}{\partial y} = 2x + 4y + 6$
$\frac{\partial^2 f}{\partial x^2} = 2$
$\frac{\partial^2 f}{\partial y^2} = 4$
$\frac{\partial^2 f}{\partial x \partial y} = 2$
$\frac{\partial^2 f}{\partial y \partial x} = 2$
所以 Hessian 矩陣為 $H = \begin{pmatrix} 2 & 2 \\ 2 & 4 \end{pmatrix}$。
要判斷 $H$ 是否為半正定，我們檢查其特徵值或主子式。
主子式：
$D_1 = 2 > 0$
$D_2 = \det(H) = (2)(4) - (2)(2) = 8 - 4 = 4 > 0$
由於所有主子式都大於零，Hessian 矩陣 $H$ 是正定的 (positive definite)。
正定矩陣意味著函數 $f(x, y)$ 是嚴格凸函數 (strictly convex)。嚴格凸函數也是凸函數。
因此，$f(x, y)$ 是凸函數。

(b) KKT 条件:
KKT 条件是約束最优化问题寻找最优解的必要条件（对于凸问题，也是充分条件）。
原问题是：
$\min f(x, y) = x^2 + 2xy + 2y^2 + 4x + 6y + 5$
$\text{s.t. } g_1(x,y) = 3 - x - y \le 0 \implies x + y \ge 3$
$g_2(x,y) = -y \le 0 \implies y \ge 0$
引入拉格朗日乘子 $\mu_1 \ge 0$ 和 $\mu_2 \ge 0$。
KKT 条件包括：

1. 梯度条件 (Stationarity): $\nabla f(x,y) + \mu_1 \nabla g_1(x,y) + \mu_2 \nabla g_2(x,y) = \mathbf{0}$
   $\nabla f = \begin{pmatrix} 2x + 2y + 4 \\ 2x + 4y + 6 \end{pmatrix}$
   $\nabla g_1 = \begin{pmatrix} -1 \\ -1 \end{pmatrix}$ (對應 $g_1 = 3 - x - y$)
   $\nabla g_2 = \begin{pmatrix} 0 \\ -1 \end{pmatrix}$ (對應 $g_2 = -y$)
   所以，
   $2x + 2y + 4 - \mu_1(1) - \mu_2(0) = 0 \implies 2x + 2y + 4 - \mu_1 = 0$
   $2x + 4y + 6 - \mu_1(1) - \mu_2(1) = 0 \implies 2x + 4y + 6 - \mu_1 - \mu_2 = 0$

2. 可行性条件 (Primal Feasibility):
   $x + y \ge 3$
   $y \ge 0$

3. 对偶可行性条件 (Dual Feasibility):
   $\mu_1 \ge 0$
   $\mu_2 \ge 0$

4. 互补松弛性条件 (Complementary Slackness):
   $\mu_1 g_1(x,y) = 0 \implies \mu_1 (3 - x - y) = 0$
   $\mu_2 g_2(x,y) = 0 \implies \mu_2 (-y) = 0$

(c) 在 $g_1$ 和 $g_2$ 都不活跃 (inactive) 时寻找可行解:
若 $g_1$ 和 $g_2$ 都不活跃，则意味着：
$g_1(x,y) < 0 \implies 3 - x - y < 0 \implies x + y > 3$
$g_2(x,y) < 0 \implies -y < 0 \implies y > 0$
并且，根据互补松弛性条件：
$\mu_1 g_1(x,y) = 0 \implies \mu_1 = 0$ (因为 $g_1 < 0$)
$\mu_2 g_2(x,y) = 0 \implies \mu_2 = 0$ (因为 $g_2 < 0$)

此时 KKT 条件简化为：

1. 梯度条件:
   $2x + 2y + 4 - 0 = 0 \implies 2x + 2y = -4 \implies x + y = -2$

核心觀念

本題考察有限狀態離散時間馬可夫鏈，包括：

• 狀態空間的建立
• 轉移機率矩陣
• 穩態機率與流量平衡
• 穩態下的期望值
• 首達時間的期望值

令狀態 $X_t$ 表示第 $t$ 個時間槽結束時停放在站上的腳踏車數量。由於最多只有 $2$ 個車位，因此狀態只可能為 $0,1,2$。

其中：

• 歸還腳踏車的機率為 $p=0.4$
• 租借腳踏車的機率為 $q=0.6$
• $p+q=1$

在狀態 $0$ 時，雖然租借事件仍可能發生，但因為沒有腳踏車可租，系統仍停留在狀態 $0$。在狀態 $2$ 時，雖然歸還事件仍可能發生，但因為車位已滿，系統仍停留在狀態 $2$。

---

(a) 狀態空間與轉移機率矩陣

狀態空間

$$\mathcal{S}=\{0,1,2\}$$

各狀態的轉移

由狀態 $0$：

• 歸還一輛：$0\to 1$，機率 $p=0.4$
• 租借事件但無車可租：$0\to 0$，機率 $q=0.6$

由狀態 $1$：

• 歸還一輛：$1\to 2$，機率 $p=0.4$
• 租借一輛：$1\to 0$，機率 $q=0.6$

由狀態 $2$：

• 歸還事件但無空位：$2\to 2$，機率 $p=0.4$
• 租借一輛：$2\to 1$，機率 $q=0.6$

依照狀態排列順序 $(0,1,2)$，轉移機率矩陣為

$$P= \begin{bmatrix} q & p & 0\\ q & 0 & p\\ 0 & q & p \end{bmatrix} = \begin{bmatrix} 0.6 & 0.4 & 0\\ 0.6 & 0 & 0.4\\ 0 & 0.6 & 0.4 \end{bmatrix}.$$

每一列的總和皆為 $1$，符合轉移機率矩陣的要求。

---

(b) 租借學生遇到兩個車位皆空的機率

設穩態機率為

$$\boldsymbol{\pi}=(\pi_0,\pi_1,\pi_2),$$

其中 $\pi_i$ 表示長期而言系統處於狀態 $i$ 的機率。

此題是出生—死亡型馬可夫鏈，利用相鄰狀態的流量平衡：

$$\pi_0p=\pi_1q.$$

因此

$$\pi_1=\frac{p}{q}\pi_0 =\frac{0.4}{0.6}\pi_0 =\frac{2}{3}\pi_0.$$

同理，

$$\pi_1p=\pi_2q,$$

所以

$$\pi_2=\frac{p}{q}\pi_1 =\frac{2}{3}\pi_1 =\frac{4}{9}\pi_0.$$

再利用機率總和為 $1$：

$$\pi_0+\pi_1+\pi_2=1.$$

代入上式：

$$\pi_0+\frac{2}{3}\pi_0+\frac{4}{9}\pi_0=1.$$ $$\frac{19}{9}\pi_0=1,$$

因此

$$\pi_0=\frac{9}{19}.$$

當學生到站租借時，若系統處於穩態，遇到兩個車位皆空的機率就是處於狀態 $0$ 的穩態機率：

$$\boxed{\pi_0=\frac{9}{19}\approx 0.4737}.$$

因此，機率約為 $47.37\%$。

---

(c) 學生預期看到的腳踏車數量

穩態下，腳踏車數量的期望值為

$$E[X]=\sum_{i=0}^{2}i\pi_i.$$

由前面的計算，

$$\pi_0=\frac{9}{19},\qquad \pi_1=\frac{6}{19},\qquad \pi_2=\frac{4}{19}.$$

因此