AQA A-Level Further Maths
The simplex algorithm
Total 27 marks
Name
Class
Date
- 1Maximise subject to , , and . The simplex algorithm is to be used, with slack variables and added to the first and second constraints.(a)Which equation results from adding the slack variable to the constraint ?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(b)Which entry is the pivot in the first iteration?[1 mark]- AThe 3 in the row
- BThe 1 in the row
- CThe in the objective row
- DThe 18 in the row
Show the mark scheme
Mark scheme
Answer: A(c)Carry out the first iteration. State the values of , and after it.[2 marks]Show the mark scheme
Mark scheme
M1: divides the row by 3, giving (pivot on the 3)
A1: , ,
Accept: for the objective rowTotal for question 1: 4 marks
- 2The simplex algorithm is used to maximise subject to and , with slack variables and . After the first iteration the equations are , and .(a)What are the values of the variables after the first iteration?[1 mark]
- A, , , ,
- B, , , ,
- C, , , ,
- D, , , ,
Show the mark scheme
Mark scheme
Answer: C(b)What should be done next?[1 mark]- AStop, because every basic variable is positive
- BDo another iteration with the column as the pivot column
- CStop, because has reached 21
- DDo another iteration with the column as the pivot column
Show the mark scheme
Mark scheme
Answer: D(c)Find the pivot row for the next iteration, giving a reason.[2 marks]Show the mark scheme
Mark scheme
M1: ratios for the column: and
A1: pivot row is the row (pivot ), because is the smaller ratioTotal for question 2: 4 marks
- 3Maximise subject to , , and . The simplex algorithm is to be used with slack variables and added to the first and second constraints.(a)Write down the initial simplex tableau as equations, and state which entry is the pivot in the first iteration, with a reason.[3 marks]
Show the mark scheme
Mark scheme
B1: and , and
B1: pivot column , because is the most negative objective-row entry
B1: pivot is the 2 in the row, because is smaller than(b)Complete the simplex algorithm to find the optimal values of , and .[4 marks]Show the mark scheme
Mark scheme
M1: first iteration: , ,
M1: second pivot in the column, with ratios and , so the row is chosen
A1: ,
A1: , optimal because the objective row has no negative coefficientsTotal for question 3: 7 marks
- 4A bakery makes trays of buns and trays of loaves. Each tray of buns needs 3 hours of oven time, 4 kg of flour and 1 hour of packing. Each tray of loaves needs 2 hours of oven time, 1 kg of flour and 3 hours of packing. There are 23 hours of oven time, 29 kg of flour and 18 hours of packing available. The profit is £5 per tray of buns and £3 per tray of loaves. The bakery uses the simplex algorithm to maximise the profit , with slack variables , and for the oven, flour and packing constraints.(a)Use the simplex algorithm to find how many trays of each to make for the greatest profit, and the maximum profit.[6 marks]
Show the mark scheme
Mark scheme
B1: initial equations , , ,
M1: first pivot in the column, with ratios , , , so the row is chosen
A1: after the first iteration
M1: second pivot in the column, with ratios , , , so the row is chosen
A1: final objective row
A1: , , , optimal because no coefficient in the objective row is negative(b)(i) Interpret the final tableau in (a) in terms of the oven, the flour and the packing. (ii) The bakery also considers minimising subject to the same constraints. Explain how to use the simplex algorithm for this, and find the minimum value of .[6 marks]Show the mark scheme
Mark scheme
B1: (i) and , so the oven time and the flour are fully used
B1: (i) , so 8 hours of packing are unused
B1: (i) the objective row has no negative coefficients, so the plan is optimal
B1: (ii) maximise , then the minimum of is
M1: (ii) pivots on the column, with the smallest ratio in the row
A1: (ii) , , giving and a minimum valueTotal for question 4: 12 marks
End of questions