112 年 國立成功大學工業與資訊管理學系研究所甲組《作業研究》

核心觀念

本題是平衡型運輸問題：

• 供給量總和：$10+20+20+10=60$
• 需求量總和：$20+10+10+20=60$

令 $x_{ij}$ 表示每月由工廠 $i$ 運送至零售店 $j$ 的批數，目標函數為

$$\min Z= 500x_{11}+600x_{12}+400x_{13}+200x_{14} +200x_{21}+900x_{22}+100x_{23}+300x_{24}$$ $$+300x_{31}+400x_{32}+200x_{33}+100x_{34} +200x_{41}+100x_{42}+300x_{43}+200x_{44}$$

供給限制：

$$x_{11}+x_{12}+x_{13}+x_{14}=10$$ $$x_{21}+x_{22}+x_{23}+x_{24}=20$$ $$x_{31}+x_{32}+x_{33}+x_{34}=20$$ $$x_{41}+x_{42}+x_{43}+x_{44}=10$$

需求限制：

$$x_{11}+x_{21}+x_{31}+x_{41}=20$$ $$x_{12}+x_{22}+x_{32}+x_{42}=10$$ $$x_{13}+x_{23}+x_{33}+x_{43}=10$$ $$x_{14}+x_{24}+x_{34}+x_{44}=20$$

運輸單純形法使用位勢法。對每個基底格滿足

$$u_i+v_j=c_{ij}$$

非基底格的相對成本為

$$\Delta_{ij}=c_{ij}-(u_i+v_j)$$

對最小化問題：

• 若所有 $\Delta_{ij}\ge 0$，目前解為最適解。
• 若存在 $\Delta_{ij}<0$，選取負值格子進入基底，沿封閉迴路交替加減，改善總成本。

---

解題方法：西北角法求初始基本解

依西北角法配置：

1. $x_{11}=\min(10,20)=10$
2. $x_{21}=\min(20,10)=10$
3. $x_{22}=\min(10,10)=10$
4. $x_{33}=10$
5. $x_{34}=10$
6. $x_{44}=10$

由於在 $x_{22}$ 同時耗盡供給與需求，產生退化基本解，補入一個 $0$ 基底格 $x_{23}=0$。

初始配置如下：

	零售店 1	零售店 2	零售店 3	零售店 4	供給
工廠 1	10	0	0	0	10
工廠 2	10	10	0	0	20
工廠 3	0	0	10	10	20
工廠 4	0	0	0	10	10
需求	20	10	10	20

初始成本：

$$Z_0=10(500)+10(200)+10(900)+10(200)+10(100)+10(200)$$ $$Z_0=21{,}000$$

---

第一次改善

取 $u_1=0$，由基底格求得：

$$v_1=500,\quad u_2=-300,\quad v_2=1200$$ $$v_3=400,\quad u_3=-200,\quad v_4=300,\quad u_4=-100$$

主要負相對成本為：

$$\Delta_{12}=600-(0+1200)=-600$$

因此 $x_{12}$ 進入基底。

封閉迴路為：

$$(1,2)^+ \rightarrow (2,2)^- \rightarrow (2,1)^+ \rightarrow (1,1)^-$$

可調整量：

$$\theta=\min(x_{22},x_{11})=10$$

調整後：

$$x_{12}=10,\quad x_{22}=0,\quad x_{21}=20,\quad x_{11}=0$$

成本改善：

$$\Delta Z=-600(10)=-6{,}000$$

因此：

$$Z_1=21{,}000-6{,}000=15{,}000$$

---

第二次改善

重新計算位勢，得到主要負相對成本：

$$\Delta_{42}=100-(u_4+v_2)=-400$$

因此 $x_{42}$ 進入基底。

封閉迴路為：

$$(4,2)^+ \rightarrow (1,2)^- \rightarrow (1,1)^+ \rightarrow (2,1)^-$$

核心觀念

• 原始問題的標準型：最小化問題 (min‑LP) 以「$Ax=b,\;x\ge 0$」的形式呈現。
• 對偶問題：若原始問題為

$$\min \;c^{\mathsf T}x\qquad \text{s.t. }Ax=b,\;x\ge 0$$

則其對偶為

