Hungarian Method for Solving the Assignment Problem

The Hungarian Method is an efficient algorithm used to solve the assignment problem, where the goal is to assign tasks to agents in a way that minimizes the total cost or maximizes the total profit. The algorithm ensures that each task is assigned to exactly one agent, and each agent is assigned to exactly one task.

Steps for the Hungarian Method

1. Create the Cost Matrix

2. Start with a matrix where rows represent agents and columns represent tasks. Each element in the matrix represents the cost of assigning a particular agent to a particular task.

3. Row Reduction

4. Subtract the smallest element in each row from every element in that row. This step ensures that each row contains at least one zero.

5. Column Reduction

6. After the row reduction, subtract the smallest element in each column from every element in that column. This step ensures that each column contains at least one zero.

7. Cover All Zeros with a Minimum Number of Lines

8. Cover all the zeros in the matrix using the minimum number of horizontal and vertical lines. The goal is to use as few lines as possible.

9. Check for Optimality

10. If the minimum number of covering lines equals the number of rows (or columns) in the matrix, an optimal assignment can be made using the covered zeros. If not, proceed to the next step.

11. Adjust the Matrix

12. Find the smallest uncovered element in the matrix (i.e., not covered by any line). Subtract this smallest value from all uncovered elements and add it to the elements that are covered by both a horizontal and vertical line. The matrix is then adjusted, and steps 4 and 5 are repeated.

13. Make the Optimal Assignment

14. Once the minimum number of lines used to cover all zeros equals the number of rows or columns, find the optimal assignment by selecting zeros in such a way that no two selected zeros are in the same row or column.

Example of the Hungarian Method

Suppose we have three workers (A, B, and C) and three tasks (1, 2, and 3), and the cost matrix is given as:

	Task 1	Task 2	Task 3
Worker A	8	15	13
Worker B	10	12	18
Worker C	14	8	11

Step 1: Row Reduction

Subtract the smallest element in each row from all elements of that row.

• Row 1: 8, 15, 13 → Minimum is 8 → 0, 7, 5
• Row 2: 10, 12, 18 → Minimum is 10 → 0, 2, 8
• Row 3: 14, 8, 11 → Minimum is 8 → 6, 0, 3

The resulting matrix after row reduction is:

	Task 1	Task 2	Task 3
Worker A	0	7	5
Worker B	0	2	8
Worker C	6	0	3

Step 2: Column Reduction

Subtract the smallest element in each column from all elements of that column.

• Column 1: 0, 0, 6 → Minimum is 0 → 0, 0, 6
• Column 2: 7, 2, 0 → Minimum is 0 → 7, 2, 0
• Column 3: 5, 8, 3 → Minimum is 3 → 2, 5, 0

The resulting matrix after column reduction is:

	Task 1	Task 2	Task 3
Worker A	0	7	2
Worker B	0	2	5
Worker C	6	0	0

Step 3: Cover All Zeros with the Minimum Number of Lines

• Cover the zeros using the minimum number of horizontal and vertical lines. In this matrix, we can cover all zeros using three lines.

Step 4: Check for Optimality

• Since the number of lines used (3) equals the number of rows, an optimal assignment can be made.

Step 5: Make the Optimal Assignment

Select zeros such that no two selected zeros are in the same row or column.

• Assign Worker A to Task 1 (0).
• Assign Worker B to Task 2 (2).
• Assign Worker C to Task 3 (0).

The optimal assignment is:

• Worker A → Task 1
• Worker B → Task 2
• Worker C → Task 3

Summary

The Hungarian Method is an efficient algorithm for solving the assignment problem. It guarantees finding the optimal solution by systematically reducing the matrix and using a series of steps to ensure an optimal assignment. It is widely used in job scheduling, resource allocation, and various optimization problems in business and industry.

Hive Chat

Hi, I'm Hive Chat, an AI assistant created by CollegeHive.
How can I help you today?

Give a simple example for this Explain it in simple terms

🎶