Hungarian method of assignment problem

14/03/2023 0 By indiafreenotes

The Hungarian method is a popular algorithm used to solve assignment problems, which involve assigning a set of agents to a set of tasks with given costs, such that each agent is assigned to exactly one task and each task is assigned to exactly one agent, while minimizing the total cost of the assignments.

The Hungarian method involves the following steps:

Create a cost matrix: Create an n x n matrix representing the costs of assigning each agent to each task, where n is the number of agents and tasks.
Subtract the smallest cost in each row from all the costs in that row, and subtract the smallest cost in each column from all the costs in that column.
Draw the minimum number of horizontal or vertical lines to cover all the zeros in the matrix. If the number of lines equals n, then an optimal assignment has been found. If not, proceed to step 4.
Determine the smallest uncovered element in the matrix, and subtract it from all uncovered elements. Then, add it to all elements at the intersection of two lines.
Repeat steps 3 and 4 until an optimal assignment has been found.
Assign the agents to the tasks based on the lines. If an agent is assigned to a task covered by a vertical line, or a task is assigned to an agent covered by a horizontal line, the assignment is optimal.
If there are any unassigned agents or tasks, return to step 2 and continue until all agents and tasks are assigned.

Here is an example of the Hungarian method in action:

Suppose we have the following cost matrix representing the costs of assigning three agents to three tasks:

	T1	T2	T3
A1	10	3	8
A2	9	7	5
A3	1	6	8

Step 1: Create a cost matrix.

Step 2: Subtract the smallest cost in each row from all the costs in that row, and subtract the smallest cost in each column from all the costs in that column.

	T1	T2	T3
A1	7	0	5
A2	4	2	0
A3	0	5	7

Step 3: Draw the minimum number of horizontal or vertical lines to cover all the zeros in the matrix. In this case, we can cover all the zeros with two horizontal lines (through rows A2 and A3).

	T1	T2	T3
A1	7	0	5
A2	4	2	0
A3	0	5	7

Step 4: Determine the smallest uncovered element in the matrix, which is 2. Subtract it from all uncovered elements, and add it to all elements at the intersection of two lines.

	T1	T2	T3
A1	5	0	3
A2	2	0	0
A3	0	3	5

Step 5: Repeat steps 3 and 4 until an optimal assignment has been found.

We can cover all the zeros in the matrix with two horizontal lines, but we still need to cover one more cell to have a complete assignment.
The uncovered cell with the smallest value is (A2, T2) with a cost of 0.
We can draw a vertical line through column T2 to cover cell (A2, T2).

	T1	T2	T3
A1	5	0	3
A2	2	0	0
A3	0	3	5

Now we can cover all the zeros in the matrix with two lines. The covered cells correspond to an optimal assignment:

	T1	T2	T3
A1	5		3
A2		0
A3	0	3	5

The optimal assignment is:
- Agent 1 is assigned to Task 2 with a cost of 0.
- Agent 2 is assigned to Task 1 with a cost of 2.
- Agent 3 is assigned to Task 3 with a cost of 5.