$$\max \;b^{\mathsf T}y\qquad \text{s.t. }A^{\mathsf T}y\le c,$$

其中 $y$ 為自由變數（可正可負）。

• 對偶可行解的可行性證明 (Farkas Lemma)：若存在一個對偶可行解 $y$ 使得 $b^{\mathsf T}y<0$，則原始問題 不可行。
• 強對偶定理：若原始問題與對偶問題同時有可行解，且至少一者有界，則兩者的最適值相等。若對偶取得有限最適值，則原始必然可行；若對偶無界或不可行，則原始必然不可行。

---

(a) 寫下並求解對偶問題

1. 轉寫原始問題的標準型

原始題目

$$\begin{aligned} \min\quad & Z=x_{1}+2x_{2}\\ \text{s.t.}\quad & x_{1}+2x_{2}=3\\ & x_{1}-1\;\;(\text{此式應為「$\le 0$」或「$\ge 0$」皆可，以下取 $\le 0$})\\ & x_{1}\ge 0,\;x_{2}\ge 0 \end{aligned}$$

把第二條約束寫成不等式形式

$x_{1}\le 1 .$

於是可寫成標準形式

$$\begin{array}{ll} \min & \;c^{\mathsf T}x = [1\;\;2]\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}\\[4pt] \text{s.t.} & \underbrace{\begin{bmatrix}1 & 2\\ 1 & 0\end{bmatrix}}_{A} \begin{bmatrix}x_{1}\\x_{2}\end{bmatrix} = \underbrace{\begin{bmatrix}3\\ 1\end{bmatrix}}_{b},\\[6pt] & x\ge 0 . \end{array}$$

說明：第一列是等式 $x_{1}+2x_{2}=3$，第二列是「$x_{1}\le 1$」寫成等式 $x_{1}+s=1,\;s\ge0$；此處直接以不等式加入對偶式會更簡潔，故在對偶推導時直接使用 $x_{1}\le 1$。

2. 對偶問題的構建

對於最小化問題的標準型，對偶為

$$\begin{aligned} \max\;& b^{\mathsf T}y \\ \text{s.t.}\;& A^{\mathsf T}y \le c . \end{aligned}$$

把 $A$ 與 $c$ 代入：

$$A^{\mathsf T}= \begin{bmatrix} 1 & 1\\ 2 & 0 \end{bmatrix}, \qquad c= \begin{bmatrix} 1\\2 \end{bmatrix}, \qquad b= \begin{bmatrix} 3\\1 \end{bmatrix}.$$

設對偶變數 $y=(y_{1},y_{2})^{\mathsf T}$（兩個自由變數），對偶問題寫成

$$\boxed{ \begin{aligned} \max\;& 3y_{1}+1y_{2}\\ \text{s.t.}&\; \begin{cases} 1\cdot y_{1}+1\cdot y_{2}\ \le\ 1\\[2pt] 2\cdot y_{1}+0\cdot y_{2}\ \le\ 2 \end{cases} \end{aligned}}$$

簡化得到

核心觀念

• 線性規劃（LP）標準型：最大化目標式，約束式全部以「≤」形式加入鬆弛變數成等式，變數皆非負。
• 單形法（Simplex Method）：在相鄰的基本可行解（Basic Feasible Solutions, BFS）之間移動，透過「進基變數」與「出基變數」使目標函數值持續改善，直至所有非基變數的簡化成本（Reduced Cost） ≤ 0（對最大化問題）即為最適。
• 簡化成本：在單形表（Simplex Tableau）中，目標列的係數 $c_j - \mathbf{c}_B^{\mathsf T}B^{-1}A_j$，若全部 ≤ 0，則當前基解已達最適。

---

解題方法

1. 建立標準型
   引入鬆弛變數 $s_1,s_2,s_3\ge 0$，將三個不等式寫成等式：

$$\begin{aligned} x_1 -2x_2 +4x_3 +3x_4 + s_1 &= 20\\ -4x_1 +6x_2 +5x_3 +4x_4 + s_2 &= 40\\ 2x_1 -3x_2 +3x_3 +8x_4 + s_3 &= 50 \end{aligned}$$

目標式仍為

$\max Z = 5x_1 + x_2 + 3x_3 + 4x_4 .$

