← 2019 Paper 2

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

10 marks · Section A

Graphical method · Linear Programming · asked 5× in 13 yrs · Read the full method →

Question

Use graphical method to solve the linear programming problem. Maximize $Z=3x_1+2x_2$ subject to

and $x_1,x_2,x_3\ge 0$.

Technique

Graphical method; recognize the redundant slack-like variable $x_3$, reduce to the plane, identify the single vertex and an unbounded edge along which $Z\to\infty$.

Solution

Step 1 — Reduce to a planar (graphical) problem

The objective $Z=3x_1+2x_2$ does not involve $x_3$. The variable $x_3$ appears only in the second constraint $x_1+x_3\ge 3$. Since $x_3\ge0$ is free to be as large as we like, the constraint $x_1+x_3\ge3$ can always be satisfied for any $x_1\ge0$ (choose $x_3\ge 3-x_1$, e.g. $x_3=\max(0,3-x_1)$). Hence the second constraint imposes no restriction on the objective variables $(x_1,x_2)$.

The problem therefore reduces, in the $(x_1,x_2)$-plane, to:

Step 2 — Feasible region in the $(x_1,x_2)$-plane

$x_1-x_2\ge1$ is the half-plane on/below the line $x_2=x_1-1$ (intercept $(1,0)$, slope $1$), intersected with the first quadrant. The boundary line meets the $x_1$-axis at $(1,0)$. The region is the set

a wedge opening to the right, unbounded in the $+x_1$ (and along it $+x_2$) direction. Its only vertex is $(1,0)$.

Step 3 — Behaviour of the objective on the region

Move along the edge $x_2=x_1-1$ (a feasible boundary, with $x_2\ge0\Leftrightarrow x_1\ge1$):

So $Z$ can be made arbitrarily large within the feasible region.

Answer