175 Years of linear programming: 2. Pivots in column space

Abstract

The simplex method has been the veritable workhorse of linear programming for five decades now. An elegant geometric interpretation of the simplex method can be visualised by viewing the animation of the algorithm in acolumn space representation. In fact, it is this interpretation that explains why it is called the simplex method. The extreme points of the feasible region (polyhedron) of the linear programme can be shown to correspond to an arrangement of simplices in this geometry and the pivoting operation to a physical pivot from one simplex to an adjacent one in the arrangement. This paper introduces this vivid description of the simplex method as a tutored dance of simplices performing 'pivots in column space'.