Note There should be navigation links on the left. If you got here directly from the outside world and see nothing on the left, press here to bring up the frames that will allow you to properly navigate this tutorial and site.
 | Download Simplex Method Software
for your Mac |
 | Pivot & Gauss-Jordan Tool
(New Javascript Version) |
 |
Pivoting program for
TI 82 and TI 83 |
| Simplex Method Tool |
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.
N Examples
The following are not standard maximization problems (reasons shown in red):
| 1. | Non-Standard Maximization Problem | |
| Maximize p = 2x - 3y + 4z subject to | ||
4x + 2y + z  10 |
||
| x + y - z 5 |
Non-standard constraint | |
| x 0, y 0, z 0. |
||
| 2. | Minimzation Problem | |
| Minimize c = 2x + 3y + 4z subject to | Minimize problem | |
| 4x + 2y + z 10 |
||
| x + y - z 5 |
Non-standard constraint | |
| x 0, y 0, z 0. |
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 method we use in Finite Mathematics and Finite Mathematics and Applied Calculus.
How to Solve a General Maximization Problems
These are liuner programming problems in which you are asked to maximize an objective function, but where at least one of the constraints may be a constraint.
| Step1: 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 . For the constraints, we need to subtract "surplus" variables. Thus, for instance, the constraint
5
Rewrite the following LP problem as a system of linear equations.
40
10
10,
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:
40
10
10,
where x, y, and z are non-negative. (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:
| x | y | z | s | t | u | p | Ans | |||
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |  | 40 | ||
| * | 2 | 1 | -1 | 0 | -1 | 0 | 0 | | 10 | |
| * | 0 | -1 | 1 | 0 | 0 | -1 | 0 | | 10 | |
| -2 | -3 | -1 | 0 | 0 | 0 | 1 | | 0 | ||
Our first order of business is to get into the feasible region, or, equivalently,
|
We can (eventually) get rid of all the stars by pivoting several 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.
|
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
| x | y | z | s | t | u | p | Ans | |||
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | | 40 | ||
| * | 2 | 1 | -1 | 0 | -1 | 0 | 0 | | 10 | This is the first starred row |
| * | 0 | -1 | 1 | 0 | 0 | -1 | 0 | | 10 | |
| -2 | -3 | -1 | 0 | 0 | 0 | 1 | | 0 | ||
To select the pivot, identify the smallest test ratio:
| x | y | z | s | t | u | p | Ans | ||||
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | | 40 | Test Ratio: 40/1 = 40 | ||
| * | 2 | 1 | -1 | 0 | -1 | 0 | 0 | | 10 | Test Ratio: 10/2 = 5 | Smallest test ratio |
| * | 0 | -1 | 1 | 0 | 0 | -1 | 0 | | 10 | ||
| -2 | -3 | -1 | 0 | 0 | 0 | 1 | | 0 | |||
Thus, we pivot on the "2" in Row 2, and we get the following tableau (check this yourself!)
| x | y | z | s | t | u | p | Ans | |||
| 0 | 1 | 3 | 2 | 1 | 0 | 0 | | 70 | ||
| 2 | 1 | -1 | 0 | -1 | 0 | 0 | | 10 | ||
| * | 0 | -1 | 1 | 0 | 0 | -1 | 0 | | 10 | |
| 0 | -2 | -2 | 0 | 0 | 0 | 1 | | 10 | ||
Q What happened to the star in Row 2?
A It is gone, because the basic solution we now get from Row 2 is
Since there is still one starred row left, we are not done with Phase I.
Click on any 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
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 usual: pivot until there are no negative numbers in the bottom row (with the possible exception of the Answer column). |
Since 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
| x | y | z | s | t | u | p | Ans | |||
| 0 | 4 | 0 | 2 | 1 | 3 | 0 | 40 | |||
| 2 | 0 | 0 | 0 | -1 | -1 | 0 | | 20 | ||
| 0 | 0 | 4 | 2 | 1 | -1 | 0 | | 80 | ||
| 0 | 0 | 0 | 2 | 0 | 1 | 1 | | 70 | ||
Since there are no more negative numbers in the bottom row, we are done, and the optimal solution is
Note
After a pivoting step in Phase I, no stars may vanish, but no extra stars should arise. To decide which rows to star at each step, check the basic solution:.
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
100
50
80.
Since minimizing c is the same as maximizing p = -c, we can rewrite the above problem as
100
50
80.
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.
