113 年 國立中央大學工業管理研究所碩士班《作業研究》

本題要求使用高斯-約旦消去法 (Gauss-Jordan Elimination) 求取給定矩陣 A 的逆矩陣。此方法的核心是將原矩陣 A 與同階的單位矩陣 I 組合，形成增廣矩陣 [A|I]。接著，透過一系列合法的列運算，將增廣矩陣的左半部（即 A）轉換為單位矩陣 I。當 A 被轉換為 I 時，增廣矩陣的右半部就會自動轉換成 A 的逆矩陣 $A^{-1}$，即得到 [I|$A^{-1}$]。

步驟 (a): 設定增廣矩陣 [A|I]
將矩陣 A 與 4x4 的單位矩陣 I 組合：

$$[A|I] = \left[ \begin{array}{cccc|cccc} -3 & -0.5 & 1 & 1.5 & 1 & 0 & 0 & 0 \\ 1 & 0.25 & -0.5 & -0.25 & 0 & 1 & 0 & 0 \\ 3 & 0.25 & -0.5 & -1.25 & 0 & 0 & 1 & 0 \\ -3 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{array} \right]$$

步驟 (b) 與 (c): 執行列運算，將 [A|I] 轉換為 [I|$A^{-1}$]

為了簡化計算，我們優先處理數值較小的元素，並嘗試將主對角線元素變為 1。

1. 將第一列乘以 -1/3，使 $a_{11}$ 變為 1。
   $R_1 \leftarrow -\frac{1}{3}R_1$

   $$\left[ \begin{array}{cccc|cccc} 1 & 1/6 & -1/3 & -0.5 & -1/3 & 0 & 0 & 0 \\ 1 & 0.25 & -0.5 & -0.25 & 0 & 1 & 0 & 0 \\ 3 & 0.25 & -0.5 & -1.25 & 0 & 0 & 1 & 0 \\ -3 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{array} \right]$$

2. 將第一列減去第二列，使 $a_{21}$ 變為 0。
   $R_2 \leftarrow R_2 - R_1$

   $$\left[ \begin{array}{cccc|cccc} 1 & 1/6 & -1/3 & -0.5 & -1/3 & 0 & 0 & 0 \\ 0 & 0.25 - 1/6 & -0.5 - (-1/3) & -0.25 - (-0.5) & 0 - (-1/3) & 1 & 0 & 0 \\ 3 & 0.25 & -0.5 & -1.25 & 0 & 0 & 1 & 0 \\ -3 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{array} \right]$$

   計算：$0.25 - 1/6 = 1/4 - 1/6 = 3/12 - 2/12 = 1/12$
   $-0.5 + 1/3 = -1/2 + 1/3 = -3/6 + 2/6 = -1/6$
   $-0.25 + 0.5 = 0.25 = 1/4$

   $$\left[ \begin{array}{cccc|cccc} 1 & 1/6 & -1/3 & -0.5 & -1/3 & 0 & 0 & 0 \\ 0 & 1/12 & -1/6 & 1/4 & 1/3 & 1 & 0 & 0 \\ 3 & 0.25 & -0.5 & -1.25 & 0 & 0 & 1 & 0 \\ -3 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{array} \right]$$

3. 將第一列乘以 -3 並加到第三列，使 $a_{31}$ 變為 0。
   $R_3 \leftarrow R_3 - 3R_1$

   $$\left[ \begin{array}{cccc|cccc} 1 & 1/6 & -1/3 & -0.5 & -1/3 & 0 & 0 & 0 \\ 0 & 1/12 & -1/6 & 1/4 & 1/3 & 1 & 0 & 0 \\ 0 & 0.25 - 3(1/6) & -0.5 - 3(-1/3) & -1.25 - 3(-0.5) & 0 - 3(-1/3) & 0 & 1 & 0 \\ -3 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{array} \right]$$

   計算：$0.25 - 1/2 = 1/4 - 1/2 = -1/4$
   $-0.5 + 1 = 0.5 = 1/2$
   $-1.25 + 1.5 = 0.25 = 1/4$
   $1$

   $$\left[ \begin{array}{cccc|cccc} 1 & 1/6 & -1/3 & -0.5 & -1/3 & 0 & 0 & 0 \\ 0 & 1/12 & -1/6 & 1/4 & 1/3 & 1 & 0 & 0 \\ 0 & -1/4 & 1/2 & 1/4 & 1 & 0 & 1 & 0 \\ -3 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{array} \right]$$

