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

本題考驗動態規劃在求最短路徑的應用。我們將從節點 O 開始，逐步計算到達各節點的最短距離，直到到達節點 T。

令 $d(v)$ 為從節點 O 到達節點 $v$ 的最短距離。
初始狀態：$d(O) = 0$，所有其他節點的距離設為無限大。

節點的順序可以根據與 O 的距離來推進，或者直接考慮所有節點。這裡我們採用依節點順序推進的方式：O -> {A, B, C} -> {D, E} -> T。

1. 從 O 出發：

   • $d(A) = d(O) + \text{dist}(O, A) = 0 + 4 = 4$
   • $d(B) = d(O) + \text{dist}(O, B) = 0 + 6 = 6$
   • $d(C) = d(O) + \text{dist}(O, C) = 0 + 5 = 5$

2. 考慮到達 D 的最短路徑：
   節點 D 可以從 A 或 B 到達。

   • 經由 A 到達 D：$d(A) + \text{dist}(A, D) = 4 + 7 = 11$
   • 經由 B 到達 D：$d(B) + \text{dist}(B, D) = 6 + 1 = 7$

核心觀念

最小成本流問題必須同時滿足：

1. 每個節點的流量守恆：
   $\text{流出量}-\text{流入量}=b_i.$
2. 每條弧的容量限制：
   $0\le x_{ij}\le u_{ij}.$
3. 目標是使總流量成本最小。

本題共有 5 個節點，因此流量平衡式的獨立秩為 $5-1=4$。若選出的基弧形成涵蓋所有節點的生成樹，則可判定為基本解。

---

(a) 線性規劃模型

令 $x_{ij}$ 表示弧 $i\to j$ 上的流量。圖中弧及其單位成本為：

$A\to B:2,\quad A\to C:6,\quad A\to D:5,$

$B\to C:3,\quad B\to D:5,\quad C\to E:3,\quad D\to E:4.$

因此目標函數為

$$\min z= 2x_{AB}+6x_{AC}+5x_{AD} +3x_{BC}+5x_{BD}+3x_{CE}+4x_{DE}.$$

各節點的流量平衡式如下。

節點 $A$：

$$x_{AB}+x_{AC}+x_{AD}=20.$$

節點 $B$：

$$x_{BC}+x_{BD}-x_{AB}=10.$$

節點 $C$：

$$x_{CE}-x_{AC}-x_{BC}=0.$$

節點 $D$：

$$x_{DE}-x_{AD}-x_{BD}=0.$$

節點 $E$：

$$x_{CE}+x_{DE}=30.$$

容量及非負限制為

$$0\le x_{AC}\le 10,$$ $$0\le x_{BC}\le 25,$$ $$x_{AB},x_{AD},x_{BD},x_{CE},x_{DE}\ge 0.$$

其中節點 $E$ 的平衡式與其他節點式具有一條線性相關關係，刪除該式仍不影響模型。

---

(b) 求可行流與判斷基本解

題目給定

$$x_{AD}=x_{BD}=x_{DE}=0.$$

代入各節點平衡式：

由節點 $A$：

$$x_{AB}+x_{AC}=20.$$

由節點 $B$：

$$x_{BC}-x_{AB}=10.$$

由節點 $C$ 與 $E$：

$$x_{CE}=x_{AC}+x_{BC}=30.$$

令

$$x_{AC}=t.$$

則

$$x_{AB}=20-t,$$ $$x_{BC}=30-t,$$ $$x_{CE}=30.$$

考慮容量限制：

$$0\le t\le 10,$$

且

$$x_{BC}=30-t\le25 \quad\Longrightarrow\quad t\ge5.$$

所以所有可行流可表示為

$$5\le t\le10.$$

題目後續所使用的成本最小基本可行流取 $t=5$，得到

$$x_{AB}=15,\quad x_{AC}=5,\quad x_{BC}=25,\quad x_{CE}=30.$$

連同題目給定的流量：

$$\begin{array}{c|c} \text{弧} & \text{流量}\\ \hline A\to B & 15\\ A\to C & 5\\ A\to D & 0\\ B\to C & 25\\ B\to D & 0\\ C\to E & 30\\ D\to E & 0 \end{array}$$

