The Simplex Method:
Step 8

The Min Ratio Test

Once we are guaranteed that we will not increase the entering variable without bound, we need to calculate how much it can increase. To help give you an idea of this, here is a java applet.

The red bars represent the values of the basic variables for some linear program. The slide bar represents the value of an incoming variable to the basis. When the slide bar is moved up from zero, it changes the values of the other variables depending on the search direction. Notice that some of the values increase, some of the values decrease, and some do not change at all as the slide bar is moved up from zero. Since there is a non-negativity constraint on the values of x, the first variable that hits the line limits us from increasing the entering variable further. In the applet, the second variable is the limiting one.

The way the limiting variable is found is by calculating the quantity xBi / yBi where Bi are each of the basic variables. These ratios are only computed when the search direction, yBi is positive. In the applet above, you can see the ratios where it is appropriate. Notice the variable with the minimum of these is the variable that leaves the basis (goes to zero). This is always the case. The minimum ratio is referred to as theta.

There are only a couple of more steps to go. Here is a link the the next one.


[ Indice spiegazione | Applet di calcolo | Torna indietro ]