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

核心觀念

本題考查線性規劃的敏感度分析：

1. 目標函數係數變動：分析產品售價改變時，最佳解與最佳目標值如何變化。
2. 右手邊資源限制變動：分析資源可用量改變時，最佳解與最大收益如何變化。
3. 參數規劃：將價格或資源變動量視為參數，找出不同參數區間下的最適基底與目標值函數。

原始限制式的可行域頂點為

$$(0,0),\quad (12.5,0),\quad (5,5),\quad (0,7.5)$$

各頂點的收益如下：

$$\begin{array}{c|c} \text{頂點} & z=6x_1+10x_2\\ \hline (0,0)&0\\ (12.5,0)&75\\ (5,5)&80\\ (0,7.5)&75 \end{array}$$

因此原始問題的最佳解為

$$x_1=5,\qquad x_2=5,\qquad z^*=80$$

---

(a) 售價同時增加 $\lambda$

解題方法

價格變動後，目標函數為

$$z=(6+\lambda)x_1+(10+\lambda)x_2$$

將其整理為

$$z=6x_1+10x_2+\lambda(x_1+x_2)$$

由於可行域不變，只需比較各個頂點在新目標函數下的收益。

各頂點目標值

在 $(12.5,0)$：

$$z_A=(6+\lambda)(12.5)=75+12.5\lambda$$

在 $(5,5)$：

$$z_B=5(6+\lambda)+5(10+\lambda)=80+10\lambda$$

在 $(0,7.5)$：

$$z_C=7.5(10+\lambda)=75+7.5\lambda$$

原點的目標值為 $0$，不會成為最佳解。

比較最佳頂點

先比較 $(5,5)$ 與 $(12.5,0)$：

$$80+10\lambda \ge 75+12.5\lambda$$ $$5\ge 2.5\lambda$$ $$\lambda\le 2$$

再比較 $(5,5)$ 與 $(0,7.5)$：

$$80+10\lambda-(75+7.5\lambda) =5+2.5\lambda>0$$

對所有 $\lambda\ge0$ 均成立，因此 $(0,7.5)$ 不會成為最佳解。

所以：

參數化結果

當 $0\le\lambda<2$：

$$x_1^*=5,\qquad x_2^*=5$$ $$z^*(\lambda)=80+10\lambda$$

當 $\lambda=2$：

$$z_A=z_B=100$$

此時目標函數為

$$z=8x_1+12x_2=4(2x_1+3x_2)$$

因此第二條限制式成為等收益線，線段

$$2x_1+3x_2=25$$

上介於 $(12.5,0)$ 與 $(5,5)$ 的所有可行點皆為最佳解，且

$$z^*=100$$

當 $\lambda>2$：

$$x_1^*=12.5,\qquad x_2^*=0$$ $$z^*(\lambda)=75+12.5\lambda$$

因此最大收益函數為

$$z^*(\lambda)= \begin{cases} 80+10\lambda, & 0\le\lambda\le2,\\ 75+12.5\lambda, & \lambda\ge2. \end{cases}$$

在 $\lambda=2$ 時，兩段函數數值相同；最佳解則由單一點擴展為一條線段上的多重最佳解。

---

(b) 第一項資源減少 $b_1$

第一條限制式改為

$$x_1+2x_2\le 15-b_1$$

令

$$R=15-b_1$$

則問題變為

$$\max z=6x_1+10x_2$$ $$\begin{aligned} x_1+2x_2&\le R,\\ 2x_1+3x_2&\le25,\\ x_1,x_2&\ge0. \end{aligned}$$

先判斷可行性

因為 $x_1,x_2\ge0$，所以

$$x_1+2x_2\ge0$$

要有可行解，必須滿足

$$15-b_1\ge0$$

因此：

• $0\le b_1\le15$：問題可行。
• $15<b_1\le60$：第一條限制式右側為負數，問題無可行解。

以下分析 $0\le b_1\le15$。

---

核心觀念

本題考查「固定設置成本（fixed setup cost）」與「生產決策邏輯」的混合整數規劃模型。

• 生產數量是連續變數。
• 是否生產某產品是 $0$–$1$ 整數變數。
• 只要產品 $i$ 被生產，就必須支付固定設置成本 $f_i$。
• 各項生產限制以二元變數之間的邏輯關係表示。

題目未提供市場需求上限、產能上限與單位生產成本。以下假設產品 $i$ 的最大可生產量為 $U_i$，且未提供單位生產成本，因此利潤只包含銷售收入與設置成本。

---

決策變數

令

$$x_i=\text{產品 }i\text{ 的生產量},\qquad i\in\{A,B,C,D\}$$

其中 $x_i\ge 0$，為連續變數。

令

$$y_i= \begin{cases} 1,&\text{產品 }i\text{ 被生產},\\ 0,&\text{產品 }i\text{ 不被生產}, \end{cases} \qquad i\in\{A,B,C,D\}$$

其中 $y_i\in\{0,1\}$。

---

目標函數

產品 $i$ 的銷售收入為 $p_i x_i$，若生產該產品，則需支付固定設置成本 $f_i y_i$。因此最大化總利潤：

$$\max Z = p_Ax_A+p_Bx_B+p_Cx_C+p_Dx_D -f_Ay_A-f_By_B-f_Cy_C-f_Dy_D$$

---

生產量與生產決策的連結

若產品未被生產，則生產量必須為零；若產品被生產，生產量不得超過其上限：

$$0\le x_i\le U_i y_i, \qquad i\in\{A,B,C,D\}$$

例如：

$$0\le x_A\le U_Ay_A$$

當 $y_A=0$ 時，$x_A=0$；當 $y_A=1$ 時，產品 A 才能有正的生產量。

若題目要求「只要宣告生產就必須達到最小生產量」$L_i$，可再加入：

$$x_i\ge L_i y_i$$

本題未給定最小生產量，因此不需要加入此限制。

---

行銷規則的模型化

1. 最多生產三種產品

$$y_A+y_B+y_C+y_D\le 3$$

---

2. 若生產 A，則不可生產 B

邏輯關係為

$$y_A=1\Rightarrow y_B=0$$

可寫成：

$$y_A+y_B\le 1$$

因此 A、B 不得同時被選取。

---

3. 若生產 C，則必須生產 D

邏輯關係為

核心觀念

這題考的是有向網路的最小成本斷路模型。若要切斷節點 $0$ 到節點 $5$ 的所有通路，必須在每一條由 $0$ 通往 $5$ 的路徑上，至少移除一條弧。這也可視為以最低成本選出一組弧，使其涵蓋所有路徑。

令 $x_{ij}$ 表示是否移除弧 $(i,j)$：

$$x_{ij}= \begin{cases} 1, & \text{移除弧 }(i,j),\\ 0, & \text{保留弧 }(i,j). \end{cases}$$

解題方法

依照圖中的箭頭方向，網路共有以下九條弧：

$$(0,1),\ (0,3),\ (1,2),\ (1,4),\ (2,5),\ (3,2),\ (3,5),\ (4,3),\ (4,5).$$

由節點 $0$ 出發，依箭頭逐段列出所有抵達節點 $5$ 的路徑：

1. $0\to1\to4\to5$
2. $0\to1\to4\to3\to5$
3. $0\to1\to4\to3\to2\to5$
4. $0\to1\to2\to5$
5. $0\to3\to5$
6. $0\to3\to2\to5$

每條路徑都必須至少移除一條弧，因此對每條路徑分別加入「路徑上弧的 $x_{ij}$ 總和至少為 1」的限制。

數學模型

目標函數是最小化所有移除弧的總成本：

解題步驟

1. 利潤函數

$$\Pi =\text{收入}-\text{成本} =(1200-6q)q-6q_{1}-3q_{2}, \qquad q=q_{1}+q_{2}$$

2. 以 $q_{1},q_{2}$ 表示

$$\Pi =1200(q_{1}+q_{2})-6(q_{1}+q_{2})^{2}-6q_{1}-3q_{2} =1194q_{1}+1197q_{2}-6q_{1}^{2}-12q_{1}q_{2}-6q_{2}^{2}$$

3. 對 $q_{1},q_{2}$ 求偏導

$$\frac{\partial\Pi}{\partial q_{1}}=1194-12(q_{1}+q_{2}),\qquad \frac{\partial\Pi}{\partial q_{2}}=1197-12(q_{1}+q_{2})$$

核心觀念

本題屬於動態規劃（Dynamic Programming, DP）中的多階段決策過程（Multi-Stage Decision Process）與庫存／生產控制模型。

1. 貝爾曼最佳化原理（Bellman's Principle of Optimality）：
   無論初始狀態與初始決策為何，後續決策相對於由前一決策所形成的狀態，皆必須構成最佳策略。求解時通常採用**逆向遞迴（Backward Induction）**由最後一階段倒推至第一階段。
