LPP: standard form; basic, basic feasible, optimal solutions

At a Glance

• Frequency: 6 sub-parts across 4 of 13 years (2015, 2018, 2020, 2025)
• Priority tier: T3
• Marks (count): 10 (5), 15 (1)
• Average solve time: ~10 min
• Difficulty mix: medium 4, easy 2
• Section: A | Dominant type: computation

Why This Chapter Matters

This atom covers the foundational vocabulary of LP theory: what a basic solution is, how to count and enumerate them, and how to pose a real problem as a standard-form program. Questions here are purely definitional or formulative — no simplex needed — and they appear almost every time LP appears on Paper 2. The basic-solutions archetype is a guaranteed 10–15 mark question whenever the examiner wants to test LP foundations; the lpp-formulation type appears as a compulsory Q1 sub-part. Mastering the column-singularity shortcut (for counting basic solutions) is the difference between 8 minutes and 18 minutes on the basic-solutions questions.

Minimum Theory

Standard form. A linear program in standard form has all constraints as equalities with non-negative variables: $\min\; c^T x \quad \text{s.t.} \quad Ax = b,\; x \ge 0,$ where $A$ is $m \times n$ with $m \le n$. Inequality constraints $a_i^T x \le b_i$ become equalities by adding a slack $s_i \ge 0$; inequality $a_i^T x \ge b_i$ is converted by subtracting a surplus $s_i \ge 0$.

Basic solution. Choose $m$ columns of $A$ forming a non-singular $m \times m$ submatrix $B$ (the basis matrix). Set the remaining $n - m$ variables (non-basic) to zero and solve $B x_B = b$. The resulting solution (with the non-basic variables set to zero) is a basic solution. The maximum number of basic solutions is $\binom{n}{m}$; those where the corresponding $m \times m$ submatrix is singular yield no solution and are not counted.

Feasibility and degeneracy. A basic solution is a basic feasible solution (BFS) if $x_B \ge 0$ (equivalently, all $n$ variables are non-negative). It is non-degenerate if every basic variable is strictly positive. Geometrically, BFS = extreme points (vertices) of the feasible polytope.

Fundamental theorem of LP. If the feasible region is non-empty and the objective is bounded on it, the optimum is attained at a BFS. This is the license to restrict attention to vertices when proving optimality.

Question Archetypes

basic-solutions (3 questions; 2015, 2018, 2025)

Recognition Cues

• “Find all basic solutions of the following system.”
• “How many basic solutions are there? Find all of them.”
• “Classify feasible/non-feasible/degenerate/non-degenerate.”

All three UPSC appearances use the same system: $2x_1-x_2+3x_3+x_4=6$, $4x_1-2x_2-x_3+2x_4=10$. The 2015 question uses a different (easier) system; 2018 and 2025 use this one. Know the column-proportionality trick cold.

Solution Template

1. Identify $m$ and $n$. $m$ = number of equations, $n$ = number of variables. Maximum basic solutions: $\binom{n}{m}$.
2. Check for proportional columns. Write out all $n$ columns as $m$-vectors. If any subset of $\ge 2$ columns are scalar multiples of each other, every pair drawn entirely from that subset is singular. Count the singular pairs — subtract from $\binom{n}{m}$.
3. Enumerate non-singular pairs. For each non-singular pair of columns $(j_1, j_2)$: set all other variables to 0, solve the $2 \times 2$ system for $x_{j_1}, x_{j_2}$.
4. Classify each. Feasible: all components $\ge 0$. Degenerate: a basic variable equals 0 (non-basic variables are always 0 by definition, so degeneracy is about the basic values only).

Worked Example(s)

2015 Paper 2, 2015-P2-Q3c-i (10 marks)

Find all basic solutions of $x_1+x_2+2x_3+3x_4=12$, $x_2+2x_3+x_4=8$; classify degenerate vs non-degenerate BFS.

$m=2$, $n=4$, so at most $\binom{4}{2}=6$ basic solutions.

Check for singular pairs. Columns of $A$: $A_1=\binom{1}{0},\; A_2=\binom{1}{1},\; A_3=\binom{2}{2}=2\binom{1}{1},\; A_4=\binom{3}{1}.$ $A_3 = 2A_2$, so the pair $\{x_2, x_3\}$ gives $\det(A_2|A_3) = 0$ — singular, no basic solution. All other pairs have independent columns.

Five non-singular pairs (and their solutions):

Four BFS, all non-degenerate. No basic variable equals 0 in any feasible solution.

