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

核心觀念

本題考查：

• 單純形法最終表的基底變數與非基底變數。
• 基底矩陣 $B$ 與 $B^{-1}$ 的運算。
• 最終表各欄係數及 RHS 的推回。
• 目標列的 reduced cost（約化成本）與最適解判定。

依附圖，最終基底變數為 $x_1,x_3$，非基底變數為 $x_2,x_4,x_5$。其中 $x_4,x_5$ 為兩個限制式的鬆弛變數。

解題方法

將原限制式寫成等式：

$$6x_1+3x_2+5x_3+x_4=i$$ $$3x_1+4x_2+5x_3+x_5=j$$

基底矩陣由 $x_1,x_3$ 的欄所組成：

$$B= \begin{bmatrix} 6&5\\ 3&5 \end{bmatrix}$$

其反矩陣為：

$$B^{-1} =\frac{1}{15} \begin{bmatrix} 5&-5\\ -3&6 \end{bmatrix} = \begin{bmatrix} \frac13&-\frac13\\ -\frac15&\frac25 \end{bmatrix}$$

原係數矩陣包含 $x_1,x_2,x_3,x_4,x_5$：

$$A= \begin{bmatrix} 6&3&5&1&0\\ 3&4&5&0&1 \end{bmatrix}$$

計算 $B^{-1}A$：

$$B^{-1}A= \begin{bmatrix} 1&-\frac13&0&\frac13&-\frac13\\ 0&1&1&-\frac15&\frac25 \end{bmatrix}$$

因此最終表的兩個限制式列為：

$$x_1-\frac13x_2+\frac13x_4-\frac13x_5 =\frac{i-j}{3}$$ $$x_3+x_2-\frac15x_4+\frac25x_5 =\frac{-i+2j}{5}$$

與附圖比較：

$$e=-\frac13,\qquad g=\frac13$$ $$f=1,\qquad h=-\frac15$$

RHS 比較得：

$$\frac{i-j}{3}=\frac53 \quad\Longrightarrow\quad i-j=5$$ $$\frac{-i+2j}{5}=3 \quad\Longrightarrow\quad -i+2j=15$$

解聯立方程式：

$$j=20,\qquad i=25$$

由目標列求 $a,b,c,d$

核心觀念

本題考查「含固定設置成本的生產規劃」與「資源擴充決策」之混合整數線性規劃模型。

需要掌握三個觀念：

1. 生產數量變數：決定各產品生產多少。
2. 固定成本與二元變數：只要產品有生產，就必須支付一次固定成本。
3. 設備升級決策：兩個製程中恰好選擇一個升級，且升級後增加可用工時。

題目表格可解讀為三項產品與兩個製程的單位工時需求：

製程	產品 1	產品 2	產品 3	原可用工時
製程 I	0.25	0.20	0.30	300
製程 II	0.40	0.50	0.20	400

---

解題方法

令：

• $x_i$：產品 $i$ 的生產數量，$i=1,2,3$
• $y_i$：產品 $i$ 是否生產的二元變數
• $z_1$：是否升級製程 I
• $z_2$：是否升級製程 II

其中：

$$y_i= \begin{cases} 1, & \text{產品 }i\text{ 有生產}\\ 0, & \text{產品 }i\text{ 未生產} \end{cases}$$ $$z_j= \begin{cases} 1, & \text{升級製程 }j\\ 0, & \text{不升級製程 }j \end{cases}$$

產品 $i$ 每單位的淨變動利潤為：

$$r_i-c_i$$

因此，產品 $i$ 的總貢獻為：

$$(r_i-c_i)x_i-F_i y_i$$

其中 $F_i y_i$ 表示只要生產產品 $i$，便支付一次固定成本 $F_i$。

---

目標函數

最大化總利潤：

$$\max Z = \sum_{i=1}^{3}\left[(r_i-c_i)x_i-F_i y_i\right]$$

展開為：

$$\max Z = (r_1-c_1)x_1+(r_2-c_2)x_2+(r_3-c_3)x_3 -F_1y_1-F_2y_2-F_3y_3$$

題目未提供升級成本，因此目標函數中不扣除升級費用。若實際存在製程升級成本 $K_1,K_2$，則可再加入 $-K_1z_1-K_2z_2$。

---

製程工時限制

製程 I

原本可用工時為 $300$ 小時。

若升級製程 I，可增加 $20\%$：

$$300(1+0.2z_1)=300+60z_1$$

因此製程 I 的限制為：

$$0.25x_1+0.20x_2+0.30x_3 \leq 300+60z_1$$

當 $z_1=0$ 時，右側為 $300$；當 $z_1=1$ 時，右側為 $360$。

製程 II

原本可用工時為 $400$ 小時。

