地特三等申論題
111年
[工業工程] 作業研究
第 一 題
📖 題組：
旅行推銷員問題（travelling salesman problem）可以用下列整數規劃模式表現之。其中符號定義如下： $x_{ij}$為雙元整數變數，若節線（i, j）有納入路線中，則$x_{ij} = 1$，否則$x_{ij} = 0$。 $c_{ij}$為節線（i, j）之長度。 $V$為所有節點所成的集合。 $S$為$V$中之若干節點所成的集合，$|S|$為集合$S$之元素個數。 以下為一個表現旅行推銷員問題之整數規劃模式： Minimize $\sum_{i\in V} \sum_{j\in V} c_{ij}x_{ij}$ ⑴ Subject to $\sum_{j\in V} x_{ij} = 1, \quad i \in V$ ⑵ $\sum_{i\in V} x_{ij} = 1, \quad j \in V$ ⑶ $\sum_{i\in S} \sum_{j\in S} x_{ij} \leq |S| - 1, \quad \forall S \subset V, S \neq \phi, S \neq V$ ⑷ $x_{ij} \in \{0,1\} \quad \forall i, j \in V$
旅行推銷員問題（travelling salesman problem）可以用下列整數規劃模式表現之。其中符號定義如下： $x_{ij}$為雙元整數變數，若節線（i, j）有納入路線中，則$x_{ij} = 1$，否則$x_{ij} = 0$。 $c_{ij}$為節線（i, j）之長度。 $V$為所有節點所成的集合。 $S$為$V$中之若干節點所成的集合，$|S|$為集合$S$之元素個數。 以下為一個表現旅行推銷員問題之整數規劃模式： Minimize $\sum_{i\in V} \sum_{j\in V} c_{ij}x_{ij}$ ⑴ Subject to $\sum_{j\in V} x_{ij} = 1, \quad i \in V$ ⑵ $\sum_{i\in V} x_{ij} = 1, \quad j \in V$ ⑶ $\sum_{i\in S} \sum_{j\in S} x_{ij} \leq |S| - 1, \quad \forall S \subset V, S \neq \phi, S \neq V$ ⑷ $x_{ij} \in \{0,1\} \quad \forall i, j \in V$
📝 此題為申論題，共 3 小題
小題 (一)
試分別說明式⑴、⑵、⑶、⑷之意義。（10 分）
思路引導 VIP
看到此題應立刻辨識出這是旅行推銷員問題（TSP）經典的 DFJ（Dantzig-Fulkerson-Johnson）整數規劃模型。解題時需依數學規劃的結構，依序點出「目標函數（最小化總成本）」、「節點進出限制（確保每個節點進出各一次）」以及最核心的「子巡迴消除限制式（Subtour Elimination Constraints，防止形成不連通的小迴圈）」。
小題 (二)
若自模式中刪去式⑷而其餘不變，對求解難易程度有何影響？具體說明關鍵原因。（5 分）
思路引導 VIP
考生看到此題應立刻聯想到 TSP 的數學模型結構。式⑷為「消除子迴路限制（Subtour Elimination Constraints）」，若刪除此條件，原問題將退化為「指派問題（Assignment Problem）」。接著需點出指派問題具有「完全單模矩陣（Totally Unimodular）」的特性，可用多項式時間求解，故難度大幅降低。
小題 (三)
有無自模式中刪去式⑷，對於求解得到之最佳解有何影響？具體說明其影響以及原因。（10 分）
思路引導 VIP
看到此題，應立即辨識出此為標準的旅行推銷員問題（TSP）整數規劃模型，其中式⑷為「次迴路消除限制式（Subtour Elimination Constraints）」。答題時需點出若刪去此式，問題將退化為「指派問題（Assignment Problem）」，進而說明「次迴路（Subtour）」產生的現象及對目標函數值的影響（成為原問題之下界）。