線性規劃 Karmarkar 相關演算之探討
The Variants of Karmarkar’s and Simplex Algorithms for Linear Programming
國立臺灣大學工商管理學系(Department of Business Administration, National Taiwan University)
- 類型
- 論文
- 卷期
- 1卷1期
- 出版
- 1990年05月
- 頁碼
- 149–172
- 編號
- NTUEJ00010552
需要全文時,可以向出版單位洽詢,聯絡方式見期刊資訊。
摘要
本論文主要是檢討並修改線性規劃Karmarkar相關演算法。這些演算法包括:內部點演算法,牛頓數值法,以及方塊法。這些方法對解線性規劃均有多項式求解時間。我們討論並改進這些方法,使求解速度更快。一共提出六套演算法,並寫成電腦程式。利用一些現有的線性規劃問題資料,在電腦上比較其求解速度。
Abstract
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.