【摘要】 基于更动约束的思想[1 ] 与方法 ,提出了求解线性规划问题的新椭球算法 .它与L .G .Khachian的椭球算法[2 ] 不同 ,在新算法的椭球迭代过程中 ,不仅用约束不等式割掉不含约束集的半个椭球 (椭球中心不在约束集内时 ) ,称之为约束割 ;而且在椭球中心落在约束集内时 ,它用目标不等式割掉含约束集的半个椭球 ,称之为目标割 .新算法的不等式系统是由原规划 (或对偶规划 )的约束不等式与目标不等式组成的 (规模小 ) ,而不是由原椭球算法的K K T条件[5] 组成的不等式系统 (规模大 ) .这种新椭球算法即有多项式计算复杂性的特性 ,又在迭代过程中得到一系列单调趋向最优解的可行解 (在解存在时 ) .如果认为已得满意解 ,可随时停机 .对于实际问题 ,大多数是变量有界的 ,初始椭球不大 ,因此新算法更为实际 ,有效 .更多还原

【Abstract】 Base on the mathematical idea and method to alter constraints of a problem, a new algorithm for linear programming to solve has been given. This method is different from the primary ellipsoid method by L.G.Khachian. The step by step procedure in the new method is not only cutting down the half ellipsoid, that does not contain the constraint set by the constraint inequalities named the constraint function cut, when the center of ellipsoid is not in the constraint set; but also cutting down the half ellipsoid that contain the constraint set by the objective inequalities named the objective function cut when the center of this ellipsoid fall in the constraint set. The inequality set of this new algorithms consist of the constraint inequalities of primary program (or dual program) and objective inequality, which is small in scale, and does not resemble to consist of K K T optimality conditions for the primary ellipsoid method inequalities set which is large in scale. This new ellipsoid algorithm not only has characteristic of polynomial complexity, but also can get a series of monotone feasible solutions to approach the optimal solution if this solution exist. If we think to get a satisfied solution, we can terminate the iterative scheme at any time. So the new method is more practical and effective than the primary method. Because the variables and bounded, and the initial ellipsoid is not big in the vast majority of practical problems, the new algorithms is more feasible.更多还原