Mathematics 340 Homework 8 Due Mar. 19th
You will not be able to use a calculator or computer for either the midterm or the final exam, so please do not use one for this assignment. You may use one to check your answer, but please do not use one to solve the problem.
Only part of the problems may be graded. But, you have to submit all the problems.
Submit only pdf files.
1. Given the following dictionary of a primal problem, find the corresponding dual dic- tionary. Express the corresponding basic (infeasible) solution for the dual problem in terms of the dual decision variables and dual slack variables.
Z=2−3×1 +x3 x2 =2 −x1 −x3 x4 = 3 −2×1 +x3 x5 =4 +x1 +x3
Solution:
Recall the correspondence between the primal and dual variables. As there are 2 original variables and 3 slack variables, we have
xj ←→zj =uj forj=1,2, x2+i ←→ z2+i = yi for i = 1, 2, 3.
Then, use the “− transpose” property of the dual dictionary
−W = −2 −2z2 −3z4 −4z5 z1 = 3 +z2 +2z4 −z5 z3 = −1 +z2 −z4 −z5
Thedualdecisionvariablesarey1 =z3 =−1,y2 =z4 =0,y4 =z5 =0,and thedualslackvariablesareu1 =z1 =3,u2 =z2 =0.
2. Consider the following LP problem.
Minimize Subject to
W = 3×1 +2×2 −x1 +2×2 2×1 −3×2
≥ 4
≥ 6 x1, x2 ≥0
Page 1 of 5
Mathematics 340 Homework 8 Due Mar. 19th (a) Rewrite the above LP in standard form (do not give the dual of this problem).
Solution:
This becomes
where Z = −W.
Maximize Subject to
Z =
−3×1 −2×2
x1 −2×2 ≤ −4
−2×1 +3×2 ≤ −6 x1, x2 ≥0
(b) What is dictionary corresponding to the LP in your answer to part (a)?
Solution:
In dictionary form this is
Z = −3×1 −2×2 x3 = −4 −x1 +2×2 x4 = −6 +2×1 −3×2
(c) Your answer to part (b) should be a dictionary that is not feasible, but is dual- feasible (that is, its corresponding dual dictionary is feasible). Use the dual- simplex method to find the optimal dictionary (for the LP problem of (a)) and so solve the original LP problem. (Remember to choose the most negative basic variable to be the leaving variable.) (To earn credits for this problem, you have to use the dual simplex method.)
Solution:
The most negative basic variable is x4 — it leaves
Rewrite this as 0 = −6+2×1 −3×2 −x4 and add q× this equation to the
equation for z:
Z =−6q+x1(−3+2q)+x2(−2−3q)−qx4
Hence q = 3/2 and x1 enters.
Pivoting gives
Z = −9 −(13/2)x2 −(3/2)x4
x1 = 3 +(3/2)x2 +(1/2)x4 x3 = −7 +(1/2)x2 −(1/2)x4
Page 2 of 5
Mathematics 340 Homework 8 Due Mar. 19th
Still not feasible. Now x3 leaves.
Rewrite pivot row as 0 = −7 + (1/2)x2 − (1/2)x4 − x3 and add q× this
equation to z:
Z =−9−7q+x2(−13/2+q/2)+x4(−3/2−q/2)−qx3
Hence q = 13 and x2 enters.
Pivoting gives
Z = −100 −13×3 −8×4
x1 = 24 +3×3 +2×4 x2 = 14 +2×3 +x4
This is now dual-feasible and feasible, and hence optimal.
The optimal solution is
x1 =24 x2 =14 z=−100 w=100.
3. Consider the following LP.
Maximize Z = −5×1 + 5×2 + 13×3, subject to
−x1 +x2 +3×3 ≤20 12×1 +4×2 +10×3 ≤ 90
andx1,x2,x3 ≥0.
With x4 and x5 as the slack variables, the simplex methods yields the following optimal
dictionary
Z = 100 −2×3 −5×4 x2 = 20 +x1 −3×3 −x4 x5 = 10 −16×1 +2×3 +4×4
Perform sensitivity analysis by independently investigating each of the following six changes in the original model. For each change, use sensitivity analysis procedure to revise the optimal dictionary to identify and evaluate the updated basic solution. Then test this solution for feasibility and for optimality. (Do not reoptimize.)
(a) Change the right-hand side of constraint 1 to b′1 = 30.
Page 3 of 5
Mathematics 340 Homework 8 Due Mar. 19th
Solution: We replace x4 with x′4 − 10 since b′1 = b1 + 10.
Z = 150
x2 = 30 +x1 x5 = −30 −16×1
−2×3 −5x′4 −3×3 −x′4 +2×3 +4x′4 .
The dictionary is now infeasible and superoptimal.
(b) Change the right-hand side of constraint 2 to b′2 = 70.
Solution: We replace x5 with x′5 + 20 because b′2 = b2 − 20. This is the same as subtracting 20 from the basic value of x5.
Z = 100 −2×3 −5×4 x2 = 20 +x1 −3×3 −x4 x′5 = −10 −16×1 +2×3 +4×4
The dictionary is infeasible and superoptimal.
(c) Change the right-hand sides to b′1 = 10 and b′2 = 100.
Solution: We replace x4 with x′4 + 10 and x5 with x′5 − 10.
Z = 50 −2×3 −5x′4 x2 = 10 +x1 −3×3 −x′4 x′5 = 60 −16×1 +2×3 +4x′4
The dictionary is still feasible and optimal.
(d) Change the coefficient of x3 in the objective function to c′3 = 8.
Solution: We subtract 5 from the coefficient of x3 since c′3 = c3 − 5.
Z = 100 −7×3 −5×4 x2 = 20 +x1 −3×3 −x4 x5 = 10 −16×1 +2×3 +4×4
The dictionary remains feasible and optimal.
(e) Introduce a new constraint 2×1 + 3×2 + 5×3 ≤ 50. (Denote its slack variable by x6.)
Page 4 of 5
Mathematics 340 Homework 8 Due Mar. 19th
Solution: In augmented form this solution is
x6 =50−2×1 −3×2 −5×3.
To add it to the dictionary we must substitute in for x2.
Z = 100 −2×3 −5×4 x2 = 20 +x1 −3×3 −x4 x5 = 10 −16×1 +2×3 +4×4 x6 = −20 −5×1 +4×3 +3×4 .
(f) Change constraint 2 to 10×1 + 5×2 + 10×3 ≤ 100.
Solution: We replace the second constraint with
x′5 =100−10×1 −5×2 −10×3.
To add it to the dictionary we must substitute in for x2.
Z = 100 −2×3 −5×4 x2 = 20 +x1 −3×3 −x4 x′5 = 0 −15×1 +15×3 +5×4 .
This dictionary is feasible and optimal.
Page 5 of 5