write hungarian assignment algorithm

Index     Assignment problem     Hungarian algorithm     Solve online    

The Hungarian algorithm

The Hungarian algorithm consists of the four steps below. The first two steps are executed once, while Steps 3 and 4 are repeated until an optimal assignment is found. The input of the algorithm is an n by n square matrix with only nonnegative elements.

Step 1: Subtract row minima

For each row, find the lowest element and subtract it from each element in that row.

Step 2: Subtract column minima

Similarly, for each column, find the lowest element and subtract it from each element in that column.

Step 3: Cover all zeros with a minimum number of lines

Cover all zeros in the resulting matrix using a minimum number of horizontal and vertical lines. If n lines are required, an optimal assignment exists among the zeros. The algorithm stops.

If less than n lines are required, continue with Step 4.

Step 4: Create additional zeros

Find the smallest element (call it k ) that is not covered by a line in Step 3. Subtract k from all uncovered elements, and add k to all elements that are covered twice.

Continue with:

The Hungarian algorithm explained based on an example.

The Hungarian algorithm explained based on a self chosen or on a random cost matrix.

HungarianAlgorithm.com © 2013-2023

HungarianAlgorithm.com uses cookies to provide you with an optimal user experience.

Yes, I accept cookies.

• DSA for Beginners
• DSA Tutorial
• Data Structures
• Linked List
• Dynamic Programming
• Binary Tree
• Binary Search Tree
• Divide & Conquer
• Mathematical
• Backtracking
• Branch and Bound
• Pattern Searching

• Explore Our Geeks Community
• Hungarian Algorithm for Assignment Problem | Set 2 (Implementation)
• Clustering Coefficient in Graph Theory
• Erdos Renyl Model (for generating Random Graphs)
• Count of nodes with maximum connection in an undirected graph
• Types of Graphs with Examples
• Maximum number of edges in Bipartite graph
• Program to find the number of region in Planar Graph
• Number of Simple Graph with N Vertices and M Edges
• Count of Disjoint Groups by grouping points that are at most K distance apart
• Convert the undirected graph into directed graph such that there is no path of length greater than 1
• Maximize count of nodes disconnected from all other nodes in a Graph
• Cost of painting n * m grid
• Find node having maximum number of common nodes with a given node K
• Ways to Remove Edges from a Complete Graph to make Odd Edges
• Find the sum of the first Nth Centered Pentadecagonal Number
• Check if incoming edges in a vertex of directed graph is equal to vertex itself or not
• Find the sum of the first Nth Centered Hexadecagonal Number
• Horner's Method for Polynomial Evaluation
• Check whether the structure of given Graph is same as the game of Rock-Paper-Scissor

Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)

• For each row of the matrix, find the smallest element and subtract it from every element in its row.
• Do the same (as step 1) for all columns.
• Cover all zeros in the matrix using minimum number of horizontal and vertical lines.
• Test for Optimality: If the minimum number of covering lines is n, an optimal assignment is possible and we are finished. Else if lines are lesser than n, we haven’t found the optimal assignment, and must proceed to step 5.
• Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Try it before moving to see the solution

Explanation for above simple example:

  An example that doesn’t lead to optimal value in first attempt: In the above example, the first check for optimality did give us solution. What if we the number covering lines is less than n.

Time complexity : O(n^3), where n is the number of workers and jobs. This is because the algorithm implements the Hungarian algorithm, which is known to have a time complexity of O(n^3).

Space complexity :   O(n^2), where n is the number of workers and jobs. This is because the algorithm uses a 2D cost matrix of size n x n to store the costs of assigning each worker to a job, and additional arrays of size n to store the labels, matches, and auxiliary information needed for the algorithm.

In the next post, we will be discussing implementation of the above algorithm. The implementation requires more steps as we need to find minimum number of lines to cover all 0’s using a program. References: http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf https://www.youtube.com/watch?v=dQDZNHwuuOY Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

• DSA in Java
• DSA in Python
• DSA in JavaScript

