关键词: 椭球算法, 约束割, 目标割

Abstract:

Base on the mathematical idea and method to alter const raints of a problem, a new a-l gorithm for linear prog ramming to solve has been given. This method is different from the primary e-l lipsoid method by L. G. Khachian. The step-by-step procedure in the new method is not only cut t ing dow n the hal-f ellipsoid, that does not contain the const raint set by the constraint inequalit ies named the constraint funct ion cut, w hen the center of ellipsoid is not in the const raint set ; but also cut t ing dow n the hal-f ellipsoid that contain the constraint set by the object ive inequalit ies named the object ive funct ion cut w hen the center of this ellipsoid fall in the constraint set. The inequality set of this new algorithms consist of the const raint inequalit ies of primary prog ram ( or dual prog ram) and object ive inequality, w hich is small in scale, and does not resemble to consist of K-K-T opt imality conditions for the primary ellipsoid method inequalit ies set w hich is large in scale. T his new ellipsoid algorithm not only has characterist ic of poly nomial complex ity, but also can get a series of monotone feasible solut ions to approach the optimal solut ion if this solut ion exist. If we think to g et a sat isfied solut ion, w e can terminate the iterative scheme at any t ime. So the new method is more practical and effect ive than the primary method. Because the variables and bounded, and the initial ellipsoid is not big in the vast majority of pract ical problems, the new algorithms is more feasible.

Key words: ellipsoid method, const raint function cut, object ive funct ion cut