Abstract
傳統上，求解整數規劃問題所採用的方法，有列舉法 (enumeration)，分枝界定法 (branch and bound),以及割面法(cutting planes) 等。這些方法皆可發展而應用至參數分析的問題。然而，從這些方法衍伸而出的演算法，皆有其共同之缺點，亦即在求解過程中，它們皆需要龐大的儲存量。也因此，這些演算法尚無法處理大型整數規劃的參數分析問題。有鑑於此，Jenkins 提出另一種不同於傳統的求解程序。其主要精神在於，希望只要針對參數的數個點值 (point-values) 獨立地求解，而整個參數分析的問題即可完成。然而不幸的是，當等式右方 (RHS)需作參數分析時，Jenkins 所提出的演算法，並無法完全地解出所有的最佳解。此外，這個方法亦無法有效率地應用到其等式右方干擾 (perturbation) 均為正數之特例。於是根據 Jenkins 的精神，我們在本文裡，對於整數規劃中其等式右方之參數分析，定義了一個步距 (stepsize)。從這個觀念，我們可以推導出一個可以解決其等式右方形式為 b + .theta. b' 的整數規劃參數分析之演算法，其中 b 及 b' 為向量，而唯一之參數 .theta. 為一單值。此提出之演算法，可應用至其 b' 中包含正或(且)負元素之問題。至於求解整個問題之複雜度分析，則以數值分析演繹，並以例子說明。In this paper, we define a step size to parametrize the righthand side of an integer programming problem. From this concept,we derive an algorithm for solving families of integer linearprogramming problems with the right hand side in the form of b+ .theta.b', where b and b' are vectors, and the singleparameter .theta. is a scalar. The proposed algorithm isapplicable to the cases when the vector b' consists of positiveand/or negative components. The complexity analysis of solvingthe entire problem is done with numerical examples.