2. 動態規劃四大要素：
   • 階段（Stage, $i$）：代表時間（年度 $i = 1, 2, \dots, n$）。
   • 狀態（State, $s_i$）：進入階段 $i$ 時可用的資源量（第 $i$ 年底賣羊決策前的山羊總數）。
   • 決策（Decision, $x_i$）：在階段 $i$ 所做的選擇（第 $i$ 年底賣出的山羊數量）。
   • 狀態轉移（State Transition）：決定下一階段狀態的物理規則（本題為保留的山羊在下一年數量翻倍）。

---

解題方法

(a) 動態規劃模型建構（General Dynamic Programming Model）

1. 符號與變數定義：

• 階段（Stage）：$i \in \{1, 2, \dots, n\}$，代表第 $i$ 年。
• 狀態變數（State Variable）$s_i$：在第 $i$ 年年底、執行賣出決策前，農場擁有的山羊總數（$s_i \ge 0$）。
  • 初始狀態：去年底（第 $0$ 年底）保留 $m$ 隻山羊，經過一年繁殖翻倍，故第 $1$ 年底的初始可用山羊數為 $s_1 = 2m$。
• 決策變數（Decision Variable）$x_i$：在第 $i$ 年年底決定賣出的山羊數量，限制條件為 $0 \le x_i \le s_i$ 且 $x_i$ 為整數。
• 狀態轉移方程式（State Transition Equation）：
  第 $i$ 年底賣出 $x_i$ 隻後，保留 $s_i - x_i$ 隻，經過一年後數量翻倍，故下一年度可用山羊數為： $$s_{i+1} = 2(s_i - x_i), \quad \forall i = 1, 2, \dots, n-1$$
• 即時收益（Immediate Return）：第 $i$ 年賣羊獲得之利潤為 $p_i \cdot x_i$。
• 價值函數（Value Function / Optimal Value Function）：
  令 $f_i(s_i)$ 表示從第 $i$ 年開始直到第 $n$ 年結束，在第 $i$ 年底初始山羊數為 $s_i$ 的條件下所能獲得的最大累積總利潤。

2. 遞迴關係式（Recursive Equation / Bellman Equation）：

• 終點邊界條件（Terminal Stage $i = n$）：
  題目規定第 $n$ 年底必須將所有山羊全部賣出，故決策為 $x_n = s_n$： $$f_n(s_n) = p_n \cdot s_n$$
• 中間階段遞迴式（Stage $i = 1, 2, \dots, n-1$）： $$f_i(s_i) = \max_{0 \le x_i \le s_i} \left\{ p_i x_i + f_{i+1}(2(s_i - x_i)) \right\}$$
• 求解目標：求出 $f_1(2m)$ 與對應之最佳決策序列 $(x_1^*, x_2^*, \dots, x_n^*)$。

---

(b) 數值求解（$m = 2, n = 3, p_1 =$$$50, p_2 =$$$65, p_3 =$$60）

由初始條件可知，第 $1$ 年底可用山羊數為 $s_1 = 2m = 2 \times 2 = 4$。利用逆向遞迴法（Backward Induction）依序計算各階段：

步驟 1：階段 3（$i = 3$，最後一年）

• 終點條件：必須賣出所有山羊（$x_3 = s_3$）。
• 價值函數： $$f_3(s_3) = p_3 s_3 = 60 s_3$$
• 最佳決策：$x_3^*(s_3) = s_3$。

步驟 2：階段 2（$i = 2$）

• 遞迴方程式： $$f_2(s_2) = \max_{0 \le x_2 \le s_2} \left\{ 65 x_2 + f_3(2(s_2 - x_2)) \right\}$$
• 代入 $f_3$：

核心觀念

本題屬於**隨機過程（Stochastic Processes）中離散時間馬可夫鏈（Discrete-Time Markov Chain, DTMC）在存貨控制模型（Inventory Control Model）**的應用。

1. 馬可夫性質（Markov Property）：
   系統在第 $n+1$ 期的狀態分佈僅取決於第 $n$ 期的狀態，而與第 $n-1$ 期之前的歷史無關：
   $P(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i) = P_{ij}$
