Solutions — Assignment Problems and the Hungarian Algorithm

Fluency Row reduction of cost matrix (Q1).

Row minima: Row 1 = 3, Row 2 = 2, Row 3 = 1
After subtracting each row minimum:

	X	Y	Z
1	2	0	6
2	2	6	0
3	6	0	5

Fluency After row and column reduction, zeros at (1,X), (2,Z), (3,Y). Is assignment complete?

Three zeros, all in different rows and different columns → yes, this is an optimal assignment.

Assignment: Worker 1 → Task X, Worker 2 → Task Z, Worker 3 → Task Y
Costs from original matrix: 1→X=5, 2→Z=2, 3→Y=1
Minimum total cost = 5+2+1 = 8

Fluency Purpose of the adjustment step.

The adjustment step (subtracting θ from uncovered cells, adding θ to doubly-covered cells) creates new zeros in positions that were previously uncovered, without destroying existing zeros in covered positions.

The goal is to obtain enough independent zeros (n zeros, one per row and column) to make a complete optimal assignment. When fewer than n lines are needed to cover all zeros, the current zero pattern cannot support a full assignment — the adjustment step introduces additional zeros and shifts the opportunity for a new, complete assignment.

Fluency 3×3 matrix reduced; 2 lines cover all zeros. What to do next?

Lines = 2 < n = 3. This tells us no complete optimal assignment exists yet (there are not enough independent zeros for a 3-worker, 3-task assignment).

Apply the adjustment step: find the minimum value among all cells NOT covered by the 2 lines (θ). Subtract θ from every uncovered cell. Add θ to every cell covered by two lines. Then repeat Step 3 (cover zeros again).

Understanding Hungarian algorithm: P(9,2,7), Q(3,6,4), R(5,8,1).

Step 1 — Row reduction (mins: P=2, Q=3, R=1):
P: [7,0,5] Q: [0,3,1] R: [4,7,0]

Step 2 — Column reduction (col mins: A=0, B=0, C=0; no change needed):
P: [7,0,5] Q: [0,3,1] R: [4,7,0]

Step 3 — Cover zeros: zeros at (P,B), (Q,A), (R,C).
These are 3 independent zeros → 1 line per zero → 3 lines = n. Done.

Optimal assignment: P→B, Q→A, R→C
Costs from original: P→B=2, Q→A=3, R→C=1
Minimum cost = 2+3+1 = 6

Understanding 4×4 assignment: W(8,4,6,3), X(5,7,2,8), Y(3,6,9,4), Z(7,2,5,6).

Row reduction (mins: W=3, X=2, Y=3, Z=2):
W:[5,1,3,0] X:[3,5,0,6] Y:[0,3,6,1] Z:[5,0,3,4]

Column reduction (col mins all 0; no change):
Same matrix as above.

Zeros: (W,4), (X,3), (Y,1), (Z,2) → 4 independent zeros. Done.

Optimal assignment: W→Task 4, X→Task 3, Y→Task 1, Z→Task 2
Costs: W→4=3, X→3=2, Y→1=3, Z→2=2
Minimum total cost = 3+2+3+2 = 10

Understanding Maximisation: profits A(10,6,8), B(4,9,5), C(7,3,11). Maximum = 11.

Convert to minimisation: subtract each value from max (11):
A:[1,5,3] B:[7,2,6] C:[4,8,0]

Row reduction (mins: A=1, B=2, C=0):
A:[0,4,2] B:[5,0,4] C:[4,8,0]

Column reduction (mins all 0; no change).

Zeros: (A,J1), (B,J2), (C,J3) → 3 independent zeros. Done.

Optimal assignment: A→J1, B→J2, C→J3
From original profit matrix: A→J1=10, B→J2=9, C→J3=11
Maximum profit = 10+9+11 = 30

Understanding 4×4 matrix; 3 lines; θ=2. Show adjustment step effect.

With 3 lines covering all zeros (n=4, so we need 4 lines), the adjustment step applies:

Effect of θ=2:
• Uncovered cells: subtract 2 from each → some may become 0 (new zeros created)
• Cells covered by 2 lines (at intersections): add 2 → no new zeros, but values increase
• Cells covered by 1 line: unchanged

Outcome: new zeros appear in previously uncovered positions; existing zeros in singly-covered lines remain. The new zero pattern may now support 4 independent zeros, allowing the algorithm to terminate with an optimal assignment on the next iteration.

Problem Solving Maximise donations: A(15,9,12), B(8,13,10), C(11,7,14). Max=15.

Convert to minimisation (subtract from 15):
A:[0,6,3] B:[7,2,5] C:[4,8,1]

Row reduction (mins: A=0, B=2, C=1):
A:[0,6,3] B:[5,0,3] C:[3,7,0]

Column reduction (col mins: X=0, Y=0, Z=0; no change).

Zeros: (A,X), (B,Y), (C,Z) → 3 independent zeros. Done.

Optimal assignment: A→X, B→Y, C→Z
Donations: A→X=$1500, B→Y=$1300, C→Z=$1400
Maximum total donations = $1500+$1300+$1400 = $4200

Problem Solving Transport company: 4 drivers to 4 routes. Minimise total hours.

Row reduction (mins: 1=8, 2=6, 3=5, 4=6):
1:[2,6,0,4] 2:[0,3,5,1] 3:[8,2,0,4] 4:[2,5,7,0]

Column reduction (col mins: A=0, B=2, C=0, D=0):
Subtract 2 from column B:
1:[2,4,0,4] 2:[0,1,5,1] 3:[8,0,0,4] 4:[2,3,7,0]

Zeros: (1,C), (2,A), (3,B), (3,C), (4,D)
Independent zeros: 1→C, 2→A, 3→B, 4→D → 4 independent zeros. Done.

Optimal assignment: Driver 1→Route C, Driver 2→Route A, Driver 3→Route B, Driver 4→Route D
Times: 1→C=8, 2→A=6, 3→B=7, 4→D=6
Minimum total time = 8+6+7+6 = 27 hours