Pratidin
2026 · Mathematics Optional Paper II · 20 marksMainsQuestion 4c

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

Answer

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

Step 2: Second tableau

Step 3: Optimality and the alternate-optimum signal

Step 4: Bring x₁ into the basis

Step 5: Alternate optimum

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

Facts to remember

Sources used for the explanation

Write a timed answer in the app