4.3: The Simplex Method: Solving Standard Maximization Problems

Based on Section 4.3 in Finite Mathematics and Finite Mathematics and Applied Calculus

Goodies

On-line Pivot & Gauss-Jordan Tool     Excel Pivot & Gauss-Jordan Tool    
Pivoting program for TI 82 and TI 83   On-line Simplex Method Tool    

Standard maximization problems are special kinds of linear programming problems.

Q Remind me what a linear programming problem is.
A A linear programming (LP) problem is a problem in which we are asked to find the maximum (or minimum) value of a linear objective function

       p = ax + by + cz + ...Example: p = 3x - 2y + z

 
Subject to one or more linear constraints of the form
 
Ax + By + Cz + . . . (or ) N       Example: x + y - 3z 12

The desired largest (or smallest) value of the objective function is called the optimal value, and a collection of values of x, y, z, . . . that gives the optimal value constitutes an optimal solution. The variables x, y, z, . . . are called the decision variables.

Q Ok, now what is a standard maximization problem?

Standard Maximization Problem

A linear programming (LP) problem is called a standard maximization problem if:

  • We are to find the maximum (not minimum) value of the objective function.
  • All the variables x, y, z, ... are constrained to be non-negative.
  • All further constraints have the form Ax + By + Cz + . . . N (and not ) with N nonnegative.
Example

The following is a standard maximization problem:

    Maximize p = 2x - 3y + 4z subject to the constraints

    4x - 3y + z 3
    x + y + z 10
    2x + y - z 10,
    x 0, y 0, z 0

The following is not a standard maximization problem:

    Maximize p = 2x - 3y + z subject to

    4x - 3y + z 3
    3x - y       10
    x 0, y 0, z 0

The reason it is not a standard maximization problem is that:

Press here or the "Next Tutorial" button on the sidebar to find out about linear programming problems other than standard maximization ones.

The method most frequently used to solve LP problems is the simplex method. Here is a step-by-step approach.

Step 1: Convert the LP problem to a system of linear equations.

Q What is a system of linear equations?
A To review systems of linear equations, take a look at the summary of Chapter 2. For an on-line tutorial on systems of linear equations, press here.

Q OK. I know what a system of linear equations is. But how do we do Step 1?
A We do this by rewriting the constraint inequalities as equations by adding new "slack variables," and by rewriting the objective function as shown in the following example.

Example
The constraints

in the above LP problem are written as equations by adding a new "slack" variable to the left-hand side of each to "take up the slack." In addition, the objective function is rewritten with all the unknowns on the left-hand side. This gives the following system of equations.


 

Rewrite the following LP problem as a system of linear equations.

where x, y, and z are non-negative. (Use slack variables s and t respectively, and type all equations with the variables in the order shown above. Press "Check" to check each equation.)

We can now go to Step 2.

Step 2: Set up the initial tableau.

Q What is the initial tableau?
A By the initial "tableau," we mean the augmented matrix of the system of equations we just obtained.

Example
For the system

the initial tableau is as follows (notice how we separate the last row using a line).

Set up the first tableau for the following LP problem.

Maximize p = x + 2y + 3z subject to the constraints

where x, y, and z are non-negative. (You can use the Tab key to move from cell to cell. Press "Check" when done.)

Associated with each tableau (including the initial one above) is a so-called basic solution. This is one of the infintely many possible solutions of the system of equations represented by the tableau.

To obtain the basic solution in a tablueau, look for the columns that are cleared (all zeros except for one entry). An example is the "t"-column in the above tableau. We assign to the corresponding variable the ratio shown in the example below. We call these variables the active variables. All variables whose columns are not cleared are assigned zero and are called inactive.

Example
In the following tableau, the active variables are shown in color and their values computed as illustrated.

As an additional aid to recognizing which variables are active and which are inactive, we label each row with the name of the corresponding active variable. The complete tableau looks like this:

Here is the initial tableau you obtained in the last interactive question:

The associated basic solution is:

Now fill in the names of the corresponding active variables.

Notice that the current value of p (p = 0) hardly seems like a maximum value. In the simplex method, we obtain larger and larger values of p by pivoting and then looking at the new basic solution. (For quick instructions on how to pivot, press here. To go to a tutorial which shows you how to pivot, press here) To find a pivot, we first select a column, then a row.

Step 3: Select the pivot column.

The rule for the selecting a pivot column is this: Look at all the numbers in the bottom row, excluding the Answer column. From these, choose the negative number with the largest magnitude. Its column is the pivot column. (If there are two candidates, choose either one.) If all the numbers in the bottom row are zero or positive, then you are done, and the basic solution is the optimal solution.

Example
In the intial tableau you just analyzed, the most negative number in the bottom row is the -3, and hence the pivot column is the z-column. This means that the pivot will be somewhere in the z-column.

Step 4: Select the pivot in the pivot column.

Here is what we are told to do in Section 4.3 of Finite Mathematics and Finite Mathematics and Applied Calculus

Selecting the Pivot

1) The pivot must always be a positive number. (This rules out zeros and negative numbers, such as the -3 in the bottom row.)
2) For each positive entry b in the pivot column, compute the ratio a/b, where a is the number in the rightmost column in that row. We call this a test ratio.
3) Of these ratios, choose the smallest one. The corresponding number b is the pivot.

Example
In the following tableau, the pivot column is the "t"-column. Since neither zeros nor negative numbers can serve as a pivot, we must choose between the 3 and the 1 in the "t"-column. The test ratios are shown on the side.

Since 3/3 = 1 is the smaller of the two test ratios, the pivot is the 3 (which is why it may be blinking, depending on your browser).

Here is a multiple choice quesion: select (click on) the pivot in the following tableau.

Having selected the pivot, we now proceed to the next step.

Step 5: Use the pivot to clear the pivot column in the normal manner. This gives the next tableau.

To do this, we follow the exact prescription for formulating the row operations described in Section 2.2 of Finite Mathematics or Finite Mathematics and Applied Calculus This method is also summarized on-line. For quick instructions on how to pivot, press here. For a detailed tutorial which shows you how to pivot, press here.)

Example
In the following tableau, the pivot is shown in color, and we clear its column using the given row operations.

This gives the next tableau:

If you want to automate the process of pivoting, you have several options available on-line -- see the goodies at the top of this page.

Q Why did the row label on the left of the first row change from "z" to "t"?.
A After we pivot on the 3 in the t-column, the tableau has t as an active variable (t = 3/3 = 1) whereas z is no longer an active variable. z is called the departing variable and t is called the entering variable. In general, when we pivot, the variable that lables its column ("t" in this example) becomes the entering variable for its row.
 

Here is the first tableau we have been working with in the interactive questions.

You now know where the first pivot is. Carry out Step 5 to obtain the second tableau. (You can use the Tab key to move from cell to cell. Press "Check" when done.)

Now that we have the second tableau, we carry out the next instruction.

Step 6: Repeat Steps 3-5 until there are no more negative numbers in the bottom row (with the possible exception of the Answer column).

Since there is still a negative number there: the -2 in the "y"-column, you will now need to select another pivot, and then pass to the next tableau. Let us see how well you do it...

Going back to the problem you have been working on, the next tableau is:

xyzstupAns

If you got this right, you will notice that there are no negative numbers in the bottom row. This means that we are done, and the current tableau is the final tableau. The solution for the problem is the current basic solution:

Press here to bring up a window that summarizes all the steps in the simplex method. (You might find this useful to print out.)

You now have several options.

Top of Page

Last Updated: June, 2006
Copyright © 1999, 2003, 2006 Stefan Waner