零壹整數規劃問題新解法之研究: 位置搜尋法之建立輿評估

Abstract

本研究係針對雙元整數規劃問題，提出一種新的演算方法。雙元整數規劃問題是一個 具有特殊形式的線性規劃問題，它限制所有的雙數值只能是0或1。此類問題之應用極 廣，舉凡集合涵蓋(Set Covering)或集合分割(Set Partitioning)或其他路網(Netwo rk)、路徑(Routing)等類型的問題皆屬之。另外整數規劃問題亦可依一定的方式轉換 成雙元整數規劃問題，因此求解雙元整數規劃問題之演算法一直是重要的研究課題。 本研究提出之「位置搜尋法」(Location Search Algorithm) 係採用分技定限(Branc h and Bound)的架構去設計一個新的求解雙元整數規劃問題的演算法，但捨棄傳統BA LAS 演算法以變數值為0或1作分枝依據的方式, 而改以零壹數值出現的位置作為設計 新演算法的依據。其在搜尋過程中，考慮限制式條件約束可行解零或壹出現位置的分 枝範圍，然後依縱向搜尋(Depth First Search)之原則巡迴(Traverse)所有的分枝。 在巡迴的過程中運用分枝定限的架構，如此可避免巡迴所有的可能組合。 位置搜尋法和BALAS 演算法皆為加法性演算法，且在架構上十分相似，因此本研究用 BALAS 演算法作為新演算法的比較評估依據，以進一步膫解新演算法之特性。 依據840 個演算例題及9 個實例的測試結果顯示；當係數矩陣中之元素皆為正時或係 數矩陣之密度大時，位置搜尋法之解題效率優于BALAS 演算法。又根據結果分析顯示 ：位置搜尋法第一次搜尋所得之可行解與最佳解比較，平均誤差在9%以內；位置搜尋 法平均只搜尋二至三個可行解便可得最佳解，因此位置搜尋法亦可作為求近似解之啟 發式方法架構。