The simplex algorithmAQA A-Level Further Maths: Subtopic test

1. 1
   Maximise $P=2x+y$ subject to $x+y\leq8$, $3x+y\leq18$, $x\geq0$ and $y\geq0$. The simplex algorithm is to be used, with slack variables $r$ and $s$ added to the first and second constraints.

   (a)

   Which equation results from adding the slack variable $r$ to the constraint $x+y\leq8$?

   [1 mark]

   • A$x+y-r=8$
   • B$x+y+r=8$
   • C$x+y+r\leq8$
   • D$r=x+y+8$

   (b)

   Which entry is the pivot in the first iteration?

   [1 mark]

   • AThe 3 in the $s$ row
   • BThe 1 in the $r$ row
   • CThe $-2$ in the objective row
   • DThe 18 in the $s$ row

   (c)

   Carry out the first iteration. State the values of $x$, $y$ and $P$ after it.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   The simplex algorithm is used to maximise $P=2x+3y$ subject to $x+2y\leq14$ and $3x+y\leq18$, with slack variables $r$ and $s$. After the first iteration the equations are $\frac12x+y+\frac12r=7$, $\frac52x-\frac12r+s=11$ and $P-\frac12x+\frac32r=21$.

   (a)

   What are the values of the variables after the first iteration?

   [1 mark]

   • A$x=7$, $y=0$, $r=0$, $s=11$, $P=21$
   • B$x=0$, $y=7$, $r=11$, $s=0$, $P=21$
   • C$x=0$, $y=7$, $r=0$, $s=11$, $P=21$
   • D$x=0$, $y=7$, $r=0$, $s=11$, $P=-21$

   (b)

   What should be done next?

   [1 mark]

   • AStop, because every basic variable is positive
   • BDo another iteration with the $r$ column as the pivot column
   • CStop, because $P$ has reached 21
   • DDo another iteration with the $x$ column as the pivot column

   (c)

   Find the pivot row for the next iteration, giving a reason.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Maximise $P=4x+3y$ subject to $2x+y\leq10$, $x+y\leq8$, $x\geq0$ and $y\geq0$. The simplex algorithm is to be used with slack variables $r$ and $s$ 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]

   (b)

   Complete the simplex algorithm to find the optimal values of $x$, $y$ and $P$.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A bakery makes $x$ trays of buns and $y$ 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 $P$, with slack variables $r$, $s$ and $t$ 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]

   (b)

   (i) Interpret the final tableau in (a) in terms of the oven, the flour and the packing. (ii) The bakery also considers minimising $Q=2x-3y$ subject to the same constraints. Explain how to use the simplex algorithm for this, and find the minimum value of $Q$.

   [6 marks]

   Total for question 4: 12 marks

End of questions