Published by: Dikshya
Published date: 25 Jul 2023
The Assignment Model, also known as the Assignment Problem, is a mathematical optimization problem that deals with finding the optimal assignment of a set tasks to an equal number of resources, where each task can be assigned to only one resource and vice versa. The objective is to minimize the total cost ormaximize the total profit associated with the assignments.
The Hungarian Method is an algorithm used to solve the Assignment Problem efficiently. It was developed by Hrold Kuhn in 1955 and later refined by James Munkres in 1957, hence sometimes referred to as the Kuhn-Munkres algorithm. The Hungarian Method is based on the principle of finding agumenting paths ina cost matrix, ultimately leading to the optimal assignment.
Steps to find the optimum solution using Hungarian Method:
Step 1: Formulate the Cost Matrix
- Start by creating a square matrix, where the number of rows and columns are equal to the number of tasks and resources, respectively.
- In the cost matrix, each element represents the cost or profit associated with assigning a particular task to a specific resource. Ensure that the matrix is properly set up with appropriate values.
Step 2: Reduce the Matrix
- In this step, reduce the matrix to a more manageable size by performing row and column operations.
- First, subtract the minimum value of each row from all the elements in that row.
- Next, subtract the minimum value of each column from all the elements in that column.
- These operations aim to create at least one zero in each row and each column.
Step 3: Cover Zeroes with Minimum Number of Lines
- Draw lines (horizontal and vertical) to cover all the zeros in the matrix. The objective is to cover all the zeros with the minimum possible number of lines.
- If the number of lines equals the number of rows (or columns), proceed to Step 5.
- If not, go to Step 4.
Step 4: Modify Matrix and Repeat Step 3
- Find the smallest uncovered element in the matrix (i.e., an element that is not covered by any line).
- Subtract this smallest element from all uncovered elements.
- Add this smallest element to all elements that are covered by two lines (intersection of a row and a column covered by lines).
- Repeat Step 3 and Step 4 until the number of lines equals the number of rows (or columns).
Step 5: Find the Optimal Assignment
- At this point, you have a matrix with the same number of lines as the number of rows (or columns).
- Each row will have exactly one zero. These zeros represent the optimal assignments.
- If there is only one zero in each row, the solution is unique.
- If there are multiple zeros in any row, you can select any one of them without affecting the optimality of the solution.
Step 6: Interpret the Results
- Once you have the optimal assignment, interpret the results accordingly. If it is a cost matrix, the optimal assignment represents the tasks and resources that minimize the total cost.
- If it is a profit matrix, the optimal assignment represents the tasks and resources that maximize the total profit.
The Hungarian Method guarantees an optimal solution for the Assignment Problem in polynomial time, making it an efficient approach to solve this type of optimization problem. It is widely used in various applications, such as job assignment, transportation planning, and resource allocation.