LINEAR EQUATION IN TWO VARIABLES SUBJECT TO LINEAR CONSTRAINT INEQUALITIES
Pre-Algebra chapter 2 evaluate expressions, worksheet triangle expressions answers ,     TI- 83 ,84 graphing calculator step by step of how to use to find slope of lines graphing calculator What are sqaure root method of Quadratic Equations?
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

 
Subject to one or more linear constraints of the form
 

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:

  • We are to find the maximum (not minimum) value of the objective function.
  • All the variables x, y, z, ... are constrained to be non-negative.
  • All further constraints have the form Ax + By + Cz + . . . N (and not ).
Example

The following is a standard maximization problem:

    Maximize p = 2x - 3y + 4z subject to the constraints

    4x - 3y + z 3
    x + y + z 10
    2x + y - z 10,

where x, y, and z are non-negative.

The following is not a standard maximization problem:

    Maximize p = 2x - 3y + z subject to

    4x - 3y + z 3
    x + y + z 10

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 3
    x + y + z 10
    2x + y - z 10
in the above LP problem are written as equations by adding a new "slack" variable to the left-hand side of each to "take up the slack." In addition, the objective function
    p = 2x - 3y + 4z
is rewritten with all the unknowns on the left-hand side. This gives the following system of equations.
    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
the initial tableau is as follows (notice how we separate the last row using a line).
    xyzstupAns

    4-31 10003
    11101 0010
    21-1001010

    -23-40001 0

Set up the first tableau for the following LP problem.

Maximize p = x + 2y + 3z subject to the constraints

    7x + z 6
    x + 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.

    xyzstupAns

    0-31 13003z = 3/1 = 3
    41001 0010x = 10/4 = 2.5
    010-1002010u = 10/2 = 5

    0300-405 15p = 15/5 = 3
    y = 0, s = 0, t = 0 (inactive)

The initial tableau you obtained in the last interactive question is:

    xyzstupAns

    701 10006
    12001 0020
    034001030

    -1-2-30001 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.)
2) For each positive entry b in the pivot column, compute the ratio a/b, where a is the number in the rightmost column in that row. We call this a test ratio.
3) Of these ratios, choose the smallest one. The corresponding number b is the pivot.

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.

    xyzstupAns

    0-3113003test ratio = 3/3 = 1
    41001 0010test ratio = 10/1 =10
    010-1002010

    0300-405 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.

    xyzstupAns

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.

    xyzstupAns

    0-3113003
    41001 00103R2 - R1
    010-1002010

    0300-405 153R4 + 4R1

This gives the next tableau:

    xyzstupAns

    0-3113003
    126-1-10 0027
    010-1002010

    0-3440015 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.

    xyzstupAns

    701 10006
    12001 0020
    034001030

    -1-2-30001 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).