2. 初始基底
   取鬆弛變數 $s_1,s_2,s_3$ 為基變數，原始變數 $x_1\sim x_4$ 為非基變數。
   初始單形表（$B=I_3$）：

   基本變數	$x_1$	$x_2$	$x_3$	$x_4$	RHS
   $s_1$	1	-2	4	3	20
   $s_2$	-4	6	5	4	40
   $s_3$	2	-3	3	8	50
   Z	-5	-1	-3	-4	0

   目標列係數皆為負，表示仍可提升 $Z$（因為我們使用「$c_j - \mathbf{c}_B^{\mathsf T}B^{-1}A_j$」的形式，負值＝正向進步的指標）。

3. 選擇進基變數
   取最負的係數 $-5$（$x_1$）作為進基變數。

4. 計算比值測試（Ratio Test）
   只考慮 RHS 正且對應係數為正的列：

$$\begin{aligned} \text{第 1 列：}&\; \frac{20}{1}=20\\ \text{第 2 列：}&\; \frac{40}{-4}\;\text{（係數負，忽略）}\\ \text{第 3 列：}&\; \frac{50}{2}=25 \end{aligned}$$

最小正比值為 $20$，故第 1 列（$s_1$）為出基變數。

5. 第一輪樞紐（Pivot）
   以第 1 列第 1 欄的元素 $1$ 為樞紐，將 $s_1$ 換成 $x_1$。
   進行高斯消去：

   • 第 1 列除以 1（已是 1），得到新基 $x_1$ 行。
   • 第 2 列：$R_2 \leftarrow R_2 + 4R_1$ →

$$\begin{aligned} x_1:&\;0,\; 2,\; 21,\; 16,\; 120 \end{aligned}$$

• 第 3 列：$R_3 \leftarrow R_3 - 2R_1$ →

$$\begin{aligned} x_1:&\;0,\; 1,\; -5,\; 2,\; 10 \end{aligned}$$

• 目標列：$R_Z \leftarrow R_Z +5R_1$ →

$$\begin{aligned} x_1:&\;0,\; -11,\; 17,\; 11,\; 100 \end{aligned}$$

更新後的單形表：

基本變數	$x_1$	$x_2$	$x_3$	$x_4$	RHS
$x_1$	1	-2	4	3	20
$s_2$	0	2	21	16	120
$s_3$	0	1	-5	2	10
Z	0	-11	17	11	100

6. 檢查是否仍有正向改進的非基變數
   目標列中仍有負係數 $-11$（對應 $x_2$），故需再迭代。

7. 第二輪進基變數
   選 $x_2$（係數 -11）為進基變數。

8. 第二輪比值測試
   只看係數正的列：

$$\begin{aligned} \text{第 2 列 (}s_2\text{)}:&\; \frac{120}{2}=60\\ \text{第 3 列 (}s_3\text{)}:&\; \frac{10}{1}=10 \end{aligned}$$

最小正比值為 $10$，故 $s_3$ 為出基變數。

9. 第二輪樞紐
   樞紐元素為第 3 列第 2 欄的 $1$。

   • 第 3 列除以 1 → $s_3$ 行成 $x_2$ 行。
   • 第 1 列：$R_1 \leftarrow R_1 +2R_3$ →

$x_1:1,\; x_2:0,\; x_3: -6,\; x_4:7,\; RHS:40$

• 第 2 列：$R_2 \leftarrow R_2 -2R_3$ →

$s_2:0,\; x_2:0,\; x_3:31,\; x_4:12,\; RHS:100$

• 目標列：$R_Z \leftarrow R_Z +11R_3$ →

$Z:0,\; x_2:0,\; x_3: -38,\; x_4: 33,\; RHS:210$

更新後的單形表：

基本變數	$x_1$	$x_2$	$x_3$	$x_4$	RHS
$x_1$	1	0	-6	7	40
$s_2$	0	0	31	12	100

此題為馬可夫鏈（Markov Chain）的應用題，主要考驗對轉移矩陣、多步轉移機率以及初始分佈的理解與計算。

核心觀念：
馬可夫鏈的性質，特別是 $n$ 步轉移機率由 $P^n$ 給出，以及條件機率的計算。

