Two-stage Simplex and big-M methodsEdexcel A-Level Further Maths: Subtopic test

1. 1
   A maximising problem has the constraint $2x+y\ge8$, to which a surplus variable $s$ and an artificial variable $t$ are added. The objective is $P=3x+2y$ and the big-M method is used, where $M$ is a very large positive number.

   (a)

   Which equation is the constraint after $s$ and $t$ are introduced?

   [1 mark]

   • A$2x+y-s+t=8$
   • B$2x+y+s+t=8$
   • C$2x+y-s=8$
   • D$2x+y+s-t=8$

   (b)

   Which is the objective function used in the big-M method?

   [1 mark]

   • A$P=3x+2y+Mt$
   • B$P=3x+2y-Mt$
   • C$P=3x+2y-Ms$
   • D$P=3x+2y-M$

   (c)

   Explain the purpose of the term $-Mt$, and what it means if $t>0$ in the final optimal tableau.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A maximising problem has the constraints $x+y\le6$ and $x+y\ge9$, with $x,y\ge0$. It is solved using the two-stage Simplex method, with a slack variable $s_1$ in the first constraint and a surplus variable $s_2$ and an artificial variable $t$ in the second.

   (a)

   What is the minimum value of the stage 1 objective $I=t$?

   [1 mark]

   • A$0$
   • B$6$
   • C$9$
   • D$3$

   (b)

   What does the end of stage 1 show?

   [1 mark]

   • AThe optimal solution is $x=6$, $y=0$
   • BThe problem is unbounded
   • CThe problem has no feasible solution
   • DStage 2 starts from $x=y=0$

   (c)

   Explain, without using the Simplex algorithm, why the stage 1 result is correct.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A company makes $x$ tonnes of product X and $y$ tonnes of product Y. It wishes to maximise the profit $P=3x+4y$ subject to $x+y\le12$ and $x+2y\ge6$, with $x\ge0$ and $y\ge0$. The big-M method is used, with slack variable $s_1$, surplus variable $s_2$ and artificial variable $t$. Tableau columns are in the order $x$, $y$, $s_1$, $s_2$, $t$, then the value.

   (a)

   Write the constraints as equations and write down the objective function for the big-M method.

   [3 marks]

   (b)

   Eliminate $t$ from the objective row to find the $P$ row of the initial tableau, and hence identify the first pivot.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A company maximises $P=2x+5y$ subject to $x+y\le10$ and $3x+y\ge6$, with $x,y\ge0$. The two-stage Simplex method is used, with slack variable $s_1$, surplus variable $s_2$ and artificial variable $t$. In stage 1 the aim is to minimise $I=t$, which is done by maximising $Q=-t$. Tableau columns are in the order $x$, $y$, $s_1$, $s_2$, $t$, then the value.

   (a)

   (i) Write the constraints as equations and the stage 1 objective row, with $t$ eliminated. Carry the $P$ row through stage 1.
   (ii) Perform the first iteration of stage 1 and write down the new tableau. State what it shows.

   [6 marks]

   (b)

   (i) Carry out stage 2 until an optimal tableau is reached.
   (ii) State the optimal solution and verify that it satisfies both constraints.

   [6 marks]

   Total for question 4: 12 marks

End of questions