The Variants of Karmarkar’s and Simplex Algorithms for Linear Programming

本論文主要是檢討並修改線性規劃Karmarkar相關演算法。這些演算法包括：內部點演算法，牛頓數值法，以及方塊法。這些方法對解線性規劃均有多項式求解時間。我們討論並改進這些方法，使求解速度更快。一共提出六套演算法，並寫成電腦程式。利用一些現有的線性規劃問題資料，在電腦上比較其求解速度。We review and modify the Karmarkar’s polynomial-time algorithm and its variants for linear programming. These variants are interior point algorithms, Newton barrier methods, and box method. Those algorithms still have polynomial-time computational complexity. For logarithm barrier function algorithm, each iteration updates a penalty parameter and finds an approximate Newton’s direction associated with the Kuhn-Tucker system of equations. This paper briefly discusses those algorithms and some extensions of Karmarkar type algorithm to simplex method. We implemented those algorithms in Fortran programs and tested the computational results for iteration numbers and CPU times