111 地方特考三等 工業工程 作業研究 考古題詳解

核心觀念

本題評量重點為「旅行推銷員問題」（Traveling Salesman Problem, TSP）的整數線性規劃模式（Dantzig-Fulkerson-Johnson 模式，簡稱 DFJ 模式），以及整數限制對線性規劃鬆弛（LP Relaxation）、多面體理論與演算法複雜度的核心影響：

1. DFJ 模式架構：

• 指派限制式（Assignment Constraints）：確保每個城市恰好進入一次、離開一次。
• 次迴圈消除限制式（Subtour Elimination Constraints, SEC）：防止形成多個相互不連通的小迴圈，強制形成單一的漢彌爾頓巡迴（Hamiltonian Cycle）。
• 雙元整數限制式（Binary Integrality Constraints）：定義邊的選取狀態。

2. 計算複雜度（Computational Complexity）：

• 包含整數限制的 TSP 為著名的 NP-hard 問題。
• 鬆弛整數限制後轉為線性規劃（LP），雖然理論上可在多項式時間內求解，但限制式數量達 $O(2^{|N|})$，實務上需配合分離演算法（Separation Algorithm）進行動態生成。

3. 線性規劃鬆弛理論（LP Relaxation Theory）：

• 可行解集合放大（$S_{\text{IP}} \subseteq S_{\text{LP}}$），鬆弛後的最佳目標值提供原極小化問題的嚴格下界（Lower Bound）。
• 由於 TSP 限制式矩陣不具備全麼模性質（Total Unimodularity, TUM），極值點解可能出現分數（Fractional Solutions），使解喪失物理巡迴意義。

解題方法

(一) 試分別說明式⑴、⑵、⑶、⑷之意義

• 式⑴：$\sum_{j\in N} x_{ij} = 1,\ \forall i \in N$（出度限制／離開限制，Out-degree Constraint）

• 意義：對每一個節點 $i$ 而言，從該節點出發前往其他節點的節線選取數量總和必須恰好等於 $1$。
• 物理意涵：推銷員離開每一個城市時，只能恰好前往另一個城市一次，確保每個節點的出度（Out-degree）等於 1。

• 式⑵：$\sum_{i\in N} x_{ij} = 1,\ \forall j \in N$（入度限制／進入限制，In-degree Constraint）

• 意義：對每一個節點 $j$ 而言，從其他節點進入該節點的節線選取數量總和必須恰好等於 $1$。
• 物理意涵：推銷員進入每一個城市時，只能恰好從另一個城市抵達一次，確保每個節點的入度（In-degree）等於 1。

[!NOTE] 式⑴與式⑵合稱為指派限制（Assignment Constraints）。若僅有式⑴、⑵與⑷，該模式退化為標準的「指派問題（Assignment Problem）」，此時雖保證各節點度數為 2，但容許出現若干分離的小迴圈（Subtours）。

• 式⑶：$\sum_{i\in S}\sum_{j\in S} x_{ij} \le |S|-1,\ \forall S \subset N,\ S \neq \varnothing,\ S \neq N$（次迴圈消除限制，Subtour Elimination Constraints, SEC）

• 意義：對於節點集合 $N$ 的任一非空真子集 $S$（節點數滿足 $2 \le |S| \le |N|-1$），兩端點皆落在子集 $S$ 內部的節線被選取之總數，上限為 $|S|-1$ 條。
• 物理意涵：若子集 $S$ 內部形成封閉的次迴圈，則該子集內的邊數必為 $|S|$ 條。本式限制邊數最多為 $|S|-1$，使任何小於全體城市的子集皆無法自我封閉成圈，從而強制作業員必須走完涵蓋所有節點 $N$ 的單一封閉巡迴（Hamiltonian Cycle）。

• 式⑷：$x_{ij} \in \{0,1\},\ \forall i,j \in N$（雙元整數限制，Binary Constraints）

