The Hungarian method is a simple and effective way to solve the assignment problem. It helps match tasks to people (or jobs to workers) in the best possible way so that the total cost or time is the lowest. This method was named by Harold Kuhn in 1955 to honor Hungarian mathematicians Dénes Kőnig and Jenő Egerváry. It works step-by-step and uses basic math rules to find the best match. The Hungarian method is used in many areas like job assignments, project planning, and scheduling. It is fast and works in a reasonable amount of time for large problems.

Understanding the Hungarian Method for Assignment Problems

The Hungarian method is a smart way to solve assignment problems quickly. But before using it, let’s first understand what an assignment problem means.

Defining an Assignment Problem

An assignment problem is a special type of problem where we try to give tasks to people or machines in the best possible way. The goal is to reduce the total cost or increase the total profit while making the assignments. Each worker or machine may take more or less time or money to do a task, depending on how well they can do it. Because of this difference in efficiency, it becomes tricky to decide who should do what.

For example, suppose you have 5 tasks and 5 workers. Each worker can do each task, but they may take different amounts of time or cost different amounts. The idea is to assign one task to each worker so that the total time or cost is the least (or the total benefit is the most). This kind of problem is called an assignment problem, and it's solved using methods like the Hungarian Method to find the best solution.

Steps For Hungarian Method

1. Create the Cost Table

Make a table (matrix) where:

• Rows = agents (like workers)
• Columns = tasks (like jobs)

        Each number in the table shows the cost of assigning a worker to a job.

2. Row Reduction

For each row:

• Find the smallest number in that row.
• Subtract it from every number in the same row.

       This step makes sure every row has at least one zero.

3. Column Reduction

Now do the same for columns:

• Find the smallest number in each column.
• Subtract it from all numbers in that column.
  Now, each column will also have at least one zero.

4. Cover All Zeros

• Use the least number of horizontal and vertical lines to cover all the zeros in the table.
• Try to use as few lines as possible.

5. Check if You Can Make Assignments

• Count the lines you used.
• If the number of lines is equal to the number of rows or columns, you can make an optimal assignment now.
• If not, move to the next step.

6. Adjust the Table

• Find the smallest number that is not covered by any line.
• Subtract this number from all uncovered values.
• Add the same number to the values at the points where two lines cross.
• Now repeat Step 4 and Step 5.

7. Make the Final Assignment

• Once the number of lines = number of rows (or columns), it’s time to make assignments.
• Choose the zeros in a way that no two selected zeros are in the same row or column.
• These selected zeros show the best way to assign tasks at the lowest total cost.

Also, read:

• Linear Programming
• Linear Programming Problems
• Profit and Loss

Example: Let's apply the Hungarian method to solve an assignment problem. The matrix below represents the time taken by each worker to complete a task in hours.

\(\begin{array}{l}\begin{bmatrix} & I & II & III & IV & V \\1 & 20 & 15 & 18 & 20 & 25 \\2 & 18 & 20 & 12 & 14 & 15 \\3 & 21 & 23 & 25 & 27 & 25 \\4 & 17 & 18 & 21 & 23 & 20 \\5 & 18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

Solution: Since there are 5 tasks and 5 workers, the problem is balanced.

\(\begin{array}{l}A = \begin{bmatrix}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 \\\end{bmatrix}\end{array} \)

Now, subtract the smallest element in each row from all the elements in that row of the given cost matrix. Ensure that each row has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}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 \\\end{bmatrix}\end{array} \)

Next, subtract the smallest element in each column from all the elements in that column of the given cost matrix. Ensure that each column has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}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 \\\end{bmatrix}\end{array} \)

After assigning the zeros, we get the following:

Since each row and column contain exactly one circled zero, the current assignment is optimal.

The best assignments are 1 to II, 2 to IV, 3 to I, 4 to V, and 5 to III.

Hence, the optimal time is z = 15 + 14 + 21 + 20 + 16 = 86 hours.