Zurück zu den Preprints des Jahres 1995


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


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.