Assignment - Sensitivity Analysis and Duality
Part A - Finding the Dual of an LP
Find the duals of the following LPs:
Q1. max z = 2x1 + x2
s.t. - x1 + x2 ≤ 1
x1 + x2 ≤ 3
x1 - 2x2 ≤ 4
x1, x2 ≥ 0
Q2. min w = y1 - y2
s.t. 2y1 + y2 ≥ 4
y1 + y2 ≥ 1
y1 + 2y2 ≥ 3
y1, y2 ≥ 0
Q3. max z = 4x1 x2 + 2x3
s.t. x1 + x2 ≤ 5
2x1 + x2 + ≤ 7
2x2 + x3 ≥ 6
x1 + x3 = 4
x1 ≥ 0, x2, x3 urs
Q4. min w = 4y1 + 2y2 y3
s.t. y1 + 2y2 ≤ 6
y1 - y2 + 2y3 = 8
y1, y2 ≥ 0, y3 urs
Q5. This problem shows why the dual variable for an equality constraint should be urs.
a. Use the rules given in the text to find the dual of
max z = x1 + 2x2
s.t. 3x1 + x2 ≤ 6
2x1 + x2 = 5
x1, x2 ≥ 0
b. Now transform the LP in part (a) to the normal form. Using (16) and (17), take the dual of the transformed LP. Use y'2 and y''2 as the dual variables for the two primal constraints derived from 2x1 + x2 = 5.
c. Make the substitution y2 = y'2 - y''2 in the part (b) answer. Now show that the two duals obtained in parts (a) and (b) are equivalent.
Q6. This problem shows why a dual variable yi corresponding to a ≥ constraint in a max problem must satisfy yi ≤ 0.
a. Using the rules given in the text, find the dual of
max z = 3x1 + x2
s.t. x1 + x2 ≤ 1
-x1 + x2 ≥ 2
x1, x2 ≥ 0
b. Transform the LP of part (a) into a normal max problem. Now use (16) and (17) to find the dual of the transformed LP. Let y-2 be the dual variable corresponding to the second primal constraint.
c. Show that, defining y-2 = -y2, the dual in part (a) is equivalent to the dual in part (b).
Part B - The Dual Theorem and Its Consequences
Q1. The following questions refer to the Giapetto problem (see Problem 7 of Section 6.3).
a. Find the dual of the Giapetto problem.
b. Use the optimal tableau of the Giapetto problem to determine the optimal dual solution.
c. Verify that the Dual Theorem holds in this instance.
Q2. Consider the following LP:
max z =2x1 - x2 + x3
s.t. x1 + x2 + x3 ≤ 3
x2 + x3 ≥ 2
x1 + x3 = 1
x1, x2, x3 ≥ 0
a. Find the dual of this LP.
b. After adding a slack variable s1, subtracting an excess variable e2, and adding artificial variables a2 and a3, row 0 of the LP's optimal tableau is found to be z + 4x1 + e2 + (M - 1)a2 + (M + 2)a3 = 0
Find the optimal solution to the dual of this LP.
Q3. For the following LP,
max z = -x1 + 5x2
s.t. x1 + 2x2 ≤ 0.5
- x1 + 3x2 ≤ 0.5
x1, x2 ≥ 0
row 0 of the optimal tableau is z + 0.4s1 + 1.4s2 = ? Determine the optimal z-value for the given LP.
Q4. The following questions refer to the Bevco problem of Section 4.10.
a. Find the dual of the Bevco problem.
b. Use the optimal tableau for the Bevco problem that is given in Section 4.10 to find the optimal solution to the dual. Verify that the Dual Theorem holds in this instance.
Q5. Consider the following linear programming problem:
max z = 4x1 + x2
s.t. 3x1+ 2x2 ≤ 6
6x1 + 3x2 ≤ 10
x1, x2 ≥ 0
Suppose that in solving this problem, row 0 of the optimal tableau is found to be z + 2x2 + s2 = 20/3. Use the Dual Theorem to prove that the computations must be incorrect.
Q6. Show that (for a max problem) if the ith primal constraint is a ≥ constraint, then the optimal value of the ith dual variable may be written as (coefficient of ai in optimal row 0) M.
Q7. In this problem, we use weak duality to prove Lemma 3.
a. Show that Lemma 3 is equivalent to the following: If the dual is feasible, then the primal is bounded. (Hint: Do you remember, from plane geometry, what the con-trapositive is?)
b. Use weak duality to show the validity of the form of Lemma 3 given in part (a). (Hint: If the dual is feasible, then there must be a dual feasible point having a w-value of, say, wo. Now use weak duality to show that the primal is bounded.)
Q8. Following along the lines of Problem 7, use weak duality to prove Lemma 4.
Q9. Use the information given in Problem 8 of Section 6.3 to determine the dual of the Dorian Auto problem and its optimal solution.
Textbook - Operations Research APPLICATIONS AND ALGORITHMS, FOURTH EDITION by Wayne L. Winston WITH CASES BY Jeffrey B. Goldberg.
Chapter 6 - Sensitivity Analysis and Duality.