判斷其是否為基本解：

選取下列弧作為基弧：

核心觀念

本題考查單純形表的三項判讀：

• 最佳解：將非基底變數設為 $0$。
• 最佳目標值：讀取 $Z$ 列的 RHS。
• 資源影子價格：讀取對應鬆弛變數在 $Z$ 列的係數。
• 非基底變數的約化成本為 $0$，表示存在替代最佳解。

由圖中單純形表：

$$\begin{array}{c|c|rrrrrr|c} B.V.&Z&x_1&x_2&x_3&x_4&x_5&x_6&RHS\\ \hline Z&1&0&0&0&3&0&5&\theta\\ x_1&0&1&1&0&2&0&1&2\\ x_3&0&0&0&1&1&0&4&2\\ x_5&0&0&-2&0&-1&1&3&1 \end{array}$$

基底變數為 $x_1,x_3,x_5$，非基底變數為 $x_2,x_4,x_6$。

解題方法與計算

(a) 最佳值

將非基底變數設為 $0$：

$$x_2=x_4=x_6=0$$

因此目前的基底解為

$$x_1=2,\qquad x_3=2,\qquad x_5=1.$$

最佳目標值直接讀取 $Z$ 列的 RHS：

$$Z^*=\theta.$$

(b) 第一項資源的價值

第一項資源 $b_1$ 所對應的鬆弛變數是 $x_4$。在最佳單純形表中，$x_4$ 欄於 $Z$ 列的係數為 $3$，因此第一項資源的影子價格為

$$y_1=3.$$

本題考驗 KKT (Karush-Kuhn-Tucker) 条件在非線性規劃中的應用，特別是對於包含等式約束、不等式約束和變數範圍約束的問題。

核心觀念：
KKT 条件是局部最优解的必要條件（在某些正規性條件下，也是充分條件）。它結合了拉格朗日乘子法（處理等式約束）和對偶約束（處理不等式約束）。

(a) 寫下 KKT 条件

首先，我們需要將問題 $(P)$ 轉換成標準形式，即最小化目標函數，所有約束為 $\le$ 形式，且變數非負。
然而，題目要求的是最大化問題，並且 $y_1$ 可以是任意實數，$y_2 \le 0$。

我們將問題 $(P)$ 改寫為：
$\min \quad -4y_1 - 6y_2$
$\text{s.t.} \quad y_1 - y_2 \le 2 \quad (g_1)$
$\quad \quad 4y_1 + 5y_2 \le -3 \quad (g_2)$
$\quad \quad -2y_1 - y_2 \le 1 \quad (g_3)$
$\quad \quad -y_2 \le 0 \quad (g_4, \text{ 因為 } y_2 \le 0)$
$\quad \quad y_1 \in \mathbb{R}$

為了應用 KKT 条件，我們需要處理 $y_1 \in \mathbb{R}$ 的約束。這通常通過引入兩個非負變數來處理，或者在 KKT 条件中直接處理。
另一種方法是，將 $y_1$ 視為一個自由變數，這意味著它沒有下界。
然而，更常見的做法是將 $y_1$ 表示為兩個非負變數的差，例如 $y_1 = y_{1}^+ - y_{1}^-$, $y_{1}^+, y_{1}^- \ge 0$.
但是，題目要求的是 "Write down the KKT condition"，通常在處理自由變數時，其對應的 KKT 條件（拉格朗日乘子）是 0。

標準 KKT 条件的組成部分：

1. 梯度條件 (Stationarity): 目標函數的梯度與約束條件梯度的線性組合的梯度為零。
2. 原始可行性 (Primal Feasibility): 變數滿足所有約束。
3. 對偶可行性 (Dual Feasibility): 對應不等式約束的拉格朗日乘子（對偶變數）非負。
4. 互補鬆弛性 (Complementary Slackness): 每對約束和其對應的對偶變數，它們的乘積必須為零。

