Some Additional Views on the Simplex Method and the Geometry of Constraint Space

Orchard-Hays, W. (1976). Some Additional Views on the Simplex Method and the Geometry of Constraint Space. IIASA Research Report. IIASA, Laxenburg, Austria: RR-76-003

Preview

Text RR-76-003.pdf Download (1MB) | Preview

Abstract

In Part I, the classical statement of an LP problem is compared with the most general form which general-purpose LP software can usually accept. The latter form is then simplified to the form used internally by such software. An extended matrix representation of the conditions used in the simplex method is given, plus a list of the various outcomes of pivot selection. All this is merely a review and summary in consistent notation.

The remainder of Part I views an LP problem as a function of its objective form and parametric algorithms as families of functions. The simplex method, as a process, is also viewed as following a trajectory. The ambiguity of extending this idea to the dual feasible subspace is indicated as well as the difficulty of using this viewpoint for integer programs.

Part II begins with a fairly complete list of notation required in discussing details of the simplex method and its variants. Then a series of definitions, lemmas and theorems are given to make precise such notions as basic solution, distinct solution, adjacency, and dual basis. The main result is a clarification of the phenomena of degeneracy and alternate solutions, in both primal and dual senses. In particular, the complementary nature of ambiguous solutions and multiple solutions is shown. Two trivial examples, easily followed, are sufficient to illustrate these ideas.

Part III applies the ideas of Part II, plus one other, to the old problems of exploring the vicinity of optimality, resolving revised models from an old basis, and a few special problems for which the simplex method is sometimes useful in a non-LP context.

Actions (login required)

View Item