Hungarian Method

The Hungarian method is a computational optimization technique that addresses the

assignment problem in polynomial time and foreshadows following primal-dual alternatives.
In 1955, Harold Kuhn used the term “Hungarian method” to honour two Hungarian
mathematicians, Dénes Kőnig and Jenő Egerváry. Let’s go through the steps of the Hungarian
method with the help of a solved example.

Hungarian Method to Solve Assignment Problems

The Hungarian method is a simple way to solve assignment problems. Let us first discuss the
assignment problems before moving on to learning the Hungarian method.

What is an Assignment Problem?

A transportation problem is a type of assignment problem. The goal is to allocate an equal

amount of resources to the same number of activities. As a result, the overall cost of allocation
is minimized or the total profit is maximized. (https://byjus.com/maths/profit/)

Because available resources such as workers, machines, and other resources have varying
degrees of efficiency for executing different activities, and hence the cost, profit, or loss of
conducting such activities varies.

Assume we have ‘n’ jobs to do on ‘m’ machines (i.e., one job to one machine). Our goal is to
assign jobs to machines for the least amount of money possible (or maximum profit). Based on
the notion that each machine can accomplish each task, but at variable levels of efficiency.

Hungarian Method Steps

Check to see if the number of rows and columns are equal; if they are, the assignment problem
is considered to be balanced. Then go to step 1. If it is not balanced, it should be balanced
before the algorithm is applied.

Step 1 – In the given cost matrix, subtract the least cost element of each row from all the entries
in that row. Make sure that each row has at least one zero.

Step 2 – In the resultant cost matrix produced in step 1, subtract the least cost element in each
column from all the components in that column, ensuring that each column contains at least
one zero.

Step 3 – Assign zeros

 Analyze the rows one by one until you find a row with precisely one unmarked zero.
Encircle this lonely unmarked zero and assign it a task. All other zeros in the column
of this circular zero should be crossed out because they will not be used in any future
assignments. Continue in this manner until you’ve gone through all of the rows.

 Examine the columns one by one until you find one with precisely one unmarked zero.
Encircle this single unmarked zero and cross any other zero in its row to make an
assignment to it. Continue until you’ve gone through all of the columns.
Step 4 – Perform the Optimal Test
 The present assignment is optimal if each row and column has exactly one encircled
zero.
 The present assignment is not optimal if at least one row or column is missing an
assignment (i.e., if at least one row or column is missing one encircled zero). Continue
to step 5. Subtract the least cost element from all the entries in each column of the final
cost matrix created in step 1 and ensure that each column has at least one zero.

Step 5 – Draw the least number of straight lines to cover all of the zeros as follows:

(a) Highlight the rows that aren’t assigned.

(b) Label the columns with zeros in marked rows (if they haven’t already been marked).
(c) Highlight the rows that have assignments in indicated columns (if they haven’t
previously been marked).
(d) Continue with (b) and (c) until no further marking is needed.
(e) Simply draw the lines through all rows and columns that are not marked. If the number
of these lines equals the order of the matrix, then the solution is optimal; otherwise, it is not.

Step 6 – Find the lowest cost factor that is not covered by the straight lines. Subtract this least-
cost component from all the uncovered elements and add it to all the elements that are at the
intersection of these straight lines, but leave the rest of the elements alone.

Step 7 – Continue with steps 1 – 6 until you’ve found the highest suitable assignment.

Hungarian Method Example

Example:

Use the Hungarian method to solve the given assignment problem stated in the table. The
entries in the matrix represent each man’s processing time in hours.

20 15 18 20 25
18 20 12 14 15
21 23 25 27 25
17 18 21 23 20
[18 18 16 19 20]

Solution
With 5 jobs and 5 men/machines, the stated problem is balanced

20 15 18 20 25
18 20 12 14 15
𝐴 = 21 23 25 27 25
17 18 21 23 20
[18 18 16 19 20]
Subtract the lowest cost element in each row from all of the elements in the given cost
matrix’s row. Make sure that each row has at least one zero.

5 0 3 5 10
6 8 0 2 3
𝐴= 0 2 4 6 4
0 1 4 6 3
[2 2 0 3 4]

Subtract the least cost element in each column from all of the components in the given cost
matrix’s row. Make sure that each column has at least one zero.

5 0 3 3 7
6 8 0 0 0
𝐴= 0 2 4 4 1
0 1 4 4 0
[2 2 0 1 1]

When the zeros are assigned, we get the following:

The present assignment is OPTIMAL because each row and column contain precisely on
encircled zero.

Where, R1 to C2, R2 to C4, R3 to C1, R4 to C5 and R5 to C3.

Hence, 𝑍 = 15 + 14 + 21 + 20 + 16 = 86 hours in the optimal time.

Exercise

Use the Hungarian method to solve the following assignment problem shown in table. The
matrix entries represent the time it takes for each job to be processed by each machine in hours.

9 22 58 11 19
43 78 72 50 63
𝐵 = 41 28 91 37 45
74 42 27 49 39
[36 11 57 22 25]