The Simplex algorithmEdexcel A-Level Further Maths: Subtopic test

1. 1
   A firm makes $x$ units of product X and $y$ units of product Y. It wishes to maximise the profit $P=2x+3y$ subject to $x+y\le10$ and $x+2y\le16$, with $x\ge0$ and $y\ge0$. Slack variables $r$ and $s$ are added to the first and second constraints and the Simplex algorithm is used.

   (a)

   Which equation is the objective row of the initial tableau?

   [1 mark]

   • A$P+2x+3y=0$
   • B$P-2x-3y=10$
   • C$P-2x-3y-r-s=0$
   • D$P-2x-3y=0$

   (b)

   Which element is the first pivot?

   [1 mark]

   • Athe $1$ in the $y$ column of the $r$ row
   • Bthe $1$ in the $x$ column of the $r$ row
   • Cthe $2$ in the $y$ column of the $s$ row
   • Dthe $1$ in the $x$ column of the $s$ row

   (c)

   State which variable enters the basis and which leaves, and write down the new pivot row after the first iteration.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A maximising problem in $x$ and $y$, with slack variables $r$ and $s$, has been partly solved by the Simplex algorithm. The current tableau has columns in the order $x$, $y$, $r$, $s$, then the value:
   r row: $\frac12$, $0$, $1$, $-\frac12$ | $2$
   y row: $\frac12$, $1$, $0$, $\frac12$ | $8$
   P row: $-\frac12$, $0$, $0$, $\frac32$ | $24$

   (a)

   Which statement about this tableau is correct?

   [1 mark]

   • AIt is not optimal, because there is a negative value in the $P$ row
   • BIt is optimal, because $P=24$ is positive
   • CIt is not optimal, because there is a negative value in the $r$ row
   • DIt is optimal, because every value in the value column is positive

   (b)

   Which element is the next pivot?

   [1 mark]

   • Athe $\frac12$ in the $x$ column of the $y$ row
   • Bthe $-\frac12$ in the $s$ column of the $r$ row
   • Cthe $-\frac12$ in the $x$ column of the $P$ row
   • Dthe $\frac12$ in the $x$ column of the $r$ row

   (c)

   Perform the next iteration and state the optimal values of $x$, $y$ and $P$.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A firm makes $x$, $y$ and $z$ units of three products each day. Three resources give the constraints $2x+3y+z\le5$, $4x+y+2z\le11$ and $3x+4y+2z\le8$, with $x,y,z\ge0$. The profit is $P=5x+4y+3z$ and the firm wishes to maximise it. Slack variables $r$, $s$ and $t$ are added to the three constraints in order.

   (a)

   Write down the initial Simplex tableau.

   [3 marks]

   (b)

   Perform one complete iteration of the Simplex algorithm, showing the new tableau, and explain why the solution is not yet optimal.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A recycling plant processes $x$, $y$ and $z$ tonnes of three types of waste each day. Capacity limits give $x+y+z\le12$ and $2x+y+3z\le18$, with $x,y,z\ge0$. After income from by-products, the net cost in hundreds of pounds is $C=2x-3y-4z$, which the plant wishes to minimise. Slack variables $r$ and $s$ are added to the two constraints.

   (a)

   (i) Explain how to convert this to a maximising problem and write down the initial tableau.
   (ii) Carry out the first iteration and give the new tableau.

   [6 marks]

   (b)

   (i) Continue the Simplex algorithm until an optimal tableau is reached.
   (ii) State the optimal values of $x$, $y$, $z$ and the minimum value of $C$, and explain how you know the solution is optimal.

   [6 marks]

   Total for question 4: 12 marks

End of questions