• 意義：決策變數 $x_{ij}$ 只能取 0 或 1。
• 物理意涵：
• $x_{ij} = 1$：表示推銷員規劃的巡迴路線中包含從城市 $i$ 直達城市 $j$ 的節線。
• $x_{ij} = 0$：表示該路線未被選入巡迴路徑中。

(二) 若自模式中刪去式⑷而其餘不變，對求解難易程度有何影響？具體說明關鍵原因

• 對求解難易程度的影響： 問題性質從難以求解的 NP-hard 純整數規劃（IP），轉變為連續變數的線性規劃（LP）鬆弛問題。在理論計算複雜度上顯著降低；然而在實務計算上，依然無法直接套用一般單純形法一次求解，需要採用特殊演算法。

• 關鍵原因：

1. 計算複雜度降級（理論層面）： 原問題屬於組合最佳化中的 NP-hard 問題，無已知的多項式時間精確演算法。若刪除式⑷改為連續型變數（LP 鬆弛），由於線性規劃可使用橢球演算法（Ellipsoid Algorithm）或內點法（Interior Point Method）在多項式時間內完成求解，理論難度大幅下降。
2. 限制式數量呈指數級爆炸（實務求解層面）： 式⑶對所有非空真子集 $S$ 均需成立，其限制式數量高達 $2^{|N|} - 2$ 條。當城市數 $|N|$ 稍微增加（例如 $|N| = 50$），限制式數量超過 $10^{15}$ 條，記憶體無法容納全部限制式直接以標準單純形法列出矩陣求解。

核心觀念

1. 標準型式（Standard Form）與鬆弛變數（Slack Variables）： 線性規劃問題在應用單形法前，須將所有小於等於（$\leq$）之拘束條件引入非負鬆弛變數化為等式。本題具兩個 $\leq$ 限制式，分別引入鬆弛變數 $s_1 \ge 0, s_2 \ge 0$。
2. 單形表型式（Simplex Tableau Form）： 單形表包含目標函數列（Row 0）與拘束條件列，行欄位包含基底變數欄（Basis）、決策變數欄（$x, y$）、鬆弛變數欄（$s_1, s_2$）及常數項欄（RHS）。
3. 樞軸運算（Pivoting / Gauss-Jordan 列運算）與最小比值檢定（Minimum Ratio Test, MRT）：

• 當決定進基變數（Entering Variable）後，出基變數（Leaving Variable）由常數項除以該進基欄位正係數（$a_{ij} > 0$）之最小比值決定： $\theta = \min_{i} \left\{ \frac{\text{RHS}_i}{a_{ij}} \;\middle|\; a_{ij} > 0 \right\}$
• 藉由列運算將樞軸元素化為 1，並將同欄位其餘列之係數消去為 0，從而完成基底交換並保持基本可行解（Basic Feasible Solution, BFS）。

4. 指定基底變換： 題目要求使 $x$ 與 $y$ 二決策變數均成為基底變數，且註明「不必求解最佳解」，考查重點在於透過兩次迭代之樞軸運算，將初始基底 $\{s_1, s_2\}$ 依序替換為 $\{x, y\}$。

解題方法

(一) 寫出單形法的表格型式（Tableau Form）

1. 轉化為標準型式： 原限制式引入鬆弛變數 $s_1, s_2 \ge 0$： $-x + 4y + s_1 = 4$ $x + y + s_2 = 6$ $x, y, s_1, s_2 \ge 0$

原卷目標函數文字不全，設其一般式為 $\text{Minimize } Z = c_1 x + c_2 y$。改寫為列 0 標準式： $Z - c_1 x - c_2 y = 0$ （註：由於第 (二) 小題明確指示不需計算最佳解，僅要求使 $x, y$ 成為基底變數，故目標列係數不影響拘束條件列的基底交換與最小比值檢定）。

2. 建立初始單形表（Initial Tableau）： 以鬆弛變數 $s_1, s_2$ 為初始基底變數，對應單位矩陣：

