OTHER ALGORITHMS FOR LINEAR PROGRAMMING:THE UPPER BOUND TECHNIQUE

THE UPPER BOUND TECHNIQUE

It is fairly common in linear programming problems for some of or all the individual xj

where uj is a positive constant representing the maximum feasible value of xj. We pointed out in Sec. 4.8 that the most important determinant of computation time for the simplex method is the number of functional constraints, whereas the number of nonnegativity con- straints is relatively unimportant. Therefore, having a large number of upper bound constraints among the functional constraints greatly increases the computational effort required.

The upper bound technique avoids this increased effort by removing the upper bound constraints from the functional constraints and treating them separately, essentially like nonnegativity constraints.5 Removing the upper bound constraints in this way causes no problems as long as none of the variables gets increased over its upper bound. The only time the simplex method increases some of the variables is when the entering basic vari- able is increased to obtain a new BF solution. Therefore, the upper bound technique sim- ply applies the simplex method in the usual way to the remainder of the problem (i.e., without the upper bound constraints) but with the one additional restriction that each new BF solution must satisfy the upper bound constraints in addition to the usual lower bound (nonnegativity) constraints.

To implement this idea, note that a decision variable xj with an upper bound con- straint xj ::: uj can always be replaced by

5The upper bound technique assumes that the variables have the usual nonnegativity constraints in addition to the upper bound constraints. If a variable has a lower bound other than 0, say, xj 2: Lj, then this constraint can be converted into a nonnegativity constraint by making the change of variables, xj'= xj - Lj, so xj'2: 0.

Whenever xj = uj, use choice 2, so yj = 0 is nonbasic.

Switch choices only when the other extreme value of xj is reached.

Therefore, whenever a basic variable reaches its upper bound, you should switch choices and use its complementary decision variable as the new nonbasic variable (the leaving ba- sic variable) for identifying the new BF solution. Thus, the one substantive modification being made in the simplex method is in the rule for selecting the leaving basic variable.

Recall that the simplex method selects as the leaving basic variable the one that would be the first to become infeasible by going negative as the entering basic variable is in- creased. The modification now made is to select instead the variable that would be the first to become infeasible in any way, either by going negative or by going over the up- per bound, as the entering basic variable is increased. (Notice that one possibility is that the entering basic variable may become infeasible first by going over its upper bound, so that its complementary decision variable becomes the leaving basic variable.) If the leaving basic variable reaches zero, then proceed as usual with the simplex method. However, if it reaches its upper bound instead, then switch choices and make its comple- mentary decision variable the leaving basic variable.

The two equality constraints are already in proper form from Gaussian elimination for identifying the initial BF solution (x1 = 0, x2 = 12, x3 = 4), and none of the variables in this solution exceeds its upper bound, so x2 and x3 can be used as the initial basic variables without artificial variables being introduced. However, these variables then need to be eliminated algebraically from the objective function to obtain the initial Eq. (0), as follows:

To start the first iteration, this initial Eq. (0) indicates that the initial entering basic variable is x1. Since the upper bound constraints are not to be included, the entire initial set of equations and the corresponding calculations for selecting the leaving basic variables are those shown in Table 8.4. The second column shows how much the entering basic vari- able x1 can be increased from zero before some basic variable (including x1) becomes in- feasible. The maximum value given next to Eq. (0) is just the upper bound constraint for x1. For Eq. (1), since the coefficient of x1 is positive, increasing x1 to 3 decreases the ba- sic variable in this equation (x2) from 12 to its lower bound of zero. For Eq. (2), since the coefficient of x1 is negative, increasing x1 to 1 increases the basic variable in this equation (x3) from 4 to its upper bound of 6.