8. Bounded Dual Simplex Algorithm. The dual simplex algorithm (Section 4.4.1) can be modified to accommodate the bounded variables as follows. Given the upper bound constraint Xj :5 Uj for allj (if Uj is infinite, replace it with a sufficiently large upper bound M), the LP problem is converted to a dual feasible (Le., primal optimal) fonn by using the substitution Xj = ui - xi. where necessary.

Step 1. If any of the current basic variables (XB)i exceeds its upper bound, use the substitution (XB)i = (UB); - (XB)i. Go to step 2.

Step 2. If all the basic variables are feasible, stop. Otherwise, select the leaving variable Xr as the basic variable having the most negative value. Go to step 3.

Step 3. Select the entering variable using the optimality condition of the regular dual simplex method (Section 4.4.1). Go to step 4.

Step 4. Perform a change of basis. Go to step l.

Apply the given algorithm to the following problems:

(a) Minimize z = - 3x} - 2x2 + 2x3 subject to o :5 Xl :5 2,0 :5 x2 :5 3, 0 :5 X3 :5 1

(b) Maximize z = Xl + 5x2 - 2X3