UPSC 2015 Maths Optional Paper 2 Q1e — Step-by-Step Solution

10 marks · Section A

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

Question

Solve the following assignment problem to maximize the sales (5×5 cost matrix; salesmen A-E to territories I-V):

\begin{array}{c|ccccc} & \text{I} & \text{II} & \text{III} & \text{IV} & \text{V}\\\hline A & 3 & 4 & 5 & 6 & 7\\ B & 4 & 15 & 13 & 7 & 6\\ C & 6 & 13 & 12 & 5 & 11\\ D & 7 & 12 & 15 & 8 & 5\\ E & 8 & 13 & 10 & 6 & 9\end{array}

Technique

Hungarian method on the opportunity-loss matrix (15 − sales). Iterative Hall’s-condition check for matching feasibility; standard Hungarian reduction until a 5-matching exists.

Solution

Strategy. Convert maximization to minimization by subtracting each entry from the global maximum (here, 15). Then apply Hungarian method.

Step 1 — Convert to opportunity-loss matrix (15 − entry)

M_1=\begin{pmatrix}12 & 11 & 10 & 9 & 8\\ 11 & 0 & 2 & 8 & 9\\ 9 & 2 & 3 & 10 & 4\\ 8 & 3 & 0 & 7 & 10\\ 7 & 2 & 5 & 9 & 6\end{pmatrix}

Step 2 — Row reduction (subtract row min from each row)

Row mins: 8, 0, 2, 0, 2.

M_2=\begin{pmatrix}4 & 3 & 2 & 1 & 0\\ 11 & 0 & 2 & 8 & 9\\ 7 & 0 & 1 & 8 & 2\\ 8 & 3 & 0 & 7 & 10\\ 5 & 0 & 3 & 7 & 4\end{pmatrix}

Step 3 — Column reduction (subtract col min from each col)

Col mins: 4, 0, 0, 1, 0.

M_3=\begin{pmatrix}0 & 3 & 2 & 0 & 0\\ 7 & 0 & 2 & 7 & 9\\ 3 & 0 & 1 & 7 & 2\\ 4 & 3 & 0 & 6 & 10\\ 1 & 0 & 3 & 6 & 4\end{pmatrix}

Step 4 — Cover all zeros with minimum lines

Zeros: (A,I), (A,IV), (A,V), (B,II), (C,II), (D,III), (E,II).

Column II has 3 zeros (rows B, C, E). Cover col II. Remaining zeros: (A,I), (A,IV), (A,V), (D,III).

Row A has 3 of these zeros. Cover row A. Remaining zero: (D,III) — cover row D or col III.

Total lines so far: row A, col II, row D (or col III) = 3 lines. Need 5 (= matrix size) for optimal assignment. Not yet optimal; proceed to Step 5.

Step 5 — Reduce uncovered entries by min uncovered

Lines cover row A, col II, row D. Uncovered entries (rows B, C, E and cols I, III, IV, V):

	I	III	IV	V
B	7	2	7	9
C	3	1	7	2
E	1	3	6	4

Min uncovered = 1 (at (E,I) and (C,III)). Subtract 1 from all uncovered cells; add 1 to cells covered by two lines (intersection of row A & col II — that’s just (A,II), and (D,II)).

After:

M_4=\begin{pmatrix}0 & 4 & 2 & 0 & 0\\ 6 & 0 & 1 & 6 & 8\\ 2 & 0 & 0 & 6 & 1\\ 4 & 4 & 0 & 6 & 10\\ 0 & 0 & 2 & 5 & 3\end{pmatrix}

Step 6 — Recheck for assignment

Try to find an assignment of one zero per row & column.

Zeros by row:

A: (A,I), (A,IV), (A,V) — 3 choices
B: (B,II) — only one
C: (C,II), (C,III) — 2 choices
D: (D,III) — only one
E: (E,I), (E,II) — 2 choices

Force B → II, D → III. Then C cannot use II (B has it) or III (D has it). But C only has zeros at II and III — conflict!

So this assignment fails. Need another reduction round.

Let me cover all zeros minimum lines: B,D,E rows? E has 2 zeros in I,II. With B forcing II, the structure:

Cover lines: col II (covers (A,II)… wait, (A,II) is not zero). Let’s recount zeros:

(A,I), (A,IV), (A,V)
(B,II)
(C,II), (C,III)
(D,III)
(E,I), (E,II)

Try covering: col II covers (B,II), (C,II), (E,II). Row A covers (A,I), (A,IV), (A,V). Row D covers (D,III). That leaves (C,III) and (E,I) uncovered.

Add row C? Now covered: col II, rows A, C, D. Remaining: (E,I) only. Add col I or row E. 4 lines total.

Add col I: lines = {col II, col I, row A, row C, row D} = 5 lines. So 5 lines suffice; check whether a 5-assignment is possible from $M_4$ .

Actually if 5 lines cover all zeros, by König we can find a matching only when 5 lines are necessary (= matrix dimension). Need a strict assignment search.

Try: A→IV, B→II, C→III, D→? D has only (D,III) zero; conflict with C→III.

Try: A→IV, B→II, C→II conflict; C→III, D needs zero outside III; D has only (D,III). Conflict.

Reassign: A→I, B→II, C→III, D→? D only has III. Conflict.

So we have a structural conflict between C and D — both demand row-restrictive zeros that overlap. Need another reduction.

Step 7 — Another reduction round

Cover lines as above: {col II, row A, row C, row D} = 4 lines covering all zeros (let me re-verify):

col II: covers (B,II), (C,II), (E,II)
row A: covers (A,I), (A,IV), (A,V)
row C: covers (C,III) — already covered by row C
row D: covers (D,III)

So 4 lines cover all zeros: {row A, col II, row C, row D}.