4. 將第一列乘以 3 並加到第四列，使 $a_{41}$ 變為 0。
   $R_4 \leftarrow R_4 + 3R_1$

   $$\left[ \begin{array}{cccc|cccc} 1 & 1/6 & -1/3 & -0.5 & -1/3 & 0 & 0 & 0 \\ 0 & 1/12 & -1/6 & 1/4 & 1/3 & 1 & 0 & 0 \\ 0 & -1/4 & 1/2 & 1/4 & 1 & 0 & 1 & 0 \\ 0 & 0 + 3(1/6) & 1 + 3(-1/3) & 1 + 3(-0.5) & 0 + 3(-1/3) & 0 & 0 & 1 \end{array} \right]$$

   計算：$1/2$
   $1 - 1 = 0$
   $1 - 1.5 = -0.5 = -1/2$
   $-1$

   $$\left[ \begin{array}{cccc|cccc} 1 & 1/6 & -1/3 & -0.5 & -1/3 & 0 & 0 & 0 \\ 0 & 1/12 & -1/6 & 1/4 & 1/3 & 1 & 0 & 0 \\ 0 & -1/4 & 1/2 & 1/4 & 1 & 0 & 1 & 0 \\ 0 & 1/2 & 0 & -1/2 & -1 & 0 & 0 & 1 \end{array} \right]$$

5. 將第二列乘以 12，使 $a_{22}$ 變為 1。
   $R_2 \leftarrow 12R_2$

   $$\left[ \begin{array}{cccc|cccc} 1 & 1/6 & -1/3 & -0.5 & -1/3 & 0 & 0 & 0 \\ 0 & 1 & -2 & 3 & 4 & 12 & 0 & 0 \\ 0 & -1/4 & 1/2 & 1/4 & 1 & 0 & 1 & 0 \\ 0 & 1/2 & 0 & -1/2 & -1 & 0 & 0 & 1 \end{array} \right]$$

6. 將第二列減去第一列的 1/6，使 $a_{12}$ 變為 0。
   $R_1 \leftarrow R_1 - \frac{1}{6}R_2$

   $$\left[ \begin{array}{cccc|cccc} 1 & 0 & -1/3 - (1/6)(-2) & -0.5 - (1/6)(3) & -1/3 - (1/6)(4) & 0 - (1/6)(12) & 0 & 0 \\ 0 & 1 & -2 & 3 & 4 & 12 & 0 & 0 \\ 0 & -1/4 & 1/2 & 1/4 & 1 & 0 & 1 & 0 \\ 0 & 1/2 & 0 & -1/2 & -1 & 0 & 0 & 1 \end{array} \right]$$

   計算：$-1/3 + 1/3 = 0$
   $-0.5 - 0.5 = -1$
   $-1/3 - 4/6 = -1/3 - 2/3 = -1$
   $-2$

   $$\left[ \begin{array}{cccc|cccc} 1 & 0 & 0 & -1 & -1 & -2 & 0 & 0 \\ 0 & 1 & -2 & 3 & 4 & 12 & 0 & 0 \\ 0 & -1/4 & 1/2 & 1/4 & 1 & 0 & 1 & 0 \\ 0 & 1/2 & 0 & -1/2 & -1 & 0 & 0 & 1 \end{array} \right]$$

7. 將第二列乘以 1/4 加到第三列，使 $a_{32}$ 變為 0。
   $R_3 \leftarrow R_3 + \frac{1}{4}R_2$

本題要求使用單純形法中的「對偶單純形法」(Dual Simplex Method) 來求解一個最小化問題。對偶單純形法適用於初始基本可行解不滿足所有約束條件（尤其是當約束條件為 $\ge$ 或 $=$ 時），但其對偶問題的初始基本可行解是滿足對偶約束的。然而，在此問題中，我們可以直接將原始問題轉換為標準型，然後使用對偶單純形法。

