CHAPTER 6

Assignment Problem

6.1 What is the Assignment Problem?

An assignment problem asks: given n workers (or machines, salespeople, etc.) and n jobs (tasks,
territories, machines), which worker should be assigned to which job to minimise total cost (or maximise
total profit)?

DEFINITION — Assignment Problem

An assignment problem is a special case of the transportation problem where:
• There are n sources (workers) each with supply = 1
• There are n destinations (jobs) each with demand = 1
• Each worker must be assigned exactly one job, and each job gets exactly one worker
• cᵢⱼ = cost (or time, or profit) of assigning worker i to job j

Objective: Find a one-to-one assignment of workers to jobs that minimises total cost.

LPP formulation:
Minimise Z = Σᵢ Σⱼ cᵢⱼ xᵢⱼ
Subject to: Σⱼ xᵢⱼ = 1 for all i (each worker does exactly one job)
Σᵢ xᵢⱼ = 1 for all j (each job is done by exactly one worker)
xᵢⱼ ∈ {0, 1}

WHY? — Why not just use the Transportation method?

You CAN solve an assignment problem as a transportation problem — but it is extremely
degenerate. A balanced n×n assignment problem needs m+n−1 = 2n−1 occupied cells in its
BFS, but since supply = demand = 1 for every row and column, we can never have more
than n occupied cells (one per row). So we always need n−1 dummy ε allocations, making
MODI very tedious.

The Hungarian Assignment Method (HAM) is far more efficient — it exploits the special
structure of the cost matrix directly.

6.2 Hungarian Assignment Method (HAM)

The HAM is based on a key theorem: if we add or subtract any constant from every element of a row or
column of the cost matrix, the optimal assignment does NOT change (only the total cost changes). This lets
us reduce the matrix until zeros mark the optimal assignments.

RULE — HAM — Complete Step-by-Step Procedure

STEP 1 — ROW REDUCTION: Subtract the minimum value of each row from every element
 in that row.
Result: every row has at least one zero.

STEP 2 — COLUMN REDUCTION: Subtract the minimum value of each column from every
element in that column.
Result: every column has at least one zero. This is the Reduced Cost Table.

STEP 3 — COVER ALL ZEROS: Draw the MINIMUM number of horizontal/vertical lines
needed to cover all zeros.
(This is equivalent to finding a maximum matching in a bipartite graph.)

STEP 4 — OPTIMALITY TEST:

If lines = n → OPTIMAL. Make assignments at zeros (Step 5).
If lines < n → NOT OPTIMAL. Go to Step 4a.

STEP 4a — IMPROVE THE TABLE (when lines < n):

(i) Find the MINIMUM value among all UNCOVERED cells.
(ii) SUBTRACT this minimum from every uncovered cell.
(iii) ADD this minimum to every cell at the INTERSECTION of two lines.
(iv) Leave cells covered by exactly one line unchanged.
Return to Step 3.

STEP 5 — MAKE ASSIGNMENTS: When lines = n, make one-to-one assignments at zero

cells:
(i) Find a row with exactly ONE zero — assign it. Cross out all other zeros in that
column.
(ii) Find a column with exactly ONE zero — assign it. Cross out other zeros in that row.
(iii) Repeat until all assignments are made.
(iv) If ties remain (multiple zeros), try each option — one will give a feasible
assignment.

WHY? — Why does subtracting/adding the minimum work?

Since we subtract a constant from every element of a row (or column), the RELATIVE
differences between elements in that row do not change — the same assignment that was
cheapest before is still cheapest after. The reduction creates zeros without distorting the
optimal choice.

The minimum-lines test: if we can cover all zeros with fewer than n lines, it means no
complete one-to-one zero assignment is possible yet — we need to create more zeros in the
currently uncovered cells by the reduction in Step 4a.

EXAMPLE 6.3 HAM — 4 Workers × 4 Jobs (Minimisation)

Four workers are to be assigned to four jobs. Time taken (minutes):

 Worker Job A Job B Job C Job D
1 45 40 51 67
2 57 42 63 55
3 49 52 48 64
4 41 45 60 55

STEP — 1 — Row Reduction (subtract row minimum)

Row 1: min=40. Subtract 40: [5, 0, 11, 27]
Row 2: min=42. Subtract 42: [15, 0, 21, 13]
Row 3: min=48. Subtract 48: [1, 4, 0, 16]
Row 4: min=41. Subtract 41: [0, 4, 19, 14]

Reduced Cost Table 1 (after row reduction):

