Edexcel A-Level Further Maths
The Hungarian algorithm
Total 27 marks
Name
Class
Date
- 1A firm has three engineers, Ana, Ben and Cleo, and three tasks: wiring (W), testing (T) and installing (I). Each engineer must do exactly one task and each task is done by exactly one engineer. The cost, in £, of each engineer doing each task is given by the matrix , where the rows are Ana, Ben, Cleo and the columns are W, T, I. The firm wants the total cost to be as small as possible.(a)The rows are reduced first. What is the entry for Ben doing task W in the row-reduced matrix?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(b)The rows and then the columns are reduced. What is the minimum number of straight lines needed to cover every zero in the reduced matrix?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(c)Complete the Hungarian algorithm to find the allocation with the least total cost, and state that cost.[2 marks]Show the mark scheme
Mark scheme
M1: smallest uncovered entry subtracted from every uncovered entry and added to the entry covered twice, giving
A1: Ana–I, Ben–W, Cleo–T with total cost £
Accept: the cost found from the original matrix,
Do not accept: a total found from the reduced matrixTotal for question 1: 4 marks
- 2A company has three sales representatives, Dev, Eli and Fay, to send to three regions: North, South and East. Each representative goes to a different region. The expected monthly profit, in £ thousand, of each representative in each region is given by the matrix , where the rows are Dev, Eli, Fay and the columns are North, South, East. The company wants the total profit to be as large as possible and uses the Hungarian algorithm.(a)The matrix is converted so that the algorithm can find a minimum. What is the entry for Dev in North in the converted matrix?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(b)What is the maximum total expected profit, in £ thousand?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(c)A trainee applies the Hungarian algorithm directly to the original profit matrix, with no conversion. Explain why the allocation found would not be the one the company wants.[2 marks]Show the mark scheme
Mark scheme
B1: the Hungarian algorithm finds the allocation with the least total
B1: so the trainee would find the allocation with the least total profit, not the greatest
Do not accept: 'it gives the wrong answer' with no reasonTotal for question 2: 4 marks
- 3A courier firm has four drivers, P, Q, R and S, and three deliveries, X, Y and Z. Each delivery is made by exactly one driver and each driver makes at most one delivery. The cost, in £, of each driver making each delivery is given by the matrix , where the rows are P, Q, R, S and the columns are X, Y, Z. The firm wants the total cost to be as small as possible.(a)A dummy delivery is added so that the Hungarian algorithm can be used. Explain why this is needed, and state what should be entered in the dummy column.[3 marks]
Show the mark scheme
Mark scheme
B1: the algorithm needs a square matrix and there are 4 drivers but only 3 deliveries
B1: every entry in the dummy column is the same, e.g.
B1: the driver matched with the dummy delivery makes no real delivery and adds no cost
Accept: any equal constant in the dummy column
Do not accept: different values for different drivers(b)Use the Hungarian algorithm on the 4 by 4 matrix to find which delivery each driver makes and the least total cost. State which driver makes no delivery.[4 marks]Show the mark scheme
Mark scheme
M1: rows already contain a zero (the dummy), so reduce the columns by to get
A1: three lines (the dummy column and rows P and Q) cover the zeros, fewer than 4, so augment: subtract from uncovered entries, add to those covered twice, giving
M1: allocation from the zeros: P–X, Q–Y, S–Z, R–dummy
A1: total cost £, and R makes no delivery
Accept: the lines drawn differently, if they still cover all zeros with three lines
Accept: a total found fromTotal for question 3: 7 marks
- 4A garage has four mechanics, Kai, Lou, Mia and Ned, and four repair jobs, J1, J2, J3 and J4. Each mechanic does exactly one job. The cost, in £, of each mechanic doing each job is given below in the order J1, J2, J3, J4, where a dash means the mechanic is not qualified for that job. Kai: 44, 23, –, 40. Lou: 28, 43, 45, 34. Mia: 45, 23, 49, 48. Ned: 26, 39, 47, 30. The garage wants the total cost to be as small as possible.(a)Use the Hungarian algorithm, dealing with the missing entry, to find an allocation with the least total cost, and state that cost.[6 marks]
Show the mark scheme
Mark scheme
B1: a very large number entered for Kai doing J3
M1: rows reduced by subtracting the row minima ()
A1: columns reduced by to give
M1: three lines cover the zeros (J2 column, and the rows of Lou and Ned), fewer than 4, so augment using the smallest uncovered entry
A1: smallest uncovered entry used, giving
A1: Kai–J2, Lou–J1, Mia–J3, Ned–J4 with total cost £
Accept: any large number in place of(b)The garage can train Kai to do J3 at a cost of £ for the job, with the training costing £. Use the Hungarian algorithm to decide whether the training is worthwhile.[6 marks]Show the mark scheme
Mark scheme
M1: replaces and the row minima are subtracted
M1: columns reduced by
A1: reduced matrix
M1: allocation read from the zeros (a complete allocation exists, so no augmenting is needed): Kai–J3, Lou–J1, Mia–J2, Ned–J4
A1: total cost £
R1: saving of is greater than the training cost of , so the training is worthwhile (net saving £)
Accept: comparing £ with £Total for question 4: 12 marks
End of questions