← 2026 Paper 2

UPSC 2026 Maths Optional Paper 2 Q4c — Step-by-Step Solution

20 marks · Section A

Simplex method (basic) · Linear Programming · asked 10× in 14 yrs · Read the full method →

Question

Solve the following linear programming problem by the Simplex method:

Maximize $Z = 4x_1 + 10x_2$

subject to the constraints

Obtain an alternate optimal solution, if it exists, with explanation.

Technique

All three constraints are $\le$ with non-negative right-hand sides, so slack variables alone give a ready-made feasible basis — no artificial variables, no Big-M, no two-phase. Run the Simplex table; the optimum arrives after one pivot. The alternate-optimum question is then decided by a single diagnostic: at optimality a non-basic variable with net evaluation $c_j-z_j=0$ means the entering of that variable changes the vertex but not $Z$, so a second optimal basic feasible solution exists — pivot once more to produce it, and then report the set of optima, which is the whole segment joining the two vertices, not two isolated points. There is also a structural tell worth spotting before any tableau is written: $Z=4x_1+10x_2=2(2x_1+5x_2)$ is exactly twice the left side of the second constraint, so $Z\le 40$ identically, with equality precisely when that constraint is tight.

Solution

Step 0 — Notation and convention (state it; the sign of the optimality test depends on it).

I use the net evaluation row $\Delta_j=c_j-z_j$, where $z_j=c_B\,B^{-1}a_j$ is the “imputed cost” of column $j$. For a maximisation problem:

• the current basic feasible solution is optimal iff $c_j-z_j\le 0$ for every $j$;
• if some $c_j-z_j>0$, the variable with the largest such value enters;
• the leaving variable is fixed by the minimum ratio test $\min\{x_{Bi}/y_{ij}: y_{ij}>0\}$.

(A reader who prefers the $z_j-c_j$ convention simply reverses every sign: optimality is then $z_j-c_j\ge0$ and the entering variable is the most negative. Nothing else changes.)

Step 1 — Standard form.

Introduce slack variables $s_1,s_2,s_3\ge0$, one per constraint. The problem becomes

subject to

Since every right-hand side is non-negative, $(s_1,s_2,s_3)=(10,20,18)$ with $x_1=x_2=0$ is a basic feasible solution at once: the slack columns form an identity matrix. No artificial variables are needed.

Step 2 — Initial table (Table I).

$c_B=(0,0,0)$, so $z_j=0$ for all $j$ and $c_j-z_j=c_j$.

Entering variable. $c_2-z_2=10$ is the largest positive net evaluation $\Rightarrow$ $x_2$ enters.

Leaving variable. Ratios $x_{Bi}/y_{i2}$ over $y_{i2}>0$: $10/1=10$, $20/5=4$, $18/3=6$. The minimum is $4$ in row $2$ $\Rightarrow$ $s_2$ leaves. Pivot element $y_{22}=\mathbf 5$.

Step 3 — Pivot 1 $\;\Rightarrow\;$ Table II.

Row operations: $R_2\to R_2/5$; then $R_1\to R_1-1\cdot R_2^{\text{new}}$, $R_3\to R_3-3\cdot R_2^{\text{new}}$.

Here $c_B=(0,10,0)$ and $z_j=\sum_i c_{Bi}y_{ij}$; e.g. $z_1=0\cdot\frac85+10\cdot\frac25+0\cdot\frac45=4$ and $z_4=10\cdot\frac15=2$. The objective value is $Z=c_B\cdot x_B=0\cdot6+10\cdot4+0\cdot6=40$.

Optimality test. Every $c_j-z_j\le0$. Hence Table II is optimal:

(All basic variables are strictly positive, so this optimal basic feasible solution is non-degenerate. That matters in Step 4.)

Step 4 — Does an alternate optimum exist? The diagnostic, stated as a rule.

Rule. At an optimal Simplex table, if some non-basic variable has net evaluation $c_j-z_j=\mathbf 0$, then bringing it into the basis changes the basic feasible solution but leaves $Z$ unchanged (the objective changes by $(c_j-z_j)\theta=0$, where $\theta$ is the entering value). Hence an alternate optimal basic feasible solution exists, and every convex combination of the two is optimal too. If instead $c_j-z_j<0$ for every non-basic $j$, the optimum is unique.

In Table II the non-basic variables are $x_1$ and $s_2$, with

The zero at the non-basic column $x_1$ is exactly the signature above, so an alternate optimal solution exists. Moreover the table is non-degenerate and the entering value will be $\theta=15/4>0$, so the pivot genuinely moves to a different vertex — it is not the degenerate false alarm in which a zero $c_j-z_j$ merely relabels the same point.

Step 5 — Perform the extra pivot $\;\Rightarrow\;$ Table III (the second optimal vertex).

