This problem concerns the following linear program:

Maximize 3x1 + 7x2 + 5x3 + 4x4 + 6x5 + 3x6

Subject to 4x1 + 2x2 + 3x4 + 6x5 + 6x6 20

4x1 + 6x2 + 8x3 + 2x4 + 3x6 = 18

3x1 + 5x2 + 5x3 + 2x4 + 2x5 + 2x6 16

x1, . . . , x6 0

a: Transform this LP into our standard form for computation with only equality constraints by adding appropriate nonnegative slack variables (The maximization objective does not need to be changed to a minimization function).

b: An implementation of the simplex method has found an optimal solution to the original LP to be given by x = (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) = (0, 0, 0, 6, 0, 2). By determining the appropriate values for the slack variables, translate this to a solution of the LP you wrote in part (a). Determine which are the basic variables, and write out the corresponding basis matrix.

c: Verify that the solution found in part (b) is optimal by computing the reduced costs of the nonbasic variables.

d: You should have found that all the nonbasic variables have non-positive reduced costs. That means since you are maximzing that there are no candidates to enter the basis. Nevertheless, if you were to choose x5 to enter the basis, and were to carry out an iteration by the usual rules for the simplex method, then you would determine another basis for the primal LP. Explain how you can tell, just by looking at the reduced cost of x5, that the new basis will also be optimal.

e: Carry out the iteration suggested by part (d), and determine the feasible solution associated with the new basis that results. Verify that this solution also gives the optimal value for the objective function.