Abstract
當我們想如何以最有效的方式使用資源時，我們不可避免的就會碰到多維度背包問題。這是一個重要的離散尋優問題(discrete optimizationproblem) 。而且對大部分的整數問題而言，我們都簡化為多維度背包問題。主要的方法是把多限制式背包問題化為組合單限制式背包問題(combined single knapsack problem)。再以組合單限制式背包問題估計多限制式背包問題的上限。同時以一個懲罰值計算法求得新分枝出來節點的上限。第一章簡介，第二章回顧陳傑的分枝界定法，第三章我們提出一個新的分枝界定法，第四章我們提出另一個新的分枝界定法，第五章結論。The purpose of this thesis is to find a more efficientalgorithm for solving problem MK. We improve Chen's algorithmin the following two issues. First, we use Magazine and Oguz'sheuristic method [20] to find a heuristic solution at theinitial node. Second, we use Dantzig's method [9] and Martello's method [24] to find an upper bound which is better than thatused in Chen's algorithm. This thesis is organized as follows.In Chapter 2, we give a brief review of Chen's algorithm HUBBfor solving problem MK. In Chapters 3 and 4, we propose two newbranch and bound algorithms. The computational results of thesealgorithms are given in Section 4.4. Concluding remarks aregiven in Chapter 5.