|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|
|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:
The following is a standard maximization problem:
4x - 3y + z 3
The following is not a standard maximization problem:
4x - 3y + z 3
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.
Rewrite the following LP problem as a system of linear equations.
2x + 2y + z 8
x + 4y - 3z 12,
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.
For the system
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.
In the following tableau, the active variables are shown in color and their values computed as illustrated.
|0||-3||1||1||3||0||0||3||z = 3/1 = 3|
|4||1||0||0||1||0||0||10||x = 10/4 = 2.5|
|0||1||0||-10||0||2||0||10||u = 10/2 = 5|
|0||3||0||0||-4||0||5||15||p = 15/5 = 3|
|y = 0, s = 0, t = 0 (inactive)|
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:
|z||0||-3||1||1||3||0||0||3||z = 3/1 = 3|
|x||4||1||0||0||1||0||0||10||x = 10/4 = 2.5|
|u||0||1||0||-10||0||2||0||10||u = 10/2 = 5|
|p||0||3||0||0||-4||0||5||15||p = 15/5 = 3|
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.
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.)
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.
|z||0||-3||1||1||0||0||3||test ratio = 3/3 = 1|
|x||4||1||0||0||1||0||0||10||test ratio = 10/1 =10|
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.)
In the following tableau, the pivot is shown in color, and we clear its column using the given row operations.
|x||4||1||0||0||1||0||0||10||3R2 - R1|
|p||0||3||0||0||-4||0||5||15||3R4 + 4R1|
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:
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:
You now have several options.