论文部分内容阅读
基于更动约束的思想＾「１」与方法，提出了求解线性规划问题的新椭球算法。它与Ｌ．Ｇ．Ｋｈａｃｈｉａｎ的椭球算法＾「２」不同，在新算法的椭球迭代过程中，不仅用约束不等式割掉不含约束集的半个椭球（椭球中心不在约束集内时），称之为约束割；而且在椭球中心落在约束集内时，它用目标不等式割掉含约束集的半个椭球，称之为目标割。新算法的不等式系统是由原规划（或对偶规划）的约束不等式与目标不等式组成的（规模小），而不是由原椭球算法的Ｋ－Ｋ－Ｔ＾「５」组成的不等式系统（规模大）。这种新椭球算法即有多项式计算复杂性的特性，又在迭