Please Login to comment...

• Rohit_Goyal
• devendrasalunke
• surinderdawra388
• sagartomar9927
• spacetechbytes
• classroompxico
• esrinivasa7kps

Please write us at contrib[email protected] to report any issue with the above content

Improve your Coding Skills with Practice

Hungarian Method

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.

Hungarian Method to Solve Assignment Problems

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.

What is an Assignment Problem?

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.

Hungarian Method Steps

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

• Analyse the rows one by one until you find a row with precisely one unmarked zero. Encircle this lonely unmarked zero and assign it a task. All other zeros in the column of this circular zero should be crossed out because they will not be used in any future assignments. Continue in this manner until you’ve gone through all of the rows.
• Examine the columns one by one until you find one with precisely one unmarked zero. Encircle this single unmarked zero and cross any other zero in its row to make an assignment to it. Continue until you’ve gone through all of the columns.

Step 4 – Perform the Optimal Test

• The present assignment is optimal if each row and column has exactly one encircled zero.
• The present assignment is not optimal if at least one row or column is missing an assignment (i.e., if at least one row or column is missing one encircled zero). Continue to step 5. Subtract the least cost element from all the entries in each column of the final cost matrix created in step 1 and ensure that each column has at least one zero.

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.

Hungarian Method 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{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} \)

With 5 jobs and 5 men, the stated 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} \)

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{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} \)

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{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} \)

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.

Practice Question on Hungarian Method

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{array}{l}\begin{bmatrix}J/M & I & II & III & IV & V \\1 & 9 & 22 & 58 & 11 & 19 \\2 & 43 & 78 & 72 & 50 & 63 \\3 & 41 & 28 & 91 & 37 & 45 \\4 & 74 & 42 & 27 & 49 & 39 \\5 & 36 & 11 & 57 & 22 & 25 \\\end{bmatrix}\end{array} \)

Stay tuned to BYJU’S – The Learning App and download the app to explore all Maths-related topics.

Frequently Asked Questions on Hungarian Method

What is hungarian method.

The Hungarian method is defined as a combinatorial optimization technique that solves the assignment problems in polynomial time and foreshadowed subsequent primal–dual approaches.

What are the steps involved in Hungarian method?

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.

What is the purpose of the Hungarian method?

When workers are assigned to certain activities based on cost, the Hungarian method is beneficial for identifying minimum costs.

Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Request OTP on Voice Call

Post My Comment

• Share Share

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

2. Algorithm & Example-1

Hungarian algorithm: A step by step guide to assignment method

1. introduction to the hungarian algorithm, 2. understanding the assignment problem, 3. creating the cost matrix, 4. row reduction and column reduction, 5. assigning zeroes and covering lines, 6. finding the minimum number of lines, 7. adjusting the cost matrix, 8. repeating steps 3-7 until optimal assignment is achieved, 9. conclusion and applications of the hungarian algorithm.

The Hungarian Algorithm is a powerful method used to solve the assignment problem, which involves finding the optimal assignment of a set of tasks to a set of resources. This algorithm, also known as the Munkres Algorithm or the Kuhn-Munkres Algorithm, was developed by two mathematicians, Harold Kuhn and James Munkres, in the 1950s. It has since become widely used in various fields such as operations research, computer science, and economics.

From a high-level perspective, the Hungarian Algorithm works by iteratively finding a series of augmenting paths in a weighted bipartite graph. These paths are then used to update the current assignment until an optimal solution is reached. The algorithm guarantees that it will find the best possible assignment with the minimum total cost.

To better understand how the Hungarian Algorithm works, let's delve into its step-by-step process :

1. Constructing the Cost Matrix: The first step is to create a matrix that represents the costs associated with assigning each task to each resource. For example, consider a scenario where four tasks (A, B, C, D) need to be assigned to four resources (W, X, Y, Z). The cost matrix could look like this:

| W | X | Y | Z |

