The previous lesson taught us that we can not choose a pivot that is zero or negative if we want a basic feasible solution to remain feasible. It was mentioned then that there is still more to do. We continue with our usual example.
| Maximize z = | 4x1 | + | 3x2 | ||
| Subject to: | 2x1 | + | x2 | £ | 40 |
| x1 | + | x2 | £ | 30 | |
| x1 | £ | 15 | |||
| where | x1 | and | x2 | ³ | 0 |
The matrix below represents another basic feasible solution of the above linear programming problem. We wish to pivot again, this time entering x4. It should be obvious that x1 can not leave because the pivot would be negative. We must choose between x5 and x2.
|
|
First choose x2 to leave, then pivot. What happened to RHS? One of its values became negative. The basic feasible solution became infeasible. Now push the 'reset' button to return and select x5 as the leaving variable. Now pivot. All is okay, isn't it? The RHS is all positive, still ensuring that the basic solution remains feasible.
What made the difference? Here is a picture of the x4 and RHS columns together with a comparison of the quotients between their entries.
| Basic | x4 | RHS | Quotient | ||
|---|---|---|---|---|---|
| x1 | -1 | 10 | 10/-1 | = | -10 |
| x5 | 1 | 5 | 5/1 | = | 5 |
| x2 | 2 | 20 | 20/2 | = | 10 |
The only leaving variable we could choose, x5, has the smallest positive quotient. In this example, the smallest positive quotient is 5. This will always be our choice.
In summary
If you want a basic feasible solution to remain feasible after pivoting, then you must choose a leaving variable that has the smallest positive quotient. |
Okay. I know how to choose the leaving variable. But how do I decide which variable to enter? And what happened to the objective function? This is the subject of the next lesson.