重新定義問題，使其更適合 KKT：
$\min \quad f(y_1, y_2) = -4y_1 - 6y_2$
$\text{s.t.} \quad g_1(y_1, y_2) = y_1 - y_2 - 2 \le 0$
$\quad \quad g_2(y_1, y_2) = 4y_1 + 5y_2 + 3 \le 0$
$\quad \quad g_3(y_1, y_2) = -2y_1 - y_2 - 1 \le 0$
$\quad \quad g_4(y_2) = -y_2 \le 0 \quad (\text{ 對應 } y_2 \le 0)$
$\quad \quad y_1 \in \mathbb{R}$

對於 $y_1 \in \mathbb{R}$，我們沒有一個明確的 $\le$ 或 $\ge$ 的約束。
在 KKT 条件中，對於自由變數 $y_1$，其對應的梯度條件要求該變數的偏導為零。
對於不等式約束 $g_i(y) \le 0$，我們引入對應的對偶變數 $\mu_i \ge 0$。
對於 $y_2 \le 0$ 的約束，我們可以寫成 $-y_2 \ge 0$ 或 $y_2 \le 0$.
如果寫成 $y_2 \le 0$, 則對應的約束是 $g_4(y_2) = y_2 \le 0$.
那麼拉格朗日乘子 $\mu_4 \ge 0$.

梯度：
$\nabla f = [-4, -6]$
$\nabla g_1 = [1, -1]$
$\nabla g_2 = [4, 5]$
$\nabla g_3 = [-2, -1]$
$\nabla g_4 = [0, 1]$ (這裡 $g_4$ 是關於 $y_2$ 的，所以 $\nabla g_4 = [0, 1]$)

KKT 条件：
存在 $\mu_1, \mu_2, \mu_3, \mu_4 \ge 0$ 使得：

1. 梯度條件 (Stationarity):

   • 對於 $y_1$: $\frac{\partial f}{\partial y_1} - \mu_1 \frac{\partial g_1}{\partial y_1} - \mu_2 \frac{\partial g_2}{\partial y_1} - \mu_3 \frac{\partial g_3}{\partial y_1} = 0$
     $-4 - \mu_1(1) - \mu_2(4) - \mu_3(-2) = 0$
     $-4 - \mu_1 - 4\mu_2 + 2\mu_3 = 0$
     注意： 對於自由變數 $y_1$，其 KKT 條件是 $\nabla f + \sum \mu_i \nabla g_i = 0$。
     所以，$\frac{\partial f}{\partial y_1} + \mu_1 \frac{\partial g_1}{\partial y_1} + \mu_2 \frac{\partial g_2}{\partial y_1} + \mu_3 \frac{\partial g_3}{\partial y_1} = 0$
     $-4 + \mu_1(1) + \mu_2(4) + \mu_3(-2) = 0$
     $-4 + \mu_1 + 4\mu_2 - 2\mu_3 = 0$

   • 對於 $y_2$:

本題要求將一個分段線性函數轉換為混合整數線性規劃 (MILP) 的形式。這通常通過引入二元變數來選擇正確的區段，並引入輔助變數來處理區段之間的轉換。

核心觀念：
分段線性函數的 MILP 表述。
目標是將非線性（分段）的成本函數線性化，並使用整數變數來控制激活哪個區段。

分段函數分析：
成本函數 $C(x)$ 定義在三個區段：

1. 區段 1: $0 < x < 100$. 成本 $C_1(x) = 5x$.
2. 區段 2: $100 \le x \le 180$. 成本 $C_2(x) = 500 + 8(x - 100)$.
   • 注意：當 $x=100$ 時，$C_1(100) = 5 \times 100 = 500$.
   • $C_2(100) = 500 + 8(100 - 100) = 500$.
   • 在 $x=100$ 處，兩個區段的成本是連續的。
   • 當 $x=180$ 時，$C_2(180) = 500 + 8(180 - 100) = 500 + 8 \times 80 = 500 + 640 = 1140$.
3. 區段 3: $x > 180$. 成本 $C_3(x) = 1140 + 12(x - 180)$.
   • 在 $x=180$ 處，$C_3(180) = 1140 + 12(180 - 180) = 1140$.
   • 在 $x=180$ 處，成本也是連續的。

