As we indicated at the outset, the standard linear programming formulation requires all the variables to be non-negative. Thus, we need a mechanism to ensure that
- The initial basic solution is non-negative.
- The new basic solution we generate by pivoting is non-negative.
Thus, in the context of our table environment, or rather tableau as it is called endearingly, we have to make sure that the initial entries in the RHS column are non-negative and that this column remains nonnegative throughout the process.
The issue concerning the construction of an initial tableau comprising a non-negative basic solution is an important modelling issue that we shall discuss at a later stage. For the time being we assume that our initial tableau satisfies this condition.
The question is then:
Given that we intend to bring xj into the basis, what basic variable should we take out of the basis to ensure that the RHS remains non-negative?
The following is a partial answer to this question: suppose that we plan to bring column j into the basis. Since the RHS is non-negative and the pivot element will not be equal to zero, we better pivot on a strictly positive entry. This will ensure that the new basic variable will be non-negative. This simple rule guarantees that the new basic variable will be non-negative. So far so good!
But how about ensuring that the other (old) basic variables will remain non-negative? The answer is not too complicated either: make sure that if you pivot on (row i, column j) then
RHS i
------
t i,j<= RHS k
------
t k,jfor all rows k for which t k,j > 0. Here t i,j denote the (i,j)th entry of the simplex tableau (ignoring the headers). This is the famous ratio test of the simplex method.
In practice it dictates the following:
Variable Leaving the Basis
If you plan to bring column j into the basis, then take out of the basis the basic variable associated with row i, where i is any row where the ratio test attains its minimum value.In summary, using the simple ratio test we ensure that the basic solutions we generate by pivoting are nonnegative hence basic feasible: not only that they are basic solutions to the functional constaints, they are also non-negative. Obviously, for this scheme to make sense we must require the RHS to be non-negative at the outset!! We shall deal with this issue shortly, for the time being we shall assume that this is indeed so. Suffice it to say that this is a minor technical issue.
Now, what happens if for a given nonbasic variable, say x j, we have t i,j <= 0, for all i, namely the entire columm is non-positive? According the above analysis we shall not be able to force any basic variable to zero regardless how much we increase xj. We shall discuss the implications of this scenario shortly. For the time being we shall refer to such cases as unbounded cases.
Next, what happens if for a given nonbasic variable, say x j we have t i,j <= 0, for all i, namely the entire columm is non-positive? According the above analysis we shall not be able to force any basic variable to zero regardless how much we increase xj. We shall discuss the implications of this scenario shortly.
So now we can redesign our Simplex Machine, namely we can let It decide which variable should leave the basis! For your convenience we display the results of the ratio test. Here is the new model. Play with it!
Remarks:
- Observe that you can still select the variable leaving the basis, but this is optional: if you don't, the Machine will use the Ratio Test Rule to select the proper leaving variable .
- If necessary use the "CL" button to cancel your selection of a pivot row.
- You can use the "RT" button to comupte the ratios for any selected new basic variable (column).
- For your convenience there is a choice between a framed and an unframed version of this page.
Life is beautiful indeed!