Bydraes tot ry- en kolomseleksieprosedures vir ontaarde lineêre programme

Abstract

The reason why the simplex method and related techniques are studied is because, from a practical viewpoint, two important features - a typically linear number of iterations, and fast methods for performing each iteration - imply that the simplex method is a reliable and effective algorithm for large-scale linear programming problems. A linear programming problem is degenerate if some of the basic variables are zero. In the presence of degeneracy, the objective function may not change when we move from one basic feasible solution to another. Then we can no longer be sure that no basis will be repeated. In fact, we may get into a situation where we cycle infinitely, repeating the same sequence of bases, and never reach an optimal solution. Although cycling rarely occurs in actual practice, degeneracy is quite a frequent phenomenon. I of iterations which coincide with the same value of the objective function, and therefore much time is spent on solving a problem. Techniques for resolving degeneracy are seldom built into software packages, and it seems as if the problems that are caused by degeneracy are overlooked. The first purpose of this thesis is to study existing row and column selection procedures, with a special accent on degeneracy. The performances of these techniques are evaluated. A second purpose is to develop techniques for resolving degeneracy which can be used with existing gradient methods, without causing these methods to demand extra time and memory when solving a problem on a computer. The first part of the thesis deals with existing and known facts related to the techniques for the solution of linear programming problems. The chapters which are included in-the first part deal with definitions and notation, degeneracy, practical implementation of large scale linear programming problems, row selection procedures and column selection procedures