Optimization assignment problems

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.

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.

6. Three workers, \(\mathrm { P } , \mathrm { Q }\) and R , are to be assigned to three tasks, A, B and C. Each worker must be assigned to just one task and each task must be assigned to just one worker.
Table 1 shows the cost of using each worker for each task. The total cost is to be minimised. \begin{table}[h] \end{table}

1. Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective and constraints clear.
   You are not required to solve the problem. Table 2 shows the profit gained by using each worker for each task. The total profit is to be maximised. \begin{table}[h]

   	Task A	Task B	Task C
   Worker P	33	37	31
   Worker Q	32	36	40
   Worker R	41	35	38

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
2. Modify Table 2 in the answer book so that the Hungarian Algorithm could be used to find the maximum total profit. You are not required to solve the problem.
   (2)
   (Total 9 marks)

1. Five workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , are to be assigned to five tasks, \(1,2,3,4\) and 5 . Each worker is to be assigned to one task and each task must be assigned to one worker.

The cost, in pounds, of assigning each person to each task is shown in the table below. The cost is to be minimised.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.
2. Find the minimum cost.

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.

6. Three workers, Harriet, Jason and Katherine, are to be assigned to three tasks, 1, 2 and 3. Each worker must be assigned to just one task and each task must be done by just one worker. The amount each person would earn, in pounds, while assigned to each task is shown in the table below. The total income is to be maximised.

1. Modify the table so it can be used to find the maximum income.
2. Formulate the above situation as a linear programming problem. You must define your decision variables and make your objective function and constraints clear.

6. 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 C cannot do task 4 and worker D cannot do task 1. The cost of assigning each worker to each task is shown in the table below. The total cost is to be minimised. Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.

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.

6. Three warehouses, \(\mathrm { P } , \mathrm { Q }\) and R , supply washing machines to four retailers, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . The table gives the cost, in pounds, of transporting a washing machine from each warehouse to each retailer. It also shows the number of washing machines held at each warehouse and the number of washing machines required by each retailer. The total cost of transportation is to be minimised. Formulate this transportation problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.
You do not need to solve this problem.
(Total 7 marks)

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.

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)

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.

2 Amir, Bex, Cerys and Duncan all have birthdays in January. To save money they have decided that they will each buy a present for just one of the others, so that each person buys one present and receives one present. Four slips of paper with their names on are put into a hat and each person chooses one of them. They do not tell the others whose name they have chosen and, fortunately, nobody chooses their own name. The table shows the cost, in \(\pounds\), of the present that each person would buy for each of the others. As it happens, the names are chosen in such a way that the total cost of the presents is minimised.
Assign the cost \(\pounds 25\) to each of the missing entries in the table and then apply the Hungarian algorithm, reducing rows first, to find which name each person chose.

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.

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.

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?

3 Each of five jobs is to be allocated to one of five workers, and each worker will have one job. The table shows the cost, in \(\pounds\), of using each worker on each job. It is required to find the allocation for which the total cost is minimised. Worker \begin{table}[h] \end{table}

1. Construct a reduced cost matrix by first reducing rows and then reducing columns. Cross through the 0's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [Try to ensure that the values in your table can still be read.]
2. Augment your reduced cost matrix and hence find a minimum cost allocation. Write a list showing which job should be given to which worker for your minimum cost allocation, and calculate the total cost in this case. Gill decides that she does not like the job she has been allocated and increases her cost for this job by \(\pounds 100\). New minimum cost allocations can be found, each allocation costing just \(\pounds 1\) more than the minimum cost allocation found in part (ii).
3. Use the grid in your answer book to show the positions of the 0 's and 1 's in the augmented reduced cost matrix from part (ii). Hence find three allocations, each costing just \(\pounds 1\) more than the minimum cost allocation found in part (ii) and with Gill having a different job to the one allocated in part (ii). [5]

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.

2. A school entrance examination consists of three papers - Mathematics, English and Verbal Reasoning. Three teams of markers are to mark one style of paper each. The table below shows the average time, in minutes, taken by each team to mark one script for each style of paper. It is desired that the scripts are marked as quickly as possible.
Formulate this information as a linear programming problem.

1. State your decision variables.
2. Write down the objective function in terms of your decision variables.
3. Write down the constraints, explaining what each one represents.

5. 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: 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.
(13 marks)