Three machines $A, B, C$ are to be assigned to three jobs $J_1, J_2, J_3$. Machine $B$ **cannot** process job $J_3$ (it lacks the required attachment). The costs (in $₹$) are: | Machine | $J_1$ | $J_2$ | $J_3$ | |---|---|---|---| | $A$ | 9 | 11 | 14 | | $B$ | 6 | 15 | $\infty$ | | $C$ | 12 | 13 | 6 | Here $\infty$ marks the forbidden pairing. Find the minimum-cost assignment.

**Step 1 — Row reduction.** Treat $\infty$ as untouchable (it never reduces to $0$). Row minima: $A{:}\,9,\ B{:}\,6,\ C{:}\,6$. | Machine | $J_1$ | $J_2$ | $J_3$ | |---|---|---|---| | $A$ | 0 | 2 | 5 | | $B$ | 0 | 9 | $\infty$ | | $C$ | 6 | 7 | 0 | **Step 2 — Column reduction.** Column minima: $0, 2, 0$. | Machine | $J_1$ | $J_2$ | $J_3$ | |---|---|---|---| | $A$ | 0 | 0 | 5 | | $B$ | 0 | 7 | $\infty$ | | $C$ | 6 | 5 | 0 | **Step 3 — Assign the zeros.** - $C$ single zero at $J_3$ $\to$ assign $C \to J_3$. - $B$ single zero at $J_1$ $\to$ assign $B \to J_1$; cross $AJ_1$. - $A$ now single zero at $J_2$ $\to$ assign $A \to J_2$. Three independent zeros — optimal. The forbidden cell $BJ_3$ (cost $\infty$) is never chosen. **Total cost (original matrix):** $$AJ_2 + BJ_1 + CJ_3 = 11 + 6 + 6 = ₹\,23.$$ …

Three machines A, B, C are to be assigned to three jobs J₁, J₂, J₃. Machine B **cannot** process job J₃ (it la

Worked Examples · Example 7

Three machines $A, B, C$ are to be assigned to three jobs $J_1, J_2, J_3$ . Machine $B$ cannot process job $J_3$ (it lacks the required attachment). The costs (in $₹$ ) are:

Machine	$J_1$	$J_2$	$J_3$
$A$	9	11	14
$B$	6	15	$\infty$
$C$	12	13	6

Here $\infty$ marks the forbidden pairing. Find the minimum-cost assignment.

Maharashtra MsbshseTextbookSubjectiveImportance★★★★★

34% · 11/32 Questions

🔒 Locked · start free trial →

You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.

Start your 14-day free trial to unlock the full solution →

Step 1 — Row reduction. Treat $\infty$ as untouchable (it never reduces to $0$ ). Row minima: $A{:}\,9,\ B{:}\,6,\ C{:}\,6$ .

Machine	$J_1$	$J_2$	$J_3$
$A$	0	2	5
$B$	0	9	$\infty$
$C$	6	7	0

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

Machine	$J_1$	$J_2$	$J_3$
$A$	0	0	5
$B$	0	7	$\infty$
$C$	6	5	0

Step 3 — Assign the zeros.

$C$ single zero at $J_3$ $\to$ assign $C \to J_3$ .
$B$ single zero at $J_1$ $\to$ assign $B \to J_1$ ; cross $AJ_1$ .
$A$ now single zero at $J_2$ $\to$ assign $A \to J_2$ .

Three independent zeros — optimal. The forbidden cell $BJ_3$ (cost $\infty$ ) is never chosen.

Total cost (original matrix):

$AJ_2 + BJ_1 + CJ_3 = 11 + 6 + 6 = ₹\,23.$ …

Start your 14-day free trial to unlock the full solution →

←Previous questionExample 6 — A shop must complete four jobs J₁, J₂, J₃, J₄ but has only three machi…→Next questionExample 9 — Five jobs must each be processed first on Machine M₁ and then on Machi…

🎓Unlock everything free for 14 days

Unlock everything free for 14 days