(二) 以表格型式演算使 $x$ 與 $y$ 均成為基底變數

目標為使非基底變數 $x, y$ 全部進入基底，即最終基底變數集合為 $\{x, y\}$。依序進行兩次樞軸交換（此處採先讓 $y$ 進基、再讓 $x$ 進基；亦可先讓 $x$ 進基，結果相同）：

第一次迭代（Iteration 1）：令 $y$ 進入基底

1. 決定出基變數（最小比值檢定）：

• $s_1$ 列：$\frac{\text{RHS}}{y} = \frac{4}{4} = 1$
• $s_2$ 列：$\frac{\text{RHS}}{y} = \frac{6}{1} = 6$
• 最小比值為 1，對應 $s_1$ 列，故 $s_1$ 出基，樞軸元素為 $s_1$ 列之 $y$ 係數 $4$。

2. 高斯-喬登列運算：

• 新列 1（$y$ 列）$=$ 原列 1 $\div 4$： $0Z - \frac{1}{4}x + 1y + \frac{1}{4}s_1 + 0s_2 = 1$
• 新列 2（$s_2$ 列）$=$ 原列 2 $-$ 新列 1： $0Z + \left(1 - \left(-\frac{1}{4}\right)\right)x + (1 - 1)y + \left(0 - \frac{1}{4}\right)s_1 + 1s_2 = 6 - 1$ $\implies \frac{5}{4}x + 0y - \frac{1}{4}s_1 + 1s_2 = 5$
• 新列 0（$Z$ 列）$=$ 原列 0 $+ c_2 \times$ 新列 1： $1Z + \left(-c_1 - \frac{1}{4}c_2\right)x + 0y + \frac{1}{4}c_2 s_1 + 0s_2 = c_2$

第一次迭代完成後之單形表：

核心觀念

本題屬於作業研究中經典的**混合整數線性規劃（Mixed-Integer Linear Programming, MILP）**模式構建題，融合了兩大核心課題：

1. 固定成本問題（Fixed-Charge Problem）： 建置管線產生固定建置成本，不建置則無成本且無法輸送原料。此類「是否建置」的互斥決策必須以 0-1 二元變數（Binary Variable）連結連續採購量變數。
2. 一般分段線性成本函數（Piecewise Linear Cost Function）之線性化： 採購量分為「基本量以內」與「超過基本量」兩種不同單價。題目特別要求「除了正值之外，構建模式時不作其他假設」，代表無法預設單位成本大小關係（即可能為數量折扣 $c_{1i} > c_{2i}$，亦可能為累進費率 $c_{1i} < c_{2i}$）。若為非凸（Non-convex）的數量折扣結構，純連續變數會導致求解器跳過高單價區間而直接採用低單價區間，因此必須引入輔助二元變數強制要求：唯有在基本量全數購滿時，方能啟用超過基本量之採購。

解題方法

一、參數定義（已知常數）

依題意將已知條件符號化（均為正實數）：

• $D$：工廠所需原料液之已知總需求量（$\text{m}^3$），$D > 0$。
• 對於原料來源 $i \in \{1, 2, 3\}$：
• $F_i$：建置連接來源 $i$ 管線之已知固定建置成本，$F_i > 0$。
• $B_i$：來源 $i$ 設定之已知購買基本量（$\text{m}^3$），$B_i > 0$。
• $c_{1i}$：來源 $i$ 實際購買量小於或等於基本量時，每立方公尺之原料液成本，$c_{1i} > 0$。
• $c_{2i}$：來源 $i$ 實際購買量大於基本量時，超過部分每立方公尺之原料液成本，$c_{2i} > 0$。

二、合理假設與必要性說明（符合題目要求六）

