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

核心觀念

$x_3,x_4,x_5$ 為三個限制式的剩餘變數：

$$x_1+x_3=c$$ $$x_2+x_4=6$$ $$6x_1+dx_2+x_5=36$$

最終單純形表中，基底變數為 $x_3,x_2,x_1$，非基底變數為 $x_4,x_5$。令非基底變數 $x_4=x_5=0$，即可由 RHS 求得目前基底解。

解題方法

由表格各列可寫成：

$$x_3+\frac23x_4-\frac16x_5=3$$ $$x_2+x_4=6$$ $$x_1-\frac23x_4+\frac16x_5=2$$

因此令 $x_4=x_5=0$，得到：

$$x_3=3,\qquad x_2=6,\qquad x_1=2$$

求 $c$

由第一個限制式：

$$x_1+x_3=c$$

代入 $x_1=2,\ x_3=3$：

$$c=2+3=5$$

求 $d$

由第三個限制式：

$$6x_1+dx_2+x_5=36$$

代入 $x_1=2,\ x_2=6,\ x_5=0$：

$$6(2)+d(6)=36$$ $$12+6d=36$$ $$d=4$$

求 $a,b$

將表格中的 $x_1,x_2$ 表示式寫出：

$$x_1=2+\frac23x_4-\frac16x_5$$ $$x_2=6-x_4$$

代入目標函數：

核心觀念

本題考查決策分析中的四種方法：

• Maximin payoff：先找每個方案的最低報酬，再選其中最高者。
  $\max_i\{\min_j P_{ij}\}$
• Minimax Regret：先計算各狀態下的遺憾值，再選最大遺憾最小的方案。
  $R_{ij}=\text{該狀態最高報酬}-P_{ij}$
• Bayes’ decision rule：以先驗機率加權計算期望報酬，選擇期望值最高者。
  $EMV_i=\sum_j p_jP_{ij}$
• Expected Value of Perfect Information（EVPI）：
  $EVPI=EV_{\text{with PI}}-\max(EMV_i)$

---

(i) Maximin payoff criterion

各方案的最低報酬為：

方案	最低報酬
Alternative 1	$-50$
Alternative 2	$-20$
Alternative 3	$-40$
Alternative 4	$-60$

取最低報酬中的最大值：

$\max\{-50,-20,-40,-60\}=-20$

因此應選擇 Alternative 2。

---

(ii) Minimax Regret criterion

各狀態的最高報酬為：

• State 1：$-20$
• State 2：$70$
• State 3：$100$
• State 4：$160$

因此遺憾值表為：

方案	State 1	State 2	State 3	State 4	最大遺憾
Alternative 1	$30$	$20$	$10$	$35$	$35$
Alternative 2	$0$	$35$	$20$	$0$	$35$
Alternative 3	$20$	$0$	$0$	$50$	$50$
Alternative 4	$40$	$50$	$15$	$20$	$50$

最小的最大遺憾為：

$\min\{35,35,50,50\}=35$

所以 Alternative 1 與 Alternative 2 並列為最佳方案。

---

(iii) Bayes’ decision rule

先驗機率為：

$P(S_1,S_2,S_3,S_4)=(0.1,0.5,0.2,0.2)$

各方案的期望報酬如下：

$$EMV_1=(-50)(0.1)+(50)(0.5)+(90)(0.2)+(125)(0.2)=63$$ $$EMV_2=(-20)(0.1)+(35)(0.5)+(80)(0.2)+(160)(0.2)=63.5$$ $$EMV_3=(-40)(0.1)+(70)(0.5)+(100)(0.2)+(110)(0.2)=73$$ $$EMV_4=(-60)(0.1)+(20)(0.5)+(85)(0.2)+(140)(0.2)=49$$

比較：

$73>63.5>63>49$

因此應選擇 Alternative 3。

---

(iv) 完全資訊的最高願付價格

若擁有完全資訊，每一個狀態都可選擇該狀態下報酬最高的方案：

本題考查非線性規劃中的拉格朗日乘數法（Lagrange Multiplier Method）與 KKT (Karush-Kuhn-Tucker) 條件。

核心觀念：
對於一個最小化問題：
Minimize $f(x)$
subject to $g_i(x) \le 0$ for $i=1, \dots, m$.