Wait — does (E,I) get covered? (E,I) is in row E and col I; neither is in our covering set. So (E,I) is uncovered.

Recount: row A, col II, row C, row D. (E,I) uncovered. So 4 lines don’t suffice; add col I or row E.

4 < 5, so reduce. Uncovered cells: rows B,E and cols I, III, IV, V (intersected with not-row-C/D).

Actually with covers {row A, col II, row C, row D}, uncovered rows = {B, E}, uncovered cols = {I, III, IV, V}.

Uncovered entries:

	I	III	IV	V
B	6	1	6	8
E	0	2	5	3

Min uncovered = 0 (at (E,I)). But that’s already a zero — adjustment by 0 changes nothing.

Hmm — that means we should find a covering with fewer lines or accept that a matching exists.

Let me re-examine. Going back to $M_4$ , perhaps a different matching works.

Re-examine zeros in $M_4$ :

A: I, IV, V
B: II
C: II, III
D: III
E: I, II

To match: pick distinct rows and cols for zeros.

Bipartite matching approach. Treat as bipartite graph (rows → cols by zero entries):

A: {I, IV, V}
B: {II}
C: {II, III}
D: {III}
E: {I, II}

We need a perfect matching. Try Hall’s condition on subset {B, D}: their neighborhoods are {II} ∪ {III} = {II, III}, size 2. OK.

Subset {B, C, D}: neighborhoods = {II, III}, size 2 < 3. Hall’s condition fails!

So no perfect matching exists with these zeros; we must reduce more.

Step 8 — Second reduction

The min vertex cover for the bipartite graph above is: cover B, C, D’s neighborhoods. {II, III} covers (B,II), (C,II), (C,III), (D,III), but misses (E,I), (E,II)—well, col II covers (E,II). (E,I) needs row E or col I.

Min cover: col II + col III + row A + row E = 4 lines (covers A’s 3 zeros, B’s 1, C’s 2, D’s 1, E’s 2).

Uncovered entries: rows B, C, D and cols I, IV, V:

	I	IV	V
B	6	6	8
C	2	6	1
D	4	6	10

Min uncovered = 1 (at (C,V)). Subtract 1 from uncovered; add 1 to double-covered (intersections of two covering lines: row A ∩ col II = (A,II), row A ∩ col III = (A,III), row E ∩ col II = (E,II), row E ∩ col III = (E,III)).

M_5=\begin{pmatrix}0 & 5 & 3 & 0 & 0\\ 5 & 0 & 1 & 5 & 7\\ 1 & 0 & 0 & 5 & 0\\ 3 & 4 & 0 & 5 & 9\\ 0 & 1 & 3 & 4 & 2\end{pmatrix}

Wait — I need to also subtract the min from uncovered rows (rows B, C, D): each gets -1.

Let me redo. Standard Hungarian step:

Subtract min uncovered (=1) from each uncovered row: B, C, D each lose 1 across all entries.
Add min uncovered (=1) to each covered column: cols II, III each gain 1.
Equivalently: subtract from uncovered cells, add to doubly-covered, leave singly-covered as is.

Apply to $M_4$ :

Uncovered cells (rows B,C,D ∩ cols I,IV,V): subtract 1.
Doubly-covered cells (row A ∩ col II/III, row E ∩ col II/III): add 1.
Singly-covered: unchanged.

Doubly-covered: (A,II), (A,III), (E,II), (E,III).

From $M_4$ :

$M_4$ row A: 0, 4, 2, 0, 0 → keep (A,I)=0, (A,II)=4+1=5, (A,III)=2+1=3, (A,IV)=0, (A,V)=0.
$M_4$ row B: 6, 0, 1, 6, 8 → (B,I)=6-1=5, (B,II)=0 unchanged (covered by col II), (B,III)=1 unchanged, (B,IV)=6-1=5, (B,V)=8-1=7.
$M_4$ row C: 2, 0, 0, 6, 1 → (C,I)=1, (C,II)=0, (C,III)=0, (C,IV)=5, (C,V)=0.
$M_4$ row D: 4, 4, 0, 6, 10 → (D,I)=3, (D,II)=4, (D,III)=0, (D,IV)=5, (D,V)=9.
$M_4$ row E: 0, 0, 2, 5, 3 → (E,I)=0 unchanged, (E,II)=0+1=1, (E,III)=2+1=3, (E,IV)=5 unchanged, (E,V)=3 unchanged.

M_5=\begin{pmatrix}0 & 5 & 3 & 0 & 0\\ 5 & 0 & 1 & 5 & 7\\ 1 & 0 & 0 & 5 & 0\\ 3 & 4 & 0 & 5 & 9\\ 0 & 1 & 3 & 5 & 3\end{pmatrix}

Step 9 — Re-check for assignment

Zeros in $M_5$ :

A: I, IV, V
B: II
C: II, III, V
D: III
E: I

Bipartite:

A: {I,IV,V}
B: {II}
C: {II,III,V}
D: {III}
E: {I}

Force B→II, D→III, E→I. Then C cannot use II,III; C still has V. C→V. Then A cannot use I,V; A→IV.

Assignment: A→IV, B→II, C→V, D→III, E→I.

Verify each is a zero in $M_5$ :

(A,IV): 0 ✓
(B,II): 0 ✓
(C,V): 0 ✓
(D,III): 0 ✓
(E,I): 0 ✓

Step 10 — Compute total sales

Original sales matrix:

A→IV: 6
B→II: 15
C→V: 11
D→III: 15
E→I: 8

Total = 6 + 15 + 11 + 15 + 8 = 55.

Answer

\boxed{\;\text{Optimal assignment: A→IV, B→II, C→V, D→III, E→I; maximum sales }=55.\;}