2. 狀態定義與轉移機制（State Definition & Transition Mechanism）：
   • 設 $X_n$ 為第 $n$ 週週初（訂單送達後）的庫存量。
   • 設 $D_n$ 為第 $n$ 週的需求量，其機率分佈為：
     $P(D_n = 0) = 0.25,\quad P(D_n = 1) = 0.30,\quad P(D_n = 2) = 0.35,\quad P(D_n = 3) = 0.10$
   • 第 $n$ 週週末庫存量為 $Y_n = X_n - D_n$。
   • 存貨策略（Reorder Rule）：
     • 若 $Y_n \ge 2$：不訂貨，下週週初庫存 $X_{n+1} = Y_n = X_n - D_n$。
     • 若 $Y_n < 2$：於週末下單訂購 4 台印表機，並於下週週初送達，故下週週初庫存 $X_{n+1} = Y_n + 4 = X_n - D_n + 4$。
3. 全機率定理（Law of Total Probability）：
   求多步或特定事件機率時，對中間狀態進行分割與條件機率加權求和：
   $P(A) = \sum_{j} P(A \mid X = j) P(X = j)$

---

解題方法

(a) 將 NTUIIE 庫存量模型化為馬可夫鏈

步驟 1：確定狀態空間（State Space）
設 $X_n$ 表示第 $n$ 週**週初（訂單送達後）**的印表機庫存量。
分析 $X_n$ 可能的數值：

• 當 $X_n = 2$ 時，最大需求 $D_n = 3 \implies Y_n = -1 < 2 \implies X_{n+1} = -1 + 4 = 3$；最小需求 $D_n = 0 \implies Y_n = 2 \implies X_{n+1} = 2$。
• 當 $X_n = 5$ 時，最大需求 $D_n = 3 \implies Y_n = 2 \ge 2 \implies X_{n+1} = 2$；最小需求 $D_n = 0 \implies Y_n = 5 \implies X_{n+1} = 5$。
  因此，週初庫存狀態空間為 4 個狀態：
  $S = \{2, 3, 4, 5\}$

步驟 2：計算狀態轉移機率矩陣 $P$
定義轉移機率 $P_{ij} = P(X_{n+1} = j \mid X_n = i)$，其中 $i, j \in \{2, 3, 4, 5\}$：

• 自狀態 $i = 2$ 出發：

  • $D_n = 0 \implies Y_n = 2 \ge 2 \implies X_{n+1} = 2$（機率 $0.25$）
  • $D_n = 1 \implies Y_n = 1 < 2 \implies X_{n+1} = 1 + 4 = 5$（機率 $0.30$）
  • $D_n = 2 \implies Y_n = 0 < 2 \implies X_{n+1} = 0 + 4 = 4$（機率 $0.35$）
  • $D_n = 3 \implies Y_n = -1 < 2 \implies X_{n+1} = -1 + 4 = 3$（機率 $0.10$）
  • 對應狀態列向量 $(2, 3, 4, 5)$：$\begin{bmatrix} 0.25 & 0.10 & 0.35 & 0.30 \end{bmatrix}$

• 自狀態 $i = 3$ 出發：

  • $D_n = 0 \implies Y_n = 3 \ge 2 \implies X_{n+1} = 3$（機率 $0.25$）
  • $D_n = 1 \implies Y_n = 2 \ge 2 \implies X_{n+1} = 2$（機率 $0.30$）
  • $D_n = 2 \implies Y_n = 1 < 2 \implies X_{n+1} = 1 + 4 = 5$（機率 $0.35$）
  • $D_n = 3 \implies Y_n = 0 < 2 \implies X_{n+1} = 0 + 4 = 4$（機率 $0.10$）
  • 對應狀態列向量 $(2, 3, 4, 5)$：$\begin{bmatrix} 0.30 & 0.25 & 0.10 & 0.35 \end{bmatrix}$

• 自狀態 $i = 4$ 出發：

  • $D_n = 0 \implies Y_n = 4 \ge 2 \implies X_{n+1} = 4$（機率 $0.25$）
  • $D_n = 1 \implies Y_n = 3 \ge 2 \implies X_{n+1} = 3$（機率 $0.30$）
  • $D_n = 2 \implies Y_n = 2 \ge 2 \implies X_{n+1} = 2$（機率 $0.35$）
  • $D_n = 3 \implies Y_n = 1 < 2 \implies X_{n+1} = 1 + 4 = 5$（機率 $0.10$）
  • 對應狀態列向量 $(2, 3, 4, 5)$：$\begin{bmatrix} 0.35 & 0.30 & 0.25 & 0.10 \end{bmatrix}$