2. Initializing Assignments: Start by initializing an assignment matrix with zeros of the same size as the cost matrix. This matrix will keep track of which tasks are assigned to which resources.

3. Row Reduction: Perform row reduction on the cost matrix by subtracting the smallest element in each row from all other elements in that row. This step ensures that at least one zero is present in each row.

4. Column Reduction: Perform column reduction on the resulting matrix by subtracting the smallest element in each column from all other elements in that column. This step ensures

Introduction to the Hungarian Algorithm - Hungarian algorithm: A step by step guide to assignment method

The assignment problem is a fundamental problem in optimization and operations research. It involves assigning a set of tasks to a set of agents with the objective of minimizing the total cost or maximizing the total profit. Depending on the context, the agents can be workers, machines, or any other entities capable of performing the tasks. Similarly, the tasks can be jobs, projects, or any other activities that require the attention of the agents. The assignment problem arises in various applications, such as scheduling, logistics, resource allocation, and matching.

To solve the assignment problem, we need a method that can determine an optimal or near-optimal assignment. The Hungarian algorithm is a well-known method that can solve the assignment problem efficiently. It is based on the principle of duality and the concept of augmenting paths. The algorithm can handle both balanced and unbalanced assignment problems, and it can find a unique solution in polynomial time.

Here are some key insights about the assignment problem:

1. The assignment problem can be formulated as a linear programming problem, where the objective function and the constraints are linear. The linear programming formulation can be solved using various algorithms, such as the simplex method, the interior-point method, or the network simplex method. However, the Hungarian algorithm is preferred for its simplicity and efficiency.

2. The assignment problem can be represented as a bipartite graph, where the agents and the tasks are the two partitions of the graph. The edges of the graph are the costs or profits associated with each assignment. The Hungarian algorithm works by finding a maximum matching in the graph, which corresponds to an optimal assignment.

3. The Hungarian algorithm can be implemented using different variants, such as the matrix-based variant, the path-based variant, or the Hungarian-Ford-Fulkerson variant. Each variant has its advantages and disadvantages, depending on the size and sparsity of the input matrix.

4. The Hungarian algorithm can be extended to handle additional constraints, such as capacity constraints, precedence constraints, or multi-objective criteria. For example, if the agents have different capacities or skills, we can add capacity constraints to ensure that each agent is assigned to at most one task. If the tasks have different priorities or deadlines, we can add precedence constraints to ensure that some tasks are assigned before others. If the objective is to minimize both the cost and the time, we can use a multi-objective approach that balances the two criteria.

The assignment problem is a crucial problem in optimization and operations research, and the Hungarian algorithm is a powerful method that can solve it efficiently. By understanding the principles and insights of the assignment problem, we can apply the Hungarian algorithm to various applications and achieve optimal or near-optimal solutions.

Understanding the Assignment Problem - Hungarian algorithm: A step by step guide to assignment method

In the Hungarian algorithm, the first step is to create a cost matrix. This matrix represents the costs of assigning each worker to each task. The cost of assigning a worker to a task can be anything, but in most practical applications, the cost represents the efficiency or quality of the assignment. For example, if you are trying to assign workers to build a house, the cost of assigning a worker to a task might represent their skill level or experience in that particular task.

Creating the cost matrix is a crucial step in the Hungarian algorithm, as it forms the basis for the rest of the algorithm. There are a few different ways to create the cost matrix, depending on the specific problem you are trying to solve. Here are some methods that can be used to create the cost matrix:

1. Manual input: If you have a small number of workers and tasks, you can simply input the cost of assigning each worker to each task manually. For example, if you have 3 workers and 3 tasks, you could create a 3x3 matrix by inputting the costs like this:

| Task 1 | Task 2 | Task 3 |

2. Distance matrix: If you are trying to assign tasks to workers based on their proximity to the task location, you can create a distance matrix. This matrix represents the distance between each worker and task location. The cost of assigning a worker to a task can then be calculated based on the distance between the two points.

