On-line Pivot & Gauss-Jordan Tool | Excel Pivot & Gauss-Jordan Tool | |||
Pivoting program for TI 82 and TI 83 | On-line 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.
Examples
The following are not standard maximization problems (reasons shown next to the offending statements):
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 easy method we use in the textbooks, Finite Mathematics and Finite Mathematics and Applied Calculus.
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
Rewrite the following LP problem as a system of linear equations.
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:
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 | |||
s | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 40 | ||
* | t | 2 | 1 | -1 | 0 | -1 | 0 | 0 | 10 | |
* | u | 0 | -1 | 1 | 0 | 0 | -1 | 0 | 10 | |
p | -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 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.
|
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 | ||||
s | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 40 | |||
* | t | 2 | 1 | -1 | 0 | -1 | 0 | 0 | 10 | This is the first starred row. | |
* | u | 0 | -1 | 1 | 0 | 0 | -1 | 0 | 10 | ||
p | -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 | ||||
s | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 40 | Test ratio 40/1 = 40 | ||
* | t | 2 | 1 | -1 | 0 | -1 | 0 | 0 | 10 | Test Ratio: 10/2 = 5 (Smallest). | |
* | u | 0 | -1 | 1 | 0 | 0 | -1 | 0 | 10 | ||
p | -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 | |||
s | 0 | 1 | 3 | 2 | 1 | 0 | 0 | 70 | ||
x | 2 | 1 | -1 | 0 | -1 | 0 | 0 | 10 | ||
* | u | 0 | -1 | 1 | 0 | 0 | -1 | 0 | 10 | |
p | 0 | -2 | -2 | 0 | -1 | 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 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
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:
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
x | y | z | s | t | u | p | Ans | |||
y | 0 | 4 | 0 | 2 | 1 | 3 | 0 | 40 | ||
x | 2 | 0 | 0 | 0 | -1 | -1 | 0 | 20 | ||
z | 0 | 0 | 4 | 2 | 1 | -1 | 0 | 80 | ||
p | 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
Notes
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:
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.