← 2024 Paper 2

UPSC 2024 Maths Optional Paper 2 Q1e — Step-by-Step Solution

10 marks · Section A

Big-M / two-phase method (artificial variables) · Linear Programming · asked 5× in 13 yrs · Read the full method →

Question

Use the two-phase method to solve:

Maximise z=x1+2x2subject to x1−x2≥3,  2x1+x2≤10,  x1,x2≥0.\text{Maximise }z=x_1+2x_2\quad\text{subject to }x_1-x_2\ge 3,\;2x_1+x_2\le 10,\;x_1,x_2\ge 0.

Technique

Phase I removes the artificial variable introduced for the ≥\ge constraint; Phase II maximises the original objective.

Solution

Standard form

Introduce surplus s1≥0s_1\ge 0, slack s2≥0s_2\ge 0, and artificial a1≥0a_1\ge 0:

x1−x2−s1+a1=3,2x1+x2+s2=10.x_1-x_2-s_1+a_1=3,\qquad 2x_1+x_2+s_2=10.

Phase I — Minimise w=a1w=a_1

Initial BFS: a1=3, s2=10a_1=3,\,s_2=10.

The Phase I objective in terms of non-basic variables: w=3−x1+x2+s1w=3-x_1+x_2+s_1. Most negative coefficient: x1x_1 enters. Ratio test: min(3/1,10/2)=3(3/1, 10/2)=3, so a1a_1 leaves at x1=3x_1=3.

New BFS: x1=3, s2=4x_1=3,\,s_2=4. w=0w=0; no artificial in basis. Phase I complete.

Phase II — Maximise z=x1+2x2z=x_1+2x_2

Current basis: {x1,s2}\{x_1,s_2\}. Express zz in terms of non-basics {x2,s1}\{x_2,s_1\}:

x1=3+x2+s1,z=3+3x2+s1.x_1=3+x_2+s_1,\quad z=3+3x_2+s_1.

Coefficient of x2x_2 is +3>0+3>0: x2x_2 enters. From the s2s_2 row: s2=4−3x2−2s1≥0⇒x2≤4/3s_2=4-3x_2-2s_1\ge 0\Rightarrow x_2\le 4/3. So x2=4/3x_2=4/3, s2s_2 leaves.

New BFS: x2=4/3x_2=4/3, x1=3+4/3=13/3x_1=3+4/3=13/3. Updated z=3+3(4/3)=7z=3+3(4/3)=7. All coefficients in zz now negative. Optimal.

Optimal solution

x1=133,x2=43,zmax⁡=7.x_1=\tfrac{13}{3},\quad x_2=\tfrac{4}{3},\quad z_{\max}=7.

Answer

  x1=133,  x2=43,  zmax⁡=7.  \boxed{\;x_1=\tfrac{13}{3},\;x_2=\tfrac{4}{3},\;z_{\max}=7.\;}
We post more of this — worked solutions, CSAT trap breakdowns, guide chapters — a few times a week on Telegram. Free, no sign-in. Join

This solution is part of the Maths Coverage Map — 13 years, mapped. Get the take-away PDF free.