4.4: The Simplex Method: Solving General Linear Programming Problems

Based on Section 4.4 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    

Note: You need to know how to do standard maximization problems in order to follow this tutorial, so go here for that tutorial.

Q What is a "general linear programming problem?"
A By a general linear programming problem, we will understand a linear programming problem that may or may not be a standard maximization problem, but where all the variables are still constrained to be non-negative.

Thus, a general LP problem can fail to be a standard maximization problem for one or both of the following reasons.

Examples

The following are not standard maximization problems (reasons shown next to the offending statements):

Just as with standard maximization prblems, the method most frequently used to solve general LP problems is the simplex method. However, there are a number of different methods to use the simplex method for non-standard problems. Here is the easy method we use in the textbooks, Finite Mathematics and Finite Mathematics and Applied Calculus.

How to Solve General Maximization Problems

General maximization problems are linear programming problems in which you are asked to maximize an objective function. It may be non-standard: one or more of the constraints may be a constraint.
 
Step 1: Convert the LP problem to a system of linear equations.

Q How does this differ from the first step in solving standard maximization problems?
A As with standard maximization problems, we add slack variables for the "" constraints. For the "" constraints, we need to subtract "surplus" variables. Thus, for instance, the constraint

x + y - z 5
is written as
x + y - z - s = 5.

 

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

Maximize p = 2x + 3y + z subject to
x + y + z 40
2x + y - z 10
- y + z 10
x 0, y 0, z 0
Use slack or surplus variables s, t and u 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 for this kind of problem?
A It means the same as the initial tableau for standard maximization problems: the augmented matrix of the system of equations we just obtained.

Set up the first tableau for the above LP problem:

Maximize p = 2x + 3y + z subject to
x + y + z 40
2x + y - z 10
- y + z 10
x 0, y 0, z 0

You can use the Tab key to move from cell to cell. Press "Check" when done.


 

The associated basic solution is:

Notice that the values of the surplus variables t and u are currently negative. This is not permitted, since all variables are required to be non-negative. This tells us that the current basic solution (x, y, z) = (0, 0, 0) is not feasible, (it does not satisfy the second and third constraints). We use asterisks to mark the rows corresponding to those negative basic variables:

Our first order of business is to get into the feasible region, or, equivalently,
 

Phase I: Get rid of the stars.

We can (eventually) get rid of all the stars by pivoting one or more times. The only way this differs from the procedure for pivoting in standard maximization problems is the way in which we select the pivot column.

  • For standard maximization problems, the pivot column was chosen by selecting the most negative number in the bottom row.
  • In Phase I, on the other hand, the pivot column is chosen by selecting the largest positive number in the first starred row.
Once we have selected the pivot column, we select the actual pivot as usual by using the lowest test ratio in the pivot column. (Note: If the lowest ratio occurs both in a starred row and an unstarred row, pivot in a starred row rather than the unstarred one.) Thus, in Phase I, we don't worry about negative numbers in the bottom row at all (there might not even be any there to begin with). That is all there is to Phase I.

 
In the above tableau, the first starred row is Row 2, and the largest positive number it contains is its first entry, 2. Thus, we have the following pivot column, colored in green

To select the pivot, identify the smallest test ratio:

Thus, we pivot on the "2" in Row 2, and we get the following tableau (check this yourself!)

Q What happened to the star in Row 2?
A It is gone, because the basic solution we now get from Row 2 is

x = 10/2 = 5,
which is no longer negative! Thus, we have eliminated one of the stars.

Since there is still one starred row left, we are not done with Phase I.
 

Click on a valid pivot selected according to the instructions for Phase I.


 

Using the correct pivot, now obtain the second tableau. (You can use the Tab key to move from cell to cell. Press "Check" when done.)


 

Q I pressed the above Help button and saw that the star had vanished from Row 3. Where did it go?
A The basic solution we now get from Row 3 is

z = 10/1 = 10,
which is no longer negative, so the star disappears.

Q Ok the stars are gone. Now what?
A Since there are no more stars, we are now in the feasible region, and can proceed to:
 

Phase II: Do the simplex method as for standard maximization problems.

Revert back to selecting the pivot column using the most negative number in the bottom row (excluding the Answer column). Continue pivoting until there are no negative numbers in the bottom row (with the possible exception of the Answer column).

If you look at the tableau you just obtained, you will see that there is still a negative number there: the -4 in the "y"-column, (press the above Help button to see the current tableau if you do not have it) you will now need to select a pivot in that column in order to pass to the next tableau. Using our usual rule for selecting a pivot in a given column, we see that the pivot is the "4" in Row 1 Column 2, so we pivot on that getting

Since there are no more negative numbers in the bottom row, we are done, and the optimal solution is

Notes

How to Solve Minimization Problems

We deal wth minimzation problems by simply converting them to maximization problems, as illustrated in the following example.

Example: Converting a Minimzation Problem to a Maximization Problem
Here is a minimization problem:

Minimize c = 2x + y + 2z subject to
x + 5y + z 100
x + 2y + z 50
2x + 4y + z 80.

Since minimizing c is the same as maximizing p = -c, we can rewrite the above problem as

Since this problem is a maximization problem with mixed constraints, we can solve it as above. If you would like to see the complete solution of this problem, enter it in the simplex method tool and set it to Integer Mode. You can simply copy the following text and paste it into the top text area:

You now have several options.

Top of Page

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