ABSTRACT
Overview The simplex algorithm that is described in this chapter was invented in 1947 by George B. Dantzig (1914-2005). In 1963, his famous book Linear Programming and Extensions was published by Princeton University Press, Princeton, New Jersey. Since that time, the implementations of the algorithm have improved drastically. Linear optimization models with millions of variables and constraints can nowadays readily be solved by the simplex algorithm using modern computers and sophisticated implementations. The basic idea of Dantzig’s simplex algorithm for solving LO-models is to manipulate the columns of the technology matrix of the model in such a way that after a finite number of steps an optimal solution is achieved. These steps correspond to jumps from vertex to vertex along the edges of the feasible region of the LO-model, while these jumps in turn correspond to manipulations of the rows of the technology matrix. This relationship between manipulating columns and manipulating rows was explained in Chapter 2.