已知資訊：

• 狀態空間 $M = \{1, 2, 3\}$
• 一步轉移矩陣 $P = \begin{bmatrix} 0.3 & 0.3 & 0.4 \\ 0.5 & 0.2 & 0.3 \\ 0.6 & 0.3 & 0.1 \end{bmatrix}$
• 多步轉移矩陣：$P^2, P^3, P^4, P^5$ (已提供)
• 初始分佈：$P(X_0=1) = 0.4$, $P(X_0=2) = 0.3$, $P(X_0=3) = 0.3$

Part (a): $P(X_4 = 3 | X_2 = 2)$

觀念： 馬可夫鏈具有無條件性（Memoryless Property）。過去的狀態不影響未來的轉移機率，只取決於當前狀態。因此，從狀態 $X_2$ 到 $X_4$ 的機率，只取決於從 $X_2$ 開始的後續轉移。

計算：
我們需要計算從狀態 2 到狀態 3 的 2 步轉移機率。這由 $P^2$ 矩陣的第 2 行第 3 列元素給出。
觀察提供的 $P^2$ 矩陣：
$P^2 = \begin{bmatrix} 0.48 & 0.27 & 0.25 \\ 0.43 & 0.28 & 0.29 \\ 0.39 & 0.27 & 0.34 \end{bmatrix}$
$P(X_4 = 3 | X_2 = 2)$ 就是 $P^2$ 中第 2 行第 3 列的元素。
$P(X_4 = 3 | X_2 = 2) = (P^2)_{2,3} = 0.29$。

【答案】 0.29

Part (b): $P(X_4=1 | X_0 = 1, X_2 = 3)$

觀念： 同樣利用馬可夫鏈的無條件性。給定 $X_0=1$ 和 $X_2=3$ 的資訊，我們關心的是從 $X_2=3$ 開始，經過 2 步轉移後到達 $X_4=1$ 的機率。過去的資訊 $X_0=1$ 在已知 $X_2=3$ 後，對 $X_4$ 的預測沒有額外幫助。

計算：
我們需要計算從狀態 3 到狀態 1 的 2 步轉移機率。這由 $P^2$ 矩陣的第 3 行第 1 列元素給出。
觀察提供的 $P^2$ 矩陣：
$P^2 = \begin{bmatrix} 0.48 & 0.27 & 0.25 \\ 0.43 & 0.28 & 0.29 \\ 0.39 & 0.27 & 0.34 \end{bmatrix}$
$P(X_4=1 | X_2 = 3)$ 就是 $P^2$ 中第 3 行第 1 列的元素。
$P(X_4=1 | X_2 = 3) = (P^2)_{3,1} = 0.39$。
由於馬可夫鏈的無條件性， $P(X_4=1 | X_0 = 1, X_2 = 3) = P(X_4=1 | X_2 = 3)$。

答案： 0.39

Part (c): For any taxi, what is the probability that its fourth rider takes it to region 3? ($P(X_4 = 3)$)

觀念： 這個機率取決於出租車的初始位置分佈。我們需要計算邊緣機率 $P(X_4=3)$。
$P(X_4=3) = \sum_{i=1}^{3} P(X_4=3 | X_0=i) P(X_0=i)$
其中 $P(X_0=i)$ 是初始分佈， $P(X_4=3 | X_0=i)$ 是從狀態 $i$ 出發，經過 4 步轉移到達狀態 3 的機率。

計算：
初始分佈向量 $\pi_0 = [0.4, 0.3, 0.3]$ (對應於狀態 1, 2, 3)。
我們需要計算 $P^4$ 矩陣。觀察提供的 $P^4$ 矩陣：
$P^4 = \begin{bmatrix} 0.444 & 0.273 & 0.283 \\ 0.44 & 0.273 & 0.287 \\ 0.436 & 0.273 & 0.291 \end{bmatrix}$
$P(X_4=3 | X_0=1) = (P^4)_{1,3} = 0.283$
$P(X_4=3 | X_0=2) = (P^4)_{2,3} = 0.287$
$P(X_4=3 | X_0=3) = (P^4)_{3,3} = 0.291$

