Hungarian algorithm with restrictions

2. A team of four workers, Harry, Jess, Louis and Saul, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to one task and each task must be done by just one worker. Jess cannot be assigned to task 4.
The amount, in pounds, that each person would earn while assigned to each task is shown in the table below.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total amount earned by the team. You must make your method clear and show the table after each stage.
2. State who should be assigned to each task and the total amount earned by the team.

1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.

Worker A cannot do task 4 and worker B cannot do task 2. The amount, in pounds, that each worker would earn if assigned to the tasks, is shown in the table below. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You must make your method clear and show the table after each stage.

2. Four workers, A, B, C and D, are each to be assigned to one of four tasks, P, Q, R and S. Each worker must be assigned to one task, and each task must be done by exactly one worker. Worker C cannot be assigned to task Q. The amount, in pounds, that each worker would earn when assigned to each task is shown in the table below. The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the four workers.

1. Explain how the table should be modified so that the Hungarian algorithm may be applied.
2. Modify the table so that the Hungarian algorithm may be applied.
3. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You should explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage.

1. Four workers, A, B, C and D, are each to be assigned to one of four tasks, P, Q, R and S.

Each worker must be assigned to one task, and each task must be done by exactly one worker. Worker C cannot be assigned to task Q and worker D cannot be assigned to task S.
The time, in minutes, that each worker takes to complete each task is shown in the table below. The Hungarian algorithm is to be used to find the minimum total time for the four workers to complete the tasks.

1. Modify the table so that the Hungarian algorithm may be used.
2. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total time. You should explain how any initial row and column reductions are made and also how you determine if the table is optimal at each stage.

1. Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S.

Each worker can only be assigned to at most one task, and each task must be done by at most one worker. Worker B cannot be assigned to task Q and worker E cannot be assigned to task S.
The time, in minutes, that each worker takes to complete each task is shown in the table below. The Hungarian algorithm is to be used to find the least total time to complete all four tasks.

1. Explain how the table should be modified so that the Hungarian algorithm can be applied.
2. 1. Use the Hungarian algorithm to obtain an allocation that minimises the total time.
   2. Explain how you determined if the table was optimal at each stage.
3. Calculate the least total time to complete all four tasks.

2. A team of 5 players, A, B, C, D and E, competes in a quiz. Each player must answer one of 5 rounds, \(\mathrm { P } , \mathrm { Q } , \mathrm { R } , \mathrm { S }\) and T . Each player must be assigned to exactly one round, and each round must be answered by exactly one player. Player B cannot answer round Q, player D cannot answer round T, and player E cannot answer round R. The number of points that each player is expected to earn in each round is shown in the table. The team wants to maximise its total expected score.
The Hungarian algorithm is to be used to find the maximum total expected score that can be earned by the 5 players.

1. Explain how the table should be modified.
2. 1. Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total expected score.
   2. Calculate the maximum total expected score.

1. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S.

Each task must be assigned to just one worker and each worker can do only one task.
Worker B cannot be assigned to task Q and worker D cannot be assigned to task R.
The amount, in pounds, that each worker would earn when assigned to each task is shown in the table below. The Hungarian algorithm can be used to find the maximum total amount that would be earned by the four workers.

1. 1. Explain how to modify the table so that the Hungarian algorithm could be applied.
   2. Modify the table as described in (a)(i).
2. Formulate the above situation as a linear programming problem. You must define the decision variables and make the objective function and constraints clear.

2 The times taken in minutes for five people, Ann, Baz, Cal, Di and Ez, to complete each of five different tasks are recorded in the table below. Neither Ann nor Di can do task 2, as indicated by the asterisks in the table.

2 Alan, Beth, Callum, Diane and Ethan work for a restaurant chain. The costs, in pounds, for the five people to travel to each of five different restaurants are recorded in the table below. Alan cannot travel to restaurant 1 and Beth cannot travel to restaurants 3 and 5, as indicated by the asterisks in the table.

1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4 . Each worker must be assigned to exactly one task and each task must be done by exactly one worker.

Worker A cannot do task 3 and worker B cannot do task 4 The table below shows the profit, in pounds, that each worker would earn if assigned to each of the tasks.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.
2. Determine the resulting total profit.

During the school holidays four building tasks, rebuilding a wall (\(W\)), repairing the roof (\(R\)), repainting the hall (\(H\)) and relaying the playground (\(P\)), need to be carried out at a Junior School. Four builders, \(A\), \(B\), \(C\) and \(D\) will be hired for these tasks. Each builder must be assigned to one task. Builder \(B\) is not able to rebuild the wall and therefore cannot be assigned to this task. The cost, in thousands of pounds, of using each builder for each task is given in the table below.

Cost	\(H\)	\(P\)	\(R\)	\(W\)
\(A\)	3	5	11	9
\(B\)	3	7	8	--
\(C\)	2	5	10	7
\(D\)	8	3	7	6

1. Use the Hungarian algorithm, reducing rows first, to obtain an allocation that minimises the total cost. State the allocation and its total cost. You must make your method clear and show the table after each stage. [9]
2. State, with a reason, whether this allocation is unique. [2]

(Total 11 marks)