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

[摘要] The reason why the simplex method and related techniques arestudied is because, from a practical viewpoint, two importantfeatures - a typically linear number of iterations, and fastmethods for performing each iteration - imply that the simplexmethod is a reliable and effective algorithm for large-scalelinear programming problems.A linear programming problem is degenerate if some of the basicvariables are zero. In the presence of degeneracy, the objectivefunction may not change when we move from one basic feasiblesolution to another. Then we can no longer be sure that no basiswill be repeated. In fact, we may get into a situation where wecycle infinitely, repeating the same sequence of bases, and neverreach an optimal solution.Although cycling rarely occurs in actual practice, degeneracy isquite a frequent phenomenon. It can cause a considerable numberof iterations which coincide with the same value of the objectivefunction, and therefore much time is spent on solving a problem.Techniques for resolving degeneracy are seldom built intosoftware packages, and it seems as if the problems that arecaused by degeneracy are overlooked.The first purpose of this thesis is to study existing row andcolumn selection procedures, with a special accent on degeneracy.The performances of these techniques are evaluated. A secondpurpose is to develop techniques for resolving degeneracy whichcan be used with existing gradient methods, without causing thesemethods to demand extra time and memory when solving a problemon a computer.The first part of the thesis deals with existing and known factsrelated to the techniques for the solution of linear programmingproblems. The chapters which are included in-the first part deal with definitions and notation, degeneracy, practical implementation of large scale linear programmingproblems, row selection procedures and column selection procedures

[发布机构] North-West University