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.
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.
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 minimised or the total profit is maximised.
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.
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
Step 4 – Perform the Optimal Test
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.
(f) 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.
Also, read:
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.
\(\begin
Solution:
With 5 jobs and 5 men, the stated problem is balanced.
\(\begin
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.
\(\begin
Subtract the least cost element in each Column from all of the components in the given cost matrix’s Column. Check to see if each column has at least one zero.
\(\begin
When the zeros are assigned, we get the following:
The present assignment is optimal because each row and column contain precisely one encircled zero.
Where 1 to II, 2 to IV, 3 to I, 4 to V, and 5 to III are the best assignments.
Hence, z = 15 + 14 + 21 + 20 + 16 = 86 hours is the optimal time.
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.
\(\begin
Stay tuned to BYJU’S – The Learning App and download the app to explore all Maths-related topics.
The Hungarian method is defined as a combinatorial optimization technique that solves the assignment problems in polynomial time and foreshadowed subsequent primal–dual approaches.
The following is a quick overview of the Hungarian method:
Step 1: Subtract the row minima.
Step 2: Subtract the column minimums.
Step 3: Use a limited number of lines to cover all zeros.
Step 4: Add some more zeros to the equation.
When workers are assigned to certain activities based on cost, the Hungarian method is beneficial for identifying minimum costs.