$\boxed{(4,8,0,0),\; (4,0,4,0),\; (0,6,0,2),\; (0,0,3,2) — \text{all non-degenerate BFS.}}$

2018 / 2025 Paper 2 (10–15 marks)

$2x_1-x_2+3x_3+x_4=6$, $4x_1-2x_2-x_3+2x_4=10$. Find all basic solutions; classify.

$m=2$, $n=4$. At most $\binom{4}{2}=6$.

Key observation: columns $c_1, c_2, c_4$ are all multiples of $(1,2)^T$: $c_1=2(1,2)^T,\quad c_2=-(1,2)^T,\quad c_4=(1,2)^T.$ Any pair from $\{c_1,c_2,c_4\}$ is singular. That accounts for 3 singular pairs: $\{x_1,x_2\}$, $\{x_1,x_4\}$, $\{x_2,x_4\}$.

The remaining 3 pairs all contain $c_3$, which is not parallel to $(1,2)^T$, so each is non-singular. Exactly 3 basic solutions exist.

$\boxed{3 \text{ basic solutions: 2 feasible (both non-degenerate), 1 infeasible.}}$

The 2025 version of this question additionally asks to count non-degenerate solutions: all 3 are non-degenerate (no basic variable is zero in any of the three solutions).

Common Traps

• $\binom{n}{m}$ is only an upper bound; singular column pairs reduce the count. Always check for proportional columns before grinding through all pairs.
• Degeneracy means a basic variable equals 0 — not a non-basic variable. Non-basic variables are always set to 0 by definition. So $(0,0,2/7,36/7)$ with basis $\{x_3,x_4\}$ is non-degenerate because both $x_3$ and $x_4$ are nonzero.
• In the 2015 system, $A_3 = 2A_2$ makes $\{x_2,x_3\}$ singular — easy to miss since the columns look different at first glance (one has a leading 2, the other a leading 1).

lpp-formulation (2 questions; 2018, 2020)

Recognition Cues

• “Pose a linear programming problem.”
• “Formulate an LP in standard form; give a basic feasible solution to it.”
• A word problem with quantities to maximise/minimise subject to resource limits.

Solution Template

1. Name the decision variables. What does the candidate control? Typically: number of units of each type produced/purchased.
2. Objective function. Profit (maximise) or cost (minimise) per unit × number of units.
3. Constraints. For each resource/requirement: (usage per unit of type 1)$x_1$ + (usage per unit of type 2)$x_2$ $\le$ (available). Add non-negativity $x_i \ge 0$.
4. Standard form. Convert $\le$ to $=$ by adding slacks $s_i \ge 0$.
5. Check. Units consistent; constraints are $\le$ (not $=$) unless exhaustion is mandated.

Worked Example(s)

2018 Paper 2, 2018-P2-Q1e (10 marks)

An agricultural firm has 180 t nitrogen, 250 t phosphate, 220 t potash. Mixture I (ratio 3:3:4) yields Rs 1500/t profit; Mixture II (ratio 2:4:2) yields Rs 1200/t. Pose the LP.

Variables: $x_1$ = tonnes of Mixture I, $x_2$ = tonnes of Mixture II.

Per-tonne resource use: Ratio 3:3:4 sums to 10, so Mixture I uses $3/10$ t nitrogen, $3/10$ t phosphate, $4/10$ t potash per tonne. Ratio 2:4:2 sums to 8, so Mixture II uses $1/4$, $1/2$, $1/4$ respectively.

LPP (cleared of fractions by multiplying constraints by 20):

Maximise $Z = 1500x_1 + 1200x_2$ subject to:

$6x_1+5x_2 \le 3600 \qquad\text{(nitrogen} \times 20)$ $6x_1+10x_2 \le 5000 \qquad\text{(phosphate} \times 20)$ $8x_1+5x_2 \le 4400 \qquad\text{(potash} \times 20)$ $x_1,x_2 \ge 0.$

The question only asks to pose the LP; solving is not required.

2020 Paper 2, 2020-P2-Q1e (10 marks)

Stock pieces are 17 ft. Requirements: 5 ft (700), 9 ft (400), 7 ft (300). Minimise trim loss; give a BFS.

This is a cutting-stock problem. Decision variables: $x_j$ = number of pieces cut to pattern $P_j$.

Maximal cutting patterns (no more curtain of any length fits):

Objective: $\min\; z = x_1 + 3x_2 + 3x_3 + 0\,x_4 + 2x_5.$

