橢球算法

橢球算法，證明了能在多項式時間內解決線性規劃問題。但是橢球算法的效率很低，與單純型法沒有可比性，因此現在橢球算法沒有得到廣泛使用。

基本簡介

橢球算法（Ellipsoid algorithm）被Soviet mathematicians(1970), Yudin and Nemirovskii(1975)， Khachian（1979）證明了能在多項式時間內解決線性規劃問題。
但是橢球算法的效率很低，與單純型法沒有可比性，因此現在橢球算法沒有得到廣泛使用。然而，橢球算法在理論方面的貢獻是十分重大的，它是第一個被證明是多項式時間內解決線性規劃問題的算法，是其他後來算法的一個源頭。