← 2015 Paper 2

UPSC 2015 Maths Optional Paper 2 Q3c-ii — Step-by-Step Solution

10 marks · Section A

LPP: standard form; basic, basic feasible, optimal solutions · Linear Programming · asked 6× in 13 yrs · Read the full method →

Question

Without solving the problem, show that it has an optimal solution. Which of the basic feasible solution(s) is/are optimal?

Technique

Substitute equality constraints to reduce $Z$ to a single variable $x_3$; observe $Z=20-7x_3$ is bounded above (since $x_3\ge 0$); by LPP fundamental theorem, optimum is attained; check each BFS.

Solution

LPP (recap):

Step 1 — Existence of optimal solution

Theorem (LPP fundamental). A linear program with non-empty feasible region and bounded objective on the feasible region attains its optimum at an extreme point (= basic feasible solution).

Non-empty feasible region: From Q3(c)(i), we have at least one BFS — e.g., $(4,8,0,0)$ — so the feasible region is non-empty.

Boundedness of $Z$ above: Let’s show $Z$ is bounded above on the feasible region.

From the second constraint $x_2+2x_3+x_4=8$, we have $x_4=8-x_2-2x_3$.

Substitute into the first: $x_1+x_2+2x_3+3(8-x_2-2x_3)=12$, so $x_1=12-x_2-2x_3-24+3x_2+6x_3=-12+2x_2+4x_3$.

So $x_1=2x_2+4x_3-12$ and $x_4=8-x_2-x_4 \dots$ wait, $x_4=8-x_2-2x_3$.

Substitute into $Z$:

So $Z=20-7x_3$ on the feasible region (with $x_1\ge 0,x_4\ge 0$ as additional constraints).

Since $x_3\ge 0$, $Z=20-7x_3\le 20$, with equality iff $x_3=0$. So $Z$ is bounded above by 20.

By the fundamental theorem, the LPP has an optimal BFS, attaining $Z=20$.

Step 2 — Identify the optimal BFS

$Z=20-7x_3$ is maximized when $x_3=0$. Looking at the 4 BFS from Q3(c)(i):

Two BFS attain the maximum $Z=20$: $(4,8,0,0)$ and $(0,6,0,2)$.

Answer