Worker Job A Job B Job C Job D
1 5 0 11 27
2 15 0 21 13
3 1 4 0 16
4 0 4 19 14

STEP — 2 — Column Reduction (subtract column minimum)

Col A: min=0. No change.
Col B: min=0. No change.
Col C: min=0. No change.
Col D: min=13. Subtract 13: [27→14, 13→0, 16→3, 14→1]

Reduced Cost Table 2 (after column reduction):

Worker Job A Job B Job C Job D
1 5 0 11 14
2 15 0 21 0
3 1 4 0 3
4 0 4 19 1

STEP — 3 — Cover all zeros with minimum lines

Zeros at: (1,B), (2,B), (2,D), (3,C), (4,A).
Lines needed: Col B covers (1,B) and (2,B). Row 2 covers (2,D). Row 3 covers (3,C). Row 4
covers (4,A).
Total lines = 4 = n. → OPTIMAL immediately!

STEP — 5 — Make Assignments

 Row 4 has ONE zero → Assign Worker 4 to Job A. Cross out Col A zeros.
Row 3 has ONE zero (3,C) → Assign Worker 3 to Job C. Cross out Col C zeros.
Row 1 has ONE zero (1,B) → Assign Worker 1 to Job B. Cross out Col B zeros.
Only (2,D) remains → Assign Worker 2 to Job D.

Optimal Assignment:
Worker Job A Job B Job C Job D
1 [5] [0] 11 14
2 15 ✗ [21] [0]
3 1 [4] [0] 3
[4] [0] 4 19 1

FINAL ANSWER
Worker 1 → Job B (40 min)
Worker 2 → Job D (55 min)
Worker 3 → Job C (48 min)
Worker 4 → Job A (41 min)
Minimum total time = 40 + 55 + 48 + 41 = 184 minutes

EXAMPLE 6.4 HAM — When Iteration is Needed (5×5 with Multiple Iterations)

Five machinists (A–E) assigned to five jobs (1–5). Cost matrix:

Machinist Job 1 Job 2 Job 3 Job 4 Job 5

A 10 3 3 2 8
B 9 7 8 2 7
C 7 5 6 2 4
D 3 5 8 2 4
E 9 10 9 6 10

Step 1 — Row Reduction:

Machinist Job 1 Job 2 Job 3 Job 4 Job 5
A 8 1 1 0 6
B 7 5 6 0 5
C 5 3 4 0 2
D 1 3 6 0 2
E 3 4 3 0 4

Step 2 — Column Reduction (only Col 1 has min=1):

Machinist Job 1 Job 2 Job 3 Job 4 Job 5
 A 7 0 0 0 4
B 6 4 5 0 3
C 4 2 3 0 0
D 0 2 5 0 0
E 2 3 2 0 2

NOTE
Zeros at: A(1,2,3,4), B(4), C(4,5), D(1,4,5), E(4). Cover with lines:
Lines: Col 4 (covers all col-4 zeros), Row A (covers A1,A2,A3), Row C or D for remaining
zeros.
Minimum lines = 3 < 5. NOT OPTIMAL. Proceed to Step 4a.

STEP — 4a — Improve (Iteration 1)

Minimum uncovered value = 2 (cells B1, B2, B3, B5, E1, E2, E3, E5 — smallest is 2).
Subtract 2 from all uncovered cells.
Add 2 to intersection cells (where two lines cross).
After revision → draw lines again. Still need another iteration until lines = 5.

NOTE
After 2 iterations the reduced cost table has enough zeros to cover with 5 lines →
OPTIMAL.
Final optimal assignment (from book Table 6.14):
A→Job 3, B→Job 4, C→Job 5, D→Job 1, E→Job 3... (tie situation → multiple optimal
solutions)
One optimal: A–2, B–4, C–5, D–1, E–3. Total cost = 3+2+4+3+9 = 21.
Another optimal: A–3, B–4, C–5, D–1, E–2. Total cost = 3+2+4+3+10 = 22. ← Not same!
The HAM leads to: A→Job 2 (cost 3), B→Job 4 (cost 2), C→Job 5 (cost 4), D→Job 1 (cost
3), E→Job 3 (cost 9).
Minimum total cost = 3+2+4+3+9 = 21.

6.3 Special Cases

6.3.1 Unbalanced Assignment Problem
DEFINITION — Unbalanced Assignment Problem
When the number of workers ≠ number of jobs, the problem is UNBALANCED.

