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

Abstract

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