一种新的椭球算法

摘要

基于更动约束的思想＾「１」与方法，提出了求解线性规划问题的新椭球算法。它与Ｌ．Ｇ．Ｋｈａｃｈｉａｎ的椭球算法＾「２」不同，在新算法的椭球迭代过程中，不仅用约束不等式割掉不含约束集的半个椭球（椭球中心不在约束集内时），称之为约束割；而且在椭球中心落在约束集内时，它用目标不等式割掉含约束集的半个椭球，称之为目标割。新算法的不等式系统是由原规划（或对偶规划）的约束不等式与目标不等式组成的（规模小），而不是由原椭球算法的Ｋ－Ｋ－Ｔ＾「５」组成的不等式系统（规模大）。这种新椭球算法即有多项式计算复杂性的特性，又在迭代过程中得到一系列单调趋势向最优解的可行解（在解存在时）。如果认为已得满意解，可随时停机。对于实际问题，大多数是变量有界的，初始椭球不大，因此新算法更为实际，有效。