Enter $x_1$. Minimum ratio test (column $x_1$, all entries positive): $6\div\frac85=\frac{15}{4}$, $4\div\frac25=10$, $6\div\frac45=\frac{15}{2}$. Minimum $\frac{15}{4}$ in row 1 $\Rightarrow$ $s_1$ leaves; pivot element $\frac85$.

Row operations: $R_1\to\frac58R_1$; then $R_2\to R_2-\frac25R_1^{\text{new}}$, $R_3\to R_3-\frac45R_1^{\text{new}}$.

Check of the new $z_j$: $z_3=4\cdot\frac58+10\cdot(-\frac14)+0=\frac52-\frac52=0$, so $c_3-z_3=0-0=0$; and $z_4=4\cdot(-\frac18)+10\cdot\frac14+0=-\frac12+\frac52=2$, so $c_4-z_4=-2$. The objective is

unchanged, as the rule predicted. All $c_j-z_j\le0$, so this table is optimal as well. Note the mirror image of the diagnostic: now $s_1$ is non-basic with $c_3-z_3=0$ — pivoting on it returns to Table II, confirming the two vertices are the endpoints of one optimal edge.

Second optimal basic feasible solution:

Feasibility check of this point in the original constraints: $2(3.75)+2.5=10\le10$ (tight), $2(3.75)+5(2.5)=7.5+12.5=20\le20$ (tight), $2(3.75)+3(2.5)=7.5+7.5=15\le18$ (slack $3$). ✓

Step 6 — The full set of optimal solutions (this, not two points, is the answer to “obtain an alternate optimal solution”).

The optimal set of an LP is a face of the feasible polyhedron, hence convex. Both

are optimal with $Z=40$, so every convex combination of them is feasible (convexity of the feasible region) and gives

Therefore the complete solution set is the line segment

equivalently, in the more usable parametric form

($\lambda=1$ recovers $P_1$; $\lambda=0$ recovers $P_2$; $t=x_1$.) The two basic feasible solutions found by the Simplex method are precisely the two end points of this segment; the infinitely many optimal points strictly between them are non-basic (they are not vertices), which is why the Simplex method can only ever produce the endpoints.

Step 7 — The structural reason (why the optimum had to be an edge, and an independent proof that $Z_{\max}=40$).

The objective is an exact multiple of the second constraint’s left-hand side:

Hence for every feasible point,

with equality iff $2x_1+5x_2=20$, i.e. iff the second constraint is tight ($s_2=0$). So:

• $Z_{\max}=40$, proved directly, with no Simplex at all;
• the optimal set is exactly the feasible part of the line $2x_1+5x_2=20$.

Determining that feasible part: on the line, $x_2=4-\frac25x_1$, and

The binding restriction is $0\le x_1\le\frac{15}{4}$ — precisely the segment of Step 6. This confirms the Simplex output completely and independently, and it explains the phenomenon: the objective line is parallel to (indeed coincident with) the boundary line of constraint 2, which is the geometric signature of alternate optima. In the table language, the parallelism shows up as the zero net evaluation on a non-basic column.

Two further structural observations worth one line each:

• Constraint 3 is redundant. At all four vertices of the region cut out by $2x_1+x_2\le10$, $2x_1+5x_2\le20$, $x\ge0$ — namely $(0,0),(5,0),\left(\frac{15}{4},\frac52\right),(0,4)$ — we get $2x_1+3x_2=0,\,10,\,15,\,12$, all $\le18$; since $2x_1+3x_2$ is linear, it is $\le18$ on the whole convex hull. So $2x_1+3x_2\le18$ removes nothing and $s_3>0$ at every optimal point. It is a distractor constraint.
• Vertex enumeration as a cross-check. The feasible vertices and their objective values are $(0,0)\!:\!0$, $(5,0)\!:\!20$, $\left(\frac{15}{4},\frac52\right)\!:\!40$, $(0,4)\!:\!40$. The maximum $40$ is attained at two adjacent vertices — the tie is the alternate optimum.

A sketch is optional here, and should be the first thing sacrificed. The question prescribes the Simplex method, so the tables carry the marks and the algebra of Step 7 already proves everything a picture could show — more sharply, in fact, since $Z=2(2x_1+5x_2)\le40$ is a proof and a drawing is not. If two minutes are genuinely spare after Steps 1–6, a small graph of the quadrilateral $O(0,0)\to A(5,0)\to B\left(\frac{15}{4},\frac52\right)\to C(0,4)$, with each vertex labelled by its coordinates and its $Z$ value and with the optimal iso-profit line $4x_1+10x_2=40$ drawn along the whole edge $CB$, makes the alternate optimum visible at a glance. Draw $2x_1+3x_2=18$ too if you draw anything: its lying entirely outside the region is the redundancy claim. But do not start the graph before the second pivot is on the page.

Answer