← 2026 Paper 2

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

15 marks · Section A

Assignment problem (Hungarian method) · Linear Programming · asked 7× in 14 yrs · Read the full method →

Question

The following table represents the estimated costs of assigning jobs to machines. Solve this assignment problem to minimize the total cost.

Is the assignment unique for the total minimum cost? Justify your answer and obtain an alternate assignment, if it exists.

Technique

The matrix is $3\times4$ — unbalanced — so the Hungarian method does not apply until a dummy job (a fourth row of zeros) is added; the machine that receives the dummy job is the one left idle. Then run the Hungarian algorithm proper: row reduction, column reduction, minimum line cover, and the “subtract the smallest uncovered element, add it at the crossings” update, iterating until the minimum number of covering lines equals the order $4$. Uniqueness is not answered by “the Hungarian gave one answer” — it is answered by counting the complete matchings available in the zero set of the final reduced matrix, and confirming the second assignment has the same cost.

Solution

Step 1 — Balance the problem.

An assignment problem requires a square matrix: a one-to-one correspondence between rows and columns. Here there are $3$ jobs and $4$ machines, so one machine must go unused. Introduce a dummy job $J_4$ (fictitious — it represents “no job at all”) with cost $0$ against every machine, since a machine that is left idle incurs no assignment cost:

Operational meaning: whichever machine ends up paired with $J_4$ does no real work — that machine stays idle, and its “cost” $0$ correctly contributes nothing to the total. This is the only legitimate balancing here; adding a dummy machine (a fifth column) would be wrong, since it is machines that are in surplus, not jobs.

Step 2 — Row reduction.

Subtract from each row its row minimum (this changes every assignment’s total by the same constant $8+8+8+0=24$, hence does not change which assignment is optimal — that is the whole justification for the method, and it is worth one line):

Step 3 — Column reduction.

Column minima are $0,0,0,0$ (column $M_1$ from rows $J_1$–$J_3$, and the rest from row $J_4$). The matrix is unchanged. Note why: $8$ is simultaneously the constant entry of column $M_1$ and the minimum of each of the first three rows, so the row step has already done the column-$M_1$ step.

Step 4 — Iteration 1: cover the zeros with the minimum number of lines.

Minimality check (König’s theorem: minimum lines $=$ maximum number of independent zeros). The zeros are $\{(J_1,M_1),(J_2,M_1),(J_3,M_1)\}\cup\{(J_4,M_j)\}_{j=1}^4$. Rows $J_1,J_2,J_3$ each have their only zero in $M_1$, so at most one of them can be assigned; with $J_4$ that gives at most $2$ independent zeros. Hence $N=2$ is minimal, and $N=2<4$: not yet optimal.

Smallest uncovered element (rows $J_1,J_2,J_3$ $\times$ columns $M_2,M_3,M_4$): $\min\{16,20,24,5,9,11,7,11,14\}=5$. Subtract $5$ from every uncovered entry; add $5$ at the crossing $(J_4,M_1)$; leave singly-covered entries alone.

Step 5 — Iteration 2.

Minimality: a maximum set of independent zeros is $(J_1,M_1),(J_2,M_2),(J_4,M_3)$ — size $3$; it cannot be $4$, because rows $J_1$ and $J_3$ both have their only zeros in column $M_1$ and cannot both be assigned. So $N=3<4$: not yet optimal.

Smallest uncovered element (rows $J_1,J_3$ $\times$ columns $M_2,M_3,M_4$): $\min\{11,15,19,2,6,9\}=2$. Subtract $2$ from those; add $2$ at the two crossings $(J_2,M_1)$ and $(J_4,M_1)$.

Step 6 — Iteration 3.

Minimality: maximum independent zeros $=(J_1,M_1),(J_2,M_2),(J_4,M_3)$, size $3$; $J_3$‘s zeros lie only in $M_1,M_2$, both already used, and no rearrangement helps ($J_1$ is confined to $M_1$). So $N=3<4$: not yet optimal.

Smallest uncovered element (rows $J_1,J_2,J_3$ $\times$ columns $M_3,M_4$): $\min\{13,17,4,6,4,7\}=4$. Subtract $4$ from those six entries; add $4$ at the crossings $(J_4,M_1)$ and $(J_4,M_2)$.

Step 7 — Iteration 4: the optimal reduced matrix.

