5 This problem concerns the following linear program: Maximize 3x + 7x + 5x3+4x4 + 6x5...

Transcribed Image Text:

5 This problem concerns the following linear program: Maximize 3x + 7x + 5x3+4x4 + 6x5 + 3x6 Subject to 4x + 2x + 3x4 + 6x5 + 6x 20 + 3x6 18 4x1 + 6x + 8x3 + 2x4 3x1 + 5x2 + 5x3 + 2x4 + 2x5 + 2x6 16 XX60 a: Transform this LP into our standard form for computation with only equal- ity constraints by adding appropriate nonnegative slack variables (The maximization objective does not need to be changed to a minimization func- tion). b: An implementation of the simplex method has found an optimal solution to the original LP to be given by x* = (x1.x.x.x.x.x) = (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 re- duced costs. That means - since you are maximzing that there are no candidates to enter the basis. Nevertheless, if you were to choose x, 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. 5 This problem concerns the following linear program: Maximize 3x + 7x + 5x3+4x4 + 6x5 + 3x6 Subject to 4x + 2x + 3x4 + 6x5 + 6x 20 + 3x6 18 4x1 + 6x + 8x3 + 2x4 3x1 + 5x2 + 5x3 + 2x4 + 2x5 + 2x6 16 XX60 a: Transform this LP into our standard form for computation with only equal- ity constraints by adding appropriate nonnegative slack variables (The maximization objective does not need to be changed to a minimization func- tion). b: An implementation of the simplex method has found an optimal solution to the original LP to be given by x* = (x1.x.x.x.x.x) = (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 re- duced costs. That means - since you are maximzing that there are no candidates to enter the basis. Nevertheless, if you were to choose x, 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.