110 高普考高考三級 工業工程 作業研究 考古題詳解

核心觀念

Dijkstra 標籤設定法用來求解從指定起點到各節點的最短距離。演算法將節點分為：

• 永久節點：最短距離已確定，距離標籤不再改變。
• 暫時節點：目前已知的距離上界，之後仍可能更新。

每次選取暫時節點中標籤最小者，將其設為永久節點，再以該節點更新相鄰暫時節點的標籤。此方法成立的前提是節線長度皆為非負值；若有負值節線，已永久化的標籤仍可能被更短路徑改善，因而造成錯誤。

（一）標籤設定法步驟

設起點為 $s$，節點集合為 $V$，節線 $(i,j)$ 的長度為 $c_{ij}$。

1. 初始化：將起點設為永久節點，標籤設為 $d(s)=0$；其餘節點設為暫時節點，標籤設為 $d(j)=\infty$。
2. 更新相鄰標籤：對每一條由永久節點 $i$ 指向暫時節點 $j$ 的節線，若 $d(i)+c_{ij}<d(j),$ 則更新 $d(j)=d(i)+c_{ij}$，並記錄前置節點為 $i$。
3. 選取最小標籤：在所有暫時節點中，選取標籤最小者 $k$，將 $k$ 設為永久節點。
4. 重複更新與選取：以新永久節點 $k$ 更新其相鄰暫時節點的標籤，並重複步驟 3，直到所有可達節點皆成為永久節點，或指定終點成為永久節點。
5. 回溯路徑：由終點沿記錄的前置節點回溯至起點，即得最短路徑；各節點的永久標籤即為最短距離。

（二）含負值節線時造成錯誤的網路

設計網路

以下網路有 4 個節點、3 條有向節線，起點為 $S$：

 2
 S ─────→ A
 │ │
 5 │ −4 │
 ↓ ↓
 B ─────→ T
 2

節線及長度為：

$c_{SA}=2,\qquad c_{SB}=5,\qquad c_{AT}=-4,\qquad c_{BT}=2.$

此網路含有負值節線 $A\to T$，但沒有迴圈，因此不含負值長度迴圈。

依標籤設定法計算

起點 $S$ 為永久節點，初始標籤為 $d(S)=0$；其餘節點標籤皆為 $\infty$。

步驟	永久節點	暫時節點標籤（前置節點）
初始化	$S(0)$	$A=\infty,\ B=\infty,\ T=\infty$
由 $S$ 更新	$S(0)$	$A=2(S),\ B=5(S),\ T=\infty$
選最小標籤	$S(0), A(2)$	$B=5(S),\ T=-2(A)$
選最小標籤	$S(0), A(2), T(-2)$	$B=5(S)$
選取 $B$	$S(0), A(2), T(-2), B(5)$	—

由 $S$ 更新後，$A$ 的標籤為 $2$，$B$ 的標籤為 $5$。選取 $A$ 為永久節點後，沿 $A\to T$ 更新：

$d(T)=d(A)+c_{AT}=2+(-4)=-2.$

因此接著選取 $T$，標籤為 $-2$，並將其設為永久節點。之後 $B$ 成為永久節點，然而本網路沒有由 $B$ 通往已永久化節點 $T$ 以外的節線，故標籤不再變動。

錯誤所在及正確結果

核心觀念

本題考「指派問題」的線性整數規劃建模。每艘船最多分配一個席位，每個席位最多分配給一艘船；船舶也可以不獲分配席位，因此船舶指派限制是不等式。另以二元變數表示船舶是否獲得任何席位，再用線性限制表達特殊船舶 $a$ 與 $b$ 不可同時獲得席位的條件。

解題方法

（一）決策變數

對每艘船 $i=1,\ldots,n$ 與席位 $j=1,\ldots,m$，定義

$$x_{ij}= \begin{cases} 1, & \text{船舶 }i\text{ 分配至席位 }j,\\ 0, & \text{否則。} \end{cases}$$

另定義船舶是否獲得席位的二元變數：

$$y_i= \begin{cases} 1, & \text{船舶 }i\text{ 獲得任一席位},\\ 0, & \text{船舶 }i\text{ 未獲得席位。} \end{cases}$$

其中 $i=1,\ldots,n$。以 $y_i$ 表示船舶是否獲分配，可直接將「$a$ 與 $b$ 不可二者均獲得席位」寫成線性限制。

（二）目標函數

最大化所有已分配船舶所產生的總效益：

$$\max \quad \sum_{i=1}^{n}\sum_{j=1}^{m} F_{ij}x_{ij}.$$

當船舶 $i$ 分配至席位 $j$ 時，$x_{ij}=1$，目標函數便計入效益 $F_{ij}$；未分配時則不計入。

（三）限制式

1. 每艘船至多分配一個席位

$$\sum_{j=1}^{m}x_{ij}\leq 1, \qquad i=1,\ldots,n.$$