MILP 表述方法：
我們需要引入二元變數來表示 $x$ 屬於哪個區段。
令：

• $y_1$：二元變數，如果 $0 < x < 100$，則 $y_1=1$，否則 $y_1=0$。
• $y_2$：二元變數，如果 $100 \le x \le 180$，則 $y_2=1$，否則 $y_2=0$。
• $y_3$：二元變數，如果 $x > 180$，則 $y_3=1$，否則 $y_3=0$。

由於 $x$ 必須屬於其中一個區段（假設 $x>0$），則 $y_1 + y_2 + y_3 = 1$。

處理區段的邊界和轉換：
MILP 的一個常見方法是使用 "big M" 方法，或者引入額外的輔助變數。

方法一：使用連續變數和二元變數
我們可以引入輔助變數來表示 $x$ 在每個區段內的「部分」。
令 $x_1, x_2, x_3$ 為 $x$ 在三個區段內的貢獻。
則 $x = x_1 + x_2 + x_3$.

• 區段 1 ($0 < x < 100$)：
  如果 $y_1=1$, 則 $0 \le x_1 \le 100$. 成本為 $5x_1$.
  如果 $y_1=0$, 則 $x_1=0$.
  這可以通過約束 $0 \le x_1 \le 100 y_1$ 來實現。

• 區段 2 ($100 \le x \le 180$)：
  如果 $y_2=1$, 則 $100 \le x_2 \le 180$. 成本為 $500 + 8(x_2 - 100)$.
  如果 $y_2=0$, 則 $x_2=0$.
  這比較複雜。通常我們將區段的範圍寫成相對於區段起始點的偏移量。
  令 $x_2'$ 為 $x$ 在區段 2 的部分，即 $x_2' = x - 100$.
  如果 $y_2=1$, 則 $0 \le x_2' \le 80$. 成本為 $500 + 8x_2'$.
  如果 $y_2=0$, 則 $x_2'=0$.
  約束：$0 \le x_2' \le 80 y_2$.
  同時，為了確保 $x_2'$ 是 $x$ 的一部分，我們需要 $x = x_1 + x_2 + x_3$.
  這個方法需要小心處理。

方法二：使用 "Big M" 和二元變數（更標準）
令 $x$ 為總生產量。
令 $y_1, y_2, y_3$ 為二元變數，表示 $x$ 屬於哪個區段。
$y_1 + y_2 + y_3 = 1$.

引入輔助變數 $x_{seg1}, x_{seg2}, x_{seg3}$，分別表示 $x$ 在每個區段的貢獻。
$x = x_{seg1} + x_{seg2} + x_{seg3}$.

1. 區段 1: $0 < x < 100$

   • 如果 $y_1=1$, 則 $0 < x_{seg1} < 100$. 成本 $5x_{seg1}$.
   • 如果 $y_1=0$, 則 $x_{seg1}=0$.
   • 約束：$0 \le x_{seg1} \le 100 y_1$. (這裡 $x_{seg1} \ge 0$ 是隱含的，因為 $x$ 是生產量)

2. 區段 2: $100 \le x \le 180$

   • 如果 $y_2=1$, 則 $100 \le x \le 180$.
   • 成本 $500 + 8(x - 100)$.
   • 我們可以引入一個變數 $x_{seg2}$ 來表示 $x$ 在區段 2 的「增量」。
   • 如果 $y_2=1$, 則 $x_{seg2}$ 代表 $x$ 在 $[100, 180]$ 範圍內的貢獻。
   • 更標準的做法： 引入變數 $x_{seg2}$ 代表 $x$ 在區段 2 的部分。
   • 如果 $y_2=1$, $x_{seg2}$ 應在 $[100, 180]$ 範圍內。
   • 如果 $y_2=0$, $x_{seg2}=0$.
   • 約束：$100 y_2 \le x_{seg2} \le 180 y_2$.
   • 成本：$500 y_2 + 8(x_{seg2} - 100 y_2)$.
     • 展開：$500 y_2 + 8x_{seg2} - 800 y_2 = 8x_{seg2} - 300 y_2$.
     • 這個形式可以嗎？
     • 如果 $y_2=1$, 成本是 $8x_{seg2} - 300$.
     • 如果 $x_{seg2}=100$, 成本 $800 - 300 = 500$.
     • 如果 $x_{seg2}=180$, 成本 $8 \times 180 - 300 = 1440 - 300 = 1140$.
     • 這與原始函數 $500 + 8(x_{seg2} - 100)$ 吻合。

