Skip to content
Worked Examples · Example 6
Q.

A shop must complete four jobs J1,J2,J3,J4J_1, J_2, J_3, J_4 but has only three machines M1,M2,M3M_1, M_2, M_3 (each machine can take one job). The cost (in ₹₹) is:

MachineJ1J_1J2J_2J3J_3J4J_4
M1M_14682
M2M_26359
M3M_35748

Assign the jobs to minimise total cost, and state which job is left undone.

Maharashtra MsbshseTextbookSubjectiveImportance★★★★★
31% · 10/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 0 — Balance the problem. There are 44 jobs but only 33 machines, so add a dummy machine M4M_4 with all costs 00:

MachineJ1J_1J2J_2J3J_3J4J_4
M1M_14682
M2M_26359
M3M_35748
M4M_40000

Step 1 — Row reduction. Row minima 2,3,4,02, 3, 4, 0:

MachineJ1J_1J2J_2J3J_3J4J_4
M1M_12460
M2M_23026
M3M_31304
M4M_40000

Step 2 — Column reduction. Column minima are 0,0,0,00, 0, 0, 0 — no change.

Step 3 — Assign the zeros.

  • M1M_1 single zero at J4J_4 →\to assign M1→J4M_1 \to J_4.
  • M2M_2 single zero at J2J_2 →\to assign M2→J2M_2 \to J_2.
  • M3M_3 single zero at J3J_3 →\to assign M3→J3M_3 \to J_3.
  • M4M_4 (dummy) takes the only column left, J1J_1 (a zero) →\to M4→J1M_4 \to J_1.

Four independent zeros — optimal. …

Unlock everything free for 14 days

  • Full step-by-step solutions
  • Concept-first explanations
  • Methods, shortcuts & mistakes
  • PYQ mapping + timed mock tests

Full access for 14 days. No credit card required.