Solve the following linear programming problem by the Simplex method :
Maximize Z = 4x₁ + 10x₂
subject to the constraints
2x₁ + x₂ ≤ 10
2x₁ + 5x₂ ≤ 20
2x₁ + 3x₂ ≤ 18
x₁, x₂ ≥ 0
Obtain an alternate optimal solution, if it exists, with explanation.
20 marks · directive: Solve
The core of a good answer
The simplex method reaches the optimum Z = 40 at x₁ = 0, x₂ = 4 in one iteration; the non-basic variable x₁ then has net evaluation cⱼ - zⱼ = 0, signalling alternate optima, and bringing x₁ in gives the alternate optimal solution x₁ = 15/4, x₂ = 5/2, Z = 40 (every point on the segment joining them is optimal).
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 routine simplex computation with the added requirement to detect and obtain an alternate optimum. The key observation is that the objective 4x₁ + 10x₂ = 2(2x₁ + 5x₂) is parallel to the second constraint, which shows up in the optimal tableau as a zero cⱼ - zⱼ for a non-basic variable.
Answer outline
Introduction
Add slack variables s₁, s₂, s₃ ≥ 0: 2x₁ + x₂ + s₁ = 10, 2x₁ + 5x₂ + s₂ = 20, 2x₁ + 3x₂ + s₃ = 18; Z = 4x₁ + 10x₂ + 0s₁ + 0s₂ + 0s₃. Initial basis (s₁, s₂, s₃) = (10, 20, 18), Z = 0.
Step 1: Initial tableau and entering variable
- cⱼ - zⱼ: x₁ = 4, x₂ = 10, slacks 0. Most positive is 10: x₂ enters.
- Ratios: s₁ 10/1 = 10, s₂ 20/5 = 4, s₃ 18/3 = 6. Minimum 4: s₂ leaves, pivot 5.
Step 2: Second tableau
- x₂ row: (2/5)x₁ + x₂ + (1/5)s₂ = 4.
- s₁ row: (8/5)x₁ + s₁ - (1/5)s₂ = 6.
- s₃ row: (4/5)x₁ - (3/5)s₂ + s₃ = 6.
- Z = 10 × 4 = 40.
- cⱼ - zⱼ: x₁ = 4 - 10(2/5) = 0; s₂ = 0 - 10(1/5) = -2; basic variables 0.
Step 3: Optimality and the alternate-optimum signal
- All cⱼ - zⱼ ≤ 0, so the current solution x₁ = 0, x₂ = 4, Z = 40 is optimal.
- Non-basic x₁ has cⱼ - zⱼ = 0, so entering it changes the solution without changing Z: an alternate optimum exists.
Step 4: Bring x₁ into the basis
- Ratios: s₁ 6/(8/5) = 15/4, s₃ 6/(4/5) = 15/2, x₂ 4/(2/5) = 10. Minimum 15/4: s₁ leaves.
- x₁ row: x₁ + (5/8)s₁ - (1/8)s₂ = 15/4.
- x₂ row: x₂ - (1/4)s₁ + (1/4)s₂ = 5/2.
- s₃ row: -(1/2)s₁ - (1/2)s₂ + s₃ = 3.
- cⱼ - zⱼ: s₁ = -(4(5/8) + 10(-1/4)) = 0, s₂ = -(4(-1/8) + 10(1/4)) = -2. Still optimal.
Step 5: Alternate optimum
- x₁ = 15/4, x₂ = 5/2, Z = 4(15/4) + 10(5/2) = 15 + 25 = 40.
- General optimal solution: (x₁, x₂) = λ(0, 4) + (1 - λ)(15/4, 5/2), 0 ≤ λ ≤ 1, all with Z = 40.
Conclusion
Max Z = 40, attained at (0, 4) and at the alternate optimum (15/4, 5/2), and on the whole edge between them along 2x₁ + 5x₂ = 20. Check at (15/4, 5/2): 2x₁ + x₂ = 10, 2x₁ + 5x₂ = 20, 2x₁ + 3x₂ = 15 ≤ 18; an LP solver also returns Z = 40.
Facts to remember
- Simplex optimality (maximisation): all cⱼ - zⱼ ≤ 0.
- Entering variable: largest positive cⱼ - zⱼ; leaving variable: minimum ratio test over positive pivot-column entries.
- A zero cⱼ - zⱼ for a non-basic variable in the optimal tableau indicates alternate optimal solutions (if the ratio test gives a finite pivot).
- Any convex combination of two optimal basic feasible solutions is optimal.
- Alternate optima occur when the objective function is parallel to a binding constraint.