If workers > jobs: Add DUMMY JOBS (columns) with zero cost for all workers.
If jobs > workers: Add DUMMY WORKERS (rows) with zero cost for all jobs.

The dummy assignments represent workers left idle or jobs left unassigned.
After solving, ignore all assignments made to/from dummy rows or columns.
6.3.2 Constrained (Prohibited) Assignments
DEFINITION — Prohibited Assignments
Some worker-job combinations may be forbidden (worker lacks skill, regulatory restriction,
etc.).

Fix: Assign a very large cost M to the prohibited cell cᵢⱼ.

Since HAM minimises cost, the algorithm will never choose a cell with cost M.

After row and column reductions, M remains effectively infinite — it never becomes the
minimum uncovered value and is never selected as an assignment zero.

6.3.3 Multiple Optimal Solutions

DEFINITION — Multiple Optimal Solutions
When the final reduced cost table has more zeros than needed (more than one zero per
row/column arrangement), multiple optimal assignments are possible — all giving the same
minimum total cost.

Identification: In Step 5, if both a row and a column each have exactly one zero in the same
cell, you may have a choice. Try each combination — all valid complete assignments are
equally optimal.

Practical relevance: Management can choose among equally cheap assignments based on
other criteria (worker preference, fairness, risk).

6.3.4 Maximisation Assignment Problem

DEFINITION — Maximisation Assignment Problem
When the objective is to MAXIMISE total profit (or revenue, or efficiency):

METHOD — Opportunity Loss (Regret) Matrix:

For each cell (i,j): Opportunity Loss = Maximum value in entire matrix − pᵢⱼ

This converts the maximisation problem into an equivalent minimisation problem.

Apply HAM to the opportunity loss matrix. The optimal assignment is the same.

EXAMPLE 6.7 Maximisation — 5 Salesmen × 5 Districts

Expected sales (₹ thousands) if salesman Sᵢ is assigned to district Dⱼ:

Salesman D1 D2 D3 D4 D5
S1 40 46 48 36 48
S2 48 32 36 29 44
S3 49 35 41 38 45
 S4 30 46 49 44 45
S5 37 41 48 43 47

Maximum value = 49. Opportunity Loss = 49 − pᵢⱼ for each cell:

Salesman D1 D2 D3 D4 D5
S1 9 3 1 13 1
S2 1 17 13 20 5
S3 0 14 8 11 4
S4 19 3 0 5 4
S5 12 8 1 6 2

Apply HAM to the opportunity loss matrix:

Row reduction: S1→[8,2,0,12,0], S2→[0,16,12,19,4], S3→[0,14,8,11,4], S4→[19,3,0,5,4],
S5→[10,6,−1,4,0]... Wait — S5 min=1: [11,7,0,5,1].
Column reduction on result → further zeros appear.
After full HAM iterations (Tables 6.21–6.24 in Vohra):

FINAL ANSWER
Optimal assignment: S1→D3, S2→D1, S3→D5, S4→D3... (tie resolved)
From book: S1–D3, S2–D1, S3–D5, S4–D3 is infeasible (two in D3).
Correct optimal: S1→D5, S2→D1, S3→D5... resolve via iteration.
Book result (Table 6.24): S1–D2, S2–D1, S3–D5, S4–D3, S5–D4.
Maximum sales = 46 + 48 + 45 + 49 + 43 = ₹231 thousand.

6.4 Step-by-Step Summary

STEP — 1 — Set up matrix

Write n×n cost matrix. If unbalanced → add dummy row/column (zero costs).
If maximisation → create opportunity loss matrix (max value − each cell).
If prohibited → set those cells to M.

STEP — 2 — Row & Column Reduction

Subtract row minimum from each row.
Then subtract column minimum from each column.
Result: at least one zero in every row and column.

STEP — 3 — Cover zeros & test

Draw minimum number of lines to cover ALL zeros.
If lines = n → OPTIMAL (go to Step 5).
 If lines < n → not optimal (go to Step 4).

STEP — 4 — Improve the table

Find minimum uncovered value k.
Subtract k from all uncovered cells.
Add k to all intersection cells (covered by 2 lines).
Singly-covered cells: unchanged.
Return to Step 3.

STEP — 5 — Make assignments

Scan for rows/columns with exactly one zero → assign → cross out remaining zeros in that
col/row.
Repeat until all n assignments are made.
If tie → try alternatives (all give same cost = multiple optimal solutions).
Total cost = sum of original cᵢⱼ at assigned cells.

6.5 Practice Questions

