臺大學術期刊資料庫NTU Journal Database

線性規劃 Karmarkar 相關演算之探討

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

陳文賢(Wen-Hsien Chen)

國立臺灣大學工商管理學系(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.

關鍵詞

程式與 AI 助手可以改用資料介面(JSON、MCP),查詢比讀頁面快。給程式與 AI 代理的存取說明