拉格朗日函數定義為：$L(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i(x)$，其中 $\lambda_i \ge 0$。

KKT 條件是一組必要條件，對於可微函數，若點 $x^*$ 是最優解，則存在 $\lambda^* \ge 0$ 使得以下條件成立：

1. Stationarity (平穩性): $\nabla_x L(x^*, \lambda^*) = \nabla f(x^*) + \sum_{i=1}^m \lambda_i^* \nabla g_i(x^*) = 0$
2. Primal Feasibility (原始可行性): $g_i(x^*) \le 0$ for all $i$.
3. Dual Feasibility (對偶可行性): $\lambda_i^* \ge 0$ for all $i$.
4. Complementary Slackness (互補鬆弛性): $\lambda_i^* g_i(x^*) = 0$ for all $i$.

解題步驟：

1. 寫下拉格朗日函數 (Lagrange Function):
給定目標函數 $f(x_1, x_2) = x_1^2 + x_2^2 - 4x_1 - 4x_2 + 3$
以及約束條件 $g_1(x_1, x_2) = 2x_1^2 + 2x_2^2 - 12 \le 0$.
引入拉格朗日乘數 $\lambda_1 \ge 0$.

拉格朗日函數 $L(x_1, x_2, \lambda_1)$ 為：
$L(x_1, x_2, \lambda_1) = f(x_1, x_2) + \lambda_1 g_1(x_1, x_2)$
$L(x_1, x_2, \lambda_1) = (x_1^2 + x_2^2 - 4x_1 - 4x_2 + 3) + \lambda_1 (2x_1^2 + 2x_2^2 - 12)$

【答案】
$L(x_1, x_2, \lambda_1) = x_1^2 + x_2^2 - 4x_1 - 4x_2 + 3 + \lambda_1(2x_1^2 + 2x_2^2 - 12)$

2. 寫下 KKT 條件 (KKT Conditions):
我們需要計算梯度。
$\nabla f(x_1, x_2) = (\frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}) = (2x_1 - 4, 2x_2 - 4)$
$\nabla g_1(x_1, x_2) = (\frac{\partial g_1}{\partial x_1}, \frac{\partial g_1}{\partial x_2}) = (4x_1, 4x_2)$

KKT 條件如下：

• Stationarity (平穩性): $\nabla f(x) + \lambda_1 \nabla g_1(x) = 0$
  $\frac{\partial L}{\partial x_1} = (2x_1 - 4) + \lambda_1 (4x_1) = 0 \implies 2x_1 - 4 + 4\lambda_1 x_1 = 0$ (1)
  $\frac{\partial L}{\partial x_2} = (2x_2 - 4) + \lambda_1 (4x_2) = 0 \implies 2x_2 - 4 + 4\lambda_1 x_2 = 0$ (2)
  （注意：由於目標函數和約束條件的對稱性，可以預期 $x_1=x_2$ 的情況會比較簡單，或者 $x_1, x_2$ 的解會是對稱的。）

• Primal Feasibility (原始可行性): $g_1(x_1, x_2) \le 0$
  $2x_1^2 + 2x_2^2 - 12 \le 0$ (3)

• Dual Feasibility (對偶可行性): $\lambda_1 \ge 0$ (4)

• Complementary Slackness (互補鬆弛性): $\lambda_1 g_1(x_1, x_2) = 0$
  $\lambda_1 (2x_1^2 + 2x_2^2 - 12) = 0$ (5)

【答案】
KKT 條件為：

1. $2x_1 - 4 + 4\lambda_1 x_1 = 0$
2. $2x_2 - 4 + 4\lambda_1 x_2 = 0$
3. $2x_1^2 + 2x_2^2 - 12 \le 0$
4. $\lambda_1 \ge 0$
5. $\lambda_1 (2x_1^2 + 2x_2^2 - 12) = 0$

3. 尋找滿足 KKT 條件的點 (Find the points satisfying these conditions):
我們需要考慮兩種互補鬆弛性的情況：
Case 1: $\lambda_1 = 0$ (約束條件是鬆弛的)
Case 2: $2x_1^2 + 2x_2^2 - 12 = 0$ (約束條件是主動的)

