Skip to content
Exercises · Q8
Q.

Four workers W1,W2,W3W_1, W_2, W_3 must be assigned to three jobs J1,J2,J3J_1, J_2, J_3 — one worker per job — at minimum total cost. The cost matrix (₹) is given below. Use the Hungarian Method to find the optimal assignment and the minimum total cost.

J1J_1J2J_2J3J_3
W1W_1497
W2W_2865
W3W_36104
Puducherry TnboardTextbookSubjectiveImportance★★★★★
11% · 4/38 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 (subtract row minimums 4,5,44,5,4):

J1J_1J2J_2J3J_3
W1W_1053
W2W_2310
W3W_3260

Step 2 — Column reduction (column minimums: J1→0J_1\to0 unchanged, J2→1J_2\to1, J3→0J_3\to0 unchanged):

J1J_1J2J_2J3J_3
W1W_1043
W2W_2300
W3W_3250

Step 3/4 — Cover zeros and test: the zeros are at W1J1W_1J_1, W2J2W_2J_2, W2J3W_2J_3, W3J3W_3J_3. Notice W1J1W_1J_1, W2J2W_2J_2, W3J3W_3J_3 already form a set of three independent zeros (no two share a row or column) — the minimum number of lines needed to cover all zeros is therefore 3 (row W2W_2 plus columns J1J_1 and J3J_3, or equivalently three lines through the independent zeros themselves), which equals n=3n=3 → optimal immediately, no adjustment step needed.

Step 6 — Assignment: W1→J1W_1\to J_1, W2→J2W_2\to J_2, W3→J3W_3\to J_3 — a valid one-to-one mapping, every worker and every job used exactly once. …

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.