← 2015 Paper 2

UPSC 2015 Maths Optional Paper 2 Q3c-i — 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

Consider Maximize $Z=x_1+2x_2-3x_3+4x_4$ subject to $x_1+x_2+2x_3+3x_4=12$, $x_2+2x_3+x_4=8$, $x_1,x_2,x_3,x_4\ge 0$.

Using the definition, find all basic solutions. Which of these are degenerate basic feasible solutions and which are non-degenerate basic feasible solutions?

Technique

Enumerate $\binom{n}{m}=\binom{4}{2}=6$ basic solutions; for each, set 2 variables to 0 and solve linear system; check feasibility ($x_i\ge 0$) and degeneracy (basic variable = 0).

Solution

Setup. $m=2$ constraints (after equalities), $n=4$ variables. A basic solution sets $n-m=2$ variables to zero and solves for the remaining $m=2$ from the constraints. There are $\binom{4}{2}=6$ possible basic solutions.

A basic solution is feasible if all variables are $\ge 0$. It is degenerate if a basic variable equals 0 (i.e., the basis row has redundancy).

Step 1 — Enumerate the 6 basic solutions

Constraints in matrix form:

For each subset of 2 basic variables, set the other 2 to 0 and solve.

(1) Basis $\{x_1,x_2\}$ (set $x_3=x_4=0$):

Solution $(4,8,0,0)$. All $\ge 0$, feasible. No basic var = 0, non-degenerate.

(2) Basis $\{x_1,x_3\}$ (set $x_2=x_4=0$):

Solution $(4,0,4,0)$. All $\ge 0$, feasible. Non-degenerate.

(3) Basis $\{x_1,x_4\}$ (set $x_2=x_3=0$):

Solution $(-12,0,0,8)$. $x_1<0$, infeasible (basic but not feasible).

(4) Basis $\{x_2,x_3\}$ (set $x_1=x_4=0$):

Two equations: $12=8$, inconsistent. No basic solution exists.

So actually the basis $\{x_2,x_3\}$ corresponds to columns $(1,2)^T$ and $(2,2)^T$ — let me re-examine. Columns of $A$: $A_1=(1,0)^T$, $A_2=(1,1)^T$, $A_3=(2,2)^T$, $A_4=(3,1)^T$.

For basis $\{x_2,x_3\}$: matrix $B=(A_2|A_3)=\begin{pmatrix}1 & 2\\ 1 & 2\end{pmatrix}$, $\det=0$ — singular. No basic solution for this choice.

(5) Basis $\{x_2,x_4\}$ (set $x_1=x_3=0$): $B=(A_2|A_4)=\begin{pmatrix}1 & 3\\ 1 & 1\end{pmatrix}$, $\det=1-3=-2\ne 0$.

Subtract: $2x_4=4\Rightarrow x_4=2,\;x_2=6$. Solution $(0,6,0,2)$. All $\ge 0$, feasible. Non-degenerate.

(6) Basis $\{x_3,x_4\}$ (set $x_1=x_2=0$): $B=(A_3|A_4)=\begin{pmatrix}2 & 3\\ 2 & 1\end{pmatrix}$, $\det=2-6=-4\ne 0$.

Subtract: $2x_4=4\Rightarrow x_4=2,\;x_3=3$. Solution $(0,0,3,2)$. All $\ge 0$, feasible. Non-degenerate.

Step 2 — Summary

Basic feasible solutions: $(4,8,0,0)$, $(4,0,4,0)$, $(0,6,0,2)$, $(0,0,3,2)$ — four BFS.

Degenerate BFS: none (no basic variable equals 0 in any BFS).

Non-degenerate BFS: all four.

Answer