基本简介

椭球算法（Ellipsoid algorithm）被Soviet mathematicians(1970), Yudin and Nemirovskii(1975)， Khachian（1979）证明了能在多项式时间内解决线性规划问题。

但是椭球算法的效率很低，与单纯型法没有可比性，因此现在椭球算法没有得到广泛使用。然而，椭球算法在理论方面的贡献是十分重大的，它是第一个被证明是多项式时间内解决线性规划问题的算法，是其他后来算法的一个源头。