ABSTRACT
The simplex method, invented by George Dantzig in 1947, is still the most widely used algorithm for solving LPs. This chapter derives the core version of the simplex method, an algorithm that starts at a basic feasible solution and terminates at an optimal basic feasible solution if one exists, and at a ray of unboundedness otherwise. It describes both the geometry and algebra of the algorithm from both the primal and dual points of view. The simplex method solves the following problem: given a basic feasible solution to an LP, find an optimal basic feasible solution, or a ray of unboundedness. The chapter completes the rigorous derivation of the simplex method by showing two different ways that make it work correctly when there is degeneracy. There are two main ways to resolve the problem of potential cycling. The first is the perturbation/lexicographic method, and the second is Bland's rule.
