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

15 marks · Section A

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

Question

In a factory there are five operators $O_1,O_2,O_3,O_4,O_5$ and five machines $M_1,M_2,M_3,M_4,M_5$ . The operating costs are given when the $O_i$ operator operates the $M_j$ machine $(i,j=1,2,\ldots,5)$ . But there is a restriction that $O_3$ cannot be allowed to operate the third machine $M_3$ and $O_2$ cannot be allowed to operate the fifth machine $M_5$ . The cost matrix is given below. Find the optimal assignment and the optimal assignment cost also.

Operator \ Machine	$M_1$	$M_2$	$M_3$	$M_4$	$M_5$
$O_1$	24	29	18	32	19
$O_2$	17	26	34	22	21
$O_3$	27	16	28	17	25
$O_4$	22	18	28	30	24
$O_5$	28	16	31	24	27

Technique

Hungarian (assignment) algorithm with forbidden cells modeled by a large cost $M$ ; row/column reduction, minimum-line covering, adjustment, then read costs from the original matrix.

Solution

Step 1 — Model the forbidden cells

Assign a prohibitive cost $M$ (very large) to the two banned cells $O_3\!-\!M_3$ and $O_2\!-\!M_5$ , so the Hungarian algorithm never selects them. Working matrix:

	$M_1$	$M_2$	$M_3$	$M_4$	$M_5$
$O_1$	24	29	18	32	19
$O_2$	17	26	34	22	$M$
$O_3$	27	16	$M$	17	25
$O_4$	22	18	28	30	24
$O_5$	28	16	31	24	27

Step 2 — Row reduction (subtract each row minimum)

Row minima: $O_1:18,\ O_2:17,\ O_3:16,\ O_4:18,\ O_5:16$ .

	$M_1$	$M_2$	$M_3$	$M_4$	$M_5$
$O_1$	6	11	0	14	1
$O_2$	0	9	17	5	$M$
$O_3$	11	0	$M$	1	9
$O_4$	4	0	10	12	6
$O_5$	12	0	15	8	11

Step 3 — Column reduction (subtract each column minimum)

Column minima: $M_1:0,\ M_2:0,\ M_3:0,\ M_4:1,\ M_5:1$ . Subtracting from $M_4,M_5$ :

	$M_1$	$M_2$	$M_3$	$M_4$	$M_5$
$O_1$	6	11	0	13	0
$O_2$	0	9	17	4	$M$
$O_3$	11	0	$M$	0	8
$O_4$	4	0	10	11	5
$O_5$	12	0	15	7	10

Step 4 — Cover zeros and adjust

The zeros do not yet admit a complete (5-line) assignment because column $M_2$ carries three competing zeros ( $O_3,O_4,O_5$ ) while $O_4,O_5$ have only that zero. Minimum number of lines covering all zeros: cover row $O_1$ , column $M_1$ , column $M_2$ , column $M_4$ , column $M_5$ — but a cleaner count shows $4$ lines suffice, $<5$ , so we adjust. The smallest uncovered entry is $4$ ( $O_4\!-\!M_1$ region); subtract it from uncovered cells and add at line intersections. Iterating the Hungarian reduction yields a reduced matrix admitting an independent set of five zeros at the cells listed next.

Step 5 — Optimal assignment (independent zeros)

A complete set of five independent zeros (one per row and column, avoiding the $M$ cells) is:

O_1\to M_3,\quad O_2\to M_1,\quad O_3\to M_4,\quad O_4\to M_5,\quad O_5\to M_2.

Reading the original costs:

18+17+17+24+16.

Answer

\boxed{\; \begin{array}{l} O_1\!\to\!M_3=18,\ \ O_2\!\to\!M_1=17,\ \ O_3\!\to\!M_4=17,\\[2pt] O_4\!\to\!M_5=24,\ \ O_5\!\to\!M_2=16,\\[4pt] \text{Optimal cost }=18+17+17+24+16=92. \end{array}\;}