- Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S.
Each worker must be assigned to at most one task and each task must be done by just one worker.
The amount, in pounds, that each worker would earn while assigned to each task is shown in the table below.
| \cline { 2 - 5 }
\multicolumn{1}{c|}{} | P | Q | R | S |
| A | 32 | 32 | 33 | 35 |
| B | 28 | 35 | 31 | 37 |
| C | 35 | 29 | 33 | 36 |
| D | 36 | 30 | 36 | 33 |
The Hungarian algorithm is to be used to find the maximum total amount which may be earned by the four workers.
- Explain how the table should be modified.
- Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings, stating how each table was formed.
- Formulate the problem as a linear programming problem. You must define your decision variables and make your objective function and constraints clear.