111年 - 111 地方政府特種考試_三等_工業工程：作業研究#112622

科目：作業研究 | 年份：111年 | 選擇題數：0 | 申論題數：9

試卷資訊

所屬科目：作業研究

選擇題 (0)

申論題 (9)

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

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

(三)有無自模式中刪去式⑷，對於求解得到之最佳解有何影響？具體說明其影響以及原因。（10 分）

(一)試寫出此問題單形法（simplex method）的表格型式（tableau form）。（5 分）

(二)試以表格型式進行演算，使得x與y二個決策變數均成為基底變數（basic variable）。請完整寫出以表格型式之演算過程，不必求解最佳解。（20 分）

三、某工廠欲尋求建置管線以購買原料液的最低總成本方案。所需要之總量已知為T立方公尺。可能的原料來源有3處，編號1至 3。與成本相關的因素如下（以下所有說明中， ∈ {1,2,3}）：
1.建置連接來源之管線時，建置成本已知為Pi 。
2.每一原料來源均設定有一個已知的購買基本量Fi 。實際購買量少於或等於基本量時，每立方公尺原料液之成本已知為Bi ；實際購買量大於基本量時，超過的部分每立方公尺原料液之成本已知為Ai 。
3.若決定不向其中某些原料來源購買，則不必負擔相對應的管線建置成本。
4.總成本為購買原料與建置管線之成本的總和。
試構建線性數學模式以描述上述問題。請注意：
1.必須明確說明所有決策變數的定義。
2.必須明確說明目標函數以及限制式之意義。
3.模式可使用整數決策變數。
4.模式必須為線性。
5.以上T、Pi、Fi、Ai 、Bi 等均為已知值。這些值除了均為正值之外，構建模式時均不作其他假設。
6.若認為題目條件不足，可自行作合理假設，但必須明確說明條件，並說明該條件之必要性。（25 分）

(一)請說明最小擴充樹問題之定義。（5 分）

(二)試說明任一種最小擴充樹問題之求解演算法。請明確列出其步驟。（10 分）

(三)試求解下圖網路之最小擴充樹，請寫出完整的演算步驟。圖中共有5個節點（node），編號1至 5。各節線（arc）一側之數字即為節線之長度，例如節線（1,2）之長度為3。（10 分）