We've learned to wisely choose the leaving variable to ensure that a basic feasible solution remains feasible. The choice is determined by the smallest positive quotient. In order to make this choice we must first know the entering variable. How are we to decide which of the variables to enter? By examining the objective function. The goal is to make the objective function, z, as large as possible. Choose the entering variable that will make the largest possible increase in z. Let's see how this can be done.
Here again is our standard maximizing problem.
| Maximize z = | 4x1 | + | 3x2 | ||
| Subject to: | 2x1 | + | x2 | £ | 40 |
| x1 | + | x2 | £ | 30 | |
| x1 | £ | 15 | |||
| where | x1 | and | x2 | ³ | 0 |
We introduced slack variables, s1, s2, and s3 , turning the inequalities into equalities. For convenience we renamed the slack variables x3, x4, and x5. Our problem now looks like this:
| 2x1 | + | x2 | + | x3 | = | 40 | ||
| x1 | + | x2 | + | x4 | = | 30 | ||
| x1 | + | x5 | = | 15 |
We now rewrite the objective function so that it has the same style as these equations. All the variables on one side of the equation, a constant on the other. Here is the objective equation.
-4x1 -3x2 + z = 0 |
We now have a new variable, z, to include among the others. Here is what our problem looks like.
| 2x1 | + | x2 | + | x3 | = | 40 | ||||
| x1 | + | x2 | + | x4 | = | 30 | ||||
| x1 | + | x5 | = | 15 | ||||||
| - | 4x1 | - | 3 x2 | + | z | = | 0 |
Ignoring the decorations once again, we have the initial simplex tableau (table).
| Basic | x1 | x2 | x3 | x4 | x5 | z | RHS |
|---|---|---|---|---|---|---|---|
| x3 | 2 | 1 | 1 | 0 | 0 | 0 | 40 |
| x4 | 1 | 1 | 0 | 1 | 0 | 0 | 30 |
| x5 | 1 | 0 | 0 | 0 | 1 | 0 | 15 |
| z | -4 | -3 | 0 | 0 | 0 | 1 | 0 |
z = 4x1 + 3x2 |
The current value of z is zero because both x1 and x2 are zero. Which one should we make nonzero if our objective is to make z larger? I hope you chose x1. Its coefficient is larger than x2 which will produce a greater increase in z. This will be our method from now on. Choose the variable to enter that produces the greatest increase in z. How can we tell from the simplex tableau which variable this is? Look at the last row. Where is the LARGEST NEGATIVE number you see? What COLUMN is it in? What variable is at the top of the column? You've found your entering variable.In a nutshell here is how we decide which variable to enter.
In summary, a new row is appended to the table (at the bottom) comprising the negative values of the coefficients of
the objective function. A new column associated with z is also added. The largest negative number in
the bottom row identifies the entering variable. We can now find the quotients. The smallest positive quotient identifies the leaving variable. Here are some problems to practice on.
Okay. I know how to find the basic feasible solution from a simplex tableau and how to find the entering and leaving variables. These choices ensure that the new basic
solution remains feasible. What's next? It's time to put it all together in the last
lesson!
The largest negative number in the bottom row identifies the entering variable.
Basic x2 x3 x4 x5 z RHS Quotients x3 2 1 1 0 0 0 40 40/2=20 x4 1 1 0 1 0 0 30 30/1=30 x5 1 0 0 0 1 0 15 15/1=15 z -4 -3 0 0 0 1 0 ignore me
Exercises
Each of the tables below is the simplex tableau of a standard maximizing problem. For each of them find
Return to Index
Return to top of page
Return to Previous Lesson
Proceed to Next Lesson