本論文主要是檢討並修改線性規劃Karmarmar相關演算法。這些演算法包括：內部點演算法，牛頓數值法，以及方塊法。這些方法對解線性規劃均有多項式求解時間。我們討論並改進這些方法，使求解速度更快。一共提出六套演算法，並寫成電腦程式。利用一些現有的線性規劃問題資料，在電腦上比較其求解速度。

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.

線性規劃; 單純形法; Karmarkar演算法; 內部點演算法; 障礙函數; 方塊法; 多項式時間演算法

Linear programming; Simplex method; Karmarkar’s algorithm; Interior point algorithm; Barrier function; Box method; Polynomial-time algorithm