Thank you for visiting our site! You landed on this page because you entered a search term similar to this: linear equation in two variables subject to linear constraint inequalities.We have an extensive database of resources on linear equation in two variables subject to linear constraint inequalities. Below is one of them. If you need further help, please take a look at our software "Algebrator", a software program that can solve any algebra problem you enter!
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:
|
| Example The following is a standard maximization problem:
4x - 3y + z where x, y, and z are non-negative. The following is not a standard maximization problem:
4x - 3y + z Press here or the "next" 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.
| Step1: 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
- 4x - 3y + z
3x + y + z
102x + y - z
10- p = 2x - 3y + 4z
| 4x | - | 3y | + | z | + | s | = | 3 | ||||||
| x | + | y | + | z | + | t | = | 10 | ||||||
| 2x | + | y | - | z | + | u | = | 10 | ||||||
| -2x | + | 3y | - | 4z | + | p | = | 0 |
Rewrite the following LP problem as a system of linear equations.
- Maximize p = 12x + 15y + 5z subject to the constraints
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.
Example
For the system
| 4x | - | 3y | + | z | + | s | = | 3 | ||||||
| x | + | y | + | z | + | t | = | 10 | ||||||
| 2x | + | y | - | z | + | u | = | 10 | ||||||
| -2x | + | 3y | - | 4z | + | p | = | 0 |
| x | y | z | s | t | u | p | Ans | ||
| 4 | -3 | 1 | 1 | 0 | 0 | 0 |  | 3 | |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | | 10 | |
| 2 | 1 | -1 | 0 | 0 | 1 | 0 | | 10 | |
| -2 | 3 | -4 | 0 | 0 | 0 | 1 | | 0 | |
Set up the first tableau for the following LP problem.
Maximize p = x + 2y + 3z subject to the constraints
- 7x + z
6x + 2y
20 3y + 4z
30 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.
| x | y | z | s | t | u | p | Ans | ||
| 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) | |||||||||
The initial tableau you obtained in the last interactive question is:
| x | y | z | s | t | u | p | Ans | ||
| 7 | 0 | 1 | 1 | 0 | 0 | 0 | | 6 | |
| 1 | 2 | 0 | 0 | 1 | 0 | 0 | | 20 | |
| 0 | 3 | 4 | 0 | 0 | 1 | 0 | | 30 | |
| -1 | -2 | -3 | 0 | 0 | 0 | 1 | | 0 | |
The associated basic solution is:
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.) |
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.
| x | y | z | s | t | u | p | Ans | ||
| 0 | -3 | 1 | 1 | 3 | 0 | 0 | | 3 | test ratio = 3/3 = 1 |
| 4 | 1 | 0 | 0 | 1 | 0 | 0 | | 10 | test ratio = 10/1 =10 |
| 0 | 1 | 0 | -10 | 0 | 2 | 0 | | 10 | |
| 0 | 3 | 0 | 0 | -4 | 0 | 5 | | 15 | |
Since 3/3 = 1 is the smaller of the two test ratios, the pivot is the 3 (which is why it is blinking).
Here is a multiple choice quesion: select (click on) the pivot in the following tableau.
| x | y | z | s | t | u | p | Ans | |
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.
| x | y | z | s | t | u | p | Ans | ||
| 0 | -3 | 1 | 1 | 3 | 0 | 0 | | 3 | |
| 4 | 1 | 0 | 0 | 1 | 0 | 0 | | 10 | 3R2 - R1 |
| 0 | 1 | 0 | -10 | 0 | 2 | 0 | | 10 | |
| 0 | 3 | 0 | 0 | -4 | 0 | 5 | | 15 | 3R4 + 4R1 |
This gives the next tableau:
| x | y | z | s | t | u | p | Ans | |
| 0 | -3 | 1 | 1 | 3 | 0 | 0 | | 3 |
| 12 | 6 | -1 | -1 | 0 | 0 | 0 | | 27 |
| 0 | 1 | 0 | -10 | 0 | 2 | 0 | | 10 |
| 0 | -3 | 4 | 4 | 0 | 0 | 15 | | 57 |
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.
Here is the first tableau we have been working with in the interactive qeustions.
| x | y | z | s | t | u | p | Ans | |
| 7 | 0 | 1 | 1 | 0 | 0 | 0 | | 6 |
| 1 | 2 | 0 | 0 | 1 | 0 | 0 | | 20 |
| 0 | 3 | 4 | 0 | 0 | 1 | 0 | | 30 |
| -1 | -2 | -3 | 0 | 0 | 0 | 1 | | 0 |
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). |