Hungarian algorithm with unequal sets

1. A company, Kleenitquick, has developed a new stain remover. To promote sales, three salespersons, Jess, Matt and Rachel, will be assigned to three of four department stores \(1,2,3\) and 4 , to demonstrate the stain remover. Each salesperson can only be assigned to one department store.

The table below shows the cost, in pounds, of assigning each salesperson to each department store.

1. Explain why a dummy row needs to be added to the table.
2. Complete Table 1 in the answer book.
3. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost of assigning salespersons to department stores. You must make your method clear and show the table after each iteration.
4. Find the minimum cost.

1. A company has five machines \(A , B , C , D\) and \(E\), which it can assign to four tasks \(1,2,3\) and 4 . Each task must be assigned to just one machine and each machine may only be assigned to just one task.

The profit, in \(\pounds 100\) s, of using each machine to do each task is given in the table below.

1. Explain why it is necessary to add a dummy column to the table.
   (2)
2. Use the Hungarian algorithm to allocate machines to tasks in order to maximise the total profit. You must make your method clear and show the state of the table after each iteration.
   (7)
   (Total 9 marks)

2 Dudley has three daughters who are all planning to get married next year. The girls are named April, May and June, after the months in which they were born. Each girl wants to get married on her own birthday. Dudley has already obtained costings from four different hotels. From past experience, Dudley knows that when his family get together they are likely to end up with everyone fighting one another, so he cannot use the same hotel twice. The table shows the costs, in \(\pounds 100\), for each hotel to host each daughter's wedding. Dudley wants to choose the three hotels to minimise the total cost.
Add a dummy row and then apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the hotels and Dudley's daughters. State how each table is formed and write out the final solution and its cost to Dudley.

1 D aniel needs to clean four houses but only has one day in which to do it. He estimates that each house will take one day and so he has asked three professional cleaning companies to give him a quotation for cleaning each house. He intends to hire the three companies to clean one house each and he will clean the fourth house himself. The table below shows the quotations that Daniel was given by the three companies.

1. Copy the table and add a dummy row to represent D aniel.
2. A pply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working and say how each matrix was formed.
3. Which house should Daniel ask each company to clean? Find the total cost of hiring the three companies.

3 A team triathlon is a race involving swimming, cycling and running for teams of three people. The first person swims, then the second person cycles and finally the third person runs. The winning team is the team that completes all three stages of the triathlon in the shortest time. Four friends are training to enter as a team for the triathlon. They need to choose who to enter for each stage of the triathlon, and who to leave out (this person will be the reserve). The table shows the times, in minutes, for each of them to complete each stage in training.

1. Complete a dummy column in the table in your answer book. Apply the Hungarian algorithm, reducing columns first. Make sure that the values in your tables can all be seen. Write a list showing who should be chosen for each stage of the triathlon. What is the minimum total time in which the team can expect to complete the three stages of the triathlon? The day before the triathlon, the friend who had been chosen to swim is injured and cannot compete.
2. If the reserve takes over the swim, how much longer can the team expect the triathlon to take?
3. Remove the row corresponding to the injured swimmer to form a \(3 \times 3\) table. Apply the Hungarian algorithm to find who should be chosen for each stage to complete the triathlon in the minimum expected time. State the minimum expected time.

3 A theatre company needs to employ three technicians for a performance. One will operate the lights, one the sound system and one the flying trapeze mechanism. Four technicians have applied for these tasks. The table shows how much it will cost the theatre company, in £, to employ each technician for each task. The theatre company wants to employ the three technicians for whom the total cost is least.
The Hungarian algorithm is to be used to find the minimum cost allocation, but before this can be done the table needs to be modified.

1. Make the necessary modification to the table. Working from your modified table, construct a reduced cost matrix by first reducing rows and then reducing columns. You should show the amount by which each row has been reduced in the row reductions and the amount by which each column has been reduced in the column reductions. Cross through the 0 's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [You must ensure that the values in your table can still be read.]
2. Complete the application of the Hungarian algorithm to find a minimum cost allocation. Write a list showing which technician should be employed for each task. Calculate the total cost to the theatre company. Although Amir put in the lowest cost for operating the lighting, you should have found that he has not been allocated this task. Amir is particularly keen to be employed to operate the lights so is prepared to reduce his cost for this task.
3. Find a way to use two of Bex, Caz and Dee to operate the sound effects and the flying trapeze mechanism at the lowest cost. Hence find what Amir's new cost should be for the minimum total cost to the theatre company to be exactly \(\pounds 1\) less than your answer from part (ii).

