Abstract
本篇論文內容分為六大章。在第一章，我們對於過去這幾年來基於Karmarkar 演算法而發展完成的各種變形演算法作一縱覽性的介紹。在第二章，我們開始回顧並詳加瞭解Karmarkar 演算法。由於Karmarkar 所提出之方法在總運算次數上已經證明達到Ｏ(ｎ3.5Ｌ2)之速度，對於解線性規劃問題乃一大突破，但想要在電腦上實行時，仍有兩個缺點有待改進：一．將一般標準LP問題先轉換成目標函數最佳值已知的Karmarkar 正規形式(Karm-arkar's canonical form) ，其轉換策略使問題的維度大小增加一倍；二．進行迭代的過程中，無論如何總是必須精確地解出最小平方問題，這是電腦運算中最耗費時間的關鍵所在。因此，第三章介紹Karmarkar 方法的一種推廣，它允許一般標準線性規劃問題轉換成Karmarkar 正規形式的目標函數值未知，並利用對偶(dual)變數所生成的迭代數列收斂至目標函數最佳值之方式求解，卻無法改善上述所提到的第二種缺點。於是第四章我們描述Karmarkar 方法的一種放鬆(relaxed) 形式，它僅僅改善了第二種缺點，但反而免不了有第一種缺點，不過至少已經可以容許不必很精確地去解最小平方問題，而同時維持Karmarkar 演算法理論上之速度及準確性。第五章則終於闡述出一套較為完善的Karmarkar 演算法之放鬆變形，使上述兩種缺點得以同時獲得改善。如此一來，它可以直接應用在原始(primal)問題，也不至於將問題的維度擴大成兩倍以上，而且還可以很快到達收斂。最後，為了使本篇論文更為完備起見，第六章乃以上二、三、四、五章之總結。