Hungarian algorithm for minimisation

3 Four pupils, Wendy, Xiong, Yasmin and Zaira, are each to be allocated a different memory coach from five available coaches: Asif, Bill, Connie, Deidre and Eric. Each pupil has an initial training session with each coach, and a test which scores their improvement in memory-recall produces the following results.

2 Five students attempted five different games, and penalty points were given for any mistakes that they made. The table shows the penalty points incurred by the students. Using the Hungarian algorithm, each of the five students is to be allocated to a different game so that the total number of penalty points is minimised.

1. By reducing the rows first and then the columns, show that the new table of values is

   2	4	0	2	3
   4	2	0	1	1
   5	0	1	\(k\)	0
   1	1	0	4	2
   0	2	0	0	3

   and state the value of the constant \(k\).
2. Show that the zeros in the table in part (a) can be covered with three lines, and use augmentation to produce a table where five lines are required to cover the zeros.
3. Hence find the possible ways of allocating the five students to the five games with the minimum total of penalty points.
4. Find the minimum possible total of penalty points.
   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-05_2484_1709_223_153}

2 The times taken, in minutes, for five people, \(A , B , C , D\) and \(E\), to complete each of five different puzzles are recorded in the table below. Using the Hungarian algorithm, each of the five people is to be allocated to a different puzzle so that the total time for completing the five puzzles is minimised.

1. By reducing the columns first and then the rows, show that the new table of values is

   3	1	0	4	1
   0	\(k\)	0	1	3
   1	0	3	1	2
   2	3	2	0	0
   0	5	1	2	1

   State the value of the constant \(k\).
2. 1. Show that the zeros in the table in part (a) can be covered with one horizontal and three vertical lines.
   2. Use augmentation to produce a table where five lines are required to cover the zeros.
3. Hence find all the possible ways of allocating the five people to the five puzzles so that the total completion time is minimised.
4. Find the minimum total time for completing the five puzzles.
5. Explain how you would modify the original table if the Hungarian algorithm were to be used to find the maximum total time for completing the five puzzles using five different people.

3 The table shows the times taken, in minutes, by five people, \(A , B , C , D\) and \(E\), to carry out the tasks \(V , W , X , Y\) and \(Z\). Each of the five tasks is to be given to a different one of the five people so that the total time for the five tasks is minimised. The Hungarian algorithm is to be used.

1. By reducing the columns first, and then the rows, show that the new table of values is

   0	12	13	2	0
   14	21	0	\(k\)	9
   3	10	0	6	23
   0	2	6	20	0
   0	0	0	0	7

   and state the value of the constant \(k\).
2. Show that the zeros in the table in part (a) can be covered with four lines. Use augmentation twice to produce a table where five lines are required to cover the zeros.
3. Hence find the possible ways of allocating the five tasks to the five people to achieve the minimum total time.
4. Find the minimum total time.

5. An engineering company has 4 machines available and 4 jobs to be completed. Each machine is to be assigned to one job. The time, in hours, required by each machine to complete each job is shown in the table below. Use the Hungarian algorithm, reducing rows first, to obtain the allocation of machines to jobs which minimises the total time required. State this minimum time.

3. Talkalot College holds an induction meeting for new students. The meeting consists of four talks: I (Welcome), II (Options and Facilities), III (Study Tips) and IV (Planning for Success). The four department heads, Clive, Julie, Nicky and Steve, deliver one of these talks each. The talks are delivered consecutively and there are no breaks between talks. The meeting starts at 10 a.m. and ends when all four talks have been delivered. The time, in minutes, each department head takes to deliver each talk is given in the table below.

1. Use the Hungarian algorithm to find the earliest time that the meeting could end. You must make your method clear and show
   1. the state of the table after each stage in the algorithm,
   2. the final allocation.
2. Modify the table so it could be used to find the latest time that the meeting could end.

3. To raise money for charity it is decided to hold a Teddy Bear making competition. Teams of four compete against each other to make 20 Teddy Bears as quickly as possible. There are four stages: first cutting, then stitching, then filling and finally dressing.
Each team member can only work on one stage during the competition. As soon as a stage is completed on each Teddy Bear the work is passed immediately to the next team member. The table shows the time, in seconds, taken to complete each stage of the work on one Teddy Bear by the members \(A , B , C\) and \(D\) of one of the teams.

1. Use the Hungarian algorithm, reducing rows first, to obtain an allocation that minimises the time taken by this team to produce one Teddy Bear. You must make your method clear and show the table after each iteration.
2. State the minimum time it will take this team to produce one Teddy Bear. Using the allocation found in (a),
3. calculate the minimum total time this team will take to complete 20 Teddy Bears. You should make your reasoning clear and state your answer in minutes and seconds.
   (Total 13 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.

4 Four workers, \(A , B , C\) and \(D\), are to be allocated, one to each of the four jobs, \(W , X , Y\) and \(Z\). The table shows how much each worker would charge for each job. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_401_846_1745_642}

1. What is the total cost of the four jobs if \(A\) does \(W , B\) does \(X , C\) does \(Y\) and \(D\) does \(Z\) ?
2. Apply the Hungarian algorithm to the table, reducing rows first. Show all your working and explain each step. Give the resulting allocation and the total cost of the four jobs with this allocation.
3. What problem does the Hungarian algorithm solve?

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 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]

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)

3. Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:

• strip the wallpaper,
• paint the woodwork and ceiling,
• hang the new wallpaper,
• replace the fittings and tidy up.

The table below shows the time, in hours, that each of the friends is likely to take to complete each job. As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.

1. Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
   (6 marks)
2. Hence, find the minimum time in which the friends can redecorate the lounge.
   (1 mark)

3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below. Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.
(10 marks)

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 exactly one task and each task must be done by only one worker. The time, in hours, 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 The times taken in minutes for five people, \(\mathrm { P } , \mathrm { Q } , \mathrm { R } , \mathrm { S }\) and T , to complete each of five different tasks are recorded in the table. Using the Hungarian algorithm, each of the five people is to be allocated to a different task so that the total time for completing the five tasks is minimised.

1. By reducing the columns first and then the rows, show that the new table of values is as follows.

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

2. Show that the zeros in the table in part (a) can be covered with three lines, and use adjustments to produce a table where five lines are required to cover the zeros.
3. Hence find the two possible ways of allocating the five people to the five tasks so that the total completion time is minimised.
4. Find the minimum total time for completing the five tasks.

2 The daily costs, in pounds, for five managers A, B, C, D and E to travel to five different centres are recorded in the table below. Using the Hungarian algorithm, each of the five managers is to be allocated to a different centre so that the overall total travel cost is minimised.

1. By reducing the rows first and then the columns, show that the new table of values is

   3	6	3	6	0
   4	0	6	0	2
   6	4	3	6	0
   2	3	8	3	0
   0	2	0	0	2

2. Show that the zeros in the table in part (a) can be covered with three lines and use adjustments to produce a table where five lines are required to cover the zeros.
3. Hence find the two possible ways of allocating the five managers to the five centres with the least possible total travel cost.
4. Find the value of this minimum daily total travel cost.

1. Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:

• strip the wallpaper,
• paint the woodwork and ceiling,
• hang the new wallpaper,
• replace the fittings and tidy up.

The table below shows the time, in hours, that each of the friends is likely to take to complete each job. As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.

1. Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
2. Hence find the minimum time in which the friends can redecorate the lounge.

3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below. Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.

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

The cost of assigning each worker to each task is shown in the table below.
The total cost is to be minimised.

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

An engineering company has 4 machines available and 4 jobs to be completed. Each machine is to be assigned to one job. The time, in hours, required by each machine to complete each job is shown in the table below.

	Job 1	Job 2	Job 3	Job 4
Machine 1	14	5	8	7
Machine 2	2	12	6	5
Machine 3	7	8	3	9
Machine 4	2	4	6	10

Use the Hungarian algorithm, \emph{reducing rows first}, to obtain the allocation of machines to jobs which minimises the total time required. State this minimum time. [11]