Solve the following assignment problem to maximize sales:
| Salesman | Territories | ||||
| I | II | III | IV | V | |
| A | 11 | 16 | 18 | 15 | 15 |
| B | 7 | 19 | 11 | 13 | 17 |
| C | 9 | 6 | 14 | 14 | 7 |
| D | 13 | 12 | 17 | 11 | 13 |
The given problem is maximization problem.
This can be converted to minimization problem by subtracting all the elements from the largest element which is 19.
Also, the number of rows is not equal to number of columns.
∴ It is an unbalanced assignment problem. It can be balanced by introducing a dummy salesman E with zero sales.
The resulting matrix is
| Salesman | Territories | ||||
| I | II | III | IV | V | |
| A | 8 | 3 | 1 | 4 | 4 |
| B | 12 | 0 | 8 | 6 | 2 |
| C | 10 | 13 | 5 | 5 | 12 |
| D | 6 | 7 | 2 | 8 | 6 |
| E | 0 | 0 | 0 | 0 | 0 |
Step 2: Row minimum
Subtract the smallest element in each row from every element in its row.
The matrix obtained is given below:
| Salesman | Territories | ||||
| I | II | III | IV | V | |
| A | 7 | 2 | 0 | 3 | 3 |
| B | 12 | 0 | 8 | 6 | 2 |
| C | 5 | 8 | 0 | 0 | 7 |
| D | 4 | 5 | 0 | 6 | 4 |
| E | 0 | 0 | 0 | 0 | 0 |
Step 3: Column minimum
Here, each column contains element zero.
∴ Matrix obtained by column minimum is same as above matrix.
Step 4:
Draw minimum number of vertical and horizontal lines to cover all zeros.
First cover all rows and columns which have maximum number of zeros.
| Salesman | Territories | ||||
| I | II | III | IV | V | |
| A | 7 | 2 | 0 | 3 | 3 |
| B | 12 | 0 | 8 | 6 | 2 |
| C | 5 | 8 | 0 | 0 | 7 |
| D | 4 | 5 | 0 | 6 | 4 |
| E | 0 | 0 | 0 | 0 | 0 |
Step 5:
From step 4, minimum number of lines covering all the zeros are 4, which is less than order of matrix, i.e., 5.
∴ Select smallest element from all the uncovered elements, i.e., 2 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.
| Salesman | Territories | ||||
| I | II | III | IV | V | |
| A | 5 | 2 | 0 | 1 | 1 |
| B | 10 | 0 | 8 | 4 | 0 |
| C | 5 | 10 | 2 | 0 | 7 |
| D | 2 | 5 | 0 | 4 | 2 |
| E | 0 | 2 | 2 | 0 | 0 |
Step 6:
Draw minimum number of vertical and horizontal lines to cover all zeros.
| Salesman | Territories | ||||
| I | II | III | IV | V | |
| A | 5 | 2 | 0 | 1 | 1 |
| B | 10 | 0 | 8 | 4 | 0 |
| C | 5 | 10 | 2 | 0 | 7 |
| D | 2 | 5 | 0 | 4 | 2 |
| E | 0 | 2 | 2 | 0 | 0 |
Step 7:
From step 6, minimum number of lines covering all the zeros are 4, which is less than order of matrix, i.e., 5.
∴ Select smallest element from all the uncovered elements, i.e., 1 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.
| Salesman | Territories | ||||
| I | II | III | IV | V | |
| A | 4 | 1 | 0 | 1 | 0 |
| B | 10 | 0 | 9 | 5 | 0 |
| C | 4 | 9 | 2 | 0 | 6 |
| D | 1 | 4 | 0 | 4 | 1 |
| E | 0 | 2 | 3 | 1 | 0 |
Step 8:
Draw minimum number of vertical and horizontal lines to cover all zeros.
| Salesman | Territories | ||||
| I | II | III | IV | V | |
| A | 4 | 1 | 0 | 1 | 0 |
| B | 10 | 0 | 9 | 5 | 0 |
| C | 4 | 9 | 2 | 0 | 6 |
| D | 1 | 4 | 0 | 4 | 1 |
| E | 0 | 2 | 3 | 1 | 0 |
Step 9:
From step 8, minimum number of lines covering all the zeros are 5, which is equal to order of the matrix, i.e., 5.
∴ Select a row with exactly one zero, enclose that zero in () and cross out all zeros in its respective column.
Similarly, examine each row and column and mark the assignment ().
∴ The matrix obtained is as follows:
| Salesman | Territories | ||||
| I | II | III | IV | V | |
| A | 4 | 1 | 0 | 1 | 0 |
| B | 10 | 0 | 9 | 5 | 0 |
| C | 4 | 9 | 2 | 0 | 6 |
| D | 1 | 4 | 0 | 4 | 1 |
| E | 0 | 2 | 3 | 1 | 0 |
∴ The optimal solution is
| Salesman | Territories | Sales |
| A | V | 15 |
| B | II | 19 |
| C | IV | 14 |
| D | III | 17 |
| E | I | 0 |
∴ Maximum sales = 15 + 19 + 14 + 17 + 0
= 65 units.
Note that no salesman will be assigned at territory I, since it gets dummy salesman E.
Generate a complete, print-ready paper with questions like this in minutes — across 16+ boards, with answer keys.