or
What about nonnegativity?
Suppose we have a basic solution and all the variables are nonnegative. This means we have a basic feasible solution. Now we pivot. What guarantee do we have that the new basic solution is also feasible? If all the variables remain nonnegative, then the solution remains feasible. What promise is there that this will be so? None. We have to make it happen. If the nonbasic variable xn is chosen to enter, then the leaving basic variable xb must be chosen very carefully. The purpose of this page is to learn how to make that choice.
Firstly, how can we tell at a glance that a basic solution is feasible? If the numbers on the righthand side (RHS) are all nonnegative.
A basic solution is feasible if and only if the RHS is nonnegative. |
Secondly, the following is a partial answer to this question: Suppose that we plan to enter the nonbasic variable xn, then who should leave? That is, where is the pivot? Since the RHS is nonnegative and the pivot element can not be equal to zero, we better pivot on a strictly positive value. This will ensure that the new basic variable will be nonnegative. So far so good!
Here is the original problem.
| Maximize z = | 4x1 | + | 3x2 | ||
| Subject to: | 2x1 | + | x2 | £ | 40 |
| x1 | + | x2 | £ | 30 | |
| x1 | £ | 15 | |||
| where | x1 | and | x2 | ³ | 0 |
Below is a matrix that represents a basic feasible solution of this problem (recall that x3, x4, and x5 are the slack variables). Note that the RHS is nonnegative so that the solution is a basic feasible solution. The solution is (15,10,0,5,0). We choose to have x3 as the entering variable. We insist. Which basic variable should be selected to leave?
Begin by choosing x1 to leave. Thus, click the appropriate radio buttons to
select x3 to enter and x1 to leave. Now try to pivot.
The error message is telling you that the pivot
value can not be zero.
Okay, x1 can't leave. So instead, select x4 to leave. Is the basic solution still feasible? NO. You can not choose a negative
pivot value and have the solution remain feasible.
|
|
In summary
If you want a basic feasible solution to remain feasible after pivoting, then you must choose a pivot that is neither zero nor negative. It must be positive. |
Is that all? Are we done? Unfortunately, no. There is still a situation where a feasible solution can become infeasible. To avoid this situation and, at the same time avoid the above, we need the quotient test. This is the subject of the next lesson.