Four independent zeros now exist, e.g. $(J_1,M_1),(J_2,M_2),(J_3,M_3),(J_4,M_4)$, so the minimum cover needs $N=4$ lines $=$ order of the matrix. The algorithm terminates: this reduced matrix yields an optimal assignment.

Step 8 — Read off the assignment(s) and the cost.

Zero positions of the final matrix, listed by row:

Row $J_1$ has a single zero, so $J_1\to M_1$ is forced; column $M_1$ is then exhausted, leaving $J_3:\{M_2,M_3\}$. Enumerating the complete selections of independent zeros:

• $J_4\to M_3$ would force both $J_2$ and $J_3$ into $M_2$ — impossible. Hence $J_4\to M_4$.
• That leaves $J_2,J_3$ to fill $M_2,M_3$, and both ways are zeros:
  • $J_2\to M_2,\ J_3\to M_3$;
  • $J_2\to M_3,\ J_3\to M_2$.

So the zero set supports exactly two complete assignments:

Costs from the original table:

Equal, as they must be. Minimum total cost $=40$, with machine $M_4$ left idle in either plan.

Step 9 — Uniqueness: justified independently of the algorithm.

The Hungarian tableau exhibits two optima, but a complete justification should not rest on the bookkeeping. Two short arguments settle it outright.

(i) $J_1\to M_1$ in every optimal assignment. Note $c_{2j}<c_{1j}$ and $c_{3j}<c_{1j}$ for every $j\in\{2,3,4\}$ (row $J_1$ is strictly the dearest on all non-$M_1$ columns), while column $M_1$ is constant at $8$. Suppose an optimal assignment gave $M_1$ to $J_2$ and put $J_1$ on some $M_a$, $a\neq1$. Exchanging the two changes the total by

a strict improvement — contradicting optimality. The same computation rules out $J_3\to M_1$. Finally, $M_1$ is used: if $M_1$ were the idle machine, move any one of the three jobs onto it from wherever it sits; the cost strictly falls, because in the original $3\times4$ table every entry outside column $M_1$ is at least $13>8$. Hence every optimum has $J_1\to M_1$, contributing $8$.

(ii) The residual $2\times3$ problem. With $J_1$ fixed on $M_1$, the remaining choice is to place $J_2,J_3$ on two distinct machines from $\{M_2,M_3,M_4\}$:

All six possibilities:

The minimum $32$ is attained exactly twice: $(J_2\to M_2,\ J_3\to M_3)$ and $(J_2\to M_3,\ J_3\to M_2)$. Adding the forced $8$:

Step 10 — Why column $M_1$ being constant matters.

Every entry of column $M_1$ equals $8$. Three consequences, each worth stating:

1. $8$ is therefore the minimum of every one of the first three rows, so the row-reduction step simultaneously performs the column reduction on $M_1$ — which is exactly why Step 3 produced no change and why the first line cover needed only $2$ lines. The algorithm then had to grind through three update iterations.
2. Because the column is constant, $M_1$ carries no information about which job should be put on it. The cost of an assignment using $M_1$ is $8+(\text{cost of the other two jobs on two of }M_2,M_3,M_4)$; the identity of the job sent to $M_1$ matters only through which jobs are left over. That is precisely the exchange argument of Step 9(i), and it is what makes $J_1$ — the job that is dearest everywhere else — the one to park on $M_1$.
3. Since $8$ is strictly below every entry outside column $M_1$, $M_1$ is used in every optimum; the idle machine is never $M_1$.

Step 11 — Sensitivity remark (one line, cheap, and shows the structure).

The two optima differ by the transposition of $J_2,J_3$ between $M_2$ and $M_3$, and are tied because

i.e. the $2\times2$ submatrix on rows $\{J_2,J_3\}$, columns $\{M_2,M_3\}$ has vanishing cross-difference

(It is this quantity, not the determinant, that decides a $2\times2$ assignment tie: the two admissible pairings differ in cost by exactly the cross-difference.) Perturb any one of those four entries and the tie breaks, leaving a unique optimum. This is the algebraic reason the alternate assignment exists — it is not a coincidence of the arithmetic.

Answer

The assignment is not unique: there are exactly two optimal assignments, (A) and (B), each of total cost $40$; (B) is the required alternate assignment. In both, machine $M_4$ is left idle.