← 2018 Paper 2

UPSC 2018 Maths Optional Paper 2 Q3c — Step-by-Step Solution

15 marks · Section A

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

Question

How many basic solutions are there in the following linearly independent set of equations? Find all of them.

Technique

Basic solutions $=$ non-singular $m\times m$ column selections; $\binom{n}{m}$ candidates minus the singular ones; solve each $2\times2$ system.

Solution

We have $m=2$ equations in $n=4$ unknowns. A basic solution is obtained by choosing $m=2$ variables as basic (the rest set to $0$) such that the $2\times2$ coefficient submatrix (the basis matrix $B$) is non-singular, then solving $B\,x_B=b$.

Step 1 — Count the candidate selections

The number of ways to choose $2$ basic variables out of $4$ is

But a selection yields a (unique) basic solution only if the corresponding $2\times2$ submatrix is invertible. The coefficient matrix and RHS are

$\operatorname{rank}(A)=2$ (rows are independent), confirming the system is “linearly independent” as stated.

Step 2 — Identify which $2\times2$ submatrices are singular

Note the columns: $C_1=\binom{2}{4},\ C_2=\binom{-1}{-2},\ C_3=\binom{3}{-1},\ C_4=\binom{1}{2}$. The columns $C_1,C_2,C_4$ are all proportional to $\binom12$:

Any pair chosen entirely from $\{C_1,C_2,C_4\}$ has determinant $0$ (parallel columns). Those pairs are

The remaining $3$ pairs each contain $C_3$ (which is not parallel to $\binom12$), so each is non-singular and gives exactly one basic solution:

Step 3 — Compute the three basic solutions

(a) Basic $\{x_1,x_3\}$, set $x_2=x_4=0$:

From the pair: multiply the second by $3$: $12x_1-3x_3=30$; add to the first: $14x_1=36\Rightarrow x_1=\tfrac{18}{7}$. Then $x_3=4x_1-10=\tfrac{72}{7}-10=\tfrac{2}{7}$.

(b) Basic $\{x_2,x_3\}$, set $x_1=x_4=0$:

From the first $x_2=3x_3-6$; substitute: $-2(3x_3-6)-x_3=10\Rightarrow -7x_3+12=10\Rightarrow x_3=\tfrac{2}{7}$, then $x_2=3\cdot\tfrac27-6=-\tfrac{36}{7}$.

(c) Basic $\{x_3,x_4\}$, set $x_1=x_2=0$:

From the first $x_4=6-3x_3$; substitute: $-x_3+2(6-3x_3)=10\Rightarrow -7x_3+12=10\Rightarrow x_3=\tfrac27$, then $x_4=6-\tfrac67=\tfrac{36}{7}$.

Summary

Answer