So far so good!
We established a framework for incorporating the objective function of a LP problem into the Gaussian elimination scheme as well as for keeping the decision variables non-negative. We now have to address the obvious question: how do we optimize the objective function?
The answer is straight forward, namely: we choose the next pivot operaion so that it will "improve" the value of the objective function. That is, if we minimize the objective function then we choose the next pivot operation so that it will decrease the value of the objective function and if we maximize the objective function the next pivot operation is choosen so that the value of the objective function pertaining to the resulting basic feasible solution is increased.
The following key observation suggests a number of heuristics for determining the new basic variable:
| The reduced costs of the non-basic variables in a canonical simplex tableau are equal to the marginal decrease in the objective function pertaining to these variables |
Before we show why this is so let us examine a simple example to ensure that the term marginal decrease in the objective function is fully understood.
| BV | x1 | x2 | x3 | x4 | x5 | RHS |
|---|---|---|---|---|---|---|
| x3 | 2 | 1 | 1 | 0 | 0 | 40 |
| x4 | 1 | 1 | 0 | 1 | 0 | 30 |
| x5 | 1 | 0 | 0 | 0 | 1 | 15 |
| z | -4 | -3 | 0 | 0 | 0 | 0 |
There are two non-basic variables here, namely x1 and x2, whose reduced costs are equal to -4 and -3 respectively. The above observation asserts that the marginal decrease in the objective function with respect x1 is equal to -4 and with respect to x2 is equal to -3.
If this is indeed true, then a "small" increase, say q, in x1 will result in a decrease of q(-4) in the value of the objective function. Similarly, a "small" increase, say p, in x2 will result in a decrease of p(-3) in the objective function. This is so because Z-row of the tableau represent the following equation:
Thus, an increase of q units in x1 results in an increase of 4q units in the objective function or equivalently a decrease of -4q units.
The term "small" is used here to guard against the possibility that by increasing the value of a non-basic variable (from zero) we do not force any basic variable to become negative. The question of how small the increase should/can was discussed under the header "Ratio Test" in the preceeding chapter. We draw your attention to the fact that in certain pathological cases "small" means zero, in which case the observation is trivially true but not very informative.
The implications of this observation can be summarised as follows:
If you push this argument one step further you'll find the following:
| Greedy Rule for Selecting New Basic Variable |
|
Furthermore, this observation also supplies the following:
| Stopping Rule |
|
In short, to optimize the objective function you keep iterating (pivoting) using the above rules until the Stopping rule instructs you to stop. Observe that once you select a new basic variable (column) say accoring to the Greedy Rule, the basic variable to leave the basis is determined by the Ratio Test, which is basically fully automated in that it does not need human intervention, except perhaps in cases where it produces a tie.
The following form provides a facility for experimenting with the entire process. If you don't specify the new basic variable yourself, it will be selected automatically using the Greedy Rule.
Have fun!
Due to a JavaScript super-bug, on some platforms the last radio bottom - beg your pardon - button, on a form cannot be turned off on the screen. So the fact that you see it on does not mean that it is on computationally. To check whether or not your platform is infected
This should turn off all the radio buttons.
If you are infected, do the following:
|
If you want these facilities you'll be pleased to hear that they will be available, hopefully soon!
Back to the front page.