3. 區段 3: $x > 180$

   • 如果 $y_3=1$, 則 $x > 180$.
   • 成本 $1140 + 12(x - 180)$.
   • 引入變數 $x_{seg3}$ 代表 $x$ 在區段 3 的部分。
   • 約束：$180 y_3 \le x_{seg3}$. (上界是無限大)
   • 成本：$1140 y_3 + 12(x_{seg3} - 180 y_3)$.
     • 展開：$1140 y_3 + 12x_{seg3} - 2160 y_3 = 12x_{seg3} - 1020 y_3$.
     • 如果 $y_3=1$, 成本 $12x_{seg3} - 1020$.
     • 如果 $x_{seg3}=180$, 成本 $12 \times 180 - 1020 = 2160 - 1020 = 1140$.
     • 這與原始函數 $1140 + 12(x_{seg3} - 180)$ 吻合。

整合起來：
變數：

• $x$：生產量（連續變數，非負）。
• $y_1, y_2, y_3$：二元變數，表示 $x$ 屬於哪個區段。
• $x_{seg1}, x_{seg2}, x_{seg3}$：輔助變數，表示 $x$ 在每個區段的貢獻。

約束條件：

1. 區段選擇：
   $y_1 + y_2 + y_3 = 1$
   $y_1, y_2, y_3 \in \{0, 1\}$

2. 總量關係：
   $x = x_{seg1} + x_{seg2} + x_{seg3}$

3. 區段 1 激活與約束：

   • $0 \le x_{seg1} \le 100 y_1$ (如果 $y_1=1$, $0 \le x_{seg1} \le 100$; 如果 $y_1=0$, $x_{seg1}=0$)

4. 區段 2 激活與約束：

   • $100 y_2 \le x_{seg2} \le 180 y_2$ (如果 $y_2=1$, $100 \le x_{seg2} \le 180$; 如果 $y_2=0$, $x_{seg2}=0$)

5. 區段 3 激活與約束：

   • $180 y_3 \le x_{seg3}$ (如果 $y_3=1$, $x_{seg3} \ge 180$; 如果 $y_3=0$, $x_{seg3}$ 必須為 0，這需要約束)
   • 為了確保 $y_3=0 \implies x_{seg3}=0$, 我們需要一個上界。
   • 假設 $x$ 的最大可能值不是無限大。如果 $x$ 的總量有界，例如 $x \le X_{max}$。
   • 那麼 $x_{seg3} \le X_{max} y_3$.
   • 如果 $x$ 的總量沒有明確的上界，我們需要找到一個足夠大的 M。
   • 例如，如果 $x$ 不超過 1000，則 $x_{seg3} \le 1000 y_3$.
   • 更嚴謹的做法：
     • 區段 1: $0 \le x_{seg1} \le 100 y_1$
     • 區段 2: $100 y_2 \le x_{seg2} \le 180 y_2$
     • 區段 3: $180 y_3 \le x_{seg3} \le M y_3$ (其中 M 是一個足夠大的數，例如 1000 或 2000)

目標函數：
最小化總成本 $C(x)$.
$C(x) = 5x_{seg1} + (8x_{seg2} - 300 y_2) + (12x_{seg3} - 1020 y_3)$
$\min \quad 5x_{seg1} + 8x_{seg2} - 300 y_2 + 12x_{seg3} - 1020 y_3$

檢查連續性：

