民國111年 地方三等 工業工程 作業研究收錄考選部官方試題，共 4 題可線上瀏覽，考選部未公告本科目答案。
旅行推銷員問題（travelling salesman problem）可以用下列整數規劃模式 表現之。其中符號定義如下： ݔ為雙元整數變數，若節線（i, j）有納入路線中，則ݔ= 1，否則ݔ= 0。 ܿ為節線（i, j）之長度。 ܸ為所有節點所成的集合。 ܵ為ܸ中之若干節點所成的集合，|ܵ|為集合ܵ之元素個數。 以下為一個表現旅行推銷員問題之整數規劃模式： Minimize ∑ ∑ ܿݔ ∈ ∈ ⑴ Subject to ∑ ݔ ∈ = 1, ݅∈ܸ ⑵ ∑ ݔ ∈ = 1, ݆∈ܸ ⑶ ∑ ∑ ݔ ∈ௌ ∈ௌ ≤|ܵ| −1, ∀ܵ⊂ܸ, ܵ≠߶, ܵ≠ܸ ⑷ ݔ߳{0,1} ∀݅, ݆∈ܸ 試分別說明式⑴、⑵、⑶、⑷之意義。（10 分） 若自模式中刪去式⑷而其餘不變，對求解難易程度有何影響？具體說 明關鍵原因。（5 分） 有無自模式中刪去式⑷，對於求解得到之最佳解有何影響？具體說明 其影響以及原因。（10 分）
考慮下列線性規劃問題（linear programming problem）： Minimize ݔ Subject to −ݔ+ 4ݕ≤4 ݔ+ ݕ≤6 ݔ≥0, ݕ≥0 試寫出此問題單形法（simplex method）的表格型式（tableau form）。 （5 分） 試以表格型式進行演算，使得x 與y 二個決策變數均成為基底變數 （basic variable）。請完整寫出以表格型式之演算過程，不必求解最佳 解。（20 分）
某工廠欲尋求建置管線以購買原料液的最低總成本方案。所需要之總量 已知為ܶ立方公尺。可能的原料來源有3 處，編號1 至3。與成本相關的 因素如下（以下所有說明中，݅∈{1,2,3}）： 建置連接來源݅之管線時，建置成本已知為ܲ。 每一原料來源均設定有一個已知的購買基本量ܨ。實際購買量少於或 等於基本量時，每立方公尺原料液之成本已知為ܣ；實際購買量大於 基本量時，超過的部分每立方公尺原料液之成本已知為ܤ。 若決定不向其中某些原料來源購買，則不必負擔相對應的管線建置成 本。 總成本為購買原料與建置管線之成本的總和。 試構建線性數學模式以描述上述問題。請注意： 必須明確說明所有決策變數的定義。 必須明確說明目標函數以及限制式之意義。 模式可使用整數決策變數。 模式必須為線性。 以上ܶ、ܲ、ܨ、ܣ、ܤ等均為已知值。這些值除了均為正值之外，構 建模式時均不作其他假設。 若認為題目條件不足，可自行作合理假設，但必須明確說明條件，並 說明該條件之必要性。 （25 分）
請回答下列有關最小擴充樹問題（minimum spanning tree problem）： 請說明最小擴充樹問題之定義。（5 分） 試說明任一種最小擴充樹問題之求解演算法。請明確列出其步驟。（10分） 試求解下圖網路之最小擴充樹，請寫出完整的演算步驟。圖中共有5 個節點（node），編號1 至5。各節線（arc）一側之數字即為節線之長 度，例如節線（1,2）之長度為3。（10 分）