$P(X_4=3) = P(X_4=3 | X_0=1) P(X_0=1) + P(X_4=3 | X_0=2) P(X_0=2) + P(X_4=3 | X_0=3) P(X_0=3)$
$P(X_4=3) = (0.283)(0.4) + (0.287)(0.3) + (0.291)(0.3)$
$P(X_4=3) = 0.1132 + 0.0861 + 0.0873$
$P(X_4=3) = 0.2866$

答案： 0.2866

Part (d): $P(X_3 = 3, X_4 = 1 | X_0 = 2)$

觀念： 這是聯合條件機率。給定初始狀態 $X_0=2$，我們需要計算在第 3 步到達狀態 3 且在第 4 步到達狀態 1 的機率。
$P(X_3 = 3, X_4 = 1 | X_0 = 2) = P(X_4 = 1 | X_3 = 3, X_0 = 2) P(X_3 = 3 | X_0 = 2)$
利用無條件性，$P(X_4 = 1 | X_3 = 3, X_0 = 2) = P(X_4 = 1 | X_3 = 3)$。

核心觀念

• (q,Q) 庫存政策可用 持續時間馬可夫鏈 (CTMC) 來描述：狀態為「手頭機器數 + 是否有未到貨的訂單」；所有事件（需求、交貨）皆為指數分布且相互獨立。
• 先到達 0（缺貨）或 3（最大庫存）之間的先後次序，可用 嵌入離散鏈的先到達概率 來計算。
• 長期平均庫存 由 平衡分佈（stationary distribution）求得：πQ = π 其中 Q 為速率矩陣。

---

a) CTMC 建模

變數	說明
$X(t)$	店內即時在手洗衣機數（不含已下單尚未到貨之機器）
訂單狀態	因 Q=1，若 $X(t)\le q(=2)$ 必有 一筆未到貨的訂單。因此只要 $X(t)=0,1,2$ 時即表示「有訂單在途」；$X(t)=3$ 時表示「目前無未到貨訂單」。

狀態空間

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

• 0、1、2：手頭機器分別為 0、1、2，且 已下單（尚未到貨）。
• 3：手頭機器為 3，沒有待交付訂單。

速率 (Rate)

• 需求到達率 $\lambda =2$ 件/天（指數分布）。
• 訂單送達率 $\mu =\frac{1}{2}$ 件/天（平均 2 天）。

從 → 到	速率
3 → 2	$\lambda$（需求）
2 → 1	$\lambda$
2 → 3	$\mu$（交貨）
1 → 0	$\lambda$
1 → 2	$\mu$
0 → 1	$\mu$
0 → 0	（需求失效）

轉移率圖（文字說明）

• 3 用唯一的向左弧（需求）以速率 2 轉至 2。
• 2 有兩條出弧：向左（需求）速率 2 到 1；向右（交貨）速率 0.5 到 3。
• 1 同理：向左速率 2 到 0；向右速率 0.5 到 2。
• 0 只有向右弧（交貨）速率 0.5 到 1，需求時因無庫存直接遺失，狀態保持不變。

---

b) 「從兩台開始」先缺貨再達到最高庫存的機率

設
$p_i =P\{\text{先到達 0 再到 3}\mid X(0)=i\}$.
則邊界條件

$p_0 =1,\qquad p_3 =0$

利用 嵌入離散鏈，在每一次跳躍時的轉移機率為速率比：

• 從 2：$P_{2\to1}= \frac{\lambda}{\lambda+\mu}= \frac{2}{2.5}=0.8$，
  $P_{2\to3}= \frac{\mu}{\lambda+\mu}=0.2$。
• 從 1：$P_{1\to0}=0.8$，$P_{1\to2}=0.2$。

寫出一次步驟的期望方程式

$$\begin{aligned} p_2 &=0.8\,p_1+0.2\,p_3,\\ p_1 &=0.8\,p_0+0.2\,p_2 . \end{aligned}$$

代入 $p_0=1,\;p_3=0$：

$$\begin{aligned} p_2 &=0.8\,p_1,\\ p_1 &=0.8+0.2\,p_2 . \end{aligned}$$

解得

$$p_1=\frac{20}{21}\approx0.95238,\qquad p_2 =0.8\,p_1 = \frac{16}{21}\approx0.76190 .$$

答案