Here’s an in-depth explanation of each step in the Hungarian Method for solving the

Assignment Problem (AP):

1. Row Reduction
 Definition: The first step in the Hungarian Method is row reduction,
which involves subtracting the smallest element from every element in
each row. This creates at least one zero in each row.

 Purpose: The row reduction normalizes the matrix, laying the

foundation for minimizing the total assignment cost by ensuring that
each row has at least one zero. The goal is to reduce the original cost
matrix without changing the structure of the problem, as the total cost
remains proportionally the same.

 Process:

a. Find the smallest element in each row.

b. Subtract this element from all elements in that row.
 Example: Let’s start with the following cost matrix:

Worker/Job Job 1 Job 2 Job 3 Job 4

Worker 1 9 2 7 8
Worker 2 6 4 3 7
Worker 3 5 8 1 8
Worker 4 7 6 9 4
o Worker 1: Smallest element is 2. Subtract 2 from each element in the row:
[9 , 2, 7 , 8] becomes [7 , 0 ,5 , 6].
o Worker 2: Smallest element is 3. Subtract 3 from each element in the row:
[6 , 4 , 3 , 7] becomes [3 ,1 , 0 , 4 ].
o Worker 3: Smallest element is 1. Subtract 1 from each element in the row:
[5 ,8 , 1 , 8] becomes [4 , 7 , 0 , 7].
o Worker 4: Smallest element is 4. Subtract 4 from each element in the row:
[7 , 6 , 9 , 4] becomes [3 ,2 , 5 , 0].
Resulting matrix after row reduction:

Worker/Job Job 1 Job 2 Job 3 Job 4

Worker 1 7 0 5 6
Worker 2 3 1 0 4
Worker 3 4 7 0 7
Worker 4 3 2 5 0
2. Column Reduction
 Definition: The next step is column reduction, where the smallest
element in each column is subtracted from every element in that
column. This creates at least one zero in each column, making the
matrix easier to work with.

 Purpose: This step ensures that, in addition to rows having zero

values, each column also has at least one zero. Column reduction
further normalizes the matrix and prepares it for making assignments
based on the zeros.

 Process:

a. Find the smallest element in each column.

b. Subtract this element from all elements in that column.
 Example: Using the row-reduced matrix from Step 1:

Worker/Job Job 1 Job 2 Job 3 Job 4

Worker 1 7 0 5 6
Worker 2 3 1 0 4
Worker 3 4 7 0 7
Worker 4 3 2 5 0
o Column 1: Smallest element is 3. Subtract 3 from each element in the column:
[7 ,3 , 4 , 3] becomes [4 , 0 , 1 , 0].
o Column 2: Smallest element is 0. No change is needed.
o Column 3: Smallest element is 0. No change is needed.
o Column 4: Smallest element is 0. No change is needed.
Resulting matrix after column reduction:

Worker/Job Job 1 Job 2 Job 3 Job 4

Worker 1 4 0 5 6
Worker 2 0 1 0 4
Worker 3 1 7 0 7
Worker 4 0 2 5 0

3. Cover All Zeros with Minimum Number of Lines

 Definition: In this step, we cover all the zeros in the matrix using the
fewest number of horizontal and vertical lines. If the number of lines
equals the size of the matrix (i.e., n for an n × n matrix), then an optimal
solution can be made. If fewer lines are required, we move to the next
step.
  Purpose: The goal is to determine whether the current matrix
contains enough zeros to assign workers to jobs without further
modifications. If the number of lines equals n , we can directly make the
optimal assignment.

 Process:

a. Identify rows and columns containing zeros.

b. Use the smallest number of horizontal or vertical lines to cover all the zeros.
c. If the number of lines equals n, proceed to make assignments. Otherwise, proceed
to Step 4.
 Example: In the matrix:

Worker/Job Job 1 Job 2 Job 3 Job 4

Worker 1 4 0 5 6
Worker 2 0 1 0 4
Worker 3 1 7 0 7
Worker 4 0 2 5 0
The minimum number of lines to cover all zeros is 3 (covering columns
1, 2, and 3). Since this is less than n=4 , we proceed to Step 4.

4. Adjust the Matrix

 Definition: If the number of covering lines is less than n , the matrix is
adjusted. This is done by subtracting the smallest uncovered element
from all uncovered elements and adding it to elements at the
intersection of the lines.

 Purpose: This step creates more zeros in the matrix by adjusting the
remaining elements. The adjustment refines the matrix, helping to
bring it closer to an optimal state where assignments can be made.

 Process:

a. Identify the smallest uncovered element in the matrix.

b. Subtract this element from all uncovered elements.
c. Add this element to all elements that lie at the intersection of the lines.
d. The covered elements remain unchanged.
 Example: In the matrix, the smallest uncovered element is 1. Subtract
1 from all uncovered elements and add 1 to elements at the
intersection of the lines:

Worker/Job Job 1 Job 2 Job 3 Job 4

Worker 1 3 0 4 5
 Worker/Job Job 1 Job 2 Job 3 Job 4
Worker 2 0 1 0 3
Worker 3 0 6 0 6
Worker 4 0 2 4 0

5. Make Optimal Assignments

 Definition: Once the number of covering lines equals n , assignments
can be made based on the zeros in the matrix. The assignment is done
so that each row and each column contains exactly one assigned zero.

 Purpose: This step concludes the process by making the final

assignments, which minimize the total cost or maximize the total
profit, depending on the problem.
 Process:

a. Identify the zeros in the matrix.

b. Make assignments by selecting zeros such that each row and each column has
exactly one assignment.
c. Once the assignments are made, calculate the
total cost or profit based on the original cost matrix.
 Example: After adjusting the matrix, we can assign workers to jobs
based on the zeros:

o Worker 1 → Job 2
o Worker 2 → Job 1
o Worker 3 → Job 3
o Worker 4 → Job 4
The total minimized cost is obtained from the original cost matrix:
2+6+1+ 4=13

Detailed Insights on the Hungarian Method

1. Optimality: The Hungarian Method guarantees an optimal solution to
the assignment problem, meaning the total cost is minimized or the
total profit is maximized.

2. Efficiency: The method is highly efficient and can solve large

assignment problems in polynomial time. It is particularly suited for
balanced assignment problems where the number of jobs equals the
number of agents.
 3. Applicability: The method is flexible and can handle both
minimization and maximization problems. It can also be applied to
unbalanced problems by adding dummy rows or columns to balance
the cost matrix.

Summary
The Hungarian Method is an algorithm for solving the assignment problem by transforming the
cost matrix through row and column reductions, adjusting the matrix, and making assignments
based on the resulting zero-cost cells. The process ensures an optimal assignment with
minimized costs. It is efficient and widely used in operations research for handling resource
allocation problems.

Questions
1. Why is it necessary to adjust the matrix when fewer than n lines cover the zeros in the
Hungarian Method?
2. How does the Hungarian Method ensure that the solution to the assignment problem is
optimal?

References:
 Quantitative Techniques in Management, 4th Edition by N.D. Vohra, Chapter
6【8:3†source】【8:5†source】【8:10†source】.