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 … uj for all j (if uj is infinite, replace it with a sufficiently large upper-bound M), the LP problem is converted to a dual feasible (i.e., primal optimal) form by using the substitution xj = uj - x=

j, where necessary.

Step 1. If any of the current basic variables 1XB2i exceeds its upper bound, use the substitution 1XB2i = 1UB2i - 1XB2i

=. 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 1.

Apply the given algorithm to the following problems:

(a) Minimize z = -3x1 - 2x2 + 2x3 subject to 2x1 + x2 + x3 … 8 -x1 + 2x2 + x3 Ú 13 0 … x1 … 2, 0 … x2 … 3, 0 … x3 … 1

(b) Maximize z = x1 + 5x2 - 2x3 subject to 4x1 + 2x2 + 2x3 … 26 x1 + 3x2 + 4x3 Ú 17 0 … x1 … 2, 0 … x2 … 3, x3 Ú 0