Case 1: $\lambda_1 = 0$
將 $\lambda_1 = 0$ 代入 Stationarity 條件 (1) 和 (2)：
(1) $2x_1 - 4 + 4(0)x_1 = 0 \implies 2x_1 - 4 = 0 \implies x_1 = 2$.
(2) $2x_2 - 4 + 4(0)x_2 = 0 \implies 2x_2 - 4 = 0 \implies x_2 = 2$.

現在檢查 Primal Feasibility (3):
$2x_1^2 + 2x_2^2 - 12 \le 0$
$2(2)^2 + 2(2)^2 - 12 = 2(4) + 2(4) - 12 = 8 + 8 - 12 = 16 - 12 = 4$.
$4 \le 0$ 是 False。
因此，點 $(x_1, x_2) = (2, 2)$ 不滿足原始可行性條件。
這意味著最優解一定發生在約束邊界上，即 Case 2。

Case 2: $2x_1^2 + 2x_2^2 - 12 = 0$
此時約束條件是主動的，即 $2x_1^2 + 2x_2^2 = 12$, 或 $x_1^2 + x_2^2 = 6$.
從 Stationarity 條件 (1) 和 (2)（假設 $x_1, x_2 \ne 0$）：
(1) $2x_1 - 4 = -4\lambda_1 x_1 \implies \frac{2x_1 - 4}{4x_1} = -\lambda_1 \implies \frac{x_1 - 2}{2x_1} = -\lambda_1$

核心觀念

• 本題屬於排隊論的 M/M/1/1 (Erlang B) 系統：
  • 到達過程為泊松過程，率 $\lambda =1$ 人/小時。
  • 服務時間為指數分布，平均 $30$ 分鐘（$0.5$ 小時），服務率 $\mu =\frac{1}{0.5}=2$ 人/小時。
  • 系統容量上限為 $1$（只有理髮師在服務，沒有等候排隊），若理髮師忙碌則不允許新客人進入，屬於 「阻斷」 (loss) 系統。
• 重要指標
  • 系統利用率 $\rho =\frac{\lambda}{\mu}=0.5$。
  • 稱為「阻斷機率」$P_{\text{block}}$，即系統已滿（有客人在服務）時的機率。
  • 平衡分布 $P_n$（系統中 $n$ 位客人的機率）在 M/M/1/1 中僅有 $n=0,1$ 兩個可能。

---

解題方法

1. 求平衡分布
   M/M/1/1 的平衡方程式為

$$\lambda P_0 = \mu P_1 , \qquad P_0+P_1=1 .$$

代入 $\lambda=1,\;\mu=2$，得

$P_1 = \frac{\lambda}{\mu}P_0 = \rho P_0 .$

結合正規化條件

$$P_0+ \rho P_0 =1 \;\Longrightarrow\; P_0 =\frac{1}{1+\rho},\quad P_1 =\frac{\rho}{1+\rho}.$$

其中 $\rho=0.5$，故

$$P_0=\frac{1}{1.5}= \frac23 ,\qquad P_1=\frac{0.5}{1.5}= \frac13 .$$

2. 期望系統內客量 $L$

$L = \sum_{n=0}^{1} n P_n = 0\cdot P_0 + 1\cdot P_1 = P_1 = \frac13 .$

3. 客人平均逗留時間 $W$
   只要客人能進入系統，就立即接受服務，無等待時間。
   有效到達率（實際接受服務的到達率）

本題考查存貨管理中的經濟訂購量（Economic Order Quantity, EOQ）模型。

核心觀念：
EOQ 模型是針對確定性需求、無缺貨情況下的訂購決策模型。其目標是最小化總存貨成本，總成本包含訂購成本、持有成本（及商品成本，但常被獨立討論或忽略）。

參數定義：

• $d$: 需求率 (demand rate) - 單位時間內的需求量。
• $k$: 每次訂購成本 (setup cost per order)。
• $c$: 每單位商品成本 (unit cost)。
• $h$: 每單位商品每單位時間的持有成本 (holding cost per unit per unit time)。
• $Q$: 訂購量 (order quantity)。

假設：

• 需求率 $d$ 為常數且確定。
• 訂購提前期（lead time）為常數。
• 無缺貨（no stockout）。
• 訂購成本 $k$ 為固定值。
• 持有成本 $h$ 與持有量成正比。

