Revised Simplex Variants of the Primal and Dual Simplex Methods and Sensitivity Analysis

Consider an LP in standard form in n nonnegative variables subject to m equality constraints that the variables are required to satisfy, in which we assume that the rank of the coefficient matrix is m, without any loss of generality. So, n ≥ m. In LP models to be solved in practice, typically n will be much larger than m. The original form of the primal simplex method developed in 1947, discussed in LP textbooks (e.g., see Chap. 4 of Murty (2005b) of Chap. 1), is a wonderful educational tool to explain the principles behind the method to beginners. Starting with a primal feasible basic vector, this method goes through a series of steps, in each step one GJ pivot step is carried out to replace one basic variable in the basic vector by a specially selected nonbasic variable. All the work in a step of this method is also discussed in our Sects. 4.9 and 4.12. But as a computational method for solving LP models in practice, this original form of the primal simplex method is highly inefficient as it updates every one of the n + 1 column vectors in the canonical tableau in every pivot step to solve the LP under consideration. In this chapter, we will discuss the much more efficient revised simplex variants of the primal simplex method that are based on the same fundamental theory, but in these variants we only need to update a smaller number, m + 2, column vectors of the basis inverse in every pivot step. We will discuss several of the early (developed in 1950s and 1960s) variants of this method to describe the ideas used to make the simplex method a practically valuable tool to solve LP models in decision making.