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

本題為一線性規劃問題，要求利用圖解法求解。首先需繪製各個限制式所定義的區域，並找出其共同的交集區域，即為可行區域。再者，於可行區域內尋找使目標函數最大化的點。

1.1. 圖解法求解可行區域：
我們需要繪製出四個限制式所定義的區域，並找出它們的交集。
限制式 1: $4X+3Y \leq 12$
當 $X=0$ 時, $3Y=12 \implies Y=4$。點為 $(0, 4)$。
當 $Y=0$ 時, $4X=12 \implies X=3$。點為 $(3, 0)$。
此限制式代表通過 $(0, 4)$ 和 $(3, 0)$ 的直線下方區域。

限制式 2: $Y \leq 2$
此限制式代表 $Y$ 值小於等於 2 的區域，即直線 $Y=2$ 的下方區域。

限制式 3: $X-Y \leq 2 \implies Y \geq X-2$
當 $X=0$ 時, $Y=-2$。點為 $(0, -2)$。
當 $Y=0$ 時, $X=2$。點為 $(2, 0)$。
此限制式代表通過 $(0, -2)$ 和 $(2, 0)$ 的直線上方區域。

限制式 4: $X, Y \geq 0$
此限制式代表第一象限的區域。

綜合以上四個限制式，我們需要找出滿足所有條件的區域。

• $4X+3Y \leq 12$
• $Y \leq 2$
• $Y \geq X-2$
• $X \geq 0, Y \geq 0$

讓我們找出這些直線的交點：

• 直線 $4X+3Y=12$ 與 $Y=2$ 的交點：$4X + 3(2) = 12 \implies 4X + 6 = 12 \implies 4X = 6 \implies X = 1.5$。交點為 $(1.5, 2)$。
• 直線 $4X+3Y=12$ 與 $Y=X-2$ 的交點：$4X + 3(X-2) = 12 \implies 4X + 3X - 6 = 12 \implies 7X = 18 \implies X = \frac{18}{7}$。此時 $Y = X-2 = \frac{18}{7} - 2 = \frac{18-14}{7} = \frac{4}{7}$。交點為 $(\frac{18}{7}, \frac{4}{7})$。
• 直線 $Y=2$ 與 $Y=X-2$ 的交點：$2 = X-2 \implies X = 4$。

圖示資料與核心觀念

原圖中的活動方格排列為：

因此，依掃描圖可讀得：

• $C$ 的工期為 $2$，最早開始時間為 $4$，最早完成時間為 $6$。
• $D$ 的工期為 $3$，最早開始時間為 $7$，最早完成時間為 $10$。

題目轉錄表中的 $C=6$、$D=7$，分別是圖中的最早完成時間與最早開始時間，並非工期。

本題使用關鍵路徑法：

$EF_i=ES_i+d_i$

$ES_i=\max\{\text{所有前置活動的 }EF\}$

反向計算時：

$LS_i=LF_i-d_i$

$LF_i=\min\{\text{所有後續活動的 }LS\}$

總浮時為：

$TF_i=LS_i-ES_i=LF_i-EF_i$

總浮時為 $0$ 的活動所形成的路徑，即為關鍵路徑。

依圖中箭線，主要前置關係為：

$A\to C,\qquad B\to D,E$

$C,D\to F,\qquad D,E\to G,\qquad C,E\to H$

正向計算

所以專案工期為：

$\max(13,22,21)=22$

反向計算

以專案完成時間 $22$ 為基準：

2.1 活動 C 的方格

由正向計算：

$ES_C=EF_A=4$

$EF_C=4+2=6$

由反向計算：

$LF_C=\min(LS_F,LS_H)=\min(19,14)=14$

$LS_C=14-2=12$

因此活動 $C$ 的方格為：

選項分析：

• (a) $ES=3$ 且工期為 $3$，不符合 $C$ 必須在 $A$ 完成後才能開始，錯誤。
• (b) $ES=12$、$EF=6$，甚至有 $ES>EF$，不可能，錯誤。
• (c) 符合 $ES=4$、$EF=6$、工期 $2$、$LS=12$、$LF=14$，正確。
• (d) 工期寫成 $1$，且 $C$ 的最早開始時間不應為 $5$，錯誤。

2.2 活動 G 的方格

本題為決策分析問題，包含三種決策準則：Maximin、Maximum Likelihood (最大似然準則，在此情境下應為最大機率準則或最可能狀態準則) 以及 Bayes' 決策法則。