1. 各來源之供應量上限假設： 題目未給定各來源的最大供應容量上限。由於工廠總需求量已知為 $D$ 且各項成本均為正值，工廠絕不可能向單一來源採購超過 $D$ 的原料液。因此，將單一來源的最大採購量上界設為 $D$（即 $M = D$），此假設為建構有限界限之線性限制式（Big-$M$ 限制式）所必需，兼具數學嚴謹性與緊緻性（Tight bound）。
2. 總需求採等式滿足： 由於所有建置與購買成本皆為正值，為避免多餘購置造成成本浪費，總採購量限制式採用等式 $\sum x_i = D$。

三、決策變數定義

針對每一來源 $i \in \{1, 2, 3\}$：

• $y_i \in \{0, 1\}$：0-1 二元變數，表示是否建置來源 $i$ 之管線。 $y_i = \begin{cases} 1, & \text{建置連接來源 } i \text{ 之管線} \\ 0, & \text{不建置} \end{cases}$
• $w_i \in \{0, 1\}$：0-1 二元變數，表示向來源 $i$ 購買之原料量是否已達且超過基本量 $B_i$。 $w_i = \begin{cases} 1, & \text{向來源 } i \text{ 之採購量已達基本量 } B_i \text{，可啟用超過基本量區間} \\ 0, & \text{向來源 } i \text{ 之採購量未超過基本量 } B_i \end{cases}$
• $x_{1i} \ge 0$：向來源 $i$ 採購且在基本量 $B_i$ 以內的數量（$\text{m}^3$）。
• $x_{2i} \ge 0$：向來源 $i$ 採購超出基本量 $B_i$ 的部分之數量（$\text{m}^3$）。
• 註：向來源 $i$ 之總採購量即為 $x_{1i} + x_{2i}$。

四、目標函數與限制式推導

1. 目標函數（Objective Function）： 最小化總成本，包含管線固定建置成本與原料採購變動成本： $\min Z = \sum_{i=1}^3 F_i y_i + \sum_{i=1}^3 \left( c_{1i} x_{1i} + c_{2i} x_{2i} \right)$ 意義：明確呈現題目（四）所述「總成本為購買原料與建置管線成本之總和」。

2. 總需求滿足限制式： 三個來源的採購總量必須剛好滿足工廠總需求量 $D$： $\sum_{i=1}^3 (x_{1i} + x_{2i}) = D$ 意義：確保原料供應符合工廠營運需求。

3. 基本量區間採購與管線建置邏輯限制式： $B_i w_i \le x_{1i} \le B_i y_i, \quad \forall i \in \{1, 2, 3\}$ 意義：

• 若不建置管線（$y_i = 0$），則 $x_{1i} = 0$。
• 若建置管線（$y_i = 1$），則基本量內採購量不可超過上限 $B_i$（$x_{1i} \le B_i$）。
• 若進入第二階段超額採購（$w_i = 1$），則強制第一階段必須買滿基本量（$x_{1i} \ge B_i$，配合上限即得 $x_{1i} = B_i$）。

4. 超過基本量採購與分段啟用邏輯限制式： $x_{2i} \le D w_i, \quad \forall i \in \{1, 2, 3\}$ 意義：

• 若採購量未達超額門檻（$w_i = 0$），則超額量強制為 0（$x_{2i} = 0$）。

核心觀念

最小擴充樹（minimum spanning tree, MST）是指：在一個連通、無向且各節線有長度的網路中，選出一組節線，使所有節點彼此連通且不形成迴圈，並使所選節線的總長度最小。

若網路有 $n$ 個節點，擴充樹恰有 $n-1$ 條節線。本題有 $5$ 個節點，因此最小擴充樹須選 $4$ 條節線。

解題方法：Kruskal 演算法

Kruskal 演算法依節線長度由小至大檢視，每次選取一條不會形成迴圈的節線；選滿 $n-1$ 條即完成。

步驟如下：

1. 將所有節線依長度由小至大排序。
2. 從最短的節線開始檢視。
3. 若加入該節線不會形成迴圈，就選取；若會形成迴圈，就略過。
4. 選取的節線達 $n-1$ 條時停止；所選節線即為最小擴充樹。

演算步驟

依圖中節線長度排序：