若升級製程 II，可增加 $10\%$：

$$400(1+0.1z_2)=400+40z_2$$

因此製程 II 的限制為：

$$0.40x_1+0.50x_2+0.20x_3 \leq 400+40z_2$$

當 $z_2=0$ 時，右側為 $400$；當 $z_2=1$ 時，右側為 $440$。

---

恰好升級一個製程

核心觀念

• 約束程式 (Constraint Programming, CP)：以變數的「領域」(Domain) 以及「限制式」(Constraint) 交互作用，透過領域縮減(Domain Reduction) 及限制傳遞(Constraint Propagation) 逐步剔除不可能的取值。
• 全異約束(All‑Different)：要求所有變數取得互不相同的值，等同於在「變數‑值」二分圖上找一組匹配。
• 搜尋與列舉：在領域已盡可能縮小後，使用深度優先搜尋 (DFS) 逐一指派變數，並在每一步進行限制傳遞，若違反任何限制則回溯。
• 目標函數：本題的目標為

$$Z=\sum_{i=1}^{5}\bigl(a_i x_i-x_i^2\bigr),\qquad (a_1,a_2,a_3,a_4,a_5)=(5,8,10,15,20).$$

每個變數的貢獻皆可事先計算成單變數收益表，搜尋時只需累加即可。

---

解題方法

1. 建立初始領域

$$\begin{aligned} D_{x_1}&=\{3,6,12\},\quad D_{x_2}=\{3,6\},\quad D_{x_3}=\{6,12\},\\ D_{x_4}&=\{3,6,9,12\},\quad D_{x_5}=\{9,12,15,16\}. \end{aligned}$$

2. 全異約束的先行縮減
   • 觀察每個值在多少變數的領域中出現：

$$\begin{array}{c|c} 值 & 出現變數\\ \hline 3 & x_1,x_2,x_4\\ 6 & x_1,x_2,x_3,x_4\\ 9 & x_4,x_5\\ 12& x_1,x_3,x_4,x_5\\ 15& x_5\\ 16& x_5 \end{array}$$

• 只有 $15,16$ 僅屬於 $x_5$，故 $x_5$ 必取其中之一。其餘值仍需在不同變數之間分配。

3. 線性不等式傳遞

   • 限制式 $x_1+x_3+x_4\le 25$ 只涉及 $\{x_1,x_3,x_4\}$。
   • 先列舉三變數的所有不同組合，再檢查是否滿足不等式。
   • 這一步會把不可能的組合直接剔除，避免在搜尋時浪費分支。

4. 搜尋與列舉

   • 變數排序：先指派 $(x_1,x_3,x_4)$（受不等式約束且可組合數較多），再指派 $x_2$、最後指派 $x_5$。
   • 在每一次指派後即做全異傳遞：若某值已被使用，從所有未指派變數的領域中刪除該值。
   • 若此時任一變數的領域空集合，立即回溯。

5. 計算目標值

   • 事先計算每個可能取值的貢獻 $f_i(x)=a_i x-x^2$：

本題考驗對條件機率、全期望值定律 (Law of Total Expectation) 和全變異數定律 (Law of Total Variance) 的應用，以及泊松分佈 (Poisson distribution) 的基本性質。

核心觀念：
當一個隨機變數的機率分佈取決於另一個隨機事件（或變數）時，我們需要使用條件機率和全期望值/全變異數定律來計算其期望值和變異數。

問題設定：

• 假設 $R$ 為一個事件，表示「明天會下雨」。
• 假設 $D$ 為一個事件，表示「明天是乾旱日」（不下雨）。
• 已知 $P(R) = 0.6$。由於只有下雨或不下雨兩種情況，所以 $P(D) = 1 - P(R) = 1 - 0.6 = 0.4$。
• 令 $X$ 為「明天發生的交通事故數量」。
• 已知：
  • 若下雨 (R)，交通事故數量為泊松分佈，平均值為 9。即 $X | R \sim \text{Poisson}(\lambda_R = 9)$。
  • 若不下雨 (D)，交通事故數量為泊松分佈，平均值為 3。即 $X | D \sim \text{Poisson}(\lambda_D = 3)$。

a. 計算 E(X) (The expected value E(X))

我們使用全期望值定律：$E(X) = E(E(X|Y))$。在這裡，$Y$ 是表示天氣狀況的事件（下雨 R 或不下雨 D）。
$E(X) = E(X|R) P(R) + E(X|D) P(D)$
我們知道泊松分佈 $Y \sim \text{Poisson}(\lambda)$ 的期望值是 $E(Y) = \lambda$。
因此，$E(X|R) = \lambda_R = 9$ 且 $E(X|D) = \lambda_D = 3$。
將已知數值代入：
$E(X) = (9)(0.6) + (3)(0.4)$
$E(X) = 5.4 + 1.2$
$E(X) = 6.6$