3. Machine learning: In some cases, it may be possible to use machine learning algorithms to create the cost matrix. For example, if you are trying to assign workers to sales leads, you could use a machine learning algorithm to predict the likelihood of each worker closing a particular sale. The cost of assigning a worker to a task could then be based on this prediction.

Overall, creating the cost matrix is a critical step in the Hungarian algorithm. By carefully considering the costs of assigning each worker to each task, you can use the algorithm to find the optimal assignment that minimizes the total cost.

Creating the Cost Matrix - Hungarian algorithm: A step by step guide to assignment method

Once the cost matrix has been modified to have equal number of rows and columns, the next step is to reduce the matrix by row and column operations. This step is crucial in order to determine which cells will be assigned to each other, ultimately resulting in the final assignment.

From the perspective of linear algebra, row reduction and column reduction can be viewed as transforming the matrix into its reduced row echelon form (RREF), which is the matrix's most simplified form. This is done by performing elementary row operations, such as swapping two rows, multiplying a row with a constant, or adding a multiple of one row to another. The same operations are performed for columns, resulting in the reduced column echelon form.

Here are the steps involved in row reduction and column reduction:

1. Identify the smallest number in each row and subtract it from every element in that row. This ensures that there is at least one zero in each row.

2. Do the same for each column by finding the smallest number in each column and subtracting it from every element in that column. This ensures that there is at least one zero in each column.

3. Draw lines through the rows and columns that contain zeros. The goal is to draw the minimum number of lines required to cover all the zeros.

4. If the number of lines drawn is equal to the number of rows or columns, the matrix is fully optimized and the assignment can be made. If not, proceed to step 5.

5. Find the smallest uncovered number in the matrix and subtract it from all uncovered numbers. Then, add it to all numbers that are covered by two lines. This step is known as the "assignment step".

6. Repeat steps 3-5 until the matrix is fully optimized and the assignment can be made.

For example, consider the following cost matrix:

| | Job 1 | Job 2 | Job 3 |

| W | 8 | 6 | 5 |

| X | 5 | 4 | 7 |

| Y | 8 | 4 | 6 |

After subtracting the smallest number in each row and column, the matrix becomes:

| W | 3 | 1 | 0 |

| X | 1 | 0 | 3 |

| Y | 4 | 0 | 2 |

The minimum number of lines required to cover all the zeros is 2 (one horizontal and one vertical line). This means that two assignments can be made. The assignment step involves subtracting the smallest uncovered number (which is 1) from all uncovered numbers, and adding it to all numbers that are covered by two lines. After this step, the matrix becomes:

| W | 2 | 0 | 0 |

| X | 0 | 0 | 2 |

| Y | 3 | 0 | 1 |

The minimum number of lines required to cover all the zeros is still 2. The next assignment can be made between (W, Job 2) and (X, Job 1). After subtracting the smallest uncovered number (which is 2) from all uncovered numbers, and adding it to all numbers that are covered by two lines, the matrix becomes:

| W | 0 | 0 | 0 |

| X | 0 | 0 | 0 |

| Y | 1 | 0 | 0 |

The minimum number of lines required to cover all the zeros is now 3, which is equal to the number of rows. This means that the matrix is fully optimized and the final assignment is (W, Job 2), (X, Job 1), and (Y, Job 3).

Row Reduction and Column Reduction - Hungarian algorithm: A step by step guide to assignment method

After completing the second step of the Hungarian algorithm, which involves finding the minimum number of lines required to cover all the zeros in the cost matrix, we move on to step three: assigning zeroes and covering lines. This step is crucial in determining the optimal assignment of tasks or resources in various real-world scenarios such as job scheduling, transportation planning, or project management.

Assigning zeroes and covering lines is a process that aims to identify an assignment that maximizes efficiency and minimizes costs. It involves making strategic choices based on the positions of zeroes in the cost matrix and the lines that have been drawn to cover them. This step requires careful analysis from different perspectives to ensure an optimal solution.

From a mathematical standpoint, assigning zeroes and covering lines can be seen as a game of strategy. The goal is to find a combination of assignments that yields the lowest possible total cost. Each zero represents a potential assignment, and by covering lines, we limit the number of assignments available for each row and column.

To better understand this step, let's delve into some key insights:

1. Assigning Zeroes:

- Start by selecting a row or column with only one uncovered zero.

- Assign this zero to its corresponding task or resource.

- Cross out all other zeroes in the same row or column.

For example, consider a 3x3 cost matrix where we have identified a row with only one uncovered zero:

We assign the zero in row 1, column 2 (highlighted) to its corresponding task. The updated matrix becomes:

| 2 | X | 1 |

| X | 3 | 2 |

2. Covering Lines:

- If all rows and columns are covered, the assignment is complete.

- If not, draw lines through all rows that do not contain assignments and all columns that have been covered.

- The minimum number of lines required to cover all zeros determines the next step.

Continuing from the previous example, let's assume we have covered row 1 and column 2. The updated matrix becomes:

| X | X | 1 |

Assigning Zeroes and Covering Lines - Hungarian algorithm: A step by step guide to assignment method

Once we have completed the step of subtracting the minimum value from each row and column, it is time to move on to finding the minimum number of lines required to cover all the zeros in the matrix. This step is crucial in determining the optimal assignment of tasks or resources using the Hungarian algorithm.

From a high-level perspective, finding the minimum number of lines involves drawing lines through rows and columns in such a way that all zeros are covered. These lines will help us identify potential assignments and determine if any additional steps are needed to achieve an optimal solution.

Looking at this step from different points of view can provide valuable insights into its significance:

1. Mathematical Perspective:

- The minimum number of lines represents the maximum number of independent zeros that can be assigned without conflicts.

- By covering all zeros with a minimum number of lines, we ensure that each task or resource is assigned exactly once.

2. Graph Theory Perspective:

- The matrix can be represented as a bipartite graph, where rows and columns are nodes, and zeros represent edges between them.

- Drawing lines through rows and columns is equivalent to finding a matching in this bipartite graph.

- The minimum number of lines corresponds to finding a maximum matching, ensuring that no two edges share a common node.

To better understand this step, let's break it down into a numbered list:

1. Start by identifying rows or columns that contain only one zero. These single zeros must be assigned immediately, so draw a line through their respective row or column.

Example: Consider a 3x3 matrix with the following zeros: (1,2), (2,1), and (3,3). In this case, we would draw lines through rows 1 and 2 since they contain single zeros.

2. If there are still uncovered zeros remaining in either rows or columns, proceed to identify rows or columns with the fewest uncovered zeros. Draw lines through these rows or columns.

Example: Continuing from the previous example, if there are additional zeros at (1,1) and (3,2), we would draw a line through column 2 since it has the fewest uncovered zeros.

3. Repeat step 2 until all zeros are covered. This may involve drawing multiple lines through rows or columns.

Example: If there is an additional zero at (2,3), we would draw a line through row 2 to cover it.

Finding the Minimum Number of Lines - Hungarian algorithm: A step by step guide to assignment method

After completing the fourth step of the Hungarian algorithm, which involves finding the minimum number of lines to cover all zeros in the cost matrix, we move on to the fifth step: adjusting the cost matrix. This step is crucial as it allows us to further refine our assignment and improve its optimality. By making adjustments to the cost matrix, we can potentially reduce the overall cost of the assignment and achieve a more efficient solution.

From different perspectives, adjusting the cost matrix can be seen as a way to fine-tune the initial assignments made in step three or as a means to explore alternative assignments that may yield better results. Regardless of how one perceives it, this step plays a significant role in optimizing the assignment method.

To provide a comprehensive understanding of this step, let's delve into some key aspects through a numbered list:

1. Subtracting the Smallest Uncovered Value: In this adjustment technique, we identify the smallest value that is not covered by any line (neither horizontal nor vertical) and subtract it from all uncovered values. This adjustment reduces the overall cost of the assignment without altering any existing assignments.

