Matchings and Allocation

1 Alfred has bought six different chocolate bars. He wants to give a chocolate bar to each of his six friends. The table gives the names of the friends and indicates which of Alfred's six chocolate bars they like.

Ann, Bryn, Daljit, Gareth and Nickos have all joined a new committee. Each of them is to be allocated to one of five jobs 1, 2, 3, 4 or 5. The table shows each member's preferences for the jobs. Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.

1. Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs. [2]
2. Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path. [3]
3. Find a second alternating path from the initial allocation. [1]

1 Josh is making a calendar. He has chosen six pictures, each of which will represent two months in the calendar. He needs to choose which picture to use for each two-month period. The bipartite graph in Fig. 1 shows for which months each picture is suitable. \begin{figure}[h] \end{figure} Initially Josh chooses the sailing ships for March/April, the sunset for July/August, the snow scene for November/December and the swans for May/June. This incomplete matching is shown in Fig. 2 below. \begin{table}[h] \end{table}

1. Write down the shortest possible alternating path that starts at (JF) and finishes at either (2) or (4). Hence write down a matching that only excludes (SO) and one of the pictures.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at (SO) and finishes at whichever of (2) and (4) has still not been matched. Hence write down a complete matching between the pictures and the months.
3. Explain why three of the arcs in Fig. 1 must appear in the graph of any complete matching. Hence find a second complete matching.

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

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.

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.

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.

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.

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]

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.

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

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

Three workers, \(P\), \(Q\) and \(R\), are to be assigned to three tasks, 1, 2 and 3. Each worker is to be assigned to one task and each task must be assigned to one worker. The cost, in hundreds of pounds, of using each worker for each task is given in the table below. The cost is to be minimised.

Cost (in £100s)	Task 1	Task 2	Task 3
Worker \(P\)	8	7	3
Worker \(Q\)	9	5	6
Worker \(R\)	10	4	4

Formulate the above situation as a linear programming problem, defining the decision variables and making the objective and constraints clear. (Total 7 marks)

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.

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)

4. A furniture manufacturer has three workshops, \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\). Orders for rolls of fabric are to be placed with three suppliers, \(S _ { 1 } , S _ { 2 }\) and \(S _ { 3 }\). The supply, demand and cost per roll in pounds, according to which supplier each workshop uses, are given in the table below. Starting with the north-west corner method of finding an initial solution, find an optimal transportation pattern which minimises the total cost. State the final solution and its total cost.
(11 marks)

3. The table below shows the cost of transporting one block of staging from each of two supply points, X and Y , to each of four concert venues, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . It also shows the number of blocks held at each supply point and the number of blocks required at each concert venue. A minimal cost solution is required.

1. Use the north-west corner method to obtain a possible solution.
   (1)
2. Taking the most negative improvement index to indicate the entering square, use the stepping stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells.
3. Is your current solution optimal? Give a reason for your answer.
   (1)

3. The table below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { E } , \mathrm { F } , \mathrm { G }\) and H , to three sales points, \(\mathrm { A } , \mathrm { B }\) and C . It also shows the stock held at each supply point and the amount required at each sales point.
A minimum cost solution is required.

1. Explain why it is necessary to add a dummy demand point.
2. On Table 1 in the answer book, insert appropriate values in the dummy demand column, D. After finding an initial feasible solution and applying one iteration of the stepping-stone method, the table becomes

   	\(A\)	\(B\)	\(C\)	\(D\)
   \(E\)	21
   \(F\)	19	13
   \(G\)		6	23
   \(H\)	5			18

3. Starting with GD as the next entering cell, perform two further iterations of the stepping-stone method to obtain an improved solution. You must make your method clear by showing your routes and stating the

Define the terms

1. bipartite graph, [2]
2. alternating path, [2]
3. matching, [1]
4. complete matching. [1]

7 The table shows the times taken, in minutes, by four people, \(A , B , C\) and \(D\), to carry out the tasks \(W , X , Y\) and \(Z\). Some of the times are subject to the same delay of \(x\) minutes, where \(4 < x < 11\).

1

1. Draw a bipartite graph to represent the following adjacency matrix.

   	1	2	3	4	5
   A	0	0	0	0	1
   \(\boldsymbol { B }\)	0	0	0	1	1
   \(\boldsymbol { C }\)	0	1	0	1	1
   \(\boldsymbol { D }\)	0	0	0	1	1
   \(\boldsymbol { E }\)	1	1	1	0	1

2. If \(A , B , C , D\) and \(E\) represent five people and 1, 2, 3, 4 and 5 represent five tasks to which they are to be assigned, explain why a complete matching is impossible.
   (2 marks)

1. Draw a bipartite graph representing the following adjacency matrix. [2 marks] $$\begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\ \hline A & 1 & 0 & 0 & 0 & 1 \\ B & 0 & 1 & 1 & 1 & 0 \\ C & 0 & 1 & 1 & 1 & 0 \\ D & 1 & 0 & 0 & 0 & 1 \\ E & 1 & 0 & 0 & 0 & 1 \\ \end{array}$$
2. If \(A\), \(B\), \(C\), \(D\) and \(E\) represent five people and 1, 2, 3, 4 and 5 represent five tasks to which they are to be assigned, explain why a complete matching is impossible. [2 marks]

7. A distributor has six warehouses. At one point the distributor needs to move 25 lorries from warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) to warehouses \(W _ { \mathrm { A } } , W _ { \mathrm { B } }\) and \(W _ { \mathrm { C } }\) for the minimum possible cost. The transportation tableau below shows the unit cost, in tens of pounds, of moving a lorry between two warehouses, and the relevant figures regarding the number of lorries available or required at each warehouse.

1. Write down the initial solution given by the north-west corner rule.
2. Obtain improvement indices for the unused routes.
3. Use the stepping-stone method to find an improved solution and state why it is degenerate.
4. Placing a zero in cell \(( 2,2 )\), show that the improved solution is optimal and state the transportation pattern.
5. Find the total cost of the optimal solution. \section*{Please hand this sheet in for marking}

   Stage	State	Destination	Cost	Total cost
   \multirow[t]{3}{*}{1}	Marquee	Deluxe Cuisine
   	Castle	Deluxe Castle Cuisine
   	Hotel	Deluxe Cuisine Hotel
   \multirow[t]{3}{*}{2}	Church	Marquee Castle Hotel
   	Castle	Marquee Castle
   	Registry Office	Marquee Castle Hotel
   3	Home	Castle Church Registry

   \section*{Please hand this sheet in for marking}

   1. 	A	B	\(C\)	D	\(E\)	\(F\)	\(G\)	\(H\)
      A	-	85	59	31	47	52	74	41
      B	85	-	104	73	51	68	43	55
      C	59	104	-	54	62	88	61	45
      D	31	73	54	-	40	59	65	78
      E	47	51	62	40	-	56	71	68
      \(F\)	52	68	88	59	56	-	53	49
      \(G\)	74	43	61	65	71	53	-	63
      \(H\)	41	55	45	78	68	49	63	-

   2. 	A	\(B\)	\(C\)	D	\(E\)	\(F\)	\(G\)	\(H\)
      A	-	85	59	31	47	52	74	41
      B	85	-	104	73	51	68	43	55
      C	59	104	-	54	62	88	61	45
      D	31	73	54	-	40	59	65	78
      E	47	51	62	40	-	56	71	68
      \(F\)	52	68	88	59	56	-	53	49
      G	74	43	61	65	71	53	-	63
      \(H\)	41	55	45	78	68	49	63	-

3. Jameson cars are made in two factories A and B. Sales have been made at the two main showrooms in London and Edinburgh. Cars are to be transported from the factories to the showrooms. The table below shows the cost, in pounds, of transporting one car from each factory to each showroom. It also shows the number of cars available at each factory and the number required at each showroom. It is decided to use the transportation algorithm to obtain a minimal cost solution.

1. Explain why it is necessary to add a dummy demand point.
2. Complete the table below.

   	L	E	Dummy	Supply
   A	80	70		55
   B	60	50		45
   Demand	35	60		100

3. Use the north-west corner rule to obtain a possible pattern of distribution.
   (1)
4. Taking the most negative improvement index to indicate the entering square, use the stepping-stone method to obtain an optimal solution. You must make your shadow costs and improvement indices clear and demonstrate that your solution is optimal.
   (7)
5. State the cost of your optimal solution.
   (1) (Total 13 marks)

6. The table below shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { X } , \mathrm { Y }\) and Z to three demand points, \(\mathrm { A } , \mathrm { B }\) and C . It also shows the stock held at each supply point and the stock required at each demand point.

1. This is a balanced problem. Explain what this means.
2. Use the north west corner method to obtain a possible solution.
3. Taking ZA as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear and state your exiting cell.
4. Perform one more iteration of the stepping-stone method to find a further improved solution. You must make your shadow costs, improvement indices, entering cell, exiting cell and route clear.
5. State the cost of the solution you found in part (d).

1 Arnie (A), Brigitte (B), Charles (C), Diana (D), Edward (E) and Faye (F) are moving into a home for retired Hollywood stars. They all still expect to be treated as stars and each has particular requirements. Arnie wants a room that can be seen from the road, but does not want a ground floor room; Brigitte wants a room that looks out onto the garden; Charles wants a ground floor room; Diana wants a room with a balcony; Edward wants a second floor room; Faye wants a room, with a balcony, that can be seen from the road. The table below shows the features of each of the six rooms available.

1. Draw a bipartite graph to show the possible pairings between the stars ( \(A , B , C , D , E\) and \(F\) ) and the rooms ( \(1,2,3,4,5\) and 6 ). Originally Arnie was given room 4, Brigitte was given room 3, Charles was given room 2, Diana was given room 5, Edward was given room 6 and Faye was given room 1.
2. Identify the star that has not been given a room that satisfies their requirements. Draw a second bipartite graph to show the incomplete matching that results when this star is not given a room.
3. Construct the shortest possible alternating path, starting from the star without a room and ending at the room that was not used, and hence find a complete matching between the stars and the rooms. Write a list showing which star should be given which room. When the stars view the rooms they decide that some are much nicer than others. Each star gives each room a value from 1 to 6 , where 1 is the room they would most like and 6 is the room they would least like. The results are shown below.

   \multirow{2}{*}{}	Room
   	1	2	3	4	5	6
   Arnie (A)	3	6	4	1	5	2
   Brigitte ( \(B\) )	5	3	2	4	1	6
   Charles (C)	2	1	3	4	5	6
   Diana (D)	5	4	1	3	2	6
   Edward ( \(E\) )	5	6	4	3	2	1
   Faye (F)	5	6	4	1	3	2

4. Apply the Hungarian algorithm to this table, reducing rows first, to find a minimum 'cost' allocation between the stars and the rooms. Write a list showing which star should be given which room according to this allocation. Write down the name of any star whose original requirements are not satisfied.

2. (a) (i) Define the term complete matching.
(ii) Explain the difference between a complete matching and a maximal matching.
(3) \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of dancing partners for the Truly Come Ballroom dancing competition. Six women, Annie (A), Bella (B), Chloe (C), Danika (D), Ella (E) and Faith (F), are to be paired with six men, Kieran (K), Lucas (L), Michael (M), Nasir (N), Oliver (O) and Paul (P). Figure 2 shows an initial matching.
(b) Use the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and list your improved matching.
(3) After dance practice, it is decided that Bella could also be paired with Kieran, and Danika could also be paired with Nasir.
(c) Starting with your improved matching from part (b), use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and list your final matching.

Six people, \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake. \includegraphics{figure_1}

1. Represent this information in an adjacency matrix. [2]
2. Initially, \(B\) is assigned to task 5, \(D\) to task 2, \(E\) to task 4 and \(F\) to task 3. Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task. [5]

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Five members of staff \(1,2,3,4\) and 5 are to be matched to five jobs \(A , B , C , D\) and \(E\). A bipartite graph showing the possible matchings is given in Fig. 1 and an initial matching \(M\) is given in Fig. 2. There are several distinct alternating paths that can be generated from \(M\). Two such paths are $$2 - B = 4 - E$$ and $$2 - A = 3 - D = 5 - E$$

1. Use each of these two alternating paths, in turn, to write down the complete matchings they generate. Using the maximum matching algorithm and the initial matching \(M\),
2. find two further distinct alternating paths, making your reasoning clear. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-4_577_1476_367_333}
   \end{figure} Figure 3 shows the network of paths in a country park. The number on each path gives its length in km . The vertices \(A\) and \(I\) represent the two gates in the park and the vertices \(B , C , D , E , F , G\) and \(H\) represent places of interest.