Discrete Mathematics 4: Linear programmingAQA A-Level Further Maths: Topic test

1. 1
   A charity packs two types of hamper for a fair. Each soup hamper (there are $x$ of them) uses 4 tins and 2 jars, and each preserves hamper (there are $y$ of them) uses 3 tins and 5 jars. The charity has 120 tins and 130 jars. It raises £6 for each soup hamper and £9 for each preserves hamper, and it will make at least 5 preserves hampers.

   (a)

   Which inequality represents the number of jars available?

   [1 mark]

   • A$5x+2y\leq130$
   • B$2x+5y\leq130$
   • C$2x+5y\geq130$
   • D$7(x+y)\leq130$

   (b)

   Which of these points satisfies every constraint?

   [1 mark]

   • A$(25,10)$
   • B$(10,25)$
   • C$(30,4)$
   • D$(20,10)$

   (c)

   Find the coordinates of the point where the lines $4x+3y=120$ and $2x+5y=130$ meet.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A nursery mixes two plant feeds. Each bag of feed $X$ (there are $x$ bags) supplies 2 units of nitrogen and 1 unit of potassium, and each bag of feed $Y$ (there are $y$ bags) supplies 1 unit of nitrogen and 3 units of potassium. At least 16 units of nitrogen and at least 18 units of potassium are needed. A bag of $X$ costs £3 and a bag of $Y$ costs £2, and the nursery wants to minimise the total cost $C$ in pounds.

   (a)

   Which inequality represents the potassium requirement?

   [1 mark]

   • A$x+3y\geq18$
   • B$x+3y\leq18$
   • C$3x+y\geq18$
   • D$2x+y\geq16$

   (b)

   Which statement about the feasible region is correct?

   [1 mark]

   • AIt is a bounded region containing the origin.
   • BIt is a bounded quadrilateral with a vertex at the origin.
   • CIt is an unbounded region lying on the far side of both lines from the origin.
   • DIt is an unbounded region lying between the axes and both lines.

   (c)

   Find the minimum possible cost, and the numbers of bags of $X$ and $Y$ that give it.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   The simplex algorithm is used to maximise $P=5x+4y$ subject to $x+y\leq10$, $2x+y\leq16$, $x\geq0$ and $y\geq0$. Slack variables $r$ and $s$ are added so that $x+y+r=10$ and $2x+y+s=16$, and the initial tableau has rows for $r$, $s$ and $P$.

   (a)

   Carry out the first iteration, pivoting on the column with the most negative entry in the $P$ row. Give the new value of $P$ and explain why the solution is not yet optimal.

   [3 marks]

   (b)

   Carry out the second iteration. State the optimal values of $x$, $y$ and $P$ and explain how you know the solution is optimal.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A print shop makes $x$ batches of flyers and $y$ batches of brochures each day. A batch of flyers needs 3 hours on the printing press and 1 hour of finishing. A batch of brochures needs 2 hours on the press and 2 hours of finishing. The press can be used for at most 42 hours and finishing for at most 22 hours each day. The profit is £40 per batch of flyers and £30 per batch of brochures.

   (a)

   Formulate this as a linear programming problem and use a graphical method to find the maximum daily profit.

   [6 marks]

   (b)

   Use the simplex algorithm with slack variables $r$ and $s$ for the press and finishing constraints, starting with the initial tableau and pivoting on the most negative entry in the $P$ row each time, to find the optimal solution. Interpret the entries in the $r$ and $s$ columns of the final $P$ row.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   A school hires $x$ minibuses and $y$ coaches for a trip. A minibus holds 16 pupils and costs £70, and a coach holds 50 pupils and costs £200. At least 180 pupils must travel. At most 8 minibuses and at most 5 coaches are available. The school wants to minimise the total cost $C$ in pounds.

   (a)

   Which inequality represents the number of pupils who must travel?

   [1 mark]

   • A$16x+50y\leq180$
   • B$50x+16y\geq180$
   • C$66(x+y)\geq180$
   • D$16x+50y\geq180$

   (b)

   Which of these combinations of vehicles provides enough seats at the lowest cost?

   [1 mark]

   • A0 minibuses and 4 coaches
   • B7 minibuses and 1 coach
   • C5 minibuses and 2 coaches
   • D3 minibuses and 3 coaches

   (c)

   Complete the formulation by writing down the objective function and the two inequalities for the numbers of vehicles available.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   Maximise $Q=5x+3y$ subject to $3x+y\leq18$, $x+2y\leq16$, $x\geq0$ and $y\geq0$.

   (a)

   At which point do the lines $3x+y=18$ and $x+2y=16$ meet?

   [1 mark]

   • A$(4,6)$
   • B$(6,4)$
   • C$(2,12)$
   • D$(8,4)$

   (b)

   The objective is changed to $Q=x+4y$. Which vertex of the feasible region now gives the maximum value?

   [1 mark]

   • A$(6,0)$
   • B$(0,8)$
   • C$(4,6)$
   • D$(0,0)$

   (c)

   Find the maximum value of $Q=5x+3y$ and the point at which it occurs.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   The simplex algorithm is used to maximise $P=6x+5y$ subject to $2x+3y\leq24$, $4x+y\leq28$, $x\geq0$ and $y\geq0$. Slack variables $r$ and $s$ are added so that $2x+3y+r=24$ and $4x+y+s=28$. After the first iteration, the rows are $x+\frac14y+\frac14s=7$, $\frac52y+r-\frac12s=10$ and $P-\frac72y+\frac32s=42$.

   (a)

   Write down the values of $x$, $y$, $r$, $s$ and $P$ at this stage. Explain why the solution is not optimal and identify the next pivot, justifying your choice.

   [3 marks]

   (b)

   Carry out the next iteration and state the optimal solution. Interpret the entry $\frac75$ in the $r$ column of the final $P$ row.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   A market gardener grows $x$ trays of tomato plants and $y$ trays of pepper plants. A tray of tomato plants needs 3 hours of labour and 1 square metre of bench space. A tray of pepper plants needs 2 hours of labour and 2 square metres of bench space. There are 36 hours of labour and 24 square metres of bench space available. The profit is £25 per tray of tomato plants and £40 per tray of pepper plants.

   (a)

   Formulate this as a linear programming problem and use a graphical method to find the maximum profit.

   [6 marks]

   (b)

   The simplex algorithm gives a final tableau with rows $x+\frac12r-\frac12s=6$, $y-\frac14r+\frac34s=9$ and $P+\frac52r+\frac{35}{2}s=510$, where $r$ and $s$ are the slack variables for labour and bench space. Interpret this tableau, and use it to estimate the optimal profit and the optimal numbers of trays if the bench space is increased to 26 square metres.

   [6 marks]

   Total for question 8: 12 marks

End of questions