2 A company has organised four regional training sessions to take place at the same time in four different cities. The company has to choose four of its five trainers, one to lead each session. The cost ( \(\pounds 1000\) 's) of using each trainer in each city is given in the table.

1. Convert this into a square matrix and then apply the Hungarian algorithm, reducing rows first, to allocate the trainers to the cities at minimum cost.
2. Betty discovers that she is not available on the date set for the training. Find the new minimum cost allocation of trainers to cities.

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

Each task must be assigned to exactly one worker and each worker can do at most one task.
Worker B cannot be assigned to task R.
The amount, in pounds, that each worker will earn if they are 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 five workers.

1. Explain how the table should be modified to allow the Hungarian algorithm to be used, giving reasons for your answer.
2. Reducing rows first, use the Hungarian algorithm to obtain the maximum possible total earnings. You should explain how any initial row and column reductions were made and how you determined if the table was optimal at each stage.

1. Six workers, A, B, C, D, E and F, are to be assigned to five tasks, P, Q, R, S and T.

Each worker can be assigned to at most one task and each task must be done by just one worker. The time, in minutes, that each worker takes to complete each task is shown in the table below. Reducing rows first, use the Hungarian algorithm to obtain an allocation which minimises the total time. You must explain your method and show the table after each stage.

1 Five trainers, Ali, Bo, Chas, Dee and Eve, held an initial training session with each of four teams over an assault course. The completion times in minutes are recorded below. Each of the four teams is to be allocated a trainer and the overall time for the four teams is to be minimised. No trainer can train more than one team.

1. Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
2. Use the Hungarian algorithm, reducing columns first then rows, to decide which four trainers should be allocated to which team. State the minimum total training time for the four teams using this matching.

2 The following table shows the times taken, in minutes, by five people, Ash, Bob, Col, Dan and Emma, to carry out the tasks 1, 2, 3 and 4 . Dan cannot do task 3. Each of the four tasks is to be given to a different one of the five people so that the overall time for the four tasks is minimised.

1. Modify the table of values by adding an extra row of non-zero values so that the Hungarian algorithm can be applied.
2. Use the Hungarian algorithm, reducing columns first then rows, to decide which four people should be allocated to which task. State the minimum total time for the four tasks using this matching.
3. After special training, Dan is able to complete task 3 in 12 minutes. Determine, giving a reason, whether the minimum total time found in part (b) could be improved.
   (2 marks)

2 Four of the five students Phil, Quin, Ros, Sue and Tim are to be chosen to make up a team for a mathematical relay race. The team will be asked four questions, one each on the topics A, B, C and D. A different member of the team will answer each question. Each member has to give the correct answer to the question before the next question is asked. The team with the least overall time wins.
The average times, in seconds, for each student in some practice questions are given below.

1. Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
2. Use the Hungarian algorithm, reducing columns first, then rows, to decide which four students should be chosen for the team. State which student should be allocated to each topic and state the total time for the four students on the practice questions using this matching.

3 In the London 2012 Olympics, the Jamaican \(4 \times 100\) metres relay team set a world record time of 36.84 seconds. Athletes take different times to run each of the four legs.
The coach of a national athletics team has five athletes available for a major championship. The lowest times that the five athletes take to cover each of the four legs is given in the table below. The coach is to allocate a different athlete from the five available athletes, \(A , B , C , D\) and \(E\), to each of the four legs to produce the lowest total time. Use the Hungarian algorithm, by reducing the columns first, to assign an athlete to each leg so that the total time of the four athletes is minimised. State the allocation of the athletes to the four legs and the total time.
[0pt] [11 marks]

2. Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances. Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm.

Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances.

	Stage
	1	2	3
Alex	19	69	168
Darren	22	64	157
Leroy	20	72	166
Suraj	23	66	171

Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm. [11 marks]

A construction company has three teams of workers available, each of which is to be assigned to one of four jobs at a site. The following table shows the estimated cost, in tens of pounds, of each team doing each job: \begin{array}{c|c|c|c|c} & Windows & Conservatory & Doors & Greenhouse
\hline Team A & 27 & 80 & 8 & 81
Team B & 28 & 60 & 5 & 71
Team C & 30 & 90 & 7 & 73
\end{array} Use the Hungarian algorithm to find an allocation of jobs which will minimise the total cost. Show the state of the table after each stage in the algorithm and state the cost of the final assignment. [10 marks]