• 當 $y_1=1, y_2=0, y_3=0$: $x = x_{seg1}$. $0 \le x_{seg1} \le 100$. Cost = $5x_{seg1}$.
• 當 $y_1=0, y_2=1, y_3=0$: $x = x_{seg2}$. $100 \le x_{seg2} \le 180$. Cost = $8x_{seg2} - 300$.
  • 如果 $x_{seg2}=100$, cost = $800 - 300 = 500$.
  • 如果 $x_{seg2}=180$, cost = $1440 - 300 = 1140$.
• 當 $y_1=0, y_2=0, y_3=1$: $x = x_{seg3}$. $x_{seg3} \ge 180$. Cost = $12x_{seg3} - 1020$.
  • 如果 $x_{seg3}=180$, cost = $2160 - 1020 = 1140$.

總量約束： $x = x_{seg1} + x_{seg2} + x_{seg3}$.
如果 $x=50$:

• 如果 $y_1=1$, $x_{seg1}=50$. 成本 $5 \times 50 = 250$. $x_{seg2}=0, x_{seg3}=0$.
• 如果 $y_2=1$, $x_{seg2}=50$. 但 $100 \le x_{seg2} \le 180$ 不滿足。
• 如果 $y_3=1$, $x_{seg3}=50$. 但 $180 \le x_{seg3}$ 不滿足。

這表示，我們需要確保 $x_{seg1}, x_{seg2}, x_{seg3}$ 的定義與 $y_i$ 的激活一致。

另一種標準表述：
令 $x$ 為總生產量。
引入二元變數 $y_1, y_2, y_3$ 表示 $x$ 屬於的區段。
$y_1 + y_2 + y_3 = 1$.

引入輔助變數 $x_{break1}, x_{break2}$ 來表示斷點。
$x_{break1} = 100$
$x_{break2} = 180$

成本函數 $C(x)$ 可以寫成：
$C(x) = 5x + \text{penalty}_1 + \text{penalty}_2$
其中 penalty 是為了懲罰 $x$ 超出某個區段的範圍。

更常見的方法：
令 $x$ 為總生產量。
引入 $y_1, y_2, y_3$ 二元變數。
$y_1+y_2+y_3=1$.

引入變數 $x_1, x_2, x_3$ 代表 $x$ 在各區段的貢獻。
$x = x_1 + x_2 + x_3$.

1. 區段 1 ($0 < x < 100$)

   • 如果 $y_1=1$, $0 \le x_1 \le 100$. Cost $5x_1$.
   • 如果 $y_1=0$, $x_1=0$.
   • 約束：$0 \le x_1 \le 100 y_1$.

2. 區段 2 ($100 \le x \le 180$)

   • 如果 $y_2=1$, $100 \le x \le 180$.
   • 成本 $500 + 8(x - 100)$.
   • 引入變數 $x_2$ 代表 $x$ 在區段 2 的部分。
   • 約束：$100 y_2 \le x_2 \le 180 y_2$.
   • 成本：$500 y_2 + 8(x_2 - 100 y_2) = 8x_2 - 300 y_2$.

核心觀念
此題考的是「零和遊戲的圖形法」：先消除可支配的策略以降低問題規模，再以玩家的混合機率 $p$（或 $q$）表示期望值，使對方的純策略使自己的最小收益最大化，從而求得最優混合策略與遊戲價值。

---

(a) Player A 的最優混合策略

設 $p$ 為 Player A 選取 $A_2$ 的機率（則 $1-p$ 為選取 $A_3$ 的機率）。
若 Player B 選 $B_1$，A 的期望收益為

[
E_{B_1}=6p+1(1-p)=5p+1
]

若 Player B 選 $B_4$，A 的期望收益為

[
E_{B_4}=1p+3(1-p)=3-2p
]

在最優策略下，Player B 會選擇使 A 的收益最小的那一欄，故 A 必使兩欄收益相等：

[
5p+1=3-2p\quad\Longrightarrow\quad 7p=2\quad\Longrightarrow\quad p=\frac{2}{7}
]

因此 Player A 的最優混合策略為

[
A_2:\frac{2}{7},\qquad A_3:\frac{5}{7}
]

【答案】
Player A 的最優混合策略：(A_2) 機率 (\frac{2}{7})，(A_3) 機率 (\frac{5}{7})。

---

(b) Player B 的最優混合策略