Hungarian Method for Maximal Assignment Problem Example
In this article we will study the step by step procedure to solve assignment problem of maximization type using Hungarian method.
Maximal Assignment Problem Example
Five lathe are to be allotted to five operators (one for each) The following table gives weekly output figures (in pieces):
| Operator \ Lathe | L1 | L2 | L3 | L4 | L5 |
|---|---|---|---|---|---|
| A | 20 | 22 | 27 | 32 | 36 |
| B | 19 | 23 | 29 | 34 | 40 |
| C | 23 | 28 | 35 | 39 | 34 |
| D | 21 | 24 | 31 | 37 | 42 |
| E | 24 | 28 | 31 | 36 | 41 |
Profit per piece is Rs. 25. Find the maximum profit. Use the Hungarian method to determine the optimal assignments.
Solution
In the given problem there are 5 operators and 5 Lathe. The problem can be formulated as $5\times 5$ assignment problem with $c_{ij}$ = weekly output (in pieces) from $j^{th}$ Lathe by $i^{th}$ operator.
Let
$$ \begin{equation*} x_{ij}=\left\{ \begin{array}{ll} 1, & \hbox{if $j^{th}$ Lathe is assigned to $i^{th}$ Operator;} \\ 0, & \hbox{otherwise.} \end{array} \right. \end{equation*} $$
The following table gives weekly output figures (in pieces):
| Operator \ Lathe | L1 | L2 | L3 | L4 | L5 |
|---|---|---|---|---|---|
| A | 20 | 22 | 27 | 32 | 36 |
| B | 19 | 23 | 29 | 34 | 40 |
| C | 23 | 28 | 35 | 39 | 34 |
| D | 21 | 24 | 31 | 37 | 42 |
| E | 24 | 28 | 31 | 36 | 41 |
The profit per piece is Rs. 25. As the assignment problem is to maximize the profit, first we need to convert the assignment problem to minimization problem.
The largest element in the matrix is 42. Subtract all the elements of given matrix from the largest element (i.e. 42). The modified matrix is as follows:
Step 1
In first row smallest is 6, second row is 2, third row is 3, fourth row is 0 and fifth row is 1.
Subtract the minimum of each row of the above cost matrix, from all the elements of respective rows. The modified matrix is as follows:
Step 2
In first column smallest is 16, second column is 11, third column is 4, fourth column is 0 and fifth column is 0.
Subtract the minimum of each column of the modified matrix, from all the elements of respective columns. The modified matrix is as follows:
Step 3
Draw the minimum number of horizontal and vertical line to cover all the zeros in the modified matrix.
The minimum number of lines = 3, which is less than the order of assignment problem (i.e. 5). Hence the optimal assignment is not possible.
Step 4
The smallest element in the matrix, not covered by the lines is 2. Subtract 2 from all the uncovered elements and add 2 at the intersection of horizontal and vertical lines. And obtain the second modified matrix.
Draw the minimum number of horizontal and vertical line to cover all the zeros in the above modified matrix.
The minimum number of lines = 4, which is less than the order of assignment problem (i.e. 5). Hence the optimal assignment is not possible.
The smallest element in the matrix, not covered by the lines is 2. Subtract 2 from all the uncovered elements and add 2 at the intersection of horizontal and vertical lines. And obtain the second modified matrix.
Draw the minimum number of horizontal and vertical line to cover all the zeros in the above modified matrix.
The minimum number of lines = 4, which is less than the order of assignment problem (i.e. 5). Hence the optimal assignment is not possible.
The smallest element in the matrix, not covered by the lines is 1. Subtract 1 from all the uncovered elements and add 1 at the intersection of horizontal and vertical lines. And obtain the second modified matrix.
Draw the minimum number of horizontal and vertical line to cover all the zeros in the above modified matrix.
The smallest element in the matrix, not covered by the lines is 1. Subtract 1 from all the uncovered elements and add 1 at the intersection of horizontal and vertical lines. And obtain the second modified matrix.
Draw the minimum number of horizontal and vertical line to cover all the zeros in the above modified matrix.
Step 5
The minimum number of lines = 5, which is equal to the order of assignment problem (i.e. 5). Hence the optimal assignment using Hungarian method is possible.
Step 6
Examine the row successively until a row-wise exactly single zero is found, mark this zero by $\square$ to make the assignment and mark cross $(\times)$ over all zeros in that column. Continue in this manner until all the rows have been examined. Repeat the same procedure for columns also.
Step 7
Repeat the Step 6 successively we have
Step 8
From the above table it is clear that in each row and in each column exactly one marked $\square$ zero is obtained. The optimal assignment is
Operator A $\to$ Lathe L1
Operator B $\to$ Lathe L5
Operator C $\to$ Lathe L3
Operator D $\to$ Lathe L4
Operator E $\to$ Lathe L2
The expected time for five persons to complete five jobs is as follows:
| Operator | Lathe | Weekly Output (in Pieces) |
|---|---|---|
| Operator A | Lathe L1 | 20 |
| Operator B | Lathe L5 | 40 |
| Operator C | Lathe L3 | 35 |
| Operator D | Lathe L4 | 37 |
| Operator E | Lathe L2 | 28 |
Thus the optimal (maximum) weekly output from five Operators on five Lathe = 20+40+35+37+28 = 160 pieces.
The profit per piece is Rs. 25. So the maximum profit will be Rs $160 \times 25 = 4000$.
Endnote
In this tutorial, you learned about step by step procedure of Hungarian Algorithm to solve assignment problem of maximization type.
To learn more about Assignment problems please refer to the following tutorials:
Read step by step solution
Let me know in the comments if you have any questions on Hungarian Algorithm to solve Assignment problems of maximization type and your thought on this article.