Solve the dual problem of the following linear programming problem by the graphical method :
Minimize Y = 10y₁ + 6y₂ + 2y₃ + y₄
subject to the constraints :
y₁ + y₂ + y₃ + y₄ ≥ 2
2y₁ + y₂ - y₃ - 2y₄ ≥ 1
y₁, y₂, y₃, y₄ ≥ 0
10 marks · directive: Solve
The core of a good answer
The dual is Maximize W = 2x₁ + x₂ subject to x₁ + 2x₂ ≤ 10, x₁ + x₂ ≤ 6, x₁ - x₂ ≤ 2, x₁ - 2x₂ ≤ 1, x₁, x₂ ≥ 0; graphically its optimum is W = 10 at (x₁, x₂) = (4, 2), so the primal minimum is Y = 10, attained at y₁ = 0, y₂ = 3/2, y₃ = 1/2, y₄ = 0.
An outline written by upsc.help, not an official UPSC answer; every fact checked by a separate review. How we work
What the question asks
A four-variable minimisation cannot be drawn, but its dual has only two variables, so the method is: write the symmetric dual, plot its feasible region, evaluate the objective at the corner points, and then use the duality theorem (and complementary slackness) to read off the primal optimum.
Answer outline
Introduction
The primal is in canonical minimisation form (all constraints ≥, variables ≥ 0). Associate dual variables x₁ ≥ 0, x₂ ≥ 0 with the two constraints.
Step 1: Write the dual
- Maximize W = 2x₁ + x₂
- Column of y₁: x₁ + 2x₂ ≤ 10
- Column of y₂: x₁ + x₂ ≤ 6
- Column of y₃: x₁ - x₂ ≤ 2
- Column of y₄: x₁ - 2x₂ ≤ 1
- x₁, x₂ ≥ 0
Step 2: Plot the region
- x₁ + 2x₂ = 10 through (10, 0) and (0, 5); x₁ + x₂ = 6 through (6, 0) and (0, 6); x₁ - x₂ = 2 through (2, 0) and (0, -2); x₁ - 2x₂ = 1 through (1, 0) and (0, -1/2).
- The feasible region is the convex polygon with vertices O(0, 0), A(1, 0), B(3, 1), C(4, 2), D(2, 4), E(0, 5).
Step 3: Corner points
- A: x₂ = 0 and x₁ - 2x₂ = 1 give (1, 0).
- B: x₁ - 2x₂ = 1 and x₁ - x₂ = 2 give x₂ = 1, x₁ = 3.
- C: x₁ - x₂ = 2 and x₁ + x₂ = 6 give (4, 2).
- D: x₁ + x₂ = 6 and x₁ + 2x₂ = 10 give x₂ = 4, x₁ = 2.
- E: x₁ = 0 and x₁ + 2x₂ = 10 give (0, 5).
Step 4: Evaluate W
- W(O) = 0, W(A) = 2, W(B) = 7, W(C) = 10, W(D) = 8, W(E) = 5.
- Maximum W = 10 at C(4, 2), unique since the objective line 2x₁ + x₂ = 10 meets the region only at C.
Step 5: Recover the primal (complementary slackness)
- At C: x₁ + 2x₂ = 8 < 10 and x₁ - 2x₂ = 0 < 1, so y₁ = 0 and y₄ = 0.
- x₁ > 0 and x₂ > 0, so both primal constraints are tight: y₂ + y₃ = 2 and y₂ - y₃ = 1.
- Hence y₂ = 3/2, y₃ = 1/2.
- Y = 6(3/2) + 2(1/2) = 9 + 1 = 10 = max W.
Conclusion
Dual optimum W = 10 at x₁ = 4, x₂ = 2; primal optimum Y = 10 at (0, 3/2, 1/2, 0). The equality Y = W = 10 confirms optimality by the strong duality theorem, and a separate LP solver run on the primal gives the same value.
Facts to remember
- Symmetric dual: Min cᵀy, Ay ≥ b, y ≥ 0 has dual Max bᵀx, Aᵀx ≤ c, x ≥ 0.
- Strong duality: if either problem has a finite optimum, so does the other, with equal objective values.
- Complementary slackness: a slack dual constraint forces the corresponding primal variable to 0, and a positive dual variable forces the corresponding primal constraint to be tight.
- In the graphical method the optimum of a bounded LP occurs at a corner point of the feasible region.