b. 計算 P{X=0} (The probability P{X=0})

我們使用全機率定律：$P(A) = \sum_i P(A|B_i) P(B_i)$。在這裡，$A$ 是事件 $\{X=0\}$，$B_i$ 是天氣狀況事件 $\{R, D\}$。
$P(X=0) = P(X=0|R) P(R) + P(X=0|D) P(D)$
對於泊松分佈 $Y \sim \text{Poisson}(\lambda)$，其機率質量函數 (PMF) 為 $P(Y=k) = \frac{e^{-\lambda} \lambda^k}{k!}$。
因此：

• $P(X=0|R) = \frac{e^{-9} 9^0}{0!} = e^{-9}$
• $P(X=0|D) = \frac{e^{-3} 3^0}{0!} = e^{-3}$

將數值代入：
$P(X=0) = (e^{-9})(0.6) + (e^{-3})(0.4)$
計算 $e^{-9} \approx 0.0001234$

本題要求探討一個製程系統是否能被建模為馬可夫鏈 (Markov Chain)，並推導其轉移機率。

問題背景：

• 系統：IC 製造設施的緩衝區 (buffer)。
• 事件：晶圓 (wafers) 陸續抵達。
• 處理機制：當累積到 $k$ 個晶圓時，所有 $k$ 個晶圓會被一次性處理。處理完成後，系統重置，等待下一批晶圓。
• 抵達過程：設 $x_n$ 為第 $n$ 個時間週期內抵達的晶圓數量。$x_n$ 是獨立同分佈的隨機變數，其分佈為：
  • $P(x_n = 0) = \alpha$ (該週期沒有晶圓抵達)
  • $P(x_n = 1) = 1-\alpha$ (該週期有一個晶圓抵達)
    其中 $0 < \alpha < 1$。
• 系統狀態：令 $X_n$ 為時間 $n$ 時系統中的晶圓數量。

a. 建立馬可夫鏈所需的假設 (Assumptions for Markov Chain Modeling):

馬可夫鏈的核心假設是「無記憶性」(Memorylessness)，即系統的下一個狀態僅取決於當前狀態，而與過去的狀態無關。基於此，建立馬可夫鏈模型需要以下假設：

1. 馬可夫性質 (Markov Property): 系統的未來狀態僅取決於當前狀態，而與系統如何到達該狀態的歷史路徑無關。也就是說，$P(X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, ..., X_0 = i_0) = P(X_{n+1} = j | X_n = i)$。
2. 獨立的抵達過程： 每個時間週期內晶圓的抵達數量 $x_n$ 是相互獨立的隨機變數。這意味著某個週期的抵達情況不影響其他週期的抵達情況。
3. 固定參數： 系統的參數，如 $k$ (觸發處理的晶圓數量)、$\alpha$ (抵達率參數) 以及處理時間 (雖然題目中未明確給出處理時間，但假設處理時間是確定的或有固定分佈，且處理是瞬間完成的)，在整個系統運行過程中保持不變。
4. 離散時間和離散狀態空間： 系統的狀態和時間是離散的。我們已經確定 $X_n$ 是離散的 (晶圓數量)，且時間 $n$ 也是離散的週期。

b. 定義狀態空間並證明 {Xn: n = 0, 1, 2, ...} 是馬可夫鏈:

• 狀態空間 (State Space) $S$：
  系統的狀態 $X_n$ 代表時間 $n$ 時緩衝區中的晶圓數量。

  • 緩衝區中的晶圓數量可以從 0 開始。
  • 當晶圓抵達時，數量增加。
  • 當累積到 $k$ 個晶圓時，它們會被一次性處理，數量變為 0。
  • 因此，系統中的晶圓數量 $X_n$ 可能的值是 $0, 1, 2, ..., k-1$。
  • 當 $X_n$ 達到 $k$ 時，系統會立即進入狀態 0，因為所有晶圓都被處理了。所以，狀態 $k$ 實際上是一個瞬時狀態，它會立刻轉移到狀態 0。
  • 因此，狀態空間 $S = \{0, 1, 2, ..., k-1\}$。

• 證明 {Xn} 是馬可夫鏈：
  我們需要證明 $P(X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, ..., X_0 = i_0) = P(X_{n+1} = j | X_n = i)$。
  令 $X_n = i$ 為當前狀態，即時間 $n$ 時緩衝區有 $i$ 個晶圓。
  考慮時間 $n+1$ 時的狀態 $X_{n+1}$。這取決於時間 $n+1$ 的抵達數量 $x_{n+1}$ 以及當前狀態 $X_n=i$。

  • 情況 1： 如果 $i + x_{n+1} < k$。
    那麼 $X_{n+1} = i + x_{n+1}$。
    如果 $x_{n+1} = 0$ (機率 $\alpha$)，則 $X_{n+1} = i$。
    如果 $x_{n+1} = 1$ (機率 $1-\alpha$)，則 $X_{n+1} = i+1$。
  • 情況 2： 如果 $i + x_{n+1} = k$。
    那麼 $X_{n+1} = 0$ (因為 $k$ 個晶圓被處理)。
    這只可能發生在 $i = k-1$ 且 $x_{n+1} = 1$ 時。
    如果 $i = k-1$ 且 $x_{n+1} = 0$ (機率 $\alpha$)，則 $X_{n+1} = k-1$。
    如果 $i = k-1$ 且 $x_{n+1} = 1$ (機率 $1-\alpha$)，則 $X_{n+1} = 0$。

  在所有情況下，$X_{n+1}$ 的值僅取決於當前狀態 $X_n = i$ 和抵達數量 $x_{n+1}$。由於 $x_{n+1}$ 是獨立於過去所有狀態的隨機變數，因此 $X_{n+1}$ 的機率分佈只依賴於 $X_n = i$。這證明了馬可夫性質。
  因此，$\{X_n\}$ 是一個馬可夫鏈。

本題考驗對卜松過程 (Poisson Process) 性質的理解，特別是其獨立增量 (independent increments) 和平穩增量 (stationary increments) 的特性。

問題背景：

• 顧客抵達服務站遵循一個速率為 $\lambda$ 的卜松過程。
• $X(t)$ 代表時間 $t$ 之前抵達的顧客總數。
• 考慮兩個時間點 $s$ 和 $t$，其中 $0 < s < t$。
• 已知在時間 $s$ 時，已抵達的顧客數為 $n$，即 $X(s) = n$。

卜松過程的關鍵性質：

1. 獨立增量： 在不重疊的時間區間內發生的事件數量是相互獨立的。也就是說，在時間區間 $(t_1, t_2]$ 內發生的事件數量與在區間 $(t_3, t_4]$ 內發生的事件數量是獨立的，如果這兩個區間不重疊。
2. 平穩增量： 在長度為 $\Delta t$ 的任意時間區間內發生的事件數量，其機率分佈是相同的。也就是說，$P(\text{Events in } (t, t+\Delta t] = m) = \frac{e^{-\lambda \Delta t} (\lambda \Delta t)^m}{m!}$，與起始時間 $t$ 無關。
3. 泊松分佈： 在長度為 $\Delta t$ 的時間區間內，事件發生的次數 $m$ 服從參數為 $\lambda \Delta t$ 的泊松分佈。即 $P(\text{Events in } (t, t+\Delta t] = m) = \frac{e^{-\lambda \Delta t} (\lambda \Delta t)^m}{m!}$。

a. 計算條件機率 P{X(t) = n+k | X(s) = n}

我們想知道在已知時間 $s$ 時有 $n$ 位顧客抵達的前提下，到時間 $t$ 為止總共有 $n+k$ 位顧客抵達的機率。
這相當於問：在時間區間 $(s, t]$ 這個長度為 $t-s$ 的時間段內，有多少位顧客抵達？
設 $N(s, t)$ 為在時間區間 $(s, t]$ 內抵達的顧客數。
根據卜松過程的性質，事件數量服從泊松分佈。區間的長度是 $\Delta t = t-s$。
因此，$N(s, t)$ 服從參數為 $\lambda(t-s)$ 的泊松分佈。
$N(s, t) \sim \text{Poisson}(\lambda(t-s))$
我們感興趣的是 $P(X(t) = n+k | X(s) = n)$。
由於 $X(t) = X(s) + N(s, t)$ (總抵達數等於到 $s$ 時為止的數量加上 $(s, t]$ 區間內的數量)，
所以，$X(t) = n+k$ 等價於 $n + N(s, t) = n+k$，這意味著 $N(s, t) = k$。
因此，
$P(X(t) = n+k | X(s) = n) = P(N(s, t) = k | X(s) = n)$
由於卜松過程具有獨立增量性質，在區間 $(s, t]$ 內的抵達數 $N(s, t)$ 與在區間 $(0, s]$ 內的抵達數 $X(s)$ 是相互獨立的。
所以，
$P(N(s, t) = k | X(s) = n) = P(N(s, t) = k)$
由於 $N(s, t) \sim \text{Poisson}(\lambda(t-s))$，我們可以使用泊松分佈的機率質量函數 (PMF)：
$P(N(s, t) = k) = \frac{e^{-\lambda(t-s)} (\lambda(t-s))^k}{k!}$
因此，