(a) Formulate the total cost TC per unit time and find the optimal $Q^*$ (EOQ).
假設我們以固定週期或固定時間間隔來訂購，或者當存貨降至零時就訂購。
為了求出單位時間（例如一年）的總成本 TC，我們需要考慮：

1. 商品成本 (Annual Purchase Cost): 每年總需求量 $\times$ 每單位成本。
   假設分析的時間單位為一年。則年需求量為 $d \times 1$ (如果 $d$ 的單位是每年)。
   若 $d$ 是單位時間的需求率，則年需求量為 $D = d \times T_{year}$。
   題目中 $d$ 是「demand per unit time」，假設我們考慮的時間單位是 1，則總需求量為 $d$。
   年度商品成本 = $c \times d$。
   然而，在 EOQ 的標準推導中，通常是考慮「平均持有成本」和「總訂購成本」。商品成本 $c \times d$ 是一個常數，不會影響 $Q^*$ 的決定。

2. 訂購成本 (Annual Ordering Cost):
   每年訂購次數 = 總需求量 / 每次訂購量 = $d / Q$。
   每年訂購成本 = (每年訂購次數) $\times$ (每次訂購成本) = $(d/Q) \times k$.

3. 持有成本 (Annual Holding Cost):
   平均庫存量 = $Q / 2$ (假設存貨從 $Q$ 均勻下降至 0)。
   每年持有成本 = (平均庫存量) $\times$ (每單位持有成本率) = $(Q/2) \times h$.

總成本 TC (不含商品成本) per unit time:
$TC(Q) = \frac{d}{Q}k + \frac{Q}{2}h$

為了找到最佳訂購量 $Q^*$，我們對 $TC(Q)$ 對 $Q$ 微分並令其等於零：
$\frac{dTC}{dQ} = -\frac{dk}{Q^2} + \frac{h}{2}$
令 $\frac{dTC}{dQ} = 0$:
$-\frac{dk}{Q^2} + \frac{h}{2} = 0$
$\frac{h}{2} = \frac{dk}{Q^2}$
$Q^2 = \frac{2dk}{h}$
$Q^* = \sqrt{\frac{2dk}{h}}$

這是經濟訂購量 (EOQ) 的公式。
這裡的 $d$ 是需求率，如果我們考慮的是「單位時間」的總成本，而 $d$ 就是該單位時間的需求量，那麼這個公式是正確的。

【答案】
總成本 TC per unit time (不含商品成本): $TC(Q) = \frac{dk}{Q} + \frac{hQ}{2}$
最佳訂購量 (EOQ): $Q^* = \sqrt{\frac{2dk}{h}}$

(b) If the cost of the commodity cd is ignored, show that the optimal total cost is $TC^* = \sqrt{2hkd}$, and the ratio of the total cost associated with a non-optimal quantity to that associated with the optimal quantity $Q^*$ is $\frac{TC}{TC^*} = \frac{1}{2} (\frac{Q^*}{Q} + \frac{Q}{Q^*})$.

Part 1: Show $TC^* = \sqrt{2hkd}$
將 $Q^*$ 代入 $TC(Q)$ 的公式：
$TC^*(Q^*) = \frac{dk}{Q^*} + \frac{hQ^*}{2}$
Substitute $Q^* = \sqrt{\frac{2dk}{h}}$:
$TC^*(Q^*) = \frac{dk}{\sqrt{\frac{2dk}{h}}} + \frac{h}{2}\sqrt{\frac{2dk}{h}}$
$TC^*(Q^*) = dk \sqrt{\frac{h}{2dk}} + \frac{h}{2}\sqrt{\frac{2dk}{h}}$
$TC^*(Q^*) = \sqrt{\frac{d^2k^2h}{2dk}} + \sqrt{\frac{h^2}{4}\frac{2dk}{h}}$
$TC^*(Q^*) = \sqrt{\frac{dkh}{2}} + \sqrt{\frac{hdk}{2}}$
$TC^*(Q^*) = 2 \sqrt{\frac{dkh}{2}} = \sqrt{4 \cdot \frac{dkh}{2}} = \sqrt{2dkh}$

核心觀念

圖中的第一列與第一欄是狀態標籤 $0,1,2,3,4$，不屬於機率矩陣本身。因此實際轉移矩陣為

