Abstract
本論文就一個被推廣化的線性規劃問題－－－多重選擇限制式之線性規劃問題(Mult-iple-Choice Linear Programming) 及多限制式之零壹背包問題(Multiconstraint Zero-OneKnapsack Problem)，以懲罰值 (Penalty)方法來解決之效率進行研究。“多重選擇限制式之線性規劃問題”與一般“線性規劃問題”不同之處在於變數被劃分成數組的狀態，同在一組的變數最多只能有一個衩選擇用來當做最後的解集合。此問題屬NP-hard 的問題，並曾於1983年清大工工所李俊民先生的碩士論文中討論過，其論文中並且透過比較各種所有可能的分支界限法 (Branch-and-Bound) 而得到一個有效解決此問題的計算方法。然其計算方法在每個分支界限法的節點(Node)上，均要使用簡捷法 (Simplex Method) 來解該相對的子問題，而使用簡捷法解問題是相當耗時的工作，如果該步驟的結果可以事先測知，值得使用簡捷法去做才做，將會使解決問題所需的時間大大減少。本論文就1983年論文的計算方法上，加入計算每個節點分支出去後所引發最少懲罰值的步驟，亦即估計由某一個節點分支出新的節點時目標值的損失。計算懲罰值只需些微的時間，但可使問題在未經簡捷法計算前就概略知道問題的答案。於是整個分支界限法的過程中，所有未被簡捷法計算的節點（即子問題）均可透過與現存最好的可行解比較而得知該節點是否值得用簡捷法去做。另外，由於在分支界限法過程中，新節點的產生是在原問題上加入新的限制式，此特殊結構使用對偶簡捷法 (Dual SimplexMethod)可迅速求得其解，所以本論文的計算方法中，除了第一個節點使用簡捷法外，其餘的節點均採用對偶簡捷法。一個更有效解決多重選擇限制式之線性規劃問題的計算方法於焉產生。關於多限制式之零壹背包問題，Shih於 1979 年曾提出一相當有效率的計算方法。本論文根據一個啟發式(Heuristic) 估計問題上限值的方法，並應用計算懲罰值的方法，發展出一分支界限法。由計算結果看出，此法在問題相當衡疏，限制式的數目很少及限制式歷邊的值不是非常大時，有相當令人滿意的計算時間。