線性規劃的求解方法依幾何觀點可區分為單體法(Simplex Method)和起源於Karmarkar的內點法(Interior Point Method)，無論在理論上或應用上這兩者的許多變體仍然不斷地在改進中。Dantzig的單體法和它變體的演算法是從邊上角點走到另一角點直至到達最佳點，內點法則是透過這個可行地區的內部的可行點走到可行點的方法。眾所週知，當遭遇最壞案例時單體法求解速度的函數表示成指數形式；而內點法卻成多項式形式。就一般案例而言，實驗證據提議，當問題大小為小型時，以單體法求解速度較佳。而內點法僅僅在很大規模的線性規劃時，其解法優於以單體法為基礎的方法。
儘管內點法求解速度較單體法為快，但大多數運用內點法求得最佳解的原理，都使用一個可行解區域內部的點作為起點(或稱為中心)，然而就原始線性規劃問題而言，求得一可行解其複雜度和求得最佳解的複雜度是相同的。倘若能以單體法製造起始點的方法，搭配內點法的優點，產生一不同於過去單體法和內點法之新演算法，能降低求解速度，則是吸引人的課題。是故作者希望能以線性規劃問題的搜尋方向為主題加以整理，探討如何結合單體法及內點法的特性，深入研究搜尋方向在邊界上可能會發生的問題，並以一演算法為例，設計程式，作數據實驗，實際觀察問題發生的原因及提供解決的方法。
| Identifer | oai:union.ndltd.org:CHENGCHI/A2002001141 |
| Creators | 莊文華 |
| Publisher | 國立政治大學 |
| Source Sets | National Chengchi University Libraries |
| Language | 中文 |
| Detected Language | Unknown |
| Type | text |
| Rights | Copyright © nccu library on behalf of the copyright holders |
Page generated in 0.002 seconds