• 自狀態 $i = 5$ 出發：

  • $D_n = 0 \implies Y_n = 5 \ge 2 \implies X_{n+1} = 5$（機率 $0.25$）
  • $D_n = 1 \implies Y_n = 4 \ge 2 \implies X_{n+1} = 4$（機率 $0.30$）

核心觀念

本題屬於作業系統與作業研究（Operations Research）中的排隊理論（Queueing Theory）與排隊經濟學分析（Queueing Economics）。

1. 排隊模型識別（Kendall's Notation）：

   • 顧客到達過程為卜瓦松過程（Poisson Process），時間間隔服從指數分布 $\rightarrow$ 第一個符號為 M (Markovian/Memoryless)。
   • 結帳服務時間服從指數分布（Exponential Distribution） $\rightarrow$ 第二個符號為 M。
   • 收銀機數量為平行運作的服務通道數 $c$ $\rightarrow$ 第三個符號為 $c$。
   • 系統採用先到先服務（FCFS）且容量無限制 $\rightarrow$ 完整模型記為 $M/M/c$ 排隊模型。

2. 穩態條件（Steady-State Condition）：
   系統服務率必須大於到達率，即系統利用率 $\rho = \frac{\lambda}{c\mu} < 1$。否則佇列長度會趨近於無限大，系統無法達到穩態。

3. 期望成本函數（Expected Cost Function）：
   期望總成本為「收銀機營運成本」與「顧客等候成本」之和：
   $TC(c) = C_s \cdot c + C_w \cdot L$
   （或僅計算佇列中等待顧客成本 $TC_q(c) = C_s \cdot c + C_w \cdot L_q$）

---

解題方法

(a) 建模推導

將台大超市（NTU Mart）收銀區的顧客數建立為 $M/M/c$ 排隊模型，相關參數如下：

• 顧客到達率（$\lambda$）：$\lambda = 0.6 \text{ 人/分鐘} = 36 \text{ 人/小時}$。
• 單一收銀機服務率（$\mu$）：平均結帳時間 $\frac{1}{\mu} = 2 \text{ 分鐘/人} \implies \mu = 0.5 \text{ 人/分鐘} = 30 \text{ 人/小時}$。
• 服務通道數（$c$）：開放的收銀機數量。
• 服務強度／流量率（$r$）：$r = \frac{\lambda}{\mu} = \frac{0.6}{0.5} = 1.2$。
• 系統利用率（$\rho$）：$\rho = \frac{\lambda}{c\mu} = \frac{1.2}{c}$。

---

(b) 最佳收銀機數量計算

步驟 1：單位統一與穩定性檢查

• 單位統一（以「小時」為時間單位）：
  • 每台收銀機營運成本 $C_s =$$$200 \text{ /小時}$。
  • 每位顧客等候成本 $C_w =$$$2 \text{ /(人·分鐘)} =$$$120 \text{ /(人·小時)}$。
• 穩態條件約束：
  $\rho = \frac{1.2}{c} < 1 \implies c > 1.2$
  由於收銀機台數 $c$ 必須為正整數，故 $c \ge 2$。當 $c = 1$ 時系統無法維持穩定。

步驟 2：計算 $M/M/c$ 模型之穩態指標與成本

系統內無顧客的穩態機率 $P_0$ 公式為：
$P_0 = \left[ \sum_{k=0}^{c-1} \frac{r^k}{k!} + \frac{r^c}{c!} \cdot \frac{1}{1 - \rho} \right]^{-1}$

等待機率（Erlang-C 公式）$P_c$ 與佇列平均顧客數 $L_q$ 分別為：
$P_c = \frac{r^c}{c!(1-\rho)} P_0, \quad L_q = \frac{P_c \cdot \rho}{1 - \rho}$

系統內平均總顧客數 $L$（包含佇列中與正在結帳者）：
$L = L_q + r = L_q + 1.2$

---

當 $c = 2$ 時：

• $\rho = \frac{1.2}{2} = 0.6$
• 計算 $P_0$：
  $\sum_{k=0}^{1} \frac{1.2^k}{k!} = 1 + 1.2 = 2.2$
  $\frac{1.2^2}{2!} \cdot \frac{1}{1 - 0.6} = \frac{1.44}{2} \cdot 2.5 = 1.8$
  $P_0 = \frac{1}{2.2 + 1.8} = \frac{1}{4} = 0.25$
• 計算 $L_q$ 與 $L