首先，將最小化問題轉換為最大化問題，並將 $\ge$ 型約束轉換為 $\le$ 型約束。
原問題：
Minimize $Z = 4x_1 + 6x_2 + 8x_3$
subject to
$4x_1 - 2x_2 + 6x_3 \ge 8$ (1)
$3x_1 + 6x_2 + 3x_3 \ge 9$ (2)
$x_1, x_2, x_3 \ge 0$

轉換為最大化問題：
Maximize $Z' = -4x_1 - 6x_2 - 8x_3$
subject to
$-4x_1 + 2x_2 - 6x_3 \le -8$ (1')
$-3x_1 - 6x_2 - 3x_3 \le -9$ (2')
$x_1, x_2, x_3 \ge 0$

為了使用對偶單純形法，我們需要引入人工變數或轉換問題。對偶單純形法通常從對偶問題的初始基本可行解開始。然而，對於 $\ge$ 型約束，我們可以先引入一個「偽」的初始基底。

另一種常見的做法是，對於 $\ge$ 型約束，先引入一個鬆弛變數（slack variable）使其變為等式，然後再引入一個人工變數（artificial variable）以獲得初始基底。但對偶單純形法的優勢在於，我們可以處理原始問題的 $\ge$ 型約束，無需引入人工變數，只要確保對偶可行性即可。

我們將原問題改寫為標準型，並引入鬆弛變數 $s_1, s_2 \ge 0$：
Minimize $Z = 4x_1 + 6x_2 + 8x_3$
subject to
$4x_1 - 2x_2 + 6x_3 - s_1 = 8$ (1)
$3x_1 + 6x_2 + 3x_3 - s_2 = 9$ (2)
$x_1, x_2, x_3, s_1, s_2 \ge 0$

此時，目標函數 $Z$ 尚未表示成基底變數的函數。我們需要利用約束式來消去 $s_1, s_2$。
從 (1) 式，$s_1 = 4x_1 - 2x_2 + 6x_3 - 8$
從 (2) 式，$s_2 = 3x_1 + 6x_2 + 3x_3 - 9$

將 $Z$ 表示成所有變數的函數：
$Z = 4x_1 + 6x_2 + 8x_3$

在單純形表中，我們通常將目標函數寫成 $Z - (4x_1 + 6x_2 + 8x_3) = 0$。
但對偶單純形法更適合處理約束條件為負值的情況。

我們將問題改寫成對偶單純形法可以處理的形式。
將 $\ge$ 約束轉換為 $\le$ 約束，並引入鬆弛變數：
Minimize $Z = 4x_1 + 6x_2 + 8x_3$
subject to
$-4x_1 + 2x_2 - 6x_3 + s_1 = -8$ (1')
$-3x_1 - 6x_2 - 3x_3 + s_2 = -9$ (2')
$x_1, x_2, x_3, s_1, s_2 \ge 0$

在此形式下，$s_1$ 和 $s_2$ 是鬆弛變數，但約束右側為負，這正是對偶單純形法處理的初始狀態。
我們的目標是使右側的負值消失，同時保持目標函數的最小化。

初始單純形表：
基底變數為 $s_1, s_2$。
目標函數為 $Z - 4x_1 - 6x_2 - 8x_3 = 0$。

基底 (Basis)	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	RHS
$s_1$	-4	2	-6	1	0	-8
$s_2$	-3	-6	-3	0	1	-9
Z	-4	-6	-8	0	0	0

對偶單純形法步驟：

1. 選擇離基變數 (Leaving Variable): 選擇 RHS (常數項) 中值最負的行。在此表中，$-9$ 是最負的值，所以 $s_2$ 是離基變數。

2. 選擇入基變數 (Entering Variable): 計算比率：目標函數列 (Z 列) 的係數絕對值除以離基變數所在列的係數（若該係數為負）。

   • 對 $x_1$: $|-4| / |-3| = 4/3$
   • 對 $x_2$: $|-6| / |-6| = 1$
   • 對 $x_3$: $|-8| / |-3| = 8/3$
     選擇最小的比率，即 $1$。因此，$x_2$ 是入基變數。

3. 進行列運算: 將 $s_2$ 替換為 $x_2$ 作為基底變數。新的 $s_2$ 列（現在是 $x_2$ 列）的支點元素是 $-6$。
   將第二列乘以 $-1/6$，使支點元素變為 1。
   $R_2 \leftarrow R_2 / (-6)$

   $$\left[ \begin{array}{ccccc|c} -4 & 2 & -6 & 1 & 0 & -8 \\ 1/2 & 1 & 1/2 & 0 & -1/6 & 3/2 \\ -4 & -6 & -8 & 0 & 0 & 0 \end{array} \right]$$

   現在，用新的 $x_2$ 列（第二列）來更新其他列，使 $x_2$ 列以外的 $x_2$ 係數變為 0。

   • $R_1 \leftarrow R_1 - 2R_2$:
     $[-4, 2, -6, 1, 0, -8] - 2 \times [1/2, 1, 1/2, 0, -1/6, 3/2]$
     $= [-4, 2, -6, 1, 0, -8] - [1, 2, 1, 0, -1/3, 3]$

核心觀念

本題採用先列舉完整路線，再選擇最佳路線的建模方法。每條路線的取貨價值、重量與燃油成本都可事先算好，模型只須決定選哪一條。

John 的實際收入為：

$$\text{實際收入} = 0.02\times\text{取貨總價值} - \text{路線總燃油成本}.$$

「由節點 1 出發並返回、其他節點至多拜訪一次、到訪即全數取貨」由候選路線的建構方式保證；「每天選一條路線」與「不超過載重」則由限制式保證。

解題方法

步驟一：建構節點序列集合 $S$

令供應商節點集合為 $C=N\setminus\{1\}$。每條候選序列寫成：

$$s=(1,i_1,i_2,\ldots,i_k,1), \qquad 1\leq k\leq |C|,$$

其中 $i_1,\ldots,i_k\in C$，且彼此不同。

因此，$S$ 應涵蓋：

1. 所有非空的供應商節點子集合：John 不必拜訪全部供應商。
2. 各子集合的所有拜訪順序：拜訪順序決定行經哪些連線，進而決定燃油成本。
3. 每條序列都從節點 1 出發，最後返回節點 1：節點 1 僅作為起點與終點，其他節點不得重複。

這樣才能確保最佳路線包含在 $S$ 中。若只列出部分路線，模型求出的僅是該候選集合中的最佳解，不能保證是原問題的最佳解。此處先列舉符合路線結構的序列，載重是否合格交由步驟四判斷。

**簡例：**若 $N=\{1,2,3\}$，則可取：

$$S= \left\{ (1,2,1),\, (1,3,1),\, (1,2,3,1),\, (1,3,2,1) \right\}.$$

題目設定燃油成本與方向無關，即 $F_{i,j}=F_{j,i}$，因此：

$$F_{1,2}+F_{2,3}+F_{3,1} = F_{1,3}+F_{3,2}+F_{2,1}.$$

所以 $(1,2,3,1)$ 與 $(1,3,2,1)$ 的取貨價值、重量及燃油成本均相同。兩條都保留仍然正確；為縮小集合，也可只保留其中一條。

一般而言，一條路線與其完全反向路線等價。但拜訪相同節點的不同順序，若不是完全反向，便不保證燃油成本相同，不能一概刪除。

步驟二：計算各序列的三個參數

對每條 $s=(1,i_1,\ldots,i_k,1)$，以 $V_s^{\text{sequence}}$、$W_s^{\text{sequence}}$、$F_s^{\text{sequence}}$ 表示其參數。

（一）取貨總價值

每個到訪的供應商都必須全數取貨，因此：

$$V_s^{\text{sequence}} = \sum_{r=1}^{k}V_{i_r}.$$

節點 1 沒有待取貨零件，不列入加總。

（二）取貨總重量

同理：

$$W_s^{\text{sequence}} = \sum_{r=1}^{k}W_{i_r}.$$

途中只有取貨，回到節點 1 才交貨，因此車上載重隨取貨累加。只要總取貨重量不超過載重上限，途中各階段也都不會超載。

（三）路線總燃油成本

令 $i_0=i_{k+1}=1$，逐段加總：

$$F_s^{\text{sequence}} = \sum_{r=0}^{k}F_{i_r,i_{r+1}}.$$

此式包括出發路段、供應商之間的移動，以及最後返回節點 1 的路段。

例如 $s=(1,3,5,1)$：