Use the dual simplex method to solve the following Linear Programming Problem (LPP) :
Minimize Z = 2x₁ + x₂ + 3x₃
subject to
x₁ − 2x₂ + x₃ ≥ 4
2x₁ + x₂ + x₃ ≤ 8
x₁ − x₃ ≥ 0
and x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0
15 marks · directive: Solve
The core of a good answer
Writing all constraints as ≤ with slacks gives a dual-feasible but primal-infeasible start (s₁ = −4); s₁ leaves, x₁ enters (ratio 2 against 3 for x₃), and after one iteration all basic values are non-negative, so the optimum is x₁ = 4, x₂ = 0, x₃ = 0 with minimum Z = 8.
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
The dual simplex method needs a starting tableau that is optimal (dual feasible: all zj − cj ≤ 0 for a minimisation) but infeasible. Convert ≥ constraints to ≤ by multiplying by −1, add slacks, then pick the leaving variable as the most negative basic value and the entering variable by the minimum ratio |(zj − cj)/a_rj| over a_rj < 0. Show each tableau.
Answer outline
Introduction
Multiply the ≥ constraints by −1: −x₁ + 2x₂ − x₃ + s₁ = −4; 2x₁ + x₂ + x₃ + s₂ = 8; −x₁ + x₃ + s₃ = 0; all variables ≥ 0. Costs c = (2, 1, 3, 0, 0, 0).
Step 1: Initial tableau (basis s₁, s₂, s₃)
- s₁: −1, 2, −1, 1, 0, 0 | −4
- s₂: 2, 1, 1, 0, 1, 0 | 8
- s₃: −1, 0, 1, 0, 0, 1 | 0
- zj − cj: −2, −1, −3, 0, 0, 0; Z = 0
- All zj − cj ≤ 0, so the tableau is dual feasible; s₁ = −4 makes it primal infeasible.
Step 2: Choose pivot
- Leaving variable: s₁ (most negative right-hand side, −4).
- Ratios |(zj − cj)/a₁ⱼ| for a₁ⱼ < 0: x₁: 2/1 = 2; x₃: 3/1 = 3 (x₂ has a positive entry, not eligible).
- Minimum ratio 2: x₁ enters; pivot element −1.
Step 3: Second tableau (basis x₁, s₂, s₃)
- x₁: 1, −2, 1, −1, 0, 0 | 4
- s₂: 0, 5, −1, 2, 1, 0 | 0
- s₃: 0, −2, 2, −1, 0, 1 | 4
- zj − cj: 0, −5, −1, −2, 0, 0; Z = 8
- All right-hand sides ≥ 0 and all zj − cj ≤ 0: optimal.
Step 4: Solution and check
- x₁ = 4, x₂ = 0, x₃ = 0, Z = 2(4) = 8.
- Constraints: 4 − 0 + 0 = 4 ≥ 4 (binding); 8 + 0 + 0 = 8 ≤ 8 (binding, s₂ = 0, a degenerate basic variable); 4 − 0 = 4 ≥ 0 (surplus 4).
- All non-basic zj − cj are strictly negative, so the optimum is unique. A Python LP solver (HiGHS) gives the same point and Z = 8.
Conclusion
Minimum Z = 8 at x₁ = 4, x₂ = 0, x₃ = 0, reached in one dual simplex iteration; the optimal basis is degenerate since s₂ = 0.
Examples and data to cite
- Duality: the optimal value of the dual equals the primal minimum (strong duality).
- Duality check: the shadow price of the first constraint, read under s₁, is 2, and 2 × 4 = 8 equals the primal minimum.
Facts to remember
- Dual simplex starts dual feasible (optimality condition met) and works towards primal feasibility.
- Leaving variable: most negative basic value; entering: minimum |(zj − cj)/a_rj| with a_rj < 0.
- Stop when all basic variables are non-negative.
- If the pivot row has no negative entry the problem is infeasible.