There are problems where certain facilities have to be assigned to a number of jobs, so as to maximize the overall performance of the assignment.
The Hungarian Method can also solve such assignment problems, as it is easy to obtain an equivalent minimization problem by converting every number in the matrix to an opportunity loss.
The conversion is accomplished by subtracting all the elements of the given matrix from the highest element. It turns out that minimizing opportunity loss produces the same assignment solution as the original maximization problem.
Example: Maximization In An Assignment Problem
At the head office of www.universalteacherpublications.com there are five registration counters. Five persons are available for service.
How should the counters be assigned to persons so as to maximize the profit?
Here, the highest value is 62. So we subtract each value from 62. The conversion is shown in the following table.
On small screens, scroll horizontally to view full calculation
Now the above problem can be easily solved by Hungarian method. After applying steps 1 to 3 of the Hungarian method, we get the following matrix.
Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix.
Select the smallest element from all the uncovered elements, i.e., 4. Subtract this 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. Repeating step 3, we obtain a solution which is shown in the following table.
Final Table: Maximization Problem
Use Horizontal Scrollbar to View Full Table Calculation
The total cost of assignment = 1C + 2E + 3A + 4D + 5B
Substituting values from original table:
40 + 36 + 40 + 36 + 62 = 214.
There are problems where certain facilities have to be assigned to a number of jobs so as to maximize the overall performance of the assignment. The problem can be converted into a minimization problem in the following ways and then Hungarian method can be used for its solution.
- Change the signs of all values given in the table.
- Select the highest element in the entire assignment table and subtract all the elements of the table from the highest element.
Example : A marketing manager has five salesmen and sales districts. Considering the capabilities of the salesmen and the nature of districts, the marketing manager estimates that sales per month (in hundred rupees) for each salesman in each district would be as follows. Find the assignment of salesmen to districts that will result in maximum sales.
Solution: The given maximization problem is converted into minimization problem by subtracting from the highest sales value (i.e., 41) with all elements of the given table.
Conversion to Minimization Problem
Reduce the matrix row-wise
Matrix Reduced Row-wise
Reduce the matrix column-wise and draw minimum number of lines to cover all the zeros in the matrix, as shown in Table.
Matrix Reduced Column-wise and Zeros Covered
Number of lines drawn ≠ Order of matrix. Hence not optimal.
Select the least uncovered element, i.e., 4 and subtract it from other uncovered elements, add it to the elements at intersection of line and leave the elements that are covered with single line unchanged, Table.
Added & Subtracted the least Uncovered Element
Now, number of lines drawn = Order of matrix, hence optimality is reached. There are two alternative assignments due to presence of zero elements in cells (4, C), (4, D), (5, C) and (5, D).
Two Alternative Assignments