For example, consider a 3x3 cost matrix where we have already assigned values to some cells:

The smallest uncovered value is 6. By subtracting 6 from all uncovered values, we obtain:

This adjustment ensures that no uncovered value remains positive, making it easier to find an optimal solution.

2. Adding Values at Intersection Points: Another adjustment technique involves adding values at intersection points where two lines intersect (one horizontal and one vertical). These intersection points represent potential assignments that were not initially considered due to constraints imposed by the lines.

For instance, consider a 4x4 cost matrix with assigned values:

In this case, there are two intersection points: (1,3) and (3,1). By adding the values at these points (0 + 0 = 0), we can include them as potential assignments:

Adjusting the Cost Matrix - Hungarian algorithm: A step by step guide to assignment method

In the Hungarian algorithm, achieving an optimal assignment involves repeating steps 3-7 until the best possible solution is obtained. This iterative process allows for refining the initial assignment and finding the most efficient allocation of resources. By continuously adjusting the assignments based on cost and availability, the algorithm aims to minimize the overall cost or maximize the overall benefit of the assignment.

From a practical standpoint, repeating steps 3-7 ensures that all possibilities are explored and evaluated before settling on a final assignment. It allows for flexibility in decision-making , as adjustments can be made at each iteration to improve the overall outcome. This iterative approach is particularly useful when dealing with complex problems that require multiple iterations to reach an optimal solution.

To better understand this process, let's break it down into a numbered list:

1. Start with an initial assignment: Begin by assigning values to each element in the cost matrix based on their respective costs or benefits. This initial assignment serves as a starting point for further iterations.

2. Find a feasible solution: Apply steps 3-7 of the Hungarian algorithm to find a feasible solution. This involves identifying rows and columns with zeros and assigning them accordingly to create a complete set of assignments.

3. Evaluate the current assignment: Calculate the total cost or benefit of the current assignment based on the assigned elements in the cost matrix. This provides a measure of how well the current solution performs.

4. Check for optimality: Determine if the current assignment is optimal by examining whether all rows and columns have been assigned exactly once. If so, proceed to step 6; otherwise, continue to step 5.

5. Modify the assignment: Identify any unassigned rows or columns and adjust the assignments to improve the overall solution. This may involve modifying existing assignments or adding new ones based on available options.

6. Repeat steps 3-7: Return to step 3 and repeat the process using the modified assignment from step 5. This iterative loop allows for continuous refinement of the assignment until an optimal solution is achieved.

7. Track the best solution: Keep track of the best assignment found so far, as subsequent iterations may yield better results. This ensures that the algorithm does not settle for a suboptimal solution prematurely.

By repeating steps 3-7, the Hungarian algorithm gradually converges towards an optimal assignment by iteratively adjusting and evaluating the assignments. This iterative nature allows for flexibility in decision-making and enables the algorithm to explore different possibilities before settling on the best allocation of resources.

Repeating Steps 3 7 until Optimal Assignment is Achieved - Hungarian algorithm: A step by step guide to assignment method

The Hungarian Algorithm is a powerful tool that has proven to be highly effective in solving assignment problems . In this section, we will explore the conclusion and applications of this algorithm, shedding light on its significance from various perspectives.

1. Efficiency: One of the key advantages of the Hungarian Algorithm is its efficiency in finding an optimal solution to assignment problems. The algorithm has a time complexity of O(n^3), where n represents the number of rows or columns in the cost matrix. This makes it suitable for solving large-scale assignment problems efficiently .

For example, let's consider a scenario where a company needs to assign tasks to its employees based on their skills and preferences. Using the Hungarian Algorithm, the company can quickly determine the best possible assignments, minimizing costs and maximizing productivity.

2. Optimality: The Hungarian Algorithm guarantees an optimal solution to assignment problems. It ensures that the total cost or objective function value is minimized or maximized, depending on the problem at hand. This optimality property makes it a reliable choice for decision-making processes.

