The Dual Simplex Algorithm

In chapter 7 we studied the primal simplex algorithm which, for several years after its discovery, was regarded as a procedure to find a LP solution working on the primal problem. Analogously, a procedure that solves a dual linear programming problem may be called a dual simplex algorithm. This algorithm was discovered by C. E. Lemke in 1954, seven years after the primal simplex procedure. It is fair to say that without the dual simplex algorithm modern computer codes could not be as reliable as they are. At present, any respectable computer program based on the simplex method incorporates both the primal and the dual simplex algorithms. The reason for the importance of the dual simplex algorithm has its source in the duality and symmetry of linear programming. That it took seven years to discover it is somewhat of a mystery given the obvious symmetry of linear programming. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.