

The
goal of this unit is to provide instructions for the primal
simplex method for linear programming implemented using the
tableau method. Traditionally, this method has been used for
the first introduction to the primal simplex method. We use
an Excel addin called Teach LP (teachlp.xla) for instruction.
This unit is the introduction to that addin.
We assume that the student has the Teach LP addin
installed. The program adds new menu items to the Teach_OR
menu. To run an exercise the student selects Tableau 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 addin loaded. Use the Relink buttons command
to establish links to the worksheet buttons. 

The dialog below asks for the size of the
LP model to be used in the exercise and the selects the
Solution Option to be Instruction. The latter controls
how intermediate information is presented to the student.
As noted on the dialog, the problem is to
be entered in the equality form, so the number of variables
should include the slack or surplus variables necessary
to convert inequalities into equalities. All variables
are assumed to be nonnegative. The maximum dimensions
for this program is 20 variables and 10 constraints.
When the checkbox labeled Make Random
Problem is checked, random numbers are used to generate
data for the model. Otherwise, the model coefficients
are entered as 0.
Three solution options are available. The
Demonstration option goes through each iteration
of the primal simplex with simple explanations about how
the simplex technique operates. The student only clicks
progress buttons to move the demonstration along. The
Instruction option allows the student to choose
the variables that are to enter and leave the basis. Hints
are provided at various points to aid the student in the
process. The Do it yourself option leaves the decisions
entirely up to the student. The program performs pivot
operations initiated by the student.
The randomly generated model used as an
illustration in this section is shown below.

Model 



The random model has all nonnegative integer
coefficients. The constraints are less than or equal to
constraints, and the last three variables are slack variables.
The coefficients in the model can be changed
in any way. For the example, we have modified the coefficients
in column 6. Since an initial basis is not readily apparent
for the revised problem, the modification requires the
use of an artificial variable.



The Initial Basis 

When the model is ready, press the Start
button. Because an initial basis is not available, the
program asks whether an artificial variable should be
added.
With a positive response, the program provides
an artificial variable, art1, to construct the initial
basis. A two phase method is used. In Phase 1, the vector
C1 provides the objective coefficients. Only the artificial
variables have nonzero cost coefficients (1). Since
the algorithm is maximizing, the artificial variables
will be made as small as possible during Phase 1. If
they go to zero, the solution obtained is feasible for
the original LP model. If Phase 1 does not drive the
artificial variables to zero, no feasible solution exists
and the algorithm terminates. To begin the iterative
portion of Phase 1, press on the Phase 1 button
on the worksheet.



The Tableau 

The tableau is constructed by the program
with the initial basis provided by either slack or artificial
variables.



The tableau is located below the LP model
on the worksheet as in the figure above. As the algorithm
progresses, the view of the worksheet is focused on the
tableau. Cells indicate the Phase and Iteration number.
The cells near the center of the display show the variables
that enter and leave the basis. In this initial state,
the values shown have no meaning. The portions of the
worksheet colored yellow are controlled by the program
and generally should not be changed by the student. One
exception is the column of red numbers labeled Basic
Index. Although generally, the computer will control
these numbers, for some exercises the student may wish
to manipulate the numbers directly.

The Iteration 

Pressing the Iterate button begins
the solution process. For the primal simplex algorithm,
the first decision is to select some variable to enter
the basis. In the Instructional Mode the dialog box asks
for the index of the variable to enter the basis. Initially
the index field is blank, but pressing the Hint button,
causes the negative reduced costs in the tableau to be
colored as shown. The index with the most negative reduced
cost is inserted in the dialog box. The Hint button
is not available in the Do it yourself mode.



Accepting the selection of the entering
variable, the next dialog asks for the index of the variable
to leave the basis. Again the Hint button colors the appropriate
ratios and suggests the correct leaving variable. Note
that the variable is specified by its index, not by the
row it represents in the tableau.



After accepting the selection of the leaving
variable, the pivot row and column are colored orange,
and the pivot button is placed on the worksheet.



Pressing the Pivot button causes
the program to adjust the tableau for the new basic variables
as shown below.


Phase 2 

For this example, the iteration has resulted
in a zero value for the artificial variable. The solution
is optimal for Phase 1. Pressing the Phase 2 button
causes the original objective coefficients to be used
for the computation of the reduced costs, row 0 of the
tableau. The basic variables are the same for the tableau,
but the new reduced costs are computed with the Phase
2 objective coefficients.



Pressing the Iterate button initiates
the sequence of activities that leads to the next tableau.


The Optimum Solution 

One more iteration is necessary to find
the optimal solution.



The final
solution appears in the xvector of the original LP model.