Suppose a hospital needs to assign doctors to different shifts while considering their availability and expertise. By applying the Hungarian Algorithm, the hospital can ensure that each shift is staffed with the most suitable doctors, optimizing patient care and resource allocation.

3. Versatility: The Hungarian Algorithm is not limited to traditional assignment problems alone; it can also be adapted for other optimization tasks. For instance, it can be used for solving transportation problems, job scheduling, facility location, and more.

Let's take an example of a logistics company that needs to determine the most efficient routes for delivering goods to various destinations. By formulating this problem as an assignment problem and applying the Hungarian Algorithm, the company can identify the optimal route assignments, minimizing fuel consumption and delivery time.

4. real-world applications : The Hungarian Algorithm finds applications in diverse fields such as operations research, computer science, economics, and engineering. Its ability to solve complex optimization problems efficiently has made it a valuable tool in various industries.

For instance, in the field of computer vision, the Hungarian Algorithm is used for object tracking and matching. It helps in associating objects across multiple frames of a video, enabling applications like surveillance, motion analysis, and augmented reality.

The Hungarian Algorithm offers an efficient and optimal solution to assignment problems, making it a valuable tool in decision-making processes. Its versatility and real-world applications further highlight its significance in various domains. By understanding and applying this algorithm, individuals and organizations can tackle complex optimization

Conclusion and Applications of the Hungarian Algorithm - Hungarian algorithm: A step by step guide to assignment method

Read Other Blogs

Yield curve analysis is an important tool for investors to understand the current state of the...

In this section, we will delve into the topic of governance and GRC frameworks. Governance is a...

Leave accrual is a fundamental concept in the world of employee benefits and human resources...

The power of dividend reinvestment cannot be underestimated when it comes to long-term growth in...

The criminal justice system is designed to ensure that individuals who commit crimes are held...

When it comes to managing debt, it is essential to have a clear understanding of your debt...

Market depth is a term used to describe the level of liquidity available in a financial market. It...

Per diem interest is a term that is commonly used in the financial industry, especially in the...

Understanding the Walk-Away Lease Agreement When it comes to leasing property, one of the options...

Hungarian Method: Assignment Problem

Hungarian Method is an efficient method for solving assignment problems .

This method is based on the following principle:

• If a constant is added to, or subtracted from, every element of a row and/or a column of the given cost matrix of an assignment problem, the resulting assignment problem has the same optimal solution as the original problem.

Hungarian Algorithm

The objective of this section is to examine a computational method - an algorithm - for deriving solutions to the assignment problems. The following steps summarize the approach:

Steps in Hungarian Method

1. Identify the minimum element in each row and subtract it from every element of that row.

2. Identify the minimum element in each column and subtract it from every element of that column.

3. Make the assignments for the reduced matrix obtained from steps 1 and 2 in the following way:

• For every zero that becomes assigned, cross out (X) all other zeros in the same row and the same column.
• If for a row and a column, there are two or more zeros and one cannot be chosen by inspection, then you are at liberty to choose the cell arbitrarily for assignment.

4. An optimal assignment is found, if the number of assigned cells equals the number of rows (and columns). In case you have chosen a zero cell arbitrarily, there may be alternate optimal solutions. If no optimal solution is found, go to step 5.

5. Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix obtained from step 3 by adopting the following procedure:

• Mark all the rows that do not have assignments.
• Mark all the columns (not already marked) which have zeros in the marked rows.
• Mark all the rows (not already marked) that have assignments in marked columns.
• Repeat steps 5 (i) to (iii) until no more rows or columns can be marked.
• Draw straight lines through all unmarked rows and marked columns.

You can also draw the minimum number of lines by inspection.

6. Select the smallest element from all the uncovered elements. Subtract this smallest element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment.

7. Go to step 3 and repeat the procedure until you arrive at an optimal assignment.

For the time being we assume that number of jobs is equal to number of machines or persons. Later in the chapter, we will remove this restrictive assumption and consider a special case where no. of facilities and tasks are not equal.

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem