Hungarian algorithm for maximisation

2 A farmer has five fields. He intends to grow a different crop in each of four fields and to leave one of the fields unused. The farmer tests the soil in each field and calculates a score for growing each of the four crops. The scores are given in the table below. The farmer's aim is to maximise the total score for the four crops.

1. 1. Modify the table of values by first subtracting each value in the table above from 20 and then adding an extra row of equal values.
   2. Explain why the Hungarian algorithm can now be applied to the new table of values to maximise the total score for the four crops.
2. 1. By reducing rows first, show that the table from part (a)(i) becomes

      2	6	10	0	\(p\)
      0	5	12	4	8
      8	7	5	0	\(q\)
      1	8	2	4	0
      0	0	0	0	0

      State the values of the constants \(p\) and \(q\).
   2. Show that the zeros in the table from part (b)(i) can be covered by one horizontal and three vertical lines, and use the Hungarian algorithm to decide how the four crops should be allocated to the fields.
   3. Hence find the maximum possible total score for the four crops.

2 A team with five members is training to take part in a quiz. The team members, Abby, Bob, Cait, Drew and Ellie, attempted sample questions on each of the five topics and their scores are given in the table. For the actual quiz, each topic must be allocated to exactly one of the team members. The maximum total score for the sample questions is to be used to allocate the different topics to the team members.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(35 - x\).
2. Form a new table by subtracting each number in the table above from 35 . Hence show that, by reducing rows first then columns, the resulting table of values is as below, stating the values of the constants \(p\) and \(q\).

   8	6	8	0	4
   0	11	\(p\)	4	4
   10	4	6	0	12
   \(q\)	2	0	4	0
   0	0	6	6	0

3. Show that the zeros in the table in part (b) can be covered with two horizontal and two vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. 1. Hence find the possible allocations of topics to the five team members so that the total score for the sample questions is maximised.
   2. State the value of this maximum total score.

1. A theme park has four sites, A, B, C and D, on which to put kiosks. Each kiosk will sell a different type of refreshment. The income from each kiosk depends upon what it sells and where it is located. The table below shows the expected daily income, in pounds, from each kiosk at each site.

Reducing rows first, use the Hungarian algorithm to determine a site for each kiosk in order to maximise the total income. State the site for each kiosk and the total expected income. You must make your method clear and show the table after each stage.
(Total 13 marks)

5. Four salesperson \(A , B , C\) and \(D\) are to be sent to visit four companies \(1,2,3\) and 4 . Each salesperson will visit exactly one company, and all companies will be visited. Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in \(\pounds 10000\) s) are shown in the table below.

1. Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage.
2. State the value of the maximum sales.
3. Show that there is a second allocation that maximises the sales.
   (Total 15 marks)

6. Four salespersons, Joe, Min-Seong, Olivia and Robert, are to attend four business fairs, \(A , B , C\) and \(D\). Each salesperson must attend just one fair and each fair must be attended by just one salesperson. The expected sales, in thousands of pounds, that each salesperson would make at each fair is shown in the table below.

1. Use the Hungarian algorithm, reducing rows first, to obtain an allocation that maximises the total expected sales from the four salespersons. You must make your method clear and show the table after each stage.
2. State all possible optimal allocations and the optimal total value.
   (4)(Total 14 marks)

1. Four workers, Chris (C), James (J), Katie (K) and Nicky (N), are to be allocated to four tasks, 1, 2, 3 and 4. Each worker is to be allocated to one task and each task must be allocated to one worker.

The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.

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. State which worker should be allocated to each task and the resulting total profit made.

3. Four pupils, Alexa, Ewan, Faith and Zak, are to be allocated to four rounds, 1, 2, 3 and 4, in a mathematics competition. Each pupil is to be allocated to exactly one round and each round must be allocated to exactly one pupil. Each pupil has been given a score, based on previous performance, to show how suitable they are for each round. The higher the score the more suitable the pupil is for that round. The scores for each pupil are shown in the table below.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total score. You must make your method clear and show the table after each stage.
   (8)
2. State the maximum total score.

7. Four salespersons \(A , B , C\) and \(D\) are to be sent to visit four companies 1,2,3 and 4. Each salesperson will visit exactly one company, and all companies will be visited.
Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in \(\pounds 10000\) s) are shown in the table below.

1. Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage.
2. State the value of the maximum sales.
3. Show that there is a second allocation that maximises the sales.

1 Four friends have rented a house and need to decide who will have which bedroom. The table below shows how each friend rated each room, so the higher the rating the more the room was liked. The Hungarian algorithm is to be used to find the matching with the greatest total. Before the Hungarian algorithm can be used, each rating is subtracted from 6.

1. Explain why the ratings could not be used as given in the table.
2. Apply the Hungarian algorithm, reducing rows first, to match the friends to the rooms. You must show your working and say how each matrix was formed.

3 The famous fictional detective Agatha Parrot has been called in to investigate the theft of some jewels. Each thief is known to have taken just one item of jewellery. Agatha has invented a scoring system based on motive, opportunity and past experience. The table shows the score for each of four suspects with each of three items of jewellery. The higher the score the more likely the suspect is to have stolen that item of jewellery. Suspect

1. Assuming that three of these four suspects are the thieves, find who is most likely to have stolen each item of jewellery for the total score to be maximised. State how each table of working was calculated. Write down the two possible solutions for who should be suspected of stealing each item of jewellery and who should be thought to be innocent. Further evidence shows that the butler stole the sapphire bracelet.
2. Using this additional information, find out which suspect should be thought to be innocent. Explain your reasoning.

3 Agatha Parrot is in her garden and overhears her neighbours talking about four new people who have moved into her village. Each of the new people has a different job, and Agatha's neighbours are guessing who has which job. Using the information she has overheard, Agatha counts how many times she heard it guessed that each person has each job. Agatha wants to find the allocation of people to jobs that maximises the total number of correct guesses. She intends to use the Hungarian algorithm to do this. She starts by subtracting each value in the table from 10.

1. Write down the table which Agatha gets after she has subtracted each value from 10. Explain why she did a subtraction.
2. Apply the Hungarian algorithm, reducing rows first, to find which job Agatha concludes each person has. State how each table of working was calculated from the previous one. Agatha later meets Liz Lomax and is surprised to find out that she is the radiographer.
3. Using this additional information, but without formally using the Hungarian algorithm, find which job Agatha should now conclude each person has. Explain how you know that there is no better solution in which Liz is the radiographer.

2 Granny is on holiday in Amsterdam and has bought some postcards. She wants to send one card to each member of her family. She has given each card a score to show how suitable it is for each family member. The higher the score the more suitable the card is. \begin{table}[h] \end{table} Granny adds two dummy columns, \(G\) and \(H\), both with score 0 for each postcard. She then modifies the resulting table so that she can use the Hungarian algorithm to find the matching for which the total score is maximised.

1. Explain why the dummy columns were needed, why they should not have positive scores and how the resulting table was modified.
2. Show that, after reducing rows and columns, Granny gets this reduced cost matrix.

   	A	B	\(C\)	D	\(E\)	\(F\)	\(G\)	\(H\)
   \(P\)	4	2	4	0	6	2	2	2
   \(Q\)	2	0	2	0	2	1	1	1
   \(R\)	2	1	2	2	2	0	4	4
   \(S\)	2	0	2	2	6	2	2	2
   \(T\)	4	5	4	1	5	0	1	1
   \(U\)	1	0	0	0	1	1	0	0
   \(V\)	0	2	0	1	0	2	3	3
   \(W\)	2	0	1	2	1	1	2	2

3. Complete the application of the Hungarian algorithm, showing your working clearly. Write down which family member is sent each postcard, and which postcards are not used, to maximise the score.

2 The cadets in Blue Team have been set a task that requires them to get inside a guarded building. Every two hours one of them will attempt to get inside the building. Each cadet will have one attempt. The table shows a score for each cadet attempting to get inside the building at each time. The higher the score the more likely the cadet is to succeed. Time

1. Explain how to modify the table so that the Hungarian algorithm can be used to find the matching for which the total score is maximised.
2. Show that, after modifying the table and then reducing rows and then columns, the reduced cost matrix becomes:

   	2330	0130	0330	0530	0730
   \(G\)	0	6	0	3	4
   \(H\)	0	5	1	5	4
   \(I\)	0	4	0	3	2
   \(J\)	0	3	0	2	2
   \(K\)	0	0	0	0	0

3. Complete the application of the Hungarian algorithm, stating how each table was formed. Write down the order in which the cadets should attempt to get into the building to maximise the total score. If the cadets use this solution, which one is least likely to succeed?

6. Four sales representatives ( \(R _ { 1 } , R _ { 2 } , R _ { 3 }\) and \(R _ { 4 }\) ) are to be sent to four areas ( \(A _ { 1 } , A _ { 2 } , A _ { 3 }\) and \(A _ { 4 }\) ) such that each representative visits one area. The estimated profit, in tens of pounds, that each representative will make in each area is shown in the table below. Use the Hungarian method to obtain an allocation which will maximise the total profit made from the visits. Show the state of the table after each stage in the algorithm.
(13 marks)

5. A travel company offers a touring holiday which stops at four locations, \(A , B , C\) and \(D\). The tour may be taken with the locations appearing in any order, but the number of days spent in each location is dependent on its position in the tour, as shown in the table below. Showing the state of the table at each stage, use the Hungarian algorithm to find the order in which to complete the tour so as to maximise the total number of days. State the maximum total number of days that can be spent in the four locations.
(11 marks)

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

Each worker must be assigned to at most one task, and each task must be done by at most one worker.
The amount, in pounds, that each worker will earn while 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 three workers.

1. Explain how the table should be modified.
   (2)
2. 1. Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings.
   2. 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, Ted (T), Harold (H), James (J) and Margaret (M), 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.

The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.

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.

1. Four students, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , are to be allocated to four rounds, \(1,2,3\) and 4 , in a competition. Each student is to take part in exactly one round and no two students may play in the same round.

Each student has been given an estimated score for each round. The estimated scores for each student are shown in the table below.

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

1. 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. The Hungarian algorithm is to be used to find the maximum total amount which may be earned by the four workers.

1. Explain how the table should be modified.
2. Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings, stating how each table was formed.
3. Formulate the problem as a linear programming problem. You must define your decision variables and make your objective function and constraints clear.

2 Five successful applicants received the following scores when matched against suitability criteria for five jobs in a company. It is intended to allocate each applicant to a different job so as to maximise the total score of the five applicants.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(15 - x\).
2. Form a new table by subtracting each number in the table from 15. Use the Hungarian algorithm to allocate the jobs to the applicants so that the total score is maximised.
3. It is later discovered that Bill has already been allocated to Job 4. Decide how to alter the allocation of the other jobs so as to maximise the score now possible.

2 The following table shows the scores of five people, Alice, Baji, Cath, Dip and Ede, after playing five different computer games. Each of the five games is to be assigned to one of the five people so that the total score is maximised. No person can be assigned to more than one game.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(20 - x\).
2. Form a new table by subtracting each number in the table above from 20, and hence show that, by reducing columns first and then rows, the resulting table of values is as below.

   3	1	1	1	0
   0	4	5	2	2
   4	0	5	0	7
   5	1	0	1	1
   5	1	0	2	5

3. Show that the zeros in the table in part (b) can be covered with one horizontal and three vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. Hence find the possible allocations of games to the five people so that the total score is maximised.
5. State the value of the maximum total score.

3 Five lecturers were given the following scores when matched against criteria for teaching five courses in a college. Each lecturer is to be allocated to exactly one of the courses so as to maximise the total score of the five lecturers.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(17 - x\).
2. Form a new table by subtracting each number in the table above from 17. Hence show that, by reducing rows first and then columns, the resulting table of values is as below.

   0	0	3	3	0
   4	3	4	0	2
   0	6	7	2	2
   5	2	3	0	6
   3	1	0	2	0

3. Show that the zeros in the table in part (b) can be covered with two horizontal and two vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. Hence find the possible allocations of courses to the five lecturers so that the total score is maximised.
5. State the value of the maximum total score.

3. Five friends have rented a house that has five bedrooms. They each require their own bedroom. The table below shows how each friend rated the five bedrooms, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , where 0 is low and 10 is high. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total of all the ratings. You must make your method clear and show the table after each stage.
(Total 8 marks)

2 In an investigation into a burglary, Agatha has five suspects who were all known to have been near the scene of the crime, each at a different time of the day. She collects evidence from witnesses and draws up a table showing the number of witnesses claiming sight of each suspect near the scene of the crime at each possible time. Suspect \begin{table}[h] \end{table}

1. Use the Hungarian algorithm on a suitably modified table, reducing rows first, to find the matchings for which the total number of claimed sightings is maximised. Show your working clearly. Write down the resulting matchings between the suspects and the times. Further enquiries show that the burglary took place at 5 pm , and that Dr Silverbirch was not the burglar.
2. Who should Agatha suspect?

1. Four sales representatives ( \(R _ { 1 } , R _ { 2 } , R _ { 3 }\) and \(R _ { 4 }\) ) are to be sent to four areas ( \(A _ { 1 } , A _ { 2 } , A _ { 3 }\) and \(A _ { 4 }\) ) such that each representative visits one area. The estimated profit, in tens of pounds, that each representative will make in each area is shown in the table below.

Use the Hungarian method to obtain an allocation which will maximise the total profit made from the visits. Show the state of the table after each stage in the algorithm.