Assignment

1. Consider the following problem:

Max Z = 5x1 + 4x2 + 3x3

s.t. x1 + x3 <= 6 2x2 + x3 <= 6 x1, x2, x3 >= 0

(a) Construct the dual for this problem and solve it graphically.

(b) Use the solution in part (a) to identify the shadow prices for the resources in the primal problem.

(c) Confirm your results by solving the original problem using the simplex method and identifying the shadow prices from the final tableau.

2. Solve one iteration of the following problem using the interior-point algorithm starting with an initial trial solution of (4, 1, 0) and alpha = 0.5.

Max Z = 2x1 + 5x2 + 8x3
s.t. x1 + 2x2 + 3x3 = 6
x1, x2, x3 ≥ 0

What is the new solution (x1, x2, x3, and Z), and how much does Z improve from the initial trial solution given above?

3. Given the following original problem:

max Z = 3x1 + 2x2 + x3
s.t. 4x1 + x2 + x3 <= 30 2x1 + 3x2 + x3 <= 60 x1 + 2x2 + 3x3 <= 40
x1, x2, x3 >= 0

Answer the following questions given only the following information from SOME ITERATION of the simplex tableau, with s4, s5, and s6 representing the slack variables for constraints 1, 2, and 3, respectively.

Basic Z x1 x2 x3 s4 s5 s6 RHS
Z
x1 0.25 0 0
s5 -0.5 1 0
s6 -0.25 0 1

(a) What is the optimal solution (Z, x1, x2, x3)?

(1) What is the allowable range for b1 (originally 30) for this solution to stay optimal?

(II) Evaluate your solution if the coefficients for x3 change to 5 in the objective function, 2 in the first constraint, 4 in the second constraint, and 3 in the third constraint.

(III) Write the dual for the original problem.

(IIII) Solve the dual and give the optimal solution (y0, y1, y2, y3).

(IIIII) Using the original problem, if a new constraint enters the analysis with 2x1+ 3x2 + 5x3 <= 40, would the current solution still be feasible and optimal?

(....) Using the original problem, if a new variable enters the analysis (say x8), with c8 = 5, a18 = 3, a28 = 2, and a38 = 1, would the current solution remain feasible and optimal?

(.....) What is the allowable range for c2 in the objective function for the current solution to remain optimal?