Consider the linear programming problem
Instead, modify the pivot rules and work with the original tableau.
A variable can be nonbasic at either its lower bound or its upper bound.
If it is at its upper bound, it can enter the basis if its reduced cost is positive. The variable will be decreased.
in the minimum ratio test, ensure that no variable exceeds its upper bound.
Example
Have basic feasible solution:
Since x_{4} is at its upper bound and has a negative reduced cost, we don't bring x_{4} into the basis. Instead, x_{3} enters the basis.
Calculate the simplex direction:
We are increasing x_{3}, so the changes in the basic variables are given
by the negatives of the entries in the x_{3} column of the tableau.
Direction is
Minimum Ratio Test
Taking a step of length t in the simplex direction gives a new point:
Need to keep x within its bounds.
x_{1} is decreasing. Need to keep .
x_{2} is increasing. Need to keep .
x_{3} is increasing. Need to keep .
So choose t=1. x_{2} leaves the basis at its upper bound.
Tableaus
Initial value of objective is z=0-3(1)=-3.
x_{3} enters the basis. By the minimum ratio test, x_{2} leaves the basis at its upper bound.
Value of objective is z=2-2(4)-1(1)=-5.
x_{4} enters the basis and decreases. Thus, x_{1} decreases and x_{3} increases.
The value of the minimum ratio for the basic variables is 2.
The incoming basic variable also provides an upper bound on the maximum possible step length. Since we require , the step length must be .
Thus, the pivot is to keep x_{4} nonbasic, but switch it from being nonbasic at its upper bound to nonbasic at its lower bound.
This tableau is in optimal form.
Optimal value of objective is z=2-2(4)=-6.
x_{2} is at its upper bound, and decreasing x_{2} will increase the objective function value.
x_{4} is at its lower bound, and increasing x_{4} will increase the objective function value.