Hints on Using the Advanced Simplex Pivot Tool

Introduction

The advanced pivot tool can serve as an aid for several variants of the simplex method. In particular, it can be used for all of the variants of the simplex method described in Linear Programming: Foundations and Extensions (LP:F&E). A few pointers are given below.

The Dual-Phase-I Primal-Phase-II Method

This two-phase method is described in section 5.7 of LP:F&E. To use the applet, first enter the data that describes the particular problem. The artificial objective row (i.e., the second row) is initialized with all -1's. These numbers can be changed if desired but must all remain nonpositive. The artificial right-hand-side column (i.e., the second column) is initialized with all 1's. For this method, this column is of no use. You can either simply ignore it or, if you prefer, you can zero out the entries in this column.

The phase I procedure uses the true right-hand side column and the artificial objective row. Any negative entry in the right-hand side column may be chosen as the leaving variable. Once picked, a ratio test must be done, either by eyeballing or on scratch paper, to determine the entering variable using the artificial objective row. Once the leaving and entering variables have been determined, click on the corresponding button to actually do the pivot. If the entering variable was chosen correctly, the artificial objective row will still have all negative entries after the pivot. If it was chosen incorrectly, there will be positive entries. These will be highlighted in yellow. If a yellow highlight appears in the artificial objective row you might want to click on the Undo button to undo the last pivot. Continue with the phase I procedure until all of the entries in the right-hand-side column are nonnegative; that is, until there are no more pink highlights in this column. At this point, you are ready for phase II.

Phase II is the ordinary simplex method applied to a primal-feasible dictionary. For this phase, we ignore both the artificial column and the artificial row. Possible entering variables are highlighted in pink in the objective row. Choose one of these as the entering variable and then do a ratio test to determine the corresponding leaving variable. Click on the associated pivot button to do the pivot. If the leaving variable was selected correctly, then the new dictionary will still be primal feasible. If it is infeasible, you will see at least one pink cell in the right-hand-side column. If that happens, you might want to hit the Undo button to back up one iteration. Continue with these phase II pivots until there are no more pink highlights remaining. At this point, the dictionary is optimal. To tell the applet that you recognize that the current dictionary is optimal, click on the Optimal button. The applet will confirm if you are correct.

Infeasibility. If during phase I a ratio test reveals that no variable can enter the basis, then the problem is infeasible. If this happens, click on the Infeasible button to tell the applet that you recognize this situation. Unboundedness. If during phase II a ratio test reveals that no variable can leave the basis, then the problem is unbounded. If this happens, click on the Unbounded button to tell the applet that you recognize this situation.

The One Phase Primal-Dual Method

This one-phase method, also known in the literature as the parametric self dual method, is described in section 7.2 of LP:F&E. To use the applet, first enter the data describing a particular problem. The artificial objective row (i.e., the second row) is initialized with all -1's and the artificial right-hand-side column (i.e., the second column) is initialized with all 1's. These numbers can be changed if desired but must all retain their initial sign. The primal-dual simplex method involves a parameter, called mu in LP:F&E. The applet doesn't explicitly show mu. Instead, one is expected to remember that mu multiplies every term in the artificial objective row as well as every term in the artificial right-hand-side column.

The applet shows in the lower-left corner the interval of mu values for which the current dictionary is optimal. This interval is determined by the requirements that each coefficient of a variable in the objective function be nonpositive and each right-hand side be nonnegative. These requirements translate into a number of inequalities on mu and the interval consists of those mu values that satisfy every inequality.

The first step is to identify which row or column is responsible for the lower bound on mu. If it is a column, then the variable associated with that column will be the entering variable and the leaving variable must be determined using a usual ratio test. On the other hand, if it is a row, then the basic variable associated with that row will be the leaving variable and the entering variable must be determined using a ratio test for the dual simplex method. Once the entering and leaving variable have been identified, do the pivot by clicking on the correct pivot button. As always, the dictionary will automatically update. In addition, a new interval of mu values will appear. If the correct pivot button was selected (generally there will only be one correct choice), then the new interval will be an interval adjacent and to the left of the old interval. In most other cases, the lower limit of the interval will be larger than the upper limit. That is, the true interval will be empty. In this case, the interval will be highlighted in yellow to indicate that something is wrong. You probably will want to hit the Undo when this happens.

Once the mu interval includes zero, the current dictionary is optimal for the original problem.