Demand constraints (standard form with surplus $s_i$ and artificial $A_i$): $x_3+2x_4+3x_5 - s_1 + A_1 = 700 \quad(5\text{-ft})$ $x_1+2x_2+x_4 - s_2 + A_2 = 300 \quad(7\text{-ft})$ $x_1+x_3 - s_3 + A_3 = 400 \quad(9\text{-ft})$

A BFS: use $P_5$ for 5-ft demand, $P_2$ for 7-ft, $P_1$ for 9-ft: $x_5 = 700/3,\quad x_2 = 150,\quad x_1 = 400;\quad x_3=x_4=0, \; s_1=s_2=0,\; s_3=0.$ Trim loss $= 400 + 450 + 1400/3 \approx 1317$ ft. (This is a valid BFS, not necessarily optimal.)

Common Traps

• Normalize mixture ratios by their sum (10 and 8), not raw numbers.
• Constraints are $\le$, not $=$: the firm need not exhaust every resource.
• “Standard form” = equalities; $\le$ constraints need slack variables, $\ge$ need surplus + artificial.
• The cutting-stock question asks only to formulate + give a BFS, not solve.

optimum-without-simplex (1 question; 2015)

Recognition Cues

• “Without solving, show that it has an optimal solution.”
• “Which of the basic feasible solutions is/are optimal?”
• This always appears as the follow-up to a basic-solutions question on the same LPP.

Solution Template

1. Existence. Quote the fundamental theorem: feasible region non-empty (cite a known BFS) + objective bounded on the region $\Rightarrow$ optimum attained at a BFS.
2. Bound the objective. Substitute the equality constraints to eliminate variables. Express $Z$ in terms of the free (non-basic) variables, all of which are $\ge 0$. A coefficient of $-7$ on $x_3$ with $x_3 \ge 0$ immediately gives $Z \le Z_0$.
3. Identify the optimal BFS. Plug each BFS into the simplified $Z$-formula; the one achieving $Z_0$ is optimal.

Worked Example

2015 Paper 2, 2015-P2-Q3c-ii (10 marks)

(Continuation of Q3c-i above.) Without solving, show the LPP has an optimal solution; find which BFS are optimal.

LPP: Maximise $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_i \ge 0$.

Step 1 — Existence. From Q3c-i, $(4,8,0,0)$ is a BFS, so the feasible region is non-empty.

Step 2 — Bound $Z$. From the two constraints, express $x_4 = 8-x_2-2x_3$ and $x_1 = 2x_2+4x_3-12$. Substitute into $Z$: $Z = (2x_2+4x_3-12)+2x_2-3x_3+4(8-x_2-2x_3) = 20-7x_3.$ Since $x_3 \ge 0$, we have $Z \le 20$. So $Z$ is bounded above, and by the fundamental theorem the LPP has a finite optimal solution.

Step 3 — Find optimal BFS. $Z=20-7x_3$ is maximised when $x_3=0$:

Two BFS are optimal: $(4,8,0,0)$ and $(0,6,0,2)$, both achieving $Z_{\max}=20$.

The entire line segment between them is also optimal (alternative optima).

Common Traps

• Existence proof requires two parts: non-empty feasible region (produce a BFS) and bounded objective. Both must appear.
• The substitution may not eliminate all free variables — if $Z$ still has multiple free variables, bound them separately (all non-basic variables are $\ge 0$).
• Two BFS with the same objective value signals alternative optima — the whole edge between them is optimal. Mentioning this earns the final mark.

Marks-Aware Writing

10-mark answer (basic-solutions): Write the $\binom{n}{m}$ count up front; identify singular column pairs with a one-line determinant check; tabulate all non-singular solutions (basis, solution, feasible Y/N, degenerate Y/N). State the answer. No more, no less.

15-mark answer (basic-solutions): Same structure, but add a brief explanation of why certain pairs are singular (proportional columns), verify at least one solution by back-substitution, and explicitly state the count of feasible vs infeasible basic solutions.

10-mark formulation: Variables → objective → constraints → non-negativity → standard form. Each on its own line; dimensions/units checked in one sentence. The question says “pose” — do not solve.

Practice Set

• 2024-P2-Q4c (20 m) — transportation + LP context;
• 2023-P2-Q1e (10 m) — formulation;
• 2013-P2-Q1e (10 m) — formulation;
• 2020-P2-Q3b (15 m) — basic solutions;
• 2017-P2-Q1e (10 m) — formulation;
• 2016-P2-Q1e (10 m) — formulation;