Hungarian Method Example
In the previous section, we used Hungarian Method to solve an assignment problem.
In this section, we provide another example to enhance your knowledge. Let's concentrate on the following example:
Example 2: Hungarian Method
The Winner Publishing Company employs typists on hourly basis. There are five typists for service and their charges and speeds are different.
According to an earlier understanding only one job is given to one typist and the typist is paid for full hour even if he works for a fraction of an hour. Find the least cost allocation for the following data:
| Typist | Rate per hour (Rs.) |
No. of pages Typed / hour |
|---|---|---|
| A | 5 | 12 |
| B | 6 | 14 |
| C | 3 | 8 |
| D | 4 | 10 |
| E | 4 | 11 |
| Job | No. of pages |
|---|---|
| P | 199 |
| Q | 175 |
| R | 145 |
| S | 198 |
| T | 178 |
Solution.
The following matrix gives the cost incurred if the ith typist (i = A, B, C, D & E) executes the jth job (j = P, Q, R, S & T):
| Job | |||||
|---|---|---|---|---|---|
| Typist | P | Q | R | S | T |
| A | 85 | 75 | 65 | 125 | 75 |
| B | 90 | 78 | 66 | 132 | 78 |
| C | 75 | 66 | 57 | 114 | 69 |
| D | 80 | 72 | 60 | 120 | 72 |
| E | 76 | 64 | 56 | 112 | 68 |
Identify the minimum element in each row and subtract it from every element of that row.
Table
| Job | |||||
|---|---|---|---|---|---|
| Typist | P | Q | R | S | T |
| A | 20 | 10 | 0 | 60 | 10 |
| B | 24 | 12 | 0 | 66 | 12 |
| C | 18 | 9 | 0 | 57 | 12 |
| D | 20 | 12 | 0 | 60 | 12 |
| E | 20 | 8 | 0 | 56 | 12 |
Identify the minimum element in each column and subtract it from every element of that column.
Table
| Job | |||||
|---|---|---|---|---|---|
| Typist | P | Q | R | S | T |
| A | 2 | 2 | 0 | 4 | 0 |
| B | 6 | 4 | 0 | 10 | 2 |
| C | 0 | 1 | 0 | 1 | 2 |
| D | 2 | 4 | 0 | 4 | 2 |
| E | 2 | 0 | 0 | 0 | 2 |
Make the assignments for the reduced matrix
Table
| Job | |||||
|---|---|---|---|---|---|
| Typist | P | Q | R | S | T |
| A | 2 | 2 |  |
4 |  |
| B | 6 | 4 | |
10 | 2 |
| C | |
1 | |
1 | 2 |
| D | 2 | 4 | |
4 | 2 |
| E | 2 | |
|
|
2 |
The number of assigned cells is not equal to the number of rows (and columns). Therefore, we draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix
Table
Repeating the usual process as explained in the previous example, we get the following matrix:
Table
| Job | |||||
|---|---|---|---|---|---|
| Typist | P | Q | R | S | T |
| A | 2 | 2 | 2 | 4 | |
| B | 4 | 2 | |
8 | |
| C | |
1 | 2 | 1 | 2 |
| D | |
2 | |
2 | |
| E | 2 | |
2 | |
2 |
The number of assigned cells is not equal to the number of rows (and columns). Therefore, we draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix
Table
Hungarian Method Final Table
| Job | |||||
|---|---|---|---|---|---|
| Typist | P | Q | R | S | T |
| A | 2 | 1 | 2 | 3 | |
| B | 4 | 1 | |
7 | |
| C | |
|
2 | |
2 |
| D | |
1 | |
1 | |
| E | 3 | |
3 | |
3 |
Since the number of assignments is equal to the number of rows (& columns), this is the optimal solution.
Substituting the values from original table:
75 + 66 + 114 + 80 + 64 = Rs. 399.