首先，整理支付矩陣 (Payoff Table) 與各狀態的先驗機率 (Prior Probability)：

3.1. Maximin payoff criterion (悲觀準則)：
此準則尋找每種決策下的「最壞情況」(最小利潤)，然後選擇其中最大的利潤。

• Decision alternative 1: Minimum payoff = -100
• Decision alternative 2: Minimum payoff = -200
• Decision alternative 3: Minimum payoff = -300
• Decision alternative 4: Minimum payoff = -150
  比較這些最小值 (-100, -200, -300, -150)，最大值是 -100。
  因此，應選擇 Decision alternative 1。
  【答案】(a)

3.2. Maximum Likelihood Criterion (最大機率準則)：
此準則是指尋找機率最高的狀態，然後選擇在此狀態下利潤最高的決策。
此題的狀態機率為：State 1 (0.2), State 2 (0.5), State 3 (0.3)。
機率最高的狀態是 State of Nature 2 (機率為 0.5)。
在此狀態下，各決策的利潤為：

• Decision alternative 1: 550
• Decision alternative 2: 350
• Decision alternative 3: 700
• Decision alternative 4: 250
  比較這些利潤 (550, 350, 700, 250)，最大值是 700。

本題要求建立一個關於疾病傳播的馬可夫鏈模型。我們需要定義隨機過程 $X_n$、時間索引 $n$、狀態空間 (State Space) 以及轉移機率矩陣 (Transition Probability Matrix)。

1. 隨機過程 $X_n$：
$X_n$ 代表在時間點 $n$ 時，系統的狀態。在這個模型中，系統的狀態可以由人口中患病的人數來描述。

2. 時間索引 $n$：
$n$ 代表時間的離散步驟，在這裡代表時間週期 (period)。 $n = 0, 1, 2, \dots$。

3. 狀態空間 (State Space)：
總人口數 $N = 5$。人口中的個體可以是「健康的」或「患病的」。
由於疾病的傳播是從患病者傳染給健康者，因此系統的狀態可以定義為在某個時間點 $n$ 時，健康人口的數量。
令 $S$ 為健康人口的數量。可能的狀態是：

• 當所有人都患病時，健康人口為 0。
• 當有 1 人健康，4 人患病時，健康人口為 1。
• 當有 2 人健康，3 人患病時，健康人口為 2。
• 當有 3 人健康，2 人患病時，健康人口為 3。
• 當有 4 人健康，1 人患病時，健康人口為 4。
• 當所有人都健康時，健康人口為 5。

然而，疾病的傳播需要有患病者才能進行。如果所有人都健康 (狀態 5)，疾病不會傳播。如果所有人都患病 (狀態 0)，則疾病無法傳播給健康者 (因為沒有健康者)。
因此，更合適的狀態定義可能是「患病的人數」。
令 $k$ 為患病的人數。

• $k = 0$: 所有人都健康。
• $k = 1$: 1 人患病，4 人健康。
• $k = 2$: 2 人患病，3 人健康。
• $k = 3$: 3 人患病，2 人健康。
• $k = 4$: 4 人患病，1 人健康。
• $k = 5$: 所有人都患病。

在每一步 (一個時間週期)，會隨機選取兩個人進行互動。

• 如果選取的兩個人都是健康的，則沒有疾病傳播。
• 如果選取的兩個人都是患病的，則沒有疾病傳播。
• 如果一人患病，一人健康，則有 0.1 的機率疾病傳染給健康者。

考慮從狀態 $k$ (患病人數) 轉移到下一個時間點的狀態 $k'$。
總人口 $N=5$。
從狀態 $k$ 轉移到狀態 $k'$，有以下幾種情況：

a) 狀態空間的定義：
我們將狀態定義為「患病的人數」。狀態空間為 $\{0, 1, 2, 3, 4, 5\}$。

b) 轉移機率矩陣 (Transition Probability Matrix, P)：
$P_{ij}$ 代表從狀態 $i$ 轉移到狀態 $j$ 的機率。這裡的狀態 $i, j$ 指的是患病人數 $k$。

首先，計算在一個時間週期內，隨機選取兩個人進行互動時，各種情況的機率。
總共有 $\binom{5}{2} = \frac{5 \times 4}{2} = 10$ 種可能的配對。

• 情況 1：選取兩名健康者。
  如果當前有 $k$ 人患病，則有 $5-k$ 人健康。
  選取兩名健康者的配對數為 $\binom{5-k}{2}$。
  此情況發生時，疾病不會傳播。狀態 $k$ 保持不變。

• 情況 2：選取兩名患病者。
  選取兩名患病者的配對數為 $\binom{k}{2}$。
  此情況發生時，疾病不會傳播。狀態 $k$ 保持不變。

• 情況 3：選取一名患病者和一名健康者。
  選取一名患病者和一名健康者的配對數為 $\binom{k}{1} \times \binom{5-k}{1} = k \times (5-k)$。
  此情況發生時，有 0.1 的機率疾病傳染給健康者，導致患病人數增加 1。有 0.9 的機率疾病不傳染。

  • 疾病傳染 (患病人數從 $k$ 變為 $k+1$) 的機率為 $0.1$。
  • 疾病未傳染 (患病人數仍為 $k$) 的機率為 $0.9$。

現在，我們逐一計算各個狀態轉移的機率：

從狀態 $k=0$ (0 人患病，5 人健康)：

• 選取兩名健康者：$\binom{5}{2} = 10$ 種配對。機率為 $\frac{10}{10} = 1$。
• 疾病不會傳播，因為沒有患病者。
• 因此，從狀態 0 只能轉移回狀態 0。
  $P_{00} = 1$。
  $P_{0j} = 0$ for $j \neq 0$.

從狀態 $k=1$ (1 人患病，4 人健康)：

• 總配對數：10。
• 選取兩名健康者：$\binom{4}{2} = 6$ 種配對。機率 $\frac{6}{10} = 0.6$。狀態不變 (1人患病)。
• 選取兩名患病者：$\binom{1}{2} = 0$ 種配對。機率 0。
• 選取一名患病者和一名健康者：$1 \times 4 = 4$ 種配對。機率 $\frac{4}{10} = 0.4$。
  • 疾病傳染 (轉移到 $k=2$) 的機率 = $0.4 \times 0.1 = 0.04$。
  • 疾病未傳染 (停留在 $k=1$) 的機率 = $0.4 \times 0.9 = 0.36$。

總結從狀態 1 的轉移機率：

• $P_{11}$ (狀態保持不變，透過選兩健康者或一患一健但未傳染)：$0.6 + 0.36 = 0.96$。
• $P_{12}$ (轉移到狀態 2)：$0.04$。
• $P_{1j} = 0$ for $j \neq 1, 2$.

核心觀念

本題考查有限狀態馬可夫鏈、首次到達時間，以及吸收馬可夫鏈的基本計算。

令 $X_n$ 為第 $n$ 期結束時的庫存量。當 $X_n<2$ 時，第 $n+1$ 期開始前補進 $2$ 單位；否則不補貨。若以 $D_{n+1}$ 表示下一期需求，則

因為各期需求獨立，給定目前庫存 $X_n$ 後，下一期庫存的分布不再依賴更早的庫存狀態，所以 $\{X_n\}$ 具有馬可夫性。

以下依題目給定的轉移矩陣計算。狀態 $0$ 視為缺貨狀態；狀態 $1$ 視為未缺貨的補貨狀態。兩者都符合 $X_n<q$，因此都會觸發補貨。

解題方法與計算

(a) 證明 $\{X_n\}$ 為馬可夫鏈

由庫存更新式，$X_{n+1}$ 只由目前狀態 $X_n$ 和本期需求 $D_{n+1}$ 決定。由於需求序列相互獨立，

這符合馬可夫鏈的定義，因此 $\{X_n\}$ 是馬可夫鏈。

(b) 第一次補貨在第 2 期後發生的機率

「第一次補貨在第 2 期後發生」表示第 1 期結束時仍未補貨，而第 2 期結束時首次進入補貨狀態：

由 $X_0=3$，轉移矩陣中狀態 $3$ 的列為 $(0.2,0.3,0.4,0.1)$；狀態 $2$ 的列為 $(0.5,0.4,0.1,0)$。因此

(c) 在未缺貨補貨前先缺貨的機率

將狀態 $0,1$ 視為吸收狀態：到達狀態 $0$ 代表先缺貨，到達狀態 $1$ 代表先以未缺貨狀態補貨。暫態狀態為 $2,3$。

暫態到暫態的轉移矩陣，以及暫態到吸收狀態的轉移矩陣分別為

吸收機率矩陣為 $MR$。題目已給

此為考試封面頁資訊，非