Zurück zu den Preprints des Jahres 1995


1995-18

On a Modifikation of the Method of Enclosed Sections for Solving Systems of Linear Inequalities

by Gorokh, O. V., Werner, F..


Series: 1995-18, Preprints

MSC:

Abstract:
this paper a modification of the method of enclosed sections
for solving perfect systems of linear inequalities is presented. The
proposed algorithm is a strongly polynomial one for the class of sys-
tems of inequalities with a constant difference between the number of
constraints and the number of variables. It is based on the use of a
special sequence of systems of linear algebraic equations. To obtain
sequentially solutions of such systems of linear equations, a modi-
fied method of expanding subsystems is proposed. This modification
allows to reduce the complexity of the algorithm of the method of
enclosed sections by one degree.

Keywords: