Edexcel A-Level Further Maths
Hungarian algorithm as a linear programme
Total 27 marks
Name
Class
Date
- 1A hospital assigns three nurses, 1, 2 and 3, to three wards, 1, 2 and 3, with one nurse on each ward. Let if nurse is assigned to ward , and otherwise. The cost, in £ hundred, of nurse on ward is the entry in row , column of . The hospital wants the total cost to be as small as possible and formulates the problem as a linear programme.(a)What does mean?[1 mark]
- ANurse 3 is assigned to ward 2
- BWard 2 costs £ hundred
- CNurse 2 is assigned to ward 3
- DNurse 2 is not assigned to ward 3
Show the mark scheme
Mark scheme
Answer: C(b)What is the total cost, in £ hundred, when and all other variables are ?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(c)Write down the constraint that ensures nurse 2 is assigned to exactly one ward, and state the values each may take.[2 marks]Show the mark scheme
Mark scheme
B1:
B1: each is or (binary)
Accept: and integer, since the constraints then force
Do not accept:Total for question 1: 4 marks
- 2A company has four representatives and four regions. Let be the profit, in £ hundred, when representative works in region , and let if representative is sent to region and otherwise. Each representative goes to exactly one region and each region receives exactly one representative. The company wants to maximise the total profit and formulates the problem as a linear programme.(a)Which of these is the objective function?[1 mark]
- AMinimise
- BMaximise
- CMaximise
- DMaximise
Show the mark scheme
Mark scheme
Answer: D(b)How many equality constraints (not counting the conditions on the values of ) does the formulation have?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(c)The allocation , with all other variables , has , , and . Show that this allocation satisfies the constraints for representative 1 and for region 1, and find its total profit.[2 marks]Show the mark scheme
Mark scheme
B1: representative 1: and region 1:
B1: total profit , that is £
Accept: with the units £ hundredTotal for question 2: 4 marks
- 3A firm has four workers and three tasks. Each task must be done by exactly one worker and each worker does at most one task. The time, in hours, for worker to do task is the entry in row , column of . The firm wants the total time to be as small as possible and formulates the problem as a linear programme.(a)Define suitable variables and write down the objective function.[3 marks]
Show the mark scheme
Mark scheme
B1: if worker does task , and otherwise
M1: minimise the sum of (time variable) over the pairings
A1: minimise
Do not accept: maximise(b)Write down the constraints, and explain why the constraints for the workers are not all equalities.[4 marks]Show the mark scheme
Mark scheme
B1: each task done exactly once: , ,
B1: each worker does at most one task: , , ,
R1: there are four workers but only three tasks, so one worker has no task; equalities for every worker could not all be satisfied
B1:Total for question 3: 7 marks
- 4A theatre has three technicians, Raj, Sam and Tess, and three tasks: lighting (1), sound (2) and staging (3). Each technician does one task and each task is done by one technician. The value, in £ hundred, of each technician on each task is given below in the order lighting, sound, staging. Raj: 14, 11, 9. Sam: 8, 13, – (Sam cannot do staging). Tess: 10, 7, 12. The theatre wants the total value to be as large as possible. Technicians Raj, Sam and Tess are numbered 1, 2 and 3.(a)Formulate this as a linear programming problem.[6 marks]
Show the mark scheme
Mark scheme
B1: if technician does task , and otherwise
B1: maximise
B1: with no term
B1: each technician does one task: , ,
B1: each task done once: , ,
B1:
Accept: kept, with as an extra constraint(b)The booking system means that Raj on lighting and Tess on staging cannot both be chosen. (i) Write this as a constraint. (ii) Explain why the Hungarian algorithm cannot now be used. (iii) Given that without this condition the maximum total value is £, find the new maximum and the allocation.[6 marks]Show the mark scheme
Mark scheme
B1: (i)
R1: (ii) this is not a one-technician or one-task constraint, so the problem is no longer a pure assignment problem
M1: (iii) the unrestricted best allocation breaks the constraint
M1: the other feasible allocations have values , and (£, £, £)
A1: best allocation : Raj staging, Sam sound, Tess lighting
A1: maximum value £
Accept: £ hundredTotal for question 4: 12 marks
End of questions