Operations Research Models and Methods / Methods / Linear Programming
 The Revised Primal Simplex Method

The revised primal simplex method uses matrix operations to compute the quantities used by the simplex method. We have implemented this technique with an Excel add-in called Teach LP. This unit is the introduction to that portion of the add-in that performs the revised simplex method. To run an exercise the student selects Revised from the menu.

 The examples for this section are in the Teach LP demo (teachlpdem.xls). To solve or change the model you must have the Teach LP add-in loaded. Use the Relink buttons command to establish links to the worksheet buttons.

The dialog defining the model is the same as that used for the Tableau simplex method.

Model

 The randomly gnerated model used as an illustration in this section is shown below. The model has been modified by including an artificial variable for the first constraint. The details of this modification can be found in the tableau simplex discussion.

Initial Basis

 Pressing the Phase 1 button, initiates the process that builds the vectors and matrices that implement the simplex procedure. The figure below shows the initial basis and basis inverse matrices. These are placed to the right of the LP model. The matrices change during the algorithm as the basic variables change.

Revised Simplex Matrices

 The other information necessary for accomplishing the revised simplex procedure is placed in the rows below the LP model as shown below. All the cells in the yellowed area contain Excel formulas that compute the quantities necessary for the iteration. As for the tableau method, the Iterate button initiates the iteration, first asking for the variable to enter the basis, then the variable to leave the basis.

Selecting the Entering and Leaving Variables

 For the first iteration of the method, we have selected arc 3 to enter and arc 9 to leave. The cells colored blue indicate the cells that will change with the pivot operation. Pressing the Pivot key replaces index 9 in the vector of basic variables with that of row 3. Since all the cell contents are controlled by equations, they all change to represent the new basis.

Phase 2

 The first iteration completes phase 1 and places the Phase 2 button on the sheet.

 The Phase 2 button replaces the Phase 1 objective with the Phase 2 objective in the formulas for the values of the dual variables and reduced costs.

 The procedure continues in Phase 2 with the 5th variable replacing the 3rd variable in the basis.

The Optimum Solution

 One more step leads to the optimum solution.

 The final solution appears in the x-vector of the original LP model.

Operations Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors