Assign four workers $A, B, C, D$ to four jobs $J_1, J_2, J_3, J_4$ (one each) to minimise total cost (in $₹$):

| Worker | $J_1$ | $J_2$ | $J_3$ | $J_4$ |
|---|---|---|---|---|
| $A$ | 10 | 12 | 19 | 11 |
| $B$ | 5 | 10 | 7 | 8 |
| $C$ | 12 | 14 | 13 | 11 |
| $D$ | 8 | 15 | 11 |

Question

Assign four workers $A, B, C, D$ to four jobs $J_1, J_2, J_3, J_4$ (one each) to minimise total cost (in $₹$):

| Worker | $J_1$ | $J_2$ | $J_3$ | $J_4$ |
|---|---|---|---|---|
| $A$ | 10 | 12 | 19 | 11 |
| $B$ | 5 | 10 | 7 | 8 |
| $C$ | 12 | 14 | 13 | 11 |
| $D$ | 8 | 15 | 11 | 9 |

Find the optimal assignment and the minimum cost.

Accepted Answer

**Step 1 — Row reduction.** Row minima: $10, 5, 11, 8$.

| Worker | $J_1$ | $J_2$ | $J_3$ | $J_4$ |
|---|---|---|---|---|
| $A$ | 0 | 2 | 9 | 1 |
| $B$ | 0 | 5 | 2 | 3 |
| $C$ | 1 | 3 | 2 | 0 |
| $D$ | 0 | 7 | 3 | 1 |

**Step 2 — Column reduction.** Column minima: $0, 2, 2, 0$.

| Worker | $J_1$ | $J_2$ | $J_3$ | $J_4$ |
|---|---|---|---|---|
| $A$ | 0 | 0 | 7 | 1 |
| $B$ | 0 | 3 | 0 | 3 |
| $C$ | 1 | 1 | 0 | 0 |
| $D$ | 0 | 5 | 1 | 1 |

**Step 3 — Assign the zeros.**
- $D$ has a single zero at $J_1$ $	o$ assign $D 	o J_1$; cross $AJ_1, BJ_1$.
- $A$ now has a single zero at $J_2$ $	o$ assign $A 	o J_2$.
- $B$ now has a single zero at $J_3$ $	o$ assign $B 	o J_3$; cross $CJ_3$.
- $C$ now has a single zero at $J_4$ $	o$ assign $C 	o J_4$.

Four independent zeros — optimal.

**Total cost (original matrix):**
$$AJ_2 + BJ_3 + CJ_4 + DJ_1 = 12 + 7 + 11 + 8 = ₹\,38.$$ …

🎓Unlock everything free for 14 days

Unlock everything free for 14 days