此限制允許船舶不獲分配席位，也避免同一艘船占用多個席位。

2. 每個席位至多分配給一艘船

$$\sum_{i=1}^{n}x_{ij}\leq 1, \qquad j=1,\ldots,m.$$

此限制確保每個席位不會同時安排多艘船。

3. 連結席位分配與是否獲分配

核心觀念

本題考查單形法（simplex method）的表列運算，以及線性規劃對偶問題的建立。將每個「$\leq$」限制式加入鬆弛變數後，以原點為初始可行基底解，再依目標列的檢定數選入變數、依最小比值選出變數。當目標列不再有可改善目標值的非基底變數時，即得最佳解。

採用 $C_j-Z_j$ 列表示檢定數：最大化問題中，若所有非基底變數的 $C_j-Z_j\leq 0$，則目前基底解為最佳解。

解題方法：單形表列運算

令 $s_1,s_2$ 為兩個限制式的鬆弛變數，標準式為

$$\begin{aligned} 3x_1+x_2+x_3+s_1&=60,\\ 2x_1-2x_2+4x_3+s_2&=20,\\ x_1,x_2,x_3,s_1,s_2&\geq 0. \end{aligned}$$

初始基底為 $s_1,s_2$，目標係數為 $C_j=(2,-1,1,0,0)$。初始表如下：

$C_B$	基底變數	$b$	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$\theta$（選 $x_1$）
	$C_j$		$2$	$-1$	$1$	$0$	$0$
$0$	$s_1$	$60$	$3$	$1$	$1$	$1$	$0$	$20$
$0$	$s_2$	$20$	$2$	$-2$	$4$	$0$	$1$	$10$
	$Z_j$	$0$	$0$	$0$	$0$	$0$	$0$
	$C_j-Z_j$		$2$	$-1$	$1$	$0$	$0$

$C_j-Z_j$ 中最大的正值為 $x_1$ 欄的 $2$，故令 $x_1$ 入基。比值檢定為 $60/3=20$、$20/2=10$，最小非負比值為 $10$，故 $s_2$ 出基，樞紐元素為 $2$。

以第二列除以 $2$，再用新第二列消去第一列的 $x_1$，得到第一回合表：

$C_B$	基底變數	$b$	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$
	$C_j$		$2$	$-1$	$1$	$0$	$0$
$0$	$s_1$	$30$	$0$	$4$	$-5$	$1$	$-\frac32$
$2$	$x_1$	$10$	$1$	$-1$	$2$	$0$	$\frac12$
	$Z_j$	$20$	$2$	$-2$	$4$	$0$	$1$
	$C_j-Z_j$		$0$	$1$	$-3$	$0$	$-1$

此時 $x_2$ 的檢定數為正，故令 $x_2$ 入基。比值檢定只採用 $x_2$ 欄係數為正的列：第一列為 $30/4=15/2$；第二列係數為 $-1$，不列入比值檢定。因此 $s_1$ 出基，樞紐元素為 $4$。

將第一列除以 $4$，再以新第一列消去第二列的 $x_2$，得到第二回合表：

核心觀念

本題考查將單一機臺的排序問題轉換為旅行推銷員問題（Traveling Salesman Problem, TSP）。每批貨件的處理時間 $T_i$ 不受順序影響，所有貨件的總處理時間固定；工作順序所影響的是相鄰貨件之間的機臺清理時間 $R_{ij}$。因此，極小化總完成時間等同於極小化所選工作順序中的清理時間總和。

（一）旅行推銷員問題的定義

給定若干節點及任兩節點間的旅行成本，旅行推銷員須從某一節點出發，恰好拜訪每個節點一次，最後返回出發節點，並使整趟巡迴路線的總成本最小。

（二）轉換為旅行推銷員問題

解題方法

原機臺工作順序是一條由 $N$ 批貨件構成的排列。相鄰貨件 $i$ 與 $j$ 之間的清理時間為 $R_{ij}$，所以可用節點代表貨件，並以節線長度代表相鄰貨件的清理時間。

但原問題在開始工作前及完成工作後都沒有清理時間；標準 TSP 則要求路線返回出發節點。為避免返回成本影響原問題，加入一個虛擬節點，並令其與所有貨件間的往返節線長度為零。

節點

建立 $N+1$ 個節點：

• 每一個實際節點 $i$ 代表第 $i$ 批貨件，$i=1,\ldots,N$；
• 另設一個虛擬節點 $0$，代表機臺工作開始前及全部工作完成後的邊界。

節線長度

對任兩個不同的實際貨件節點 $i$、$j$，設定由 $i$ 至 $j$ 的有向節線長度為：

$$c_{ij}=R_{ij}.$$

若清理時間依先後順序而異，則須使用有向節線；不要求 $R_{ij}=R_{ji}$。

對虛擬節點與各實際節點之間，設定：

$$c_{0i}=c_{i0}=0,\qquad i=1,\ldots,N.$$