Q1. Solve the following assignment problem (minimise cost):

Worker Job 1 Job 2 Job 3 Job 4
A 9 2 7 8
B 6 4 3 7
C 5 8 1 8
D 7 6 9 4
[Ans: A→2 (cost 2), B→3 (cost 3), C→1 (cost 5), D→4 (cost 4). Minimum cost = 14.]

Q2. A company has 4 machines and 5 jobs. One machine will be idle. Assign jobs to machines to minimise
total processing time:
Machine J1 J2 J3 J4 J5
M1 9 22 58 11 19
M2 43 78 72 50 63
M3 41 28 91 37 45
M4 74 42 27 49 39
[Ans: Unbalanced — add dummy M5 (all zeros). After HAM: M1→J4, M2→J1, M3→J2, M4→J3, M5→J5
(idle). Min cost = 11+43+28+27+0 = 109.]

Q3. Five workers are to be assigned to five machines. Worker B cannot operate Machine 3, and Worker D
cannot operate Machine 2. Find the minimum cost assignment:
Worker M1 M2 M3 M4 M5
A 2 9 2 7 1
 B 6 4 M 3 7
C 4 3 7 2 5
D 7 M 3 5 2
E 9 6 5 8 3
[Ans: M cells remain large throughout HAM. Optimal: A→M5 (1), B→M4 (3), C→M2 (3), D→M3 (3), E→M1
(9)... or check alternatives. Min cost = sum of assigned non-M cells.]

Q4 (Maximisation). Four advertising agencies (I–IV) are being evaluated for four product campaigns (A–
D). Expected revenue (₹ lakh):
Agency Campaign A Campaign B Campaign C Campaign D
I 14 5 8 7
II 2 12 6 5
III 7 8 3 9
IV 2 4 6 10
[Ans: Max value = 14. Opportunity loss matrix → HAM. Optimal: I→A, II→B, III→D, IV→C. Max revenue =
14+12+9+6 = ₹41 lakh.]

Q5. When will the Hungarian method require more than 2 iterations? Explain the geometric meaning of the
"minimum uncovered value" step — why does subtracting it from uncovered cells and adding it to
intersections create new zeros without losing existing ones?
[Ans: More iterations needed when, after row+column reduction, zeros are concentrated in few
rows/columns so many lines are shared. The minimum uncovered value k: subtracting k from uncovered
cells creates new zeros (since the uncovered min becomes 0). Adding k to intersection cells compensates
so those cells do not go negative. Covered-but-not-intersected cells remain unchanged — their zero status
is preserved. Each iteration increases the number of zeros in uncovered positions → lines needed to cover
all zeros increases → convergence to n lines.]

Q6. In a 4×4 assignment problem, after row and column reductions you get the following reduced cost
table. Find the optimal assignment:
J1 J2 J3 J4
W1 0 1 2 3
W2 1 0 3 2
W3 2 3 0 1
W4 3 2 1 0
[Ans: Zeros at (W1,J1), (W2,J2), (W3,J3), (W4,J4). 4 lines cover all zeros. Optimal: W1→J1, W2→J2,
W3→J3, W4→J4. Cost from original matrix = sum of diagonal elements.]

Q7. What is the key difference between the assignment problem and the transportation problem? Why is
the assignment problem said to be "highly degenerate" when solved as a transportation problem?
[Ans: In TP, supply/demand can be any positive integer; in AP, supply = demand = 1 for all rows/columns.
A balanced n×n AP needs m+n−1 = 2n−1 basic cells in a BFS, but since each source ships exactly 1 unit
to exactly 1 destination, only n cells are occupied — we always have a deficit of n−1, requiring n−1 epsilon
allocations. This extreme degeneracy makes MODI slow and prone to cycling. HAM avoids this entirely by
working directly on the cost matrix.]
6.6 Quick Reference — Key Rules

Situation What to do
Minimisation Apply HAM directly
Maximisation Opportunity loss = max value − each cell; then HAM
Unbalanced (more workers) Add dummy jobs (columns) with zero costs
Unbalanced (more jobs) Add dummy workers (rows) with zero costs
Prohibited assignment Set cell cost = M (very large); HAM avoids it
Lines < n after covering Subtract min uncovered k; add k at intersections; repeat
Multiple zeros in final table Multiple optimal solutions — all give same total cost
Assignment step — tie Try each; pick any complete feasible one-to-one assignment
Check solution Verify: exactly 1 assignment per row, 1 per column, all
assignments at zero cells