$$P= \begin{pmatrix} \frac14&\frac34&0&0&0\\ \frac12&\frac12&0&0&0\\ 0&0&1&0&0\\ 0&0&\frac13&\frac23&0\\ 1&0&0&0&0 \end{pmatrix}.$$

狀態 $2$ 是吸收狀態。狀態 $3$ 最終會以機率 $1$ 進入狀態 $2$，因為連續留在狀態 $3$ 的機率為

$$\left(\frac23\right)^n\longrightarrow 0.$$

狀態 $4$ 一步便會轉移至狀態 $0$。狀態 $0,1$ 形成封閉且不可約的常返類別。

---

解題方法

先求狀態 $\{0,1\}$ 內的穩態機率。其子矩陣為

$$Q= \begin{pmatrix} \frac14&\frac34\\ \frac12&\frac12 \end{pmatrix}.$$

設穩態分配為 $\boldsymbol{\pi}=(\pi_0,\pi_1)$，則

$$\boldsymbol{\pi}Q=\boldsymbol{\pi},\qquad \pi_0+\pi_1=1.$$

由第二個平衡方程式：

$$\pi_1=\frac34\pi_0+\frac12\pi_1$$

可得

$$\frac12\pi_1=\frac34\pi_0 \quad\Longrightarrow\quad \pi_1=\frac32\pi_0.$$

代入 $\pi_0+\pi_1=1$：

$$\pi_0+\frac32\pi_0=1 \quad\Longrightarrow\quad \pi_0=\frac25,\qquad \pi_1=\frac35.$$

因此：

• 從狀態 $0$ 或 $1$ 出發，長期分布為 $\left(\frac25,\frac35,0,0,0\right)$。
• 從狀態 $2$ 出發，永遠停留在狀態 $2$。
• 從狀態 $3$ 出發，最終進入狀態 $2$。
• 從狀態 $4$ 出發，先進入狀態 $0$，再依照 $\{0,1\}$ 的穩態比例分布。

所以

本題考查馬可夫鏈（Markov Chain）的極限定律，包含穩態分佈的計算。

核心觀念：
馬可夫鏈的穩態分佈 $\pi$ 是指當鏈運行足夠長時間後，處於各狀態的機率分佈。若馬可夫鏈是不可約（irreducible）且非週期性（aperiodic）的，則存在唯一的穩態分佈 $\pi$，且 $\lim_{n\to\infty} P(n)$ 的每一列（或每一行，取決於定義）都等於 $\pi$。穩態分佈滿足 $\pi P = \pi$ 和 $\sum \pi_i = 1$。

矩陣結構分析：
提供的轉移機率矩陣 $P$ 存在明顯的格式錯誤與內容錯誤：

1. 矩陣尺寸不一致：部分列（如第 2, 3, 4 行）只有 4 個元素，而狀態數是 5 個（0, 1, 2, 3, 4）。
2. 第二列（狀態 1 的轉移機率）的總和為 $1 + 1/2 + 1/2 = 2$，這不是有效的機率分佈。
3. 根據結構，可能存在多個吸收態（如狀態 2 和 4），或者鏈不是不可約的，這意味著 $\lim_{n\to\infty} P(n)$ 可能不存在標準形式，或者穩態分佈的計算方式不同。

由於矩陣格式錯誤，我們無法直接計算。然而，題目要求計算長期的機率，這通常假設鏈是不可約且非週期性的，或者至少存在一個穩態分佈。
在標準的馬可夫鏈理論中，如果一個狀態是暫時的（transient），則它在長期（穩態）的機率為 0。

推論與假設：
基於題目的結構和常見的馬可夫鏈問題，我們可以合理推斷：

• 狀態 1 可能是一個暫時狀態。
• 即使矩陣有誤，題目可能期望我們計算穩態分佈，並找出 $\pi_1$（狀態 1 的穩態機率）。

若我們假設存在一個穩態分佈 $\pi = (\pi_0, \pi_1, \pi_2, \pi_3, \pi_4)$，它滿足 $\pi P = \pi$ 和 $\sum \pi_i = 1$。
即使矩陣有誤，如果狀態 1 是暫時的，則其穩態機率 $\pi_1$ 必定為 0。

解題步驟：