Figure 5 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.
The objective is to maximise \(P = 11x + ky\), where \(k\) is a positive constant.
The optimal value of \(P\) is to be found using the big-M method.
(a) Set up an initial tableau for solving this linear programming problem using the big-M method. You should use exactly 2 slack variables, 2 surplus variables and 2 artificial variables. (7)
After a third iteration of the big-M method, a possible tableau is
b.v.
\(x\)
\(y\)
\(s_1\)
\(s_2\)
\(s_3\)
\(s_4\)
\(a_1\)
\(a_2\)
Value
\(s_1\)
0
0
1
0
\(\dfrac{9}{7}\)
\(-\dfrac{1}{7}\)
0
\(-\dfrac{9}{7}\)
\(\dfrac{78}{7}\)
\(x\)
1
0
0
0
\(\dfrac{1}{7}\)
\(\dfrac{3}{7}\)
0
\(-\dfrac{1}{7}\)
\(\dfrac{18}{7}\)
\(y\)
0
1
0
0
\(-\dfrac{3}{7}\)
\(-\dfrac{2}{7}\)
0
\(\dfrac{3}{7}\)
\(\dfrac{2}{7}\)
\(s_2\)
0
0
0
1
\(\dfrac{1}{7}\)
\(\dfrac{3}{7}\)
−1
\(-\dfrac{1}{7}\)
\(\dfrac{11}{7}\)
\(P\)
0
0
0
0
\(\frac{11}{7} - \frac{3}{7}k\)
\(\frac{33}{7} - \frac{2}{7}k\)
\(M\)
\(M - \frac{11}{7} + \frac{3}{7}k\)
\(\frac{198}{7} + \frac{2}{7}k\)
(b) Given that the third iteration gives the optimal value for \(P\), determine this value. (5)
If correct they must use two slack, two surplus and two artificial variables. Accept alternative letters for these as long as the artificial variables are clearly identifiable
Please check suffices on \(s\) and \(a\) terms carefully – they may be in a different order – check that these are consistent
a1B1: Correctly re-writing the two \(\leqslant\) inequalities as equations with slack variables (can be implied by the corresponding two correct rows in Simplex tableau – our row 1 and 4)
a2B1: Correctly re-writing one of the \(\geqslant\) inequalities as an equation with surplus and artificial variables (can be implied by a correct corresponding row in Simplex tableau – our row 2 or 3)
a3B1: Correctly re-writing both \(\geqslant\) inequalities
a1M1: Forming an objective of the form \(P = 11x + ky - M(a_1 + a_2)\) and substituting for \(a_1\) and \(a_2\) (we must see the substitution but this does not need to be a correct expression for this mark)
a1A1: CAO for new objective (accept equivalent equation with terms in \(x\) and \(y\) collected) (M1 A1 may be implied by a correct objective row in the tableau)
a2M1: Any two rows correct on the ft from the candidate’s stated equations (ignore b.v. for this mark)
a2A1: CAO (including consistent b.v. column) – note that the candidate’s order in which the rows appear in the tableau (and choice of slack variable) may be different
A fully correct tableau implies all marks in (a) provided that there are no errors seen in the formation of the objective function
Mark scheme (b)
Scheme
Marks
AO
Using \(x = \frac{18}{7},\ y = \frac{2}{7}\) or stating \(P = \frac{198}{7} + \frac{2}{7}k\)
B1
3.4
If optimal after the third iteration, then \(\frac{11}{7} - \frac{3}{7}k \geqslant 0\) and \(\frac{33}{7} - \frac{2}{7}k \geqslant 0\)
M1
3.1a
\((0 \lt)\ k \leqslant \frac{11}{3}\)
A1
2.2a
Maximum \(P\) when \(k = \frac{11}{3}\) and \(P = 11\left(\frac{18}{7}\right) + \frac{11}{3}\left(\frac{2}{7}\right)\)
dM1
3.4
Optimal value of \(P\) is \(\frac{88}{3}\) accept answers from a stated value of k from \((0 \lt)\ k \leqslant \frac{11}{3}\) so \(\frac{198}{7} \lt P \leqslant \frac{88}{3}\)
A1
2.2a
(5)
(12 marks)
Notes
b1B1: Either using the correct values of \(x\) and \(y\) in the objective function or stating \(P = \frac{198}{7} + \frac{2}{7}k\)
b1M1: Considering at least one of the expressions (\(s_3\) or \(s_4\) columns) in the \(P\) row that involve \(k\) and compare with 0 (accept any correct inequality or equals)
b1A1: Correct range of values for \(k\) (condone missing 0 < ) but must have considered both possibilities and chosen 11/3 (may be implied by subsequent working) (allow \(k\) = 11/3 stated as the maximum value)
b2dM1:Dependent on previous M mark – using their \(k\) in given \(P\) which must come from a correct inequality or equation (they may choose a value of \(k\) from the correct range e.g. \(k = 3\))
b2A1: CAO - Correct value of \(P\) for their choice of \(k\) (accept answers in the range \(\frac{198}{7} \lt P \leqslant \frac{88}{3}\) if \(k = 3\) \(P = 204/7\))
5. Consider the following linear programming problem in \(x\), \(y\) and \(z\).
Maximise \(P = 3x + 4y + 2z\)
subject to \[\begin{aligned} 2x + 2y + 2z &\leqslant 21 \\ 2x - y - z &\leqslant 18 \\ -3x + y - 2z &\leqslant 1 \end{aligned}\] \[x \geqslant 4 \qquad y \geqslant 1 \qquad z \leqslant -3\]
(a) Explain why the Simplex algorithm cannot be used to solve this linear programming problem in its current form. (1)
(b) Use the substitutions \(x = X + 4,\ y = Y + 1,\ z = -Z - 3\) and \(P = Q + 10\) to reformulate the linear programming problem into a form in which the Simplex algorithm can be used to solve the problem. You should write the constraints as simplified inequalities with integer coefficients. (3)
After a second iteration of the Simplex algorithm, a possible tableau \(T\) is
b.v.
\(X\)
\(Y\)
\(Z\)
\(s_1\)
\(s_2\)
\(s_3\)
Value
\(X\)
1
0
\(-\dfrac{3}{4}\)
\(\dfrac{1}{8}\)
0
\(-\dfrac{1}{4}\)
\(\dfrac{5}{8}\)
\(s_2\)
0
0
\(\dfrac{9}{4}\)
\(\dfrac{1}{8}\)
1
\(\dfrac{3}{4}\)
\(\dfrac{117}{8}\)
\(Y\)
0
1
\(-\dfrac{1}{4}\)
\(\dfrac{3}{8}\)
0
\(\dfrac{1}{4}\)
\(\dfrac{63}{8}\)
\(Q\)
0
0
\(-\dfrac{5}{4}\)
\(\dfrac{15}{8}\)
0
\(\dfrac{1}{4}\)
\(\dfrac{267}{8}\)
(c) Write down the profit equation given by \(T\). (1)
(d) Using your answer to (c), explain why \(T\) is not optimal. (1)
(e)
(i) Perform the third iteration of the Simplex algorithm. You should state the row operations you use.
(ii) Hence determine the maximum value of \(P\), and the corresponding values of \(x\), \(y\) and \(z\). (6)
Mark scheme (a)
Scheme
Marks
AO
The Simplex algorithm cannot be used as the problem has no obvious basic feasible solution since the origin is not in the feasible region
Alternatively
Simplex can only be used with non-negative values of variables
B1
3.5b
(1)
Notes
a1B1: Correct reason why Simplex cannot be used to solve the LP problem. Please mark positively and award if a correct statement is seen. SC accept Because \(z \leqslant -3\) (and variables must be \(\geqslant 0\))
b1M1: Substituting given equations into all three given inequalities to form inequalities or equations with slack variables in terms of \(X\), \(Y\) and \(Z\) (condone at most two slips but see Special Case below)
b1A1: At least two of the four expressions simplified correctly (three inequalities and the new objective) (accept any equivalent rearrangement but the objective must be in terms of \(Q\) not \(P\)) (accept equations with slack variables)
b2A1: CAO (must be inequalities)
Special Case (b) If they make a consistent error when substituting by using an incorrect expression for \(X\), \(Y\) or \(Z\) (e.g. substituting \(x = X + 1\) instead of \(x = X + 4\) in all terms) they may score M1 A1 (for at least two of their four expressions correct) A0
\(Q = \frac{5}{4}Z - \frac{15}{8}s_1 - \frac{1}{4}s_3 + \frac{267}{8}\) so therefore, we can increase the profit by increasing \(Z\)
B1
2.4
(1)
Notes
d1B1: CAO (Must include mention that \(Z\) can be increased but do not award if any incorrect statement seen) Do not accept just a statement that the objective row contains a negative value and therefore it is not optimal
Mark scheme (e)
Scheme
Marks
AO
(i)
b.v.
\(X\)
\(Y\)
\(Z\)
\(s_1\)
\(s_2\)
\(s_3\)
Value
Row Ops
\(X\)
1
0
0
\(\dfrac{1}{6}\)
\(\dfrac{1}{3}\)
0
\(\dfrac{11}{2}\)
\(\text{r}1 + \frac{3}{4} \times R2\)
\(Z\)
0
0
1
\(\dfrac{1}{18}\)
\(\dfrac{4}{9}\)
\(\dfrac{1}{3}\)
\(\dfrac{13}{2}\)
\(\frac{4}{9} \times \text{r}2\)
\(Y\)
0
1
0
\(\dfrac{7}{18}\)
\(\dfrac{1}{9}\)
\(\dfrac{1}{3}\)
\(\dfrac{19}{2}\)
\(\text{r}3 + \frac{1}{4} \times R2\)
\(Q\)
0
0
0
\(\dfrac{35}{18}\)
\(\dfrac{5}{9}\)
\(\dfrac{2}{3}\)
\(\dfrac{83}{2}\)
\(\text{r}4 + \frac{5}{4} \times R2\)
B1 M1 A1 A1
1.1b 2.1 1.1b 1.1b
(ii) \(X = \frac{11}{2},\ Y = \frac{19}{2},\ Z = \frac{13}{2},\ Q = \frac{83}{2}\) \((X = 5.5\ \ Y = 9.5\ \ Z = 6.5\ \ Q = 41.5)\) \(x = \frac{19}{2},\ y = \frac{21}{2},\ z = -\frac{19}{2},\ P = \frac{103}{2}\) \((x = 9.5\ \ y = 10.5\ \ z = -9.5\ \ P = 51.5)\)
M1 A1ft
3.4 2.2a
(6)
(12 marks)
Notes
Note – accept correct recurring decimals in place of fractions or any equivalent fractions
ei1B1: Pivot row (\(Z\) row) correct including change of b.v. (ignore row ops)
ei1M1:All values in one of the non-pivot rows correct or one of the non zero and one columns (\(s_1, s_2, s_3\) or value) correct
ei1A1: Row operations used correctly at least twice, i.e. two of the non-pivot rows or two of the non zero and one columns (\(s_1, s_2, s_3\) or value) – ignore row operations for this mark
ei2A1: CAO all values and row operations correctly stated including b.v column (allow alternative numbering of rows as long as this is clear. Condone use of \(r_2\) throughout. Do not accept in terms of b.v.) (Accept in terms of original r2 so r1 + 1/3r2, 4/9r2, r3 + 1/9r2, r4 + 5/9r2) (Row ops for pivot row may be written as r2 ÷ 9/4)
eii2M1: Stating (or implying) optimal values of \(X\), \(Y\), \(Z\) and \(Q\) (see special case)
eii3A1ft: CAO for \(x\), \(y\), \(z\) and \(P\) (the correct 4 values implies both marks) (follow through their values for \(X\), \(Y\), \(Z\) and \(Q\) from the tableau)
Special Case (e) If they use the same incorrect substitution and do not state the values of \(X\), \(Y\), \(Z\) and \(Q\) they may score M1 A0 for the implied values of \(X\), \(Y\), \(Z\) and \(Q\) from their \(x\), \(y\), \(z\) and \(P\)
George is a baker who bakes \(x\) sponge cakes and \(y\) fruit cakes every day.
One of George’s constraints is shown on Figure 3.
(a) Write down this constraint as a simplified inequality with integer coefficients. (1)
Three further constraints are
George must bake at least four fruit cakes every day
for every two sponge cakes George bakes, he must bake at most three fruit cakes
George needs 200 g of butter for each sponge cake and 100 g for each fruit cake and has 2.8 kg of butter available each day
(b)
(i) Write down the three inequalities which model these constraints. Give your answers in simplified form with integer coefficients.
(ii) Add lines and shading to Diagram 1 in the answer book to represent these three constraints. Hence determine the feasible region and label it \(R\). (5)
[Diagram 1 in the answer book is a copy of Figure 3.]
George makes £8 profit from each sponge cake he sells and £5 profit from each fruit cake he sells. Given that he wishes to maximise his profit,
(c) use the vertex method to determine the number of sponge cakes and the number of fruit cakes George should bake each day. You must make your method and working clear. (5)
Mark scheme (a)
Scheme
Marks
AO
\(5x + 4y \leqslant 80\)
B1
2.5
(1)
Notes
a1B1: CAO Must be the correct inequality.
Mark scheme (b)
Scheme
Marks
AO
(i) \(y \geqslant 4\) \(2x + y \leqslant 28\)
B1
3.3
\(3x \geqslant 2y\)
M1 A1
3.3 2.2a
(ii)
B1 B1
1.1b 2.2a
(5)
Notes
bi1B1: \(y \geqslant 4\) and \(2x + y \leqslant 28\) (oe) both correct.
bi1M1: \(3x \,\square\, 2y\) where \(\square\) is any inequality sign or =, or \(2x \geqslant 3y\)
bi1A1: \(3x \geqslant 2y\) correct
bii1B1: Any two lines correctly drawn. (Use the following to help you judge; send to review any that are worthy of credit). For \(y = 4\) within one small square of (2,4) and (12,4) For \(2x + y = 28\) within one small square of at least two of (0,28), (8,12) (12,4) or (14,0) For \(3x = 2y\) within one small square of (0,0) and (8,12)
bii2B1: All three lines correctly drawn (with shading) and \(R\) correctly labelled.
c1B1: Two of the three non-optimal vertices correct or one correct with corresponding P value correct (P values should be exact or rounded to 2dp). Accept correct top-heavy fractions for coordinates and P values.
c2B1: Two non-optimal vertices correct with corresponding P values correct.
c1M1: Attempt to solve simultaneous equations for vertex (10 2/3, 6 2/3). May be implied by correct optimal vertex
c1A1: Correct optimal vertex and corresponding P value.
c3B1: CAO with context. If candidate has the incorrect feasible region (e.g following \(2x = 3y\)) award this mark even if the integer solution is outside their feasible region.
SC: Alt. Method – Candidate only considers integer solutions (3,4) P = 44 (8,10) P = 114 (12,4) P = 116 Optimal: (11,6) P = 118 B1 Two non-optimal vertices correct with P value B1 Three non-optimal vertices correct with P value M1A1 correct optimal vertex and P value B1 CAO with context
7. A maximisation linear programming problem in \(x\), \(y\) and \(z\) is to be solved using the Simplex method.
The tableau after the 1st iteration is shown below.
b.v.
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
Value
\(s_1\)
0
\(-\dfrac{1}{2}\)
\(\dfrac{3}{2}\)
1
\(-\dfrac{1}{2}\)
0
30
\(x\)
1
\(\dfrac{1}{4}\)
\(-\dfrac{1}{4}\)
0
\(\dfrac{1}{4}\)
0
10
\(s_3\)
0
1
1
0
0
1
26
\(P\)
0
\(-\dfrac{1}{4}\)
\(-\dfrac{11}{4}\)
0
\(\dfrac{3}{4}\)
0
30
(a) State the column that contains the pivot value for the 1st iteration. You must give a reason for your answer. (2)
(b) By considering the equations represented in the above tableau, formulate the linear programming problem in \(x\), \(y\) and \(z\) only. State the objective and list the constraints as inequalities with integer coefficients. (5)
(c) Taking the most negative number in the profit row to indicate the pivot column, perform the 2nd iteration of the Simplex algorithm, to obtain a new tableau, T. Make your method clear by stating the row operations you use. (4)
(d)
(i) Explain, using T, how you know that an optimal solution to the original linear programming problem has not been found after the 2nd iteration.
(ii) State the values of the basic variables after the 2nd iteration. (2)
A student attempts the 3rd iteration of the Simplex algorithm and obtains the tableau below.
b.v.
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
Value
\(z\)
0
0
1
\(\dfrac{1}{2}\)
\(-\dfrac{1}{4}\)
\(\dfrac{1}{4}\)
\(\dfrac{43}{2}\)
\(x\)
1
0
0
\(\dfrac{1}{4}\)
\(\dfrac{1}{8}\)
\(-\dfrac{1}{8}\)
\(\dfrac{57}{4}\)
\(y\)
0
1
0
\(-\dfrac{1}{2}\)
\(\dfrac{1}{4}\)
\(\dfrac{3}{4}\)
\(\dfrac{9}{2}\)
\(P\)
0
1
0
\(\dfrac{5}{4}\)
\(\dfrac{1}{8}\)
\(\dfrac{7}{8}\)
\(\dfrac{361}{4}\)
(e) Explain how you know that the student’s attempt at the 3rd iteration is not correct. (1)
Mark scheme (a)
Scheme
Marks
AO
The pivot for this first iteration came from the \(x\)-column
B1
1.1b
as it is now a basic variable
dB1
2.5
(2)
Notes
B1: CAO (correct column of \(x\) stated)
dB1:Dependent on first B1 Correct statement that \(x\) is now a basic variable (oe) Accept that \(x\) now appears in the first (bv) column or states \(x\) column has one 1 and rest 0 or \(s_2\) row has been replaced with \(x\)
Mark scheme (b)
Scheme
Marks
AO
\(x\)-row: \(4x + y - z \leqslant 40\) or \(s_3\)- row: \(y + z \leqslant 26\)
B1
3.4
Eliminating \(s_2\) from the \(s_1\) row using the \(x\) row: \(-\frac{1}{2}y + \frac{3}{2}z + s_1 - 2\left(10 - x - \frac{1}{4}y + \frac{1}{4}z\right) = 30\)
M1
2.1
Eliminating \(s_2\) from the \(P\) row using the \(x\) row: \(P - \frac{1}{4}y - \frac{11}{4}z + 3\left(10 - x - \frac{1}{4}y + \frac{1}{4}z\right) = 30\)
M1
1.1b
For either \(P - 3x - y - 2z = 0\) or \(2x + z + s_1 = 50\)
A1
1.1b
Alternatively
b.v.
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
Value
\(s_1\)
2
0
1
1
0
0
50
\(s_2\)
4
1
\(-1\)
0
1
0
40
\(s_3\)
0
1
1
0
0
1
26
\(P\)
\(-3\)
\(-1\)
\(-2\)
0
0
0
0
LP: (Maximise) \(P = 3x + y + 2z\) Subject to: \(\begin{aligned} 2x + z &\leqslant 50 \\ 4x + y - z &\leqslant 40 \\ y + z &\leqslant 26 \\ (x, y, z &\geqslant 0) \end{aligned}\)
A1
2.2a
(5)
Notes
B1: Either the constraint for the x-row or \(s_3\)- row correct (allow any equivalent form including non-integer coefficients but must be inequalities) Do not accept strict inequalities
M1: Eliminating \(s_2\) from the equation from the \(s_1\) row using the equation from the \(x\) row Correct constraint implies this mark
M1: Eliminating \(s_2\) from the equation from the \(P\) row using the equation from the \(x\) row Correct objective implies this mark
A1: \(P - 3x - y - 2z = 0\) or \(2x + z + s_1 = 50\) (allow any equivalent form including non-integer coefficients but must have been simplified to a single term in each variable) Correct constraint or objective implies the corresponding M mark
A1: Correct LP formulation (condone lack of ‘maximise’ and condone lack of the non-negative trivial constraints)
Note: It is possible to score M1 M0 A1 A0 or M0 M1 A1 A0
Alternatively – reproduces original tableau
B1: \(s_2\) row correct
M1: \(s_1\) row correct - Correct constraint implies this mark
M1: P row correct - Correct objective implies this mark
A1: fully correct tableau
A1: Correct LP formulation (condone lack of ‘maximise’ and condone lack of the non-negative trivial constraints)
Mark scheme (c)
Scheme
Marks
AO
b.v.
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
Value
Row Ops
\(z\)
0
\(-\dfrac{1}{3}\)
1
\(\dfrac{2}{3}\)
\(-\dfrac{1}{3}\)
0
20
\(\frac{2}{3}\text{r}1\)
\(x\)
1
\(\dfrac{1}{6}\)
0
\(\dfrac{1}{6}\)
\(\dfrac{1}{6}\)
0
15
r2 + 0.25R1
\(s_3\)
0
\(\dfrac{4}{3}\)
0
\(-\dfrac{2}{3}\)
\(\dfrac{1}{3}\)
1
6
r3 – R1
\(P\)
0
\(-\dfrac{7}{6}\)
0
\(\dfrac{11}{6}\)
\(-\dfrac{1}{6}\)
0
85
r4 + 2.75R1
B1 M1 A1 B1
1.1b 2.1 1.1b 2.4
(4)
Notes
(c) Note – accept correct recurring decimals in place of fractions
B1: Pivot row completely correct including change of b.v.
M1: All values in one of the non-pivot rows correct (so ignore b.v. column and ‘Row Ops’ column) or one of the ‘non zero and one’ columns (which are y, \(s_1\), \(s_2\) or Value) correct (must have pivoted on the correct value)
A1: cao all values including b.v. column – ignore ‘Row Ops’ column for this mark
B1: Correct row operations stated (allow alternative numbering of rows as long as this is clear. Condone use of \(\text{R}_1\) throughout)
Mark scheme (d)
Scheme
Marks
AO
(i) After the second iteration an optimal solution has not been found as the profit row still contains negative values
dB1
2.4
(ii) \(z = 20,\ x = 15,\ s_3 = 6\)
dB1ft
2.2a
(2)
Notes
(i) dB1: CAO (profit row still contains negative values (but not negative variables) – dependent on the M mark in (c) and a completed profit row in (c) (accept P row or objective row but not operations row or bottom row) Do not accept that not all values are positive
(ii) dB1ft: Follow through their values of \(z\), \(x\), and \(s_3\) – dependent on the M mark in (c) and a completed tableau in (c) ignore mention of any other variables including \(P\) All values must be positive
Mark scheme (e)
Scheme
Marks
AO
e.g. Their attempt is not correct as, if \(\boldsymbol{y}\) is now a basic variable, then the \(\boldsymbol{y}\) column should contain only one value of 1 (in the third row) and therefore the entry of 1 in the profit row is incorrect (and should be 0)
B1
2.3
(1)
(14 marks)
Notes
B1: CAO (e.g. correct indication that the (basic variable) column for \(y\) is not correct – see bold statement for the minimum acceptable) Accept there should not be a 1 in the objective row in the \(y\) column or that there should not be two 1s in the \(y\) column. If \(s_2\) column also mentioned then B0
\(P = -x - y - M(a_1 + a_2)\) and substitute expressions for \(a_1\) and \(a_2\) \(\big(P + (1 - 3M)x + (1 - 2M)y + Ms_1 + Ms_3 = -450M\big)\)
M1
2.1
e.g.
b.v.
\(x\)
\(y\)
\(s_1\)
\(s_2\)
\(s_3\)
\(a_1\)
\(a_2\)
Value
\(a_1\)
1
\(-1\)
\(-1\)
0
0
1
0
100
\(s_2\)
1
\(-5\)
0
1
0
0
0
0
\(a_2\)
2
3
0
0
\(-1\)
0
1
350
\(P\)
\(1 - 3M\)
\(1 - 2M\)
\(M\)
0
\(M\)
0
0
\(-450M\)
M1 A1
3.3 2.2a
(6)
Notes
(a) NOTE: if correct they must use one slack, two surplus and two artificial variables. Accept alternative letters for these as long as the artificial variables are clearly identifiable
B1: one correct equation or two correct inequalities (do not accept strict inequalities)
B1: two correct equations or three correct inequalities
B1: all three equations correct (please check suffices on \(s\) and \(a\) terms carefully – they may be in a different order)
M1: setting up the new objective which must be \(P = -x - y - M(a_1 + a_2)\) and an attempt to substitute for their \(a_1\) and \(a_2\) (accept any equivalent form, which may not be fully simplified) (accept the use of \(Q\) instead of \(P\) throughout)
M1: setting up initial tableau – all four rows complete with two correct rows (but ignore b.v. column for this mark) (Note the order of rows may be different from above) Check that the slack, surplus and artificial variables correspond to their equations
A1: CAO (any equivalent correct form, but the terms in the objective row must be simplified)
Mark scheme (b)
Scheme
Marks
AO
(i) \(x = 130\)
B1
3.4
(ii) When \(x = 130 \Rightarrow y \leqslant 30,\ y \geqslant 26,\ y \lt 130\) and \(y \geqslant 30\)
M1
3.1a
\(y = 30\)
A1
2.2a
(3)
(9 marks)
Notes
(i) B1: CAO (\(x = 130\))
(ii) M1: Substitute \(x = 130\) into candidate’s inequalities from (a) (at least 3 inequalities seen or both \(y \geqslant 30\) and \(y \leqslant 30\)) (condone \(y \leqslant 130\))
A1: CAO (\(y = 30\)) we must see both \(y \geqslant 30\) and \(y \leqslant 30\) explicitly stated for this mark (must not follow from any incorrect working)
Figure 4 shows three of the six constraints for a linear programming problem in \(x\) and \(y\)
The unshaded region and its boundaries satisfy these three constraints.
(a) State these three constraints as simplified inequalities with integer coefficients. (3)
The variables \(x\) and \(y\) represent the number of orange fish and the number of blue fish, respectively, that are to be kept in an aquarium.
The number of fish in the aquarium is subject to these three further constraints
there must be at least one blue fish
the orange fish must not outnumber the blue fish by more than ten
there must be no more than five blue fish for every orange fish
(b) Write each of these three constraints as a simplified inequality with integer coefficients. (2)
(c) Represent these three constraints by adding lines and shading to Diagram 1 in the answer book, labelling the feasible region, \(R\) (3)
[Diagram 1 in the answer book is a copy of Figure 4.]
The total value (in pounds) of the fish in the aquarium is given by the objective function
\[\text{Maximise } P = 3x + 5y\]
(d)
(i) Use the objective line method to determine the optimal point of the feasible region, giving its coordinates as exact fractions.
(ii) Hence find the maximum total value of the fish in the aquarium, stating the optimal number of orange fish and the optimal number of blue fish. (4)
M1: One correct inequality in any form e.g. \(y - 2x - 10 \leqslant 0\). Condone strict inequality. Must be simplified to three terms only but coefficients do not need to be integers.
A1: Two correct inequalities in any form e.g. \(y - 2x - 10 \leqslant 0\). Condone strict inequalities. Must be simplified to three terms only but coefficients do not need to be integers.
A1: All three inequalities correct with three terms and integer coefficients. Must not be strict inequalities.
SC: M1A0A0 for two correct “equations”, either with = or inequality reversed
The graph does NOT show \(x \geqslant 0\) and \(y \geqslant 0\), so these will not be accepted. Ignore any reference to these.
B1: Any one of \(y \geqslant x - 10\) or \(y \leqslant 5x\) in any form (accept strict inequalities)
B1: All three correct in any form. Must not be strict inequalities.
Mark scheme (c)
Scheme
Marks
AO
M1 A1ft A1
1.1b 1.1b 1.1b
(3)
Notes
M1: One line drawn with gradient 1 or gradient 5 (or 1/5). Condone dashed line.
A1ft: Either \(y \geqslant x - 10\) or \(y \leqslant 5x\) drawn correctly, with correct shading. Condone dashed line. ft their stated inequalities from part (b), but allow recovery.
A1: CAO All three correct inequalities drawn correctly with solid lines and the correct region \(R\) labelled. Penalise any poorly drawn lines (e.g. not straight). Accuracy within 1 small square. \(y \geqslant x - 10\) passes through (10,0) and (20,10). \(y \leqslant 5x\) passes through (0,0) and (5,25).
Optimal point \(\left(\dfrac{20}{3},\ \dfrac{70}{3}\right)\)
A1
2.2a
(ii) Consideration of integer coordinates around the optimal vertex.
dM1
1.1b
7 orange fish and 23 blue fish Total value \(3(7) + 5(23) =\) (£)136
A1
3.2a
(4)
(12 marks)
Notes
(d)(i) M1: Objective line drawn accurately. Parallel to a line passing through (0,6) and (10,0). Accuracy within 1 small square. (Minimum passing through (0,3) and (5,0)). Accept reciprocal gradient for M mark only.
A1: Correct optimal point \(\left(\dfrac{20}{3},\ \dfrac{70}{3}\right)\) oe. Accept \(x = \dfrac{20}{3}\) and \(y = \dfrac{70}{3}\)
(d)(ii) dM1: Dependent on 1st M1 and correct objective line. Consideration of integer point(s) around the optimal vertex. Candidate must have tested at least two of (6,23), (6,24), (7,23) and (7,24).
A1: CAO Clear statement including 7 orange (fish) and 23 blue (fish) and (total value) (£)136
7. A publisher plans to produce three versions of the same book: a paperback, a hardcover, and a deluxe edition.
Each paperback takes 4 minutes to print and 1 minute to bind
Each hardcover takes 8 minutes to print and 5 minutes to bind
Each deluxe edition takes 15 minutes to print and 12 minutes to bind
The printing machine is available for at most 150 hours and the binding machine must be used for at least 60 hours.
The publisher decides to produce
at least 1600 books in total
at least three times as many paperbacks as hardcovers
The profit on each paperback sold is £8, the profit on each hardcover sold is £20 and the profit on each deluxe edition sold is £40
Let \(x\), \(y\) and \(z\) represent the number of paperbacks, hardcovers and deluxe editions produced.
(a) Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. (5)
The publisher decides to solve this linear programming problem by using the two-stage simplex method.
(b) Set up an initial tableau for solving this problem using the two-stage simplex method. As part of your solution, you must show how
the constraints have been made into equations by using slack variables, exactly two surplus variables and exactly two artificial variables
the rows for the two objective functions are formed
(6)
The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.
b.v.
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
\(s_4\)
\(a_1\)
\(a_2\)
Value
\(s_1\)
0
0
0
1
1
3
0
\(-1\)
\(-3\)
600
\(z\)
0
\(\dfrac{4}{11}\)
1
0
\(-\dfrac{1}{11}\)
\(\dfrac{1}{11}\)
0
\(\dfrac{1}{11}\)
\(-\dfrac{1}{11}\)
\(\dfrac{2000}{11}\)
\(x\)
1
\(\dfrac{7}{11}\)
0
0
\(\dfrac{1}{11}\)
\(-\dfrac{12}{11}\)
0
\(-\dfrac{1}{11}\)
\(\dfrac{12}{11}\)
\(\dfrac{15600}{11}\)
\(s_4\)
0
\(\dfrac{40}{11}\)
0
0
\(\dfrac{1}{11}\)
\(-\dfrac{12}{11}\)
1
\(-\dfrac{1}{11}\)
\(\dfrac{12}{11}\)
\(\dfrac{15600}{11}\)
\(P\)
0
\(-\dfrac{4}{11}\)
0
0
\(-\dfrac{32}{11}\)
\(-\dfrac{56}{11}\)
0
\(\dfrac{32}{11}\)
\(\dfrac{56}{11}\)
\(\dfrac{204800}{11}\)
\(I\)
0
0
0
0
0
0
0
1
1
0
(c) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method to obtain a new tableau. Make your method clear by stating the row operations you use. (5)
After three iterations of the second stage of the two-stage simplex method, the following tableau is obtained.
b.v.
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
\(s_4\)
Value
\(s_2\)
0
0
0
1
1
3
0
600
\(z\)
0
0
1
\(\dfrac{1}{10}\)
0
\(\dfrac{1}{2}\)
\(-\dfrac{1}{10}\)
100
\(x\)
1
0
0
\(-\dfrac{3}{40}\)
0
\(-\dfrac{9}{8}\)
\(-\dfrac{7}{40}\)
1125
\(y\)
0
1
0
\(-\dfrac{1}{40}\)
0
\(-\dfrac{3}{8}\)
\(\dfrac{11}{40}\)
375
\(P\)
0
0
0
\(\dfrac{29}{10}\)
0
\(\dfrac{7}{2}\)
\(\dfrac{1}{10}\)
20500
Given that the publisher produces the optimal number of each version of the book,
(d)
(i) state the maximum profit the publisher can earn,
(ii) find the number of hours the binding machine will be used. (2)
(e) Give a reason why the publisher may not earn the profit stated in (d)(i). (1)
B1: Correct objective function \((8x + 20y + 40z)\) plus ‘maximise’ or ‘max’ but not ‘maximum’ (and ‘\(P =\)’ is not required)
M1: Either one correct inequality (need not be simplified) or both \(4x + 8y + 15z \leqslant k_1\) and \(x + 5y + 12z \geqslant k_2\) where \(k_1, k_2 \gt 0\)
A1: Both correct (\(4x + 8y + 15z \leqslant 9000,\ x + 5y + 12z \geqslant 3600\)) – allow equivalent answers (provided 4 terms only and integer coefficients e.g. \(2x + 10y + 24z - 7200 \geqslant 0\))
B1: CAO (\(x + y + z \geqslant 1600\) oe provided 4 terms only and integer coefficients)
B1: CAO (\(3y \leqslant x\) oe provided 2 terms only and integer coefficients)
(b) Note in this part that the numbering of the suffices for the slack, surplus and artificial variables seen in both the candidate’s equations and Simplex tableau will most likely be different from what is seen in the MS (e.g. \(4x + 8y + 15z + s_3 = 9000\) is correct). The correct values in the rows of the tableau do NOT imply the first four marks (the question explicitly asked for the constraints as equations and the rows for the two objectives to be explicitly stated)
B1: Any two correct inequalities converted into equations correctly (condone the same letter, say \(s_3\), being used twice) – any equivalent forms of the correct equations are acceptable (e.g. variables do not need to be on the same side)
B1: All four correct equations (using distinct slack, surplus and artificial variables) – any equivalent forms of the correct equations are acceptable
M1: Using \(I = -(a_1 + a_2)\) with their expressions for \(a_1\) and \(a_2\) (allow slips in forming \(I\) from their two expressions for the two artificial variables) but must be a clear intention to calculate \(I = -(a_1 + a_2)\)) – must be exactly two artificial variables in their expression for \(I\) for this mark
A1: CAO for \(I\) and \(P\) (must be stated as \(P - 8x - 20y - 40z = 0\) (A0 if = 0 missing) and \(I - 2x - 6y - 13z + s_2 + s_3 = -5200\) - so variables on one side and constant on the other)
M1: setting up initial tableau – all six rows complete (with no blanks) and two correct rows (but ignore b.v. column for this mark)
A1: CAO (any equivalent correct form) - note that the candidate’s order in which the rows appear in the tableau (and choice of letter to represent the slack, surplus and artificial variables) may be different – check to ensure that the basic variable column is consistent with their choice of lettering for the slack and artificial variables
Mark scheme (c)
Scheme
Marks
AO
b.v.
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
\(s_4\)
Value
Row Ops
\(s_3\)
0
0
0
\(\dfrac{1}{3}\)
\(\dfrac{1}{3}\)
1
0
200
\(\dfrac{1}{3}\text{r}_1\)
\(z\)
0
\(\dfrac{4}{11}\)
1
\(-\dfrac{1}{33}\)
\(-\dfrac{4}{33}\)
0
0
\(\dfrac{1800}{11}\)
\(\text{r}_2 - \dfrac{1}{11}\text{R}_1\)
\(x\)
1
\(\dfrac{7}{11}\)
0
\(\dfrac{4}{11}\)
\(\dfrac{5}{11}\)
0
0
\(\dfrac{18000}{11}\)
\(\text{r}_3 + \dfrac{12}{11}\text{R}_1\)
\(s_4\)
0
\(\dfrac{40}{11}\)
0
\(\dfrac{4}{11}\)
\(\dfrac{5}{11}\)
0
1
\(\dfrac{18000}{11}\)
\(\text{r}_4 + \dfrac{12}{11}\text{R}_1\)
\(P\)
0
\(-\dfrac{4}{11}\)
0
\(\dfrac{56}{33}\)
\(-\dfrac{40}{33}\)
0
0
\(\dfrac{216000}{11}\)
\(\text{r}_5 + \dfrac{56}{11}\text{R}_1\)
B1 M1 A1 A1 B1
1.1b 2.1 1.1b 1.1b 2.4
(5)
Notes
B1: Pivot (top) row completely correct including change of b.v. (but not ‘Row Ops’ column)
M1: All values in one of the non-pivot rows correct (so ignore b.v. column and ‘Row Ops’ column) or one of the ‘non zero and one’ columns (which are \(y, s_1, s_2\) or Value) correct (must have pivoted on the correct value)
A1: Row operations used correctly at least twice, i.e. two of the ‘non zero and one’ columns (\(s_1, s_2\), \(y\) or Value) correct
A1: CAO all values including b.v. column – ignore ‘Row Ops’ column for this mark
e.g. there is no guarantee that all the books will be sold
B1
3.5b
(1)
(19 marks)
Notes
B1: CAO – must explicitly mention the fact that it is possible that not all the books will be sold. Ignore reasons for why, provided they do not relate to the publisher producing less than the optimal number of books
Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\). The unshaded area, including its boundaries, forms the feasible region, \(R\). An objective line has been drawn and labelled on the graph.
(a) State the inequalities that define the feasible region. (2)
The maximum value of the objective function is \(\dfrac{160}{3}\)
The minimum value of the objective function is \(\dfrac{883}{41}\)
(b) Determine the objective function, showing your working clearly. (5)
B1: Any two correct inequalities. Condone strict inequalities
B1: All four correct inequalities (not strict)
Mark scheme (b)
Scheme
Marks
AO
Attempt to solve correct two equations to find either optimal vertex Coordinates of ‘minimum’ point is \(\left(\dfrac{56}{41},\ \dfrac{143}{41}\right)\) Coordinates of ‘maximum’ point is \(\left(8,\ \dfrac{88}{15}\right)\)
M1 A1 A1
3.4 1.1b 1.1b
Setting up a pair of simultaneous equations using their two points and an objective function of the form \(ax + by\) (If correct \(\begin{aligned}56a + 143b &= 883\\ 15a + 11b &= 100\end{aligned}\) oe)
dM1
3.1a
Objective function is \((P =)\,3x + 5y\)
A1
2.2a
(5)
(7 marks)
Notes
M1: Considering either of the following pairs of simultaneous equations: \(3y = 4x + 5,\ 3x + 8y = 32\) or \(x = 8,\ 4x + 15y = 120\) Must find at least one pair of coordinates from either of these two pairs (condone poor algebra in the solving of these equations)
A1: cao \(\left(\dfrac{56}{41},\ \dfrac{143}{41}\right)\) - must be seen exact at some point. They do not have to associate this with being the ‘minimum’
A1: cao \(\left(8,\ \dfrac{88}{15}\right)\) - must be seen exact at some point. They do not have to associate this with being the ‘maximum’
dM1: Setting up a pair of linear simultaneous equations using their two points. For this mark they must be using their solution of \(3y = 4x + 5,\ 3x + 8y = 32\) together with \(\dfrac{883}{41}\) and their solution of \(x = 8,\ 4x + 15y = 120\) together with \(\dfrac{160}{3}\). Allow use of any two different variables for their pair of linear simultaneous equations. Look out for \(\dfrac{56}{41}x + \dfrac{143}{41}y = \dfrac{883}{41}\) and \(8x + \dfrac{88}{15}y = \dfrac{160}{3}\) which implies the first four marks
A1: cao – allow just the expression \(3x + 5y\) but not any multiple or factor of this (but isw if correct expression is seen first). Allow equal to any other letter but not equal to a value, for example, \(3x + 5y = 0\) is A0
Figure 5 shows the constraints of a linear programming problem in \(x\) and \(y\) where \(R\) is the feasible region.
The objective is to maximise \(P = x + ky\), where \(k\) is a positive constant.
The optimal vertex of \(R\) is to be found using the Simplex algorithm.
(a) Set up an initial tableau for solving this linear programming problem using the Simplex algorithm. (5)
After two iterations of the Simplex algorithm a possible tableau \(T\) is
b.v.
\(x\)
\(y\)
\(s_1\)
\(s_2\)
\(s_3\)
\(s_4\)
Value
\(s_1\)
0
0
1
\(-\frac{3}{5}\)
0
\(\frac{1}{5}\)
1
\(x\)
1
0
0
\(\frac{1}{5}\)
0
\(-\frac{2}{5}\)
2
\(s_3\)
0
0
0
\(-\frac{11}{5}\)
1
\(\frac{12}{5}\)
22
\(y\)
0
1
0
\(\frac{2}{5}\)
0
\(\frac{1}{5}\)
5
\(P\)
0
0
0
\(\frac{1}{5} + \frac{2}{5}k\)
0
\(-\frac{2}{5} + \frac{1}{5}k\)
\(5k + 2\)
(b) State the value of each variable after the second iteration. (1)
It is given that \(T\) does not give an optimal solution to the linear programming problem.
After a third iteration of the Simplex algorithm the resulting tableau does give an optimal solution to the problem.
(c) Perform the third iteration of the Simplex algorithm and hence determine the range of possible values for \(P\). You should state the row operations you use and make your method and working clear. (9)
Mark scheme (a)
Scheme
Marks
AO
\(x + y \leqslant 8 \Rightarrow x + y + s_1 = 8\) \(x + 2y \leqslant 12 \Rightarrow x + 2y + s_2 = 12\) \(7x + 2y \leqslant 46 \Rightarrow 7x + 2y + s_3 = 46\) \(y \leqslant 2x + 1 \Rightarrow -2x + y + s_4 = 1\) \(P = x + ky \Rightarrow P - x - ky = 0\)
M1 A1 B1
3.4 1.1b 1.1b
e.g.
b.v.
\(x\)
\(y\)
\(s_1\)
\(s_2\)
\(s_3\)
\(s_4\)
Value
\(s_1\)
1
1
1
0
0
0
8
\(s_2\)
1
2
0
1
0
0
12
\(s_3\)
7
2
0
0
1
0
46
\(s_4\)
\(-2\)
1
0
0
0
1
1
\(P\)
\(-1\)
\(-k\)
0
0
0
0
0
M1 A1
3.3 2.2a
(5)
Notes
(a) M1: Correctly re-writing any two inequalities as equations with slack variables (can be implied by two correct rows in the Simplex tableau ignoring b.v. column). Or correctly stating all four constraints as inequalities
A1: Correctly re-writing all inequalities as equations with slack variables (can be implied by the four correct constraint rows in the Simplex tableau ignoring b.v. column)
B1: Correctly re-writes objective function (can be implied by correct row in tableau)
M1:Any two rows correct including consistent b.v. column entries or any three rows correct (ignoring b.v. column)
A1: cao (including consistent b.v. column) – note that the candidate’s order in which the rows appear in the tableau (and choice of letter to represent the slack variable) may be different. A correct tableau implies full marks in this part
(b) B1: cao for \(x\), \(y\), \(s_1, s_2, s_3\) and \(s_4\) only (ignore any mention of \(P\))
Mark scheme (c)
Scheme
Marks
AO
b.v.
\(x\)
\(y\)
\(s_1\)
\(s_2\)
\(s_3\)
\(s_4\)
Value
Row Ops
\(s_4\)
0
0
5
\(-3\)
0
1
5
5r1
\(x\)
1
0
2
\(-1\)
0
0
4
r2 + 0.4R1
\(s_3\)
0
0
\(-12\)
5
1
0
10
r3 – 2.4R1
\(y\)
0
1
\(-1\)
1
0
0
4
r4 – 0.2R1
\(P\)
0
0
\(2 - k\)
\(k - 1\)
0
0
\(4k + 4\)
\(\text{r5} - (0.2k - 0.4)\text{R1}\)
B1 M1 A1 A1 B1
1.1b 2.1 1.1b 1.1b 2.4
Optimal value of \(P\) is \(4k + 4\) (at \(x = y = 4\))
M1
3.4
Second iteration not optimal \(\Rightarrow -\tfrac{2}{5} + \tfrac{1}{5}k \lt 0 \therefore k \lt 2\)
B1
3.1a
Third iteration optimal \(\Rightarrow 2 - k \geqslant 0\) and \(k - 1 \geqslant 0\) \((\therefore k \geqslant 1)\)
dM1
3.4
\(1 \leqslant k \lt 2 \Rightarrow 8 \leqslant P \lt 12\)
A1
2.2a
(9)
(15 marks)
Notes
(c) B1: Pivot row completely correct including change of b.v.
M1: All values in one of the non-pivot rows correct (so ignore b.v. column and ‘Row Ops’ column) or one of the ‘non zero and one’ columns (which are \(s_1, s_2\) or Value) correct (must have pivoted on the correct value)
A1: Row operations used correctly at least twice, i.e. two of the ‘non zero and one’ columns (\(s_1, s_2\) or Value) correct
A1: cao all values including b.v. column – ignore ‘Row Ops’ column for this mark
M1: Their optimal value (as a linear expression in \(k\)) stated correctly following their third iteration (must have pivoted on a positive value from the \(s_4\) column and completed the bottom row of the tableau). Condone this expression (\(4k + 4\) if correct) being stated as part of an equation/inequality (or as part of their final answer) – sight of this expression (but must be seen outside of the tableau) scores this mark
B1: Correctly inferring that \(k \lt 2\) either from \(-\tfrac{2}{5} + \tfrac{1}{5}k \lt 0\) or from \(4k + 4 \gt 5k + 2\) – just stating \(k \lt 2\) without it being clear where this comes from is B0
dM1: Considering (at least) two of their linear expressions in \(k\) from their objective row (not including the Value column) after the third iteration \(\geqslant 0\) (dependent on the previous M mark) – note that working may be minimal here so please follow through their expressions in \(k\) from their objective row (so if correct, stating \(k \leqslant 2\) and \(k \geqslant 1\) implies this mark)
A1: cao for the range of values for \(P\) - this mark is dependent on a correct objective row in the tableau and the previous three marks in this part
(a) B1: One correct non-trivial inequality (allow strict inequality provided direction of inequality sign is correct) – equations with slack variables etc. scores no marks unless replaced with correct inequalities
B1: All three non-trivial inequalities correct
M1: Either expression stated correctly (allow equal to (or an inequality with) any letter e.g. \(P = -2x + 3y + z\) but not equal to a value e.g. = 0) – ignore any mention of maximum/minimum for this mark
A1: Both expressions correct including max/min correctly matched with each expression (allow equal to any letter only) – do not isw if they continue and place their expression(s) equal to a value(s)
Mark scheme (b)
Scheme
Marks
AO
(Because \(M\) is big) the only negative in the objective row is the \(2 - 4M\) so the pivot is from the \(x\)-column
B1
2.4
The 3 in the \(a_2\) row is the pivot as \(\dfrac{12}{3}\) is less than both \(\dfrac{8}{1}\) and \(\dfrac{13}{2}\)
B1
2.2a
(2)
(6 marks)
Notes
(b) B1: Correct reasoning that the pivot is a value from the \(x\)-column – as a minimum must state that the \(2 - 4M\) is the onlynegative (condone mostnegative) in the objective row (allow profit row or \(P\) row, condone ‘bottom row’)
B1: Correct justification of why the 3 in the \(a_2\) row or the 3 in the \(x\) column is the pivot – so must state the correct pivot in a clear unambiguous way (so just saying the pivot is ‘the 3’ is B0) and comparing or stating that \(\dfrac{12}{3}\) or 4 is less than/least positive for both \(\dfrac{8}{1}\) or 8 and \(\dfrac{13}{2}\) or 6.5 – must see all three values so do check the table for possibly stating the \(\theta\) values there. However, just stating that the 3 is the pivot because it is the smallest \(\theta\) value (without seeing anywhere these \(\theta\) values) is B0
Figure 3 shows the constraints of a maximisation linear programming problem in \(x\) and \(y\), where \(x \geqslant 0\) and \(y \geqslant 0\). The unshaded area, including its boundaries, forms the feasible region, \(R\). An objective line has been drawn and labelled on the graph.
(a) List the constraints as simplified inequalities with integer coefficients. (3)
The optimal value of the objective function is 216
(b)
(i) Calculate the exact coordinates of the optimal vertex.
(ii) Hence derive the objective function. (5)
Given that \(x\) represents the number of small flower pots and \(y\) represents the number of large flower pots supplied to a customer,
(c) deduce the optimal solution to the problem. (1)
Mark scheme (a)
Scheme
Marks
AO
\(x + y \leqslant 14\) \(2y - x \leqslant 12\) \(3x - y \leqslant 15\) \((x \geqslant 0,\ y \geqslant 0)\)
M1 A1 A1
3.3 1.1b 2.5
(3)
Notes
M1: One correct non-trivial inequality in any form e.g. \(x - 2y + 12 \geqslant 0\). Condone strict inequality. Must be simplified to three terms only but coefficients do not need to be integers
A1: Two correct non-trivial inequalities in any form e.g. \(x - 2y + 12 \geqslant 0\). Condone strict inequalities. Must be simplified to three terms only but coefficients do not need to be integers
A1: All three non-trivial inequalities correct with three terms and integer coefficients
Mark scheme (b)
Scheme
Marks
AO
(i) Attempts to solve two equations to find optimal vertex
(b)(i) M1: Attempt to solve their \(x + y = 14\) and \(2y - x = 12\) (so their line with negative gradient and their line that passes through (0, 6)) simultaneously with at least one equation correct – the correct answer with no working implies this mark
A1: cao \(\left(\dfrac{16}{3},\ \dfrac{26}{3}\right)\) or \(\left(5\dfrac{1}{3},\ 8\dfrac{2}{3}\right)\) - must be exact (allow \(x = \ldots,\ y = \ldots\)) and clearly stated as the optimal vertex if more than one vertex of the FR found
(b)(ii) M1: Expression comprising of a constant (unknown) multiple/factor of \(2x + 5y\) e.g. \(k(4x + 10y)\) - M0 if assuming the objective is \(4x + 10y\) or if no \(k\) (or equivalent letter)
ddM1: Dependent on both previous M marks. Forming an equation with the expression \(k(4x + 10y)\) (or any multiple/factor of this), the 216 and their optimal vertex
A1: cao – accept \(8x + 20y\) or this expression equal to any letter but not for e.g. \(8x + 20y = 0\) or 216
Mark scheme (c)
Scheme
Marks
AO
6 small (flower pots) and 8 large (flower pots)
B1
3.2a
(1)
(9 marks)
Notes
B1: 6 small and 8 large – not for (6, 8) or \(x = 6,\ y = 8\) – must be in context
8. Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running.
Susie decides that in her training next week she should
maximise the total time spent cycling and running
train for at most 39 hours
spend at least 40% of her time swimming
spend a total of at least 28 hours of her time swimming and running
Susie needs to determine how long she should spend next week training for each activity. Let
\(x\) represent the number of hours swimming
\(y\) represent the number of hours cycling
\(z\) represent the number of hours running
(a) Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. (5)
Susie decides to solve this linear programming problem by using the two-stage Simplex method.
(b) Set up an initial tableau for solving this problem using the two-stage Simplex method. As part of your solution you must show how
the constraints have been made into equations using slack variables, exactly one surplus variable and exactly one artificial variable
the rows for the two objective functions are formed
(6)
The following tableau \(T\) is obtained after one iteration of the second stage of the two-stage Simplex method.
b.v.
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
Value
\(y\)
0
1
0
1
0
1
11
\(s_2\)
0
0
5
\(-2\)
1
\(-5\)
62
\(x\)
1
0
1
0
0
\(-1\)
28
\(P\)
0
0
\(-1\)
1
0
1
11
(c) Obtain a suitable pivot for a second iteration. You must give reasons for your answer. (2)
(d) Starting from tableau \(T\), solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use. (5)
Mark scheme (a)
Scheme
Marks
AO
\(x + y + z \leqslant 39\)
B1
3.3
\(\tfrac{2}{5}(x + y + z) \leqslant x \quad (\Rightarrow -3x + 2y + 2z \leqslant 0)\)
M1 A1
3.3 1.1b
\(x + z \geqslant 28\)
B1
1.1b
Maximise \(P = y + z \quad (\Rightarrow P - y - z = 0)\)
B1
3.3
(5)
Notes
(a) B1: cao (\(x + y + z \leqslant 39\))
M1: \(\tfrac{2}{5}(x + y + z) \,\square\, x\) where \(\square\) is any inequality or equals
A1: cao
B1: cao (\(x + z \geqslant 28\))
B1: Correct objective function (\(P = y + z\)) plus ‘maximise’ or ‘max’ but not ‘maximum’
Mark scheme (b)
Scheme
Marks
AO
\(x + y + z \leqslant 39 \;\Rightarrow\; x + y + z + s_1 = 39\) \(-3x + 2y + 2z \leqslant 0 \;\Rightarrow\; -3x + 2y + 2z + s_2 = 0\)
M1 A1
2.1 1.1b
\(x + z \geqslant 28 \;\Rightarrow\; x + z - s_3 + a_1 = 28\)
B1
2.5
\(I = -a_1 \;\Rightarrow\; I - x - z + s_3 = -28\)
M1
2.1
e.g.
b.v
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
\(a_1\)
Value
\(s_1\)
1
1
1
1
0
0
0
39
\(s_2\)
\(-3\)
2
2
0
1
0
0
0
\(a_1\)
1
0
1
0
0
\(-1\)
1
28
\(P\)
0
\(-1\)
\(-1\)
0
0
0
0
0
\(I\)
\(-1\)
0
\(-1\)
0
0
1
0
\(-28\)
M1 A1
3.3 2.2a
(6)
Notes
(b) M1: One \(\leqslant\) constraint re-formulated as an equation using slack variables – dependent on either the first B mark in (a) or the M mark in (a)
A1: cao (both \(\leqslant\) constraints)
B1: \(\geqslant\) constraint re-formulated as an equation using one surplus and one artificial variable
M1: Formulates second objective with \(I = -a_1\) and their expression for \(a_1\)
M1: Setting up the initial tableau – all five rows complete with two correct rows (but ignore b.v. column for this mark)
A1: cao (any equivalent correct form)
Mark scheme (c)
Scheme
Marks
AO
The only negative in the objective row is the \(-1\) so the pivot is from the \(z\)-column
B1
2.4
The 5 in the \(s_2\) row is the pivot because \(\dfrac{62}{5}\) is less than \(\dfrac{28}{1}\)
B1
2.2a
(2)
Notes
(c) B1: Correct reasoning that the pivot is a value from the \(z\)-column – condone any mention of negative value in \(P\) row
B1: Correct justification of why the 5 in the \(s_2\) row is the next pivot – so must compare or state that 12.4 is less than 28 (not sufficient to just say that 12.4 (oe) is the least)
(d) B1: Pivot row correct including change of b.v.
M1: All values in one of the non-pivot rows correct or one of the non zero and one columns (\(s_1, s_2\) or value) correct (from their choice of pivot)
A1: Row operations used correctly at least twice, i.e. two of the non zero and one columns (\(s_1, s_2\) or value)
A1: For all values and row operations correctly stated – do not penalise lack of correct b.v. in pivot row twice. Condone blank Row Ops in the first row only
A1: Correct allocation of training times – must be in context (so not just in terms of \(x\), \(y\) and \(z\))
7. A maximisation linear programming problem in \(x\), \(y\) and \(z\) is to be solved using the two-stage simplex method.
The partially completed initial tableau is shown below.
Basic variable
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
\(a_1\)
\(a_2\)
Value
\(s_1\)
1
2
3
1
0
0
0
0
45
\(a_1\)
3
2
0
0
\(-1\)
0
1
0
9
\(a_2\)
\(-1\)
0
4
0
0
\(-1\)
0
1
4
\(P\)
\(-2\)
\(-1\)
\(-3\)
0
0
0
0
0
0
\(A\)
(a) Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities. (4)
(b) Complete the bottom row of Table 1 in the answer book. You should make your method and working clear. (2)
[Table 1 in the answer book is a copy of the partially completed initial tableau above.]
The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.
Basic variable
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
\(a_1\)
\(a_2\)
Value
\(s_1\)
0
\(\frac{5}{6}\)
0
1
\(\frac{7}{12}\)
\(\frac{3}{4}\)
\(-\frac{7}{12}\)
\(-\frac{3}{4}\)
\(\frac{147}{4}\)
\(x\)
1
\(\frac{2}{3}\)
0
0
\(-\frac{1}{3}\)
0
\(\frac{1}{3}\)
0
3
\(z\)
0
\(\frac{1}{6}\)
1
0
\(-\frac{1}{12}\)
\(-\frac{1}{4}\)
\(\frac{1}{12}\)
\(\frac{1}{4}\)
\(\frac{7}{4}\)
\(P\)
0
\(\frac{5}{6}\)
0
0
\(-\frac{11}{12}\)
\(-\frac{3}{4}\)
\(\frac{11}{12}\)
\(\frac{3}{4}\)
\(\frac{45}{4}\)
\(A\)
0
0
0
0
0
0
1
1
0
(c)
(i) Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem.
(ii) Write down the basic feasible solution for the second stage. (3)
(d) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method, to obtain a new tableau, \(T\). Make your method clear by stating the row operations you use. (5)
(e)
(i) Explain, using \(T\), whether or not an optimal solution to the original linear programming problem has been found.
(ii) Write down the value of the objective function.
(iii) State the values of the basic variables. (3)
\(A - 2x - 2y - 4z + s_2 + s_3 = -13\) therefore bottom row of the table is
\(A\)
\(-2\)
\(-2\)
\(-4\)
0
1
1
0
0
\(-13\)
A1
2.2a
(2)
Notes
(b) M1: Setting up the new objective and substituting for \(a_1\) and \(a_2\)
A1: Correct values substituted into Table 1
Mark scheme (c)
Scheme
Marks
AO
(i) In the given tableau the value of the objective \(A\) is equal to zero indicating that a basic feasible solution has been found
B1
2.4
(ii) \(x = 3,\ y = 0,\ z = \frac{7}{4},\ s_1 = \frac{147}{4},\ s_2 = s_3 = 0\)
B1 B1
3.4 1.1b
(3)
Notes
(c) B1: CAO – mention that \(A = 0\)
B1: At least three values stated correctly
B1: All six values correct (ignore values stated for \(a_1, a_2\) and \(P\))
Mark scheme (d)
Scheme
Marks
AO
b.v
\(x\)
\(y\)
\(z\)
\(s_1\)
\(s_2\)
\(s_3\)
Value
Row Ops
\(s_2\)
0
\(\frac{10}{7}\)
0
\(\frac{12}{7}\)
1
\(\frac{9}{7}\)
63
\(\text{R1} \div \frac{7}{12}\)
\(x\)
1
\(\frac{8}{7}\)
0
\(\frac{4}{7}\)
0
\(\frac{3}{7}\)
24
\(\text{R2} + \frac{1}{3}\text{R1}\)
\(z\)
0
\(\frac{2}{7}\)
1
\(\frac{1}{7}\)
0
\(-\frac{1}{7}\)
7
\(\text{R3} + \frac{1}{12}\text{R1}\)
\(P\)
0
\(\frac{15}{7}\)
0
\(\frac{11}{7}\)
0
\(\frac{3}{7}\)
69
\(\text{R4} + \frac{11}{12}\text{R1}\)
M1 A1 M1 A1 A1
2.1 1.1b 1.1b 1.1b 1.1b
(5)
Notes
(d) M1: Correct pivot located, attempt to divide row
A1: Pivot row correct including change of b.v.
M1:All values in one of the non-pivot rows correct or one of the non zero and one columns (\(y\), \(s_1, s_3\) or value) correct following through their choice of pivot from column \(s_2\) or \(s_3\)
A1: Row operations used correctly at least twice, i.e. two of the non zero and one columns (\(y\), \(s_1, s_3\) or value) correct
A1: CAO all values and row operations correctly stated – allow if row operations given in terms of old row 1 – ignore b.v. column for this mark
Mark scheme (e)
Scheme
Marks
AO
(i) Yes, an optimal solution has been found as there are no negative values in the objective (\(P\)) row
B1
2.4
(ii) \(P = 69\)
B1ft
3.4
(iii) \(s_2 = 63,\ x = 24,\ z = 7\)
B1ft
3.4
(3)
(17 marks)
Notes
(e)(i) B1: Correct reasoning of why solution is optimal or using \(P = 69 - \frac{15}{7}y - \frac{11}{7}s_1 - \frac{3}{7}s_3\) and mentioning increasing \(y, s_1, s_3\) would decrease \(P\) (oe)
(e)(ii) B1ft: their value of \(P\) – dependent on both M marks in (d)
(e)(iii) B1ft: their values of the basic variables only – dependent on both M marks in (d)
\(\left(\frac{2}{3}, \frac{5}{3}\right) \to P = \frac{11}{3}\) \(\left(\frac{60}{37}, \frac{150}{37}\right) \to P = \frac{330}{37}\) \(\left(\frac{25}{11}, \frac{36}{11}\right) \to P = \frac{111}{11}\) so optimal vertex is \(\left(\frac{25}{11}, \frac{36}{11}\right)\)
M1 A1
2.1 2.2a
(4)
Notes
(b) B1: One correct vertex (must be exact)
B1: All three correct vertices (must be exact)
M1: Testing all three of their vertices in the correct objective function
A1: Correct three values of \(P\) and correct optimal vertex either stated or clearly indicated on the graph
(c) M1: Their optimal point from (b) evaluated in \(Q\) compared to their \(\left(\frac{60}{37}, \frac{150}{37}\right)\) evaluated in \(Q\) (with correct inequality)
A1: \(a \lt \frac{5}{2}\)
M1: Their optimal point from (b) evaluated in \(Q\) compared to their \(\left(\frac{2}{3}, \frac{5}{3}\right)\) evaluated in \(Q\) (with correct inequality)
Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. Figure 3 also shows an objective line for the problem and the optimal vertex, which is labelled as \(V\).
The value of the objective at \(V\) is 556
Express the linear programming problem in algebraic form. List the constraints as simplified inequalities with integer coefficients and determine the objective. (9)
Mark scheme
Scheme
Marks
AO
Line through (0, 12) and (6, 0) is \(2x + y = 12\) Line through (0, 12) and (10, 0) is \(6x + 5y = 60\) Line through (7, 2) and (9, 8) is \(3x - y = 19\)
M1
1.1b
\(2x + y \geqslant 12\)
A1
3.4
\(6x + 5y \leqslant 60\)
A1
1.1b
\(3x - y \leqslant 19\)
A1
1.1b
Solving correct two equations to find \(V\)
M1
1.1b
\(V\left(\dfrac{155}{21},\ \dfrac{22}{7}\right)\)
A1
2.2a
\(P = k(5x + 3y)\) and substituting \(P = 556\) and their \(V\)
M1dep
3.4
Maximise \(P = 60x + 36y\)
B1 A1
2.5 2.2a
(9)
(9 marks)
Notes
M1: Correct method for finding the equation of one of the three lines
A1: CAO (with correct inequality sign from shading) \(2x + y \geqslant 12\) (allow a positive multiple but must have integer coefficients)
A1: CAO \(6x + 5y \leqslant 60\) (allow a positive multiple but must have integer coefficients)
A1: CAO \(3x - y \leqslant 19\) (allow a positive multiple but must have integer coefficients)
If A0A0A0 then award A1A0A0 only for one ‘correct’ strict inequality and/or non-integer coefficients e.g. \(x + 0.5y > 6\)
M1: Attempt to find \(V\) by solving the correct pair of simultaneous equations – for this mark either the correct method for solving the simultaneous equations must be seen or if no method seen then this mark can be implied by correctly stating the exact coordinates of \(V\) (or correct to at least 3 sf)
A1: Correct deduction of the exact coordinates for \(V\)
M1dep: Uses the model to write down a suitable objective and substitutes \(P = 556\) and their \(V\) into \(P = k(5x + 3y)\). Dependent on previous M mark.
Or this mark can be awarded for forming both equations \(\dfrac{155}{21}x + \dfrac{22}{7}y = 556\) and \(3x - 5y = 0\)
B1: Maximise (oe) e.g. allow ‘max’ – this mark is independent of all other marks
A1: Correct objective function (this mark cannot be awarded for \(5x + 3y\))
Note that the complete LP formulation is
Maximise \(P = 60x + 36y\) Subject to \(2x + y \geqslant 12\) \(\qquad\qquad\ \ 6x + 5y \leqslant 60\) \(\qquad\qquad\ \ 3x - y \leqslant 19\)
7. A shop sells two types of watch, analogue watches and digital watches.
The shop manager knows that, each month, she should order at least 60 watches in total. In addition, at most 80% of the watches she orders must be digital.
Let \(x\) be the number of analogue watches ordered and let \(y\) be the number of digital watches ordered.
(a) Write down inequalities, in terms of \(x\) and \(y\), to model these constraints. (2)
Two further constraints are
\[\begin{gathered} y + 3x \geqslant 140 \\ 4y + x \geqslant 80 \end{gathered}\]
(b) Represent all these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region, \(R\). (4)
Diagram 1
The cost to the shop of ordering an analogue watch is five times the cost of ordering a digital watch. The shop manager wishes to minimise the total cost.
(c) Determine the number of each type of watch the shop manager should order. You must make your method clear. (3)
Given that the minimum total cost of ordering the watches is £4455
(d) determine the cost of ordering one analogue watch and the cost of ordering one digital watch. You must make your method clear. (3)
Mark scheme (a)
Scheme
Marks
AO
\(x + y \geqslant 60\)
B1
3.3
\(y \leqslant \tfrac{4}{5}(x + y)\)
B1
3.3
(2)
Notes
(a) B1: CAO – allow any equivalent form of \(x + y \geqslant 60\) - do not condone strict inequality
B1: CAO – allow any equivalent form of \(y \leqslant \tfrac{4}{5}(x + y)\) (but not \(y \leqslant 80\%(x + y)\) only) and need not be simplified - do not condone strict inequality – isw if correct answer is incorrectly simplified
Mark scheme (b)
Scheme
Marks
AO
B1 B1 B1 B1
1.1b 1.1b 1.1b 2.2a
(4)
Notes
In (b), lines must be long enough to define the correct feasible region and would pass if extended through one small square of the points stated:
\(x + y = 60\) must pass within one small square of its intersection with the axes – (0, 60) and (60, 0) \(y + 3x = 140\) must pass within one small square of its intersection with the axes – (0, 140) and \(\left(\frac{140}{3}, 0\right)\) (so at 46.666…, 0) \(4y + x = 80\) must pass within one small square of its intersection with the axes – (0, 20) and (80, 0) \(y = 4x\) must pass within one small square of (0, 0) and (25, 100)
In (b) condone for full marks lines which are drawn as dashed rather than solid
(b) B1: 2 lines drawn correctly
B1: 3 lines drawn correctly
B1: 4 lines drawn correctly
B1: Region, \(R\), correctly labelled – not just implied by shading – dependent on scoring the first three marks in this part
Mark scheme (c)
Scheme
Marks
AO
objective line drawn or point-testing
M1 A1
3.1a 1.1b
(20, 80) so 20 analogue watches and 80 digital watches
A1
3.2a
(3)
Notes
(c) M1: Drawing the correct objective line (with gradient – 5) or its reciprocal (with gradient \(-\frac{1}{5}\)). Line must be correct to within one small square if extended from axis to axis. If lines shorter than (5, 0) to (0, 25) or (0, 5) to (25, 0) then M0. Or point testing at least two exact coordinates of their \(R\) using their objective function which must be of the form \(k(5x + y)\) or \(k(x + 5y)\) for some positive real value \(k\)
A1: Correct objective line – condone lack of labelling of the objective line. Or point testing at least two of the correct exact coordinates which are (20, 80), (40, 20), (80, 0) and \(\left(\frac{160}{3}, \frac{20}{3}\right)\) using a correct objective function of the form \(k(5x + y)\)
A1: Correct number of watches – must be in context (and not just in terms of \(x\) and \(y\)) – dependent on a correct feasible region in (b) (so must have scored the first three marks in (b) but may not have labelled the FR as \(R\))
Mark scheme (d)
Scheme
Marks
AO
\(20a + 80d = 4\,455\)
B1ft
3.1b
\(a = 5d\)
B1
2.1
Leading to \(a = 123.75\) and \(d = 24.75\) so an analogue watch costs £123.75 and a digital watch costs £24.75
dB1
2.2a
(3)
(12 marks)
Notes
Condone use of \(\boldsymbol{x}\) for \(\boldsymbol{a}\) and \(\boldsymbol{y}\) for \(\boldsymbol{d}\) in part (d)
(d) B1ft: A ‘correct’ equation (e.g. \(20a + 80d = 4\,455\)) involving their optimal point from (c) (accept any values even if non-integer) and 4455 –- note that for those who have done point testing in (c) the calculation 4455 / (their value for \(P\)) where \(P = 5x + y\) or \(x + 5y\) using their optimal point implies this mark
B1: CAO on the relationship between the costs of the two types of watches (\(a = 5d\)) – this mark may be implied e.g. \(20(5d) + 80d = 4455\) would score the first two marks in this part – note that for those who have done point testing in (c) the calculation 4455 / (their value for \(P\)) where \(P = 5x + y\) using their optimal point implies this mark e.g. just seeing 4455 / 180 is the first two marks in this part
dB1: CAO (dependent on first two B marks) – this mark is dependent on having the correct optimal point (20, 80) and is dependent on a correct feasible region in (b) (so must have scored at least the first three marks in (b)) – allow for \(a = 123.75\) and \(d = 24.75\) (so does not need to be in context or units) – the correct answers with no working scores no marks in this part (however, note that 4455 / 180 is the minimum amount of working that is acceptable)
(b) B1: CAO \(3x + y + 2z + s_1 = 30\) (may be seen in the simplex tableau – allow any \(s_i\) (or \(s\)) for \(s_1\))
B1: CAO \(x - y + z - s_2 + a_1 = 8\) (may be seen in the simplex tableau – allow any consistent \(s_i\) for \(s_2\) (or \(t\) say) but not the same \(s_i\) as in the previous mark and allow any \(a_i\) for \(a_1\))
B1: CAO \(4y + 2z - s_3 + a_2 = 15\) (may be seen in the simplex tableau – same conditions as above)
M1: setting up the new objective which must be \(P = 2x + 2y - z - M(a_1 + a_2)\) and substituting for their \(a_1\) and \(a_2\) (if no working then the correct objective line in the tableau implies this mark)
A1: CAO \(P - (2 + M)x - (2 + 3M)y - (-1 + 3M)z + Ms_2 + Ms_3 = -23M\) (any equivalent form – need not be factorised and does not need to be re-arranged into this form - if no working then the correct objective line in the tableau implies this mark)
M1: setting up initial tableau – all four rows complete with two correct rows (but ignore b.v. column for this mark)
A1: CAO (any equivalent correct form)
Mark scheme (c)
Scheme
Marks
AO
\(s_1 = 26.25,\ a_1 = 11.75,\ y = 3.75,\ x = z = s_2 = s_3 = a_2 = 0\)
B1
3.4
(1)
Notes
(c) B1: CAO \(s_1 = 26.25,\ a_1 = 11.75,\ y = 3.75,\ x = z = s_2 = s_3 = a_2 = 0\) (ignore expression for \(P\) if given)
Mark scheme (d)
Scheme
Marks
AO
The solution after the 1st iteration is not feasible because \(a_1 = 11.75\) is an artificial variable which must be zero in a feasible solution
B1
2.4
(1)
Notes
(d) B1: correct reasoning of why the solution is not feasible e.g. \(a_1\) is not zero but B0 for just stating that the artificial variable is non-zero (so must see either \(a_1\) or 11.75 being stated as non-zero)
Mark scheme (e)
Scheme
Marks
AO
The most negative value in the objective row is \(2 - 1.5M\) so the pivot is a value from the \(z\)-column
B1
2.4
The 0.5 in the \(y\) row is the pivot because \(\dfrac{3.75}{0.5}\) is less than both \(\dfrac{26.25}{1.5}\) and \(\dfrac{11.75}{1.5}\)
dB1
2.2a
(2)
(12 marks)
Notes
(e) B1: correct reasoning of why the pivot comes from a value from the \(z\)-column so must say that the most negative value (in the objective row) is \(2 - 1.5M\) (or this expression clearly implied)
dB1: correct justification of why the 0.5 in the third row is the next pivot (dependent on previous B mark) – so must compare or state that \(\dfrac{3.75}{0.5}\) or 7.5 is less than both \(\dfrac{26.25}{1.5}\) or 17.5 and \(\dfrac{11.75}{1.5}\) or 7.8(3333….) – just stating that the 0.5 in the third row is the next pivot without reasoning is no marks in this part
5. Ben is a wedding planner. He needs to order flowers for the weddings that are taking place next month. The three types of flower he needs to order are roses, hydrangeas and peonies.
Based on his experience, Ben forms the following constraints on the number of each type of flower he will need to order.
At least three-fifths of all the flowers must be roses.
For every 2 hydrangeas there must be at most 3 peonies.
The total number of flowers must be exactly 1000
The cost of each rose is £1, the cost of each hydrangea is £5 and the cost of each peony is £4
Ben wants to minimise the cost of the flowers.
Let \(x\) represent the number of roses, let \(y\) represent the number of hydrangeas and let \(z\) represent the number of peonies that he will order.
(a) Formulate this as a linear programming problem in \(x\) and \(y\) only, stating the objective function and listing the constraints as simplified inequalities with integer coefficients. (7)
Ben decides to order the minimum number of roses that satisfy his constraints.
(b)
(i) Calculate the number of each type of flower that he will order to minimise the cost of the flowers.
(ii) Calculate the corresponding total cost of this order. (3)
Mark scheme (a)
Scheme
Marks
AO
Minimise \((P =)\, x + 5y + 4z\)
B1
3.3
Subject to \(x \geqslant \dfrac{3}{5}(x + y + z)\ (\Rightarrow 2x \geqslant 3y + 3z)\)
B1
3.3
\(3y \geqslant 2z\)
B1
3.3
\(x + y + z = 1000\)
B1
3.3
\(z = 1000 - x - y\) substituted into objective and constraints gives
M1
3.1a
Minimise \((P =)\, y - 3x\,(+\ 4000)\) subject to \(x \geqslant 600\) and \(2x + 5y \geqslant 2000\)
A1 A1
1.1b 1.1b
(7)
Notes
B1: CAO (for objective) – must contain ‘minimise’ or ‘min’ only (so not ‘minimum’) either when stated in terms of \(x\), \(y\) and \(z\) or \(x\) and \(y\) only
B1: \(x \geqslant \dfrac{3}{5}(x + y + z)\) oe – need not be simplified for this mark, accept \(x \geqslant \dfrac{3}{5}(1000)\)
B1: \(3y \geqslant 2z\) or any equivalent form (need not be simplified nor integer coefficients for this mark)
B1: \(x + y + z = 1000\) (could be implied by earlier/later working)
M1: Eliminating \(z\) from either the objective or both constraints using the constraint \(x + y + z = 1000\)
A1: Correct objective in terms of \(x\) and \(y\) only – condone lack of ‘minimise’
A1: Both constraints correct (\(x \geqslant 600\) and \(2x + 5y \geqslant 2000\) - must be integer coefficients for this mark)
Mark scheme (b)
Scheme
Marks
AO
(i) Using least value of \(x\) to find \(y\) and \(z\) 600 roses, 160 hydrangeas and 240 peonies (ii) £2360
M1 A1 A1
3.4 3.2a 1.1b
(3)
(10 marks)
Notes
(b)(i) M1: Using their least value of \(x\) to find both \(y\) and \(z\) (with both \(y\) and \(z\) being positive integers) – note that all values must satisfy the constraint \(x + y + z = 1000\) (and must all be integers)
A1: All three types of flowers correct (in context – so not just in terms of \(x\), \(y\) and \(z\)) – must come from correct constraints in (a)
(ii) A1: CAO for cost (condone lack of units but not 2360p) – must come from correct constraints in (a)
SC for (b) – for those candidates with the constraint \(2y \geqslant 3z\) in (a) leading to 600 roses, 240 hydrangeas and 160 peonies (so not just in terms of \(x\), \(y\) and \(z\)) together with (£)2440 award SC M1A1A0 in (b)
4. The manager of a factory is planning the production schedule for the next three weeks for a range of cabinets. The following constraints apply to the production schedule.
The total number of cabinets produced in week 3 cannot be fewer than the total number produced in weeks 1 and 2
At most twice as many cabinets must be produced in week 3 as in week 2
The number of cabinets produced in weeks 2 and 3 must, in total, be at most 125
The production cost for each cabinet produced in weeks 1, 2 and 3 is £250, £275 and £200 respectively.
The factory manager decides to formulate a linear programming problem to find a production schedule that minimises the total cost of production.
The objective is to minimise \(250x + 275y + 200z\)
(a) Explain what the variables \(x\), \(y\) and \(z\) represent. (1)
(b) Write down the constraints of the linear programming problem in terms of \(x\), \(y\) and \(z\). (2)
Due to demand, exactly 150 cabinets must be produced during these three weeks. This reduces the constraints to
\[\begin{gathered} x + y \leqslant 75 \\ x + 3y \geqslant 150 \\ x \geqslant 25 \\ y \geqslant 0 \end{gathered}\]
which are shown in Diagram 1 in the answer book.
Diagram 1
Given that the manager does not want any cabinets left unfinished at the end of a week,
(c)
(i) use a graphical approach to solve the linear programming problem and hence determine the production schedule which minimises the cost of production. You should make your method and working clear.
(ii) Find the minimum total cost of the production schedule. (8)
Mark scheme (a)
Scheme
Marks
AO
\(x\) is the number of cabinets produced in week 1, \(y\) is the number of cabinets produced in week 2 and \(z\) is the number of cabinets produced in week 3
B1
2.5
(1)
Notes
B1: Cao - must contain ‘number of…’ (oe e.g. ‘amount of’, ‘quantity of’,…) at least once
Mark scheme (b)
Scheme
Marks
AO
\(x + y \leqslant z\) \(z \leqslant 2y\) \(y + z \leqslant 125\) \((x, y, z \geqslant 0)\)
B1 B1
3.3 3.3
(2)
Notes
B1: Any one correct (accept strict inequalities)
B1: All three correct
Mark scheme (c)
Scheme
Marks
AO
(i) Objective is \(P = 250x + 275y + 200(150 - x - y)\)
M1
3.1a
\(P = 50x + 75y\ (+\ 30000)\)
A1
1.1b
Objective line drawn or at least two vertices tested
M1
3.1a
Optimal point \(\left(25,\ \dfrac{125}{3}\right)\)
A1
1.1b
Consideration of integer coordinates around the optimal vertex
M1
1.1b
Correct integer coordinate (25, 42)
A1
1.1b
The production schedule is 25 cabinets in week 1, 42 cabinets in week 2 and 83 cabinets in week 3
B1
3.2a
(ii) Total cost of production is £34 400
B1
1.1b
(8)
(11 marks)
Notes
Note that the vertices of the FR are \(\left(25,\ \dfrac{125}{3}\right), (25,\ 50), \left(\dfrac{75}{2},\ \dfrac{75}{2}\right)\)
(c)(i) M1: Attempt to derive new objective function in terms of \(x\) and \(y\) only by using \(x + y + z = 150\) or attempt to calculate all three values of \(z\) using \(x + y + z = 150\)
A1: Cao for objective in terms of \(x\) and \(y\) only or all three correct \(z\) values \(\left(\dfrac{250}{3},\ 75,\ 75\right)\)
M1: Objective line drawn consistent with their objective function (or its reciprocal) or testing two of the correct vertices (to at least 1 decimal place where applicable) in their objective function involving \(x\) and \(y\) only or testing two of the correct vertices (to at least 1 decimal place where applicable) in \(250x + 275y + 200z\)
A1: Correct optimal point \(\left(25,\ \dfrac{125}{3}\right)\) or \(\left(25,\ \dfrac{125}{3},\ \dfrac{250}{3}\right)\) - accept 41.6 or 41.7 (or better) – so at least 1 decimal place (truncated or rounded) if not given exact
M1: Consideration of integer point(s) (e.g. (25, 41) etc.) around the optimal vertex – must have attempted point testing of the vertices of the feasible region or objective line
A1: Correct integer coordinate (25, 42) stated and either clear rejection of (26, 41) - by checking in \(x + 3y \geqslant 150\) or testing of (27, 41) in a correct objective function
B1: Cao (in context – so not in terms of \(x\), \(y\) and \(z\))
Figure 4 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.
The vertices of the feasible region are \(A(4, 7)\), \(B(5, 3)\), \(C(-1, 5)\) and \(D(-2, 1)\).
(a) Determine the inequality that defines the boundary of \(R\) that passes through vertices \(A\) and \(C\), leaving your answer with integer coefficients only. (3)
The objective is to maximise \(P = 5x + y\)
(b) Find the coordinates of the optimal vertex and the corresponding value of \(P\). (3)
The objective is changed to maximise \(Q = kx + y\)
(c) If \(k\) can take any value, find the range of values of \(k\) for which \(A\) is the only optimal vertex. (4)
Mark scheme (a)
Scheme
Marks
\(A(4,7), B(5,3), C(-1,5), D(-2,1)\)
Equation through \(AC\) e.g. \(\dfrac{y-7}{5-7} = \dfrac{x-4}{-1-4}\) or \(y - 7 = \left(\dfrac{5-7}{-1-4}\right)(x-4)\) or \(y - 5 = \left(\dfrac{7-5}{4-(-1)}\right)(x+1)\)
M1
\(5y - 2x = 27\) (oe)
A1
\(5y - 2x \leqslant 27\)
A1
(3)
Notes
a1M1: Correct method for finding the equation of the line through \(A\) and \(C\) – a correct equation can imply this mark – condone one sign error only
a1A1: Correct equation (any correct form (allow unsimplified or simplified incorrectly) – condone any inequality sign or equals)
a2A1: CAO (any equivalent form provided coefficients are integers)
Mark scheme (b)
Scheme
Marks
Point testing \(A\) and \(B\) or objective line (with gradient of \(-5\))
M1
At \(B(5, 3)\), \(P = 28\) at \(A(4, 7)\), \(P = 27\) so optimal point is \(B\) with \(P = 28\)
A1 A1
(3)
Notes
b1M1: Correct objective line drawn (gradient of \(-5\) - acceptable minimum length is from \((0,1)\) to \((0.2,0)\)) or testing both \(A\) and \(B\) in the correct objective function
b1A1: CAO (\(B\) or (5, 3))
b2A1: \(P = 28\) (allow if seen in working for \(B\))
Mark scheme (c)
Scheme
Marks
\(A \gt B \Rightarrow 4k + 7 \gt 5k + 3\) or objective line argument
M1
\(k \lt 4\)
A1
\(A \gt C \Rightarrow 4k + 7 \gt -k + 5\) or objective line argument
M1
\(k \gt -\dfrac{2}{5}\)
A1
(4)
10 marks
Notes
c1M1: Put expression for \(A\) > expression for \(B\) (accept any inequality or equals) or considers gradient of line segment through \(A\) and \(B\) with \(-k\). Condone \(x\) for \(k\) for the M mark only
c1A1: \(k \lt 4\)
c2M1: Put expression for \(A\) > expression for \(C\) (accept any inequality or equals) or considers gradient of line segment through \(A\) and \(C\) with \(-k\). Condone \(x\) for \(k\) for the M mark only
5. A linear programming problem in \(x\), \(y\) and \(z\) is described as follows.
Maximise \(P = 2x + 3y + z\)
subject to \[\begin{aligned} 2y - 3z &\leqslant 30 \\ -3x + y + z &\leqslant 60 \\ x + 4y - z &\leqslant 80 \end{aligned}\]
(a) Complete the initial tableau in the answer book for this linear programming problem. (3)
(b) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm to obtain a new tableau, T. Make your method clear by stating the row operations you use. (5)
(c) Write down the profit equation given by T and state the values of the slack variables given by T. (2)
The following tableau is obtained after further iterations.
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
0
2
–3
1
0
0
30
\(s\)
0
13
–2
0
1
3
300
\(x\)
1
4
–1
0
0
1
80
\(P\)
0
5
–3
0
0
2
160
(d) Explain why no optimal solution can be found by applying the simplex algorithm to the above tableau. (1)
Mark scheme (a)
Scheme
Marks
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(r\)
0
2
−3
1
0
0
30
\(s\)
−3
1
1
0
1
0
60
\(t\)
1
4
−1
0
0
1
80
\(P\)
−2
−3
−1
0
0
0
0
M1 A1 B1
(3)
Notes
a1M1: Any one row correct (but ignore b.v. column)
a1A1: All four rows correct (but ignore b.v. column)
a1B1: b.v. column correct
Mark scheme (b)
Scheme
Marks
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
row ops
\(y\)
0
1
\(-\frac{3}{2}\)
\(\frac{1}{2}\)
0
0
15
\(R_1 \div 2\)
\(s\)
−3
0
\(\frac{5}{2}\)
\(-\frac{1}{2}\)
1
0
45
\(R_2 - R_1\)
\(t\)
1
0
5
−2
0
1
20
\(R_3 - 4R_1\)
\(P\)
−2
0
\(-\frac{11}{2}\)
\(\frac{3}{2}\)
0
0
45
\(R_4 + 3R_1\)
M1 A1 M1 A1ft A1
(5)
Notes
b1M1: Correct pivot located (2 in column \(y\)), attempt to divide row
b1A1: Pivot row correct including change of b.v
b2M1: All values in one of the non-pivot rows correct or one of the non zero and one columns (\(x\), \(z\), \(r\) or value) correct following through their choice of pivot from column \(y\)
b2A1ft: Row operations used correctly at least twice, i.e. two of the non zero and one columns (\(x\), \(z\), \(r\) or value) correct following through their choice of pivot from column \(y\)
b3A1: CAO – no follow through – all values and row operations correctly stated – allow if row operations given in terms of old row 1 – ignore b.v. column for this mark
Mark scheme (c)
Scheme
Marks
\(P - 2x - \dfrac{11}{2}z + \dfrac{3}{2}r = 45\)
B1ft
\(r = 0, s = 45, t = 20\)
B1
(2)
Notes
c1B1ft: Follow their profit equation from (b) dependent on scoring both M marks in (b)
c2B1: CAO (no follow through) for slack variables (\(r = 0\), \(s = 45\), \(t = 20\))
Mark scheme (d)
Scheme
Marks
All values in the (next) pivot column (the \(z\) column) are negative and so no further iterations can occur or no viable pivot.
7. A café sells two types of scone, plain and fruit.
The café manager knows that each week she should order
at least 400 scones in total
at most 350 fruit scones
In addition, for every 3 fruit scones ordered, at most 5 plain scones should be ordered.
Each plain scone costs £0.11 and is sold at a profit of £0.75
Each fruit scone costs £0.14 and is sold at a profit of £1
The manager has £77 to spend each week on scones. The manager wants to maximise her profit and it can be assumed that all scones ordered will be sold.
Let \(x\) represent the number of plain scones and let \(y\) represent the number of fruit scones that are sold.
(a) Formulate this information as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. (6)
(b) Represent these constraints on Diagram 1 in the answer book. Hence determine the feasible region and label it R. (4)
(c) Use the objective line method to find the optimal vertex, V, of the feasible region. You must make your objective line clear and label the optimal vertex V. (3)
(d) Calculate the exact coordinates of V. (2)
(e) State the number of each type of scone that the manager should order and calculate the maximum profit. (2)
Mark scheme (a)
Scheme
Marks
Maximise \(0.75x + y\)
B1
Subject to \(x + y \geqslant 400\)
B1
\(y \leqslant 350\)
B1
\(5y \geqslant 3x\)
M1 A1
\(11x + 14y \leqslant 7700\)
B1
(6)
Notes
a1B1: Expression correct (or \(75x + 100y\)) together with ‘maximise’ or ‘max’ but not ‘maximum’ – isw if coefficients are subsequently simpified but either \(75x + 100y\) or \(0.75x + y\) must be seen at some point for this mark to be awarded. The ‘max’ must appear beside or suitably close to one of the correct two expressions
a2B1: CAO (\(x + y \geqslant 400\))
a3B1: CAO (\(y \leqslant 350\))
a1M1: \(5y \blacksquare 3x\) where \(\blacksquare\) is any inequality or equals. Accept \(3y \geqslant 5x\) for this mark. M0 if coefficients are not integers
a1A1: CAO (\(5y \geqslant 3x\))
a4B1: CAO (\(11x + 14y \leqslant 7700\))
Mark scheme (b)
Scheme
Marks
B1
B1
B1
B1
(4)
Notes
In (b), lines must be long enough to define the correct feasible region and pass through one small square of the points stated:
\(x + y = 400\) must pass within one small square of its intersection with the axes – (0, 400) and (400, 0)
\(11x + 14y = 7700\) must pass within one small square of its intersection with the axes – (0, 550) and (700, 0)
\(5y = 3x\) must pass within one small square of (0, 0) and if extended pass through (500, 300)
\(y = 350\) must pass within one small square of (0, 350) and if extended pass through (500, 350)
b1B1: Any two lines correctly drawn
b2B1: Any three lines correctly drawn
b3B1: All four lines correctly drawn
b4B1: Region, R, correctly labelled – dependent on scoring the first three marks in this part
Mark scheme (c)
Scheme
Marks
Drawing an objective line accept reciprocal gradient
M1
Correct objective line
A1
V correctly labelled
A1
(3)
Notes
c1M1: Drawing their objective line (based on their answer to (a)) or its reciprocal – if their line on the graph is shorter than the length equivalent to that of the line from (0, 37.5) to (50, 0) then M0. Line must be correct to within one small square if extended from axis to axis. Their line must have a negative gradient
c1A1: Drawing the correct objective line – same condition that the line must be correct to within one small square if extended from axis to axis
c2A1: The correct V labelled or clearly identified on their graph – note that this mark is dependent on scoring at least B1B1B1B0 in (b) and the two previous marks in this part
Mark scheme (d)
Scheme
Marks
\(\text{V}\left(\dfrac{2800}{11},\ 350\right)\)
M1 A1
(2)
Notes
d1M1:Must have scored at least B1B1B0B0 in (b) and candidates must have drawn an objective line (but note that it does not need to be correct but must have negative gradient). Must be solving one of the following three pairs of equations only: \(11x + 14y = 7700,\ y = 350\) or \(11x + 14y = 7700,\ 5y = 3x\) or \(5y = 3x,\ y = 350\). Must be a correct method to solve simultaneous equations and must arrive at \(x = \ldots\) and \(y = \ldots\) but allow slips/errors. This mark can also be awarded for the correct exact coordinates stated with no working provided B1B1B0B0 in (b) and an objective line drawn
d1A1: Correct exact coordinates of V either derived or stated (so no working required) as either \(\left(\dfrac{2800}{11},\ 350\right)\) or \(\left(254\dfrac{6}{11},\ 350\right)\). Note that this mark is dependent on B1B1B1B0 scored in (b) and a correct objective line
Mark scheme (e)
Scheme
Marks
(The manager should buy) 254 plain (scones) and 350 fruit (scones)
B1
Profit is (£) 540.50
B1
(2)
(17 marks)
Notes
e1B1: CAO in context – so not in terms of \(x\) and \(y\) only – dependent on B1B1B1B0 in (b) and a correct objective line
e2B1: CAO (allow 540.5) – dependent on B1B1B1B0 in (b) and a correct objective line – condone lack of units if given in £ (or 54050p – if given in pence, however, units must be given)
5. The initial tableau for a linear programming problem in \(x\), \(y\) and \(z\) is shown below. The objective function to be maximised is \(P = 4x + 2y + kz\), where \(k\) is a positive constant.
Basic Variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
−2
−6
1
1
0
0
40
\(s\)
2
3
2
0
1
0
80
\(t\)
1
2
2
0
0
1
50
\(P\)
−4
−2
\(-k\)
0
0
0
0
(a) Using the information in the tableau, write down the three constraints as inequalities. (2)
(b) By increasing \(x\), perform one complete iteration of the simplex algorithm to obtain tableau T1 and state the row operations you use. (4)
(c) Given that T1 is not optimal, find an inequality for the value of \(k\). (1)
(d) Perform a second complete iteration of the simplex algorithm to obtain tableau T2 and state the row operations you use. (4)
(e) Given that T2 is optimal, find a second inequality for the value of \(k\). (2)
(f) State the final value of each variable and give an expression for the final value of \(P\) in terms of \(k\). (2)
(g) Hence find the range of possible values of \(P\). (2)
a1M1: Two correct equations (e.g. \(-2x - 6y + z + r = 40\)) or inequalities
a1A1: CAO (not equations)
Mark scheme (b)
Scheme
Marks
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
row ops
\(r\)
0
–3
3
1
1
0
120
\(R_1 + 2R_2\)
\(x\)
1
3/2
1
0
1/2
0
40
\(0.5R_2\)
\(t\)
0
1/2
1
0
–1/2
1
10
\(R_3 - R_2\)
\(P\)
0
4
\(4-k\)
0
2
0
160
\(R_4 + 4R_2\)
M1 A1 M1 A1
(4)
Notes
b1M1: Correct pivot located (2 in \(x\) column), attempt to divide row. If choosing negative pivot M0M0
b1A1: CAO pivot row correct including change of b.v. (\(s\) must be changed to \(x\))
b2M1: (ft) All values in one of the non-pivot rows correct or one of the non-zero/one columns correct (that is one of the \(y\), \(z\), \(s\) or value columns correct) following through their choice of positive pivot
b2A1: CAO on all values for first iteration – ignore row operations and b.v. column for this mark
Mark scheme (c)
Scheme
Marks
\(4 - k \lt 0 \;(\Rightarrow k \gt 4)\)
B1
(1)
Notes
c1B1: CAO (must be strict inequality)
Mark scheme (d)
Scheme
Marks
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
row ops
\(r\)
0
–9/2
0
1
5/2
–3
90
\(R_1 - 3R_3\)
\(x\)
1
1
0
0
1
–1
30
\(R_2 - R_3\)
\(z\)
0
1/2
1
0
–1/2
1
10
\(R_3\)
\(P\)
0
\(2+k/2\)
0
0
\(4-k/2\)
\(-4+k\)
\(120+10k\)
\(R_4 - (4-k)R_3\)
B1 M1 A1 A1
(4)
Notes
d1B1: CAO pivot row correct including change of b.v.
d1M1: All values in one of the non-pivot rows correct or one of the non zero and one columns (\(y\), \(s\), \(t\) or value) correct following through their choice of pivot from column \(z\)
d1A1: Row operations used correctly at least twice, i.e. two of the non zero and one columns (\(y\), \(s\), \(t\) or value) correct
d2A1: CAO – both iterations - all values correct and all eight row operations correctly stated – allow if row operations given in terms of old row 2 – ignore b.v. columns for this mark
Mark scheme (e)
Scheme
Marks
\(4 - k/2 \geqslant 0 \;(\Rightarrow k \leqslant 8)\)
M1 A1
(2)
Notes
e1M1: Setting any of the expressions in terms of \(k\) from the \(P\) row from their second iteration > or \(\geqslant\) 0 - dependent on all M marks in (b) and (d) and both correct pivot rows (but ignore b.v. label)
e1A1: CAO (oe) – need not be simplified but must not be strict inequality – if no working shown and fully correct award both marks, if no working shown and incorrect M0 A0
Mark scheme (f)
Scheme
Marks
\((P =)\, 120 + 10k\)
B1
\(x = 30,\ y = 0,\ z = 10,\ r = 90,\ s = t = 0\)
B1ft
(2)
Notes
f1B1: CAO
f2B1ft: Follow through their values - dependent on all M marks earned in (b) and (d)
Mark scheme (g)
Scheme
Marks
\(160 \lt P \leqslant 200\)
M1 A1
(2)
17 marks
Notes
g1M1: Either 160 or 200 seen (but not as a term in an equation)
7. A caterer can make three different sizes of salad; small, medium and large.
The caterer will make a total of at least 280 salads.
The caterer wants at least 35% of the salads to be small and no more than 20% of the salads to be large.
The caterer has enough ingredients to make 400 small salads or 300 medium salads or 200 large salads.
The profit on each small, medium and large salad is 40p, 60p and 85p respectively. The caterer wants to maximise his total profit.
Let \(x\) represent the number of small salads, \(y\) represent the number of medium salads and \(z\) represent the number of large salads.
Formulate this information as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients.
You should not attempt to solve the problem. (8)
Mark scheme
Scheme
Marks
Maximise \((P =)\ 40x + 60y + 85z\)
B1
Subject to: \(x + y + z \geqslant 280\)
B1
\(\dfrac{7}{20}(x + y + z) \leqslant x\) which simplifies to \(13x \geqslant 7y + 7z\)
M1 A1
\(\dfrac{1}{5}(x + y + z) \geqslant z\) which simplifies to \(x + y \geqslant 4z\)
M1 A1
\(\dfrac{x}{400} + \dfrac{y}{300} + \dfrac{z}{200} \leqslant 1\) which simplifies to \(3x + 4y + 6z \leqslant 1200\)
M1 A1
\((x,\ y,\ z \geqslant 0)\)
(8 marks)
Notes
1B1: Expression correct (or \(0.4x + 0.6y + 0.85z\)) together with ‘maximise’ or ‘max’ but not ‘maximum’ – isw if coefficients are subsequently simpified but either \(40x + 60y + 85z\) or \(0.4x + 0.6y + 0.85z\) must be seen at some point for this mark to be awarded
2B1: CAO
1M1: Correct method: \(\dfrac{7}{20}(x + y + z) \bullet x\) where \(\bullet\) is any inequality or =. The bracket must be present or implied by later working. An exact equivalent answer (with or without integer coefficients but with correct inequality sign) with no working can score M1. Accept equivalent fractions or decimals for 7/20 but not 35% (unless later converted to a correct fraction/decimal)
1A1: CAO – answer must have integer coefficients with like terms collected i.e. \(k(13x \geqslant 7y + 7z)\) for any positive integer \(k\) - the correct answer with no working can score M1 A1
2M1: Correct method: \(\dfrac{1}{5}(x + y + z) \bullet z\) where \(\bullet\) is any inequality or = . The bracket must be present or implied by later working. An exact equivalent answer (with or without integer coefficients but with correct inequality sign) with no working can score M1. Accept equivalent fractions or decimals for 1/5 but not 20% (unless later converted to a correct fraction/decimal)
2A1: CAO – answer must have integer coefficients with like terms collected i.e. \(k(x + y \geqslant 4z)\) for any positive integer \(k\) - the correct answer with no working can score M1 A1
3M1: Correct complete method: \(\dfrac{x}{400} + \dfrac{y}{300} + \dfrac{z}{200} \bullet 1\) (oe) where \(\bullet\) is any inequality or =. An exact equivalent answer (with or without integer coefficients but with correct inequality sign) with no working can score M1
3A1: CAO – answer must have integer coefficients with like terms collected i.e. \(k(3x + 4y + 6z \leqslant 1200)\) for any positive integer \(k\) - the correct answer with no working can score M1 A1
Condone \(s\), \(m\) and \(l\) for \(x\), \(y\) and \(z\) for full marks – any other letter used then please send to review (unless clearly defined and then award as per the scheme)
5. The tableau below is the initial tableau for a three-variable linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
15
–2
3
1
0
0
180
\(s\)
10
1
1
0
1
0
80
\(t\)
1
6
–2
0
0
1
100
\(P\)
–1
–2
–5
0
0
0
0
(a) Using the information in the tableau, write down
(i) the objective function,
(ii) the three constraints as inequalities.
(3)
(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use. (8)
(c) State the final values of the objective function and each variable. (2)
Mark scheme (a)
Scheme
Marks
(i) \(P = x + 2y + 5z\)
B1
(ii) \(15x - 2y + 3z \leqslant 180\) \(10x + y + z \leqslant 80\) \(x + 6y - 2z \leqslant 100\)
M1 A1
(3)
Notes
ai1B1: CAO - allow in any equivalent form e.g. \(P - x - 2y - 5z = 0\) but not say \(P = x + 2y + 5z = 0\)
aii1M1: Two inequalities (or equations with slack variables) correct
aii1A1: CAO
Mark scheme (b)
Scheme
Marks
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(r\)
15
-2
3
1
0
0
180
\(s\)
10
1
1
0
1
0
80
\(t\)
1
6
-2
0
0
1
100
\(P\)
-1
-2
-5
0
0
0
0
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
row ops
\(z\)
5
\(-\frac{2}{3}\)
1
\(\frac{1}{3}\)
0
0
60
\(R_1 \div 3\)
\(s\)
5
\(\boldsymbol{\frac{5}{3}}\)
0
\(-\frac{1}{3}\)
1
0
20
\(R_2 - R_1\)
\(t\)
11
\(\frac{14}{3}\)
0
\(\frac{2}{3}\)
0
1
220
\(R_3 + 2R_1\)
\(P\)
24
\(-\frac{16}{3}\)
0
\(\frac{5}{3}\)
0
0
300
\(R_4 + 5R_1\)
M1 A1 M1 A1
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
row ops
\(z\)
7
0
1
\(\frac{1}{5}\)
\(\frac{2}{5}\)
0
68
\(R_1 + \frac{2}{3}R_2\)
\(y\)
3
1
0
\(-\frac{1}{5}\)
\(\frac{3}{5}\)
0
12
\(R_2 \div \frac{5}{3}\)
\(t\)
-3
0
0
\(\frac{8}{5}\)
\(-\frac{14}{5}\)
1
164
\(R_3 - \frac{14}{3}R_2\)
\(P\)
40
0
0
\(\frac{3}{5}\)
\(\frac{16}{5}\)
0
364
\(R_4 + \frac{16}{3}R_2\)
M1 A1ft M1 A1
(8)
Notes
b1M1: Correct pivot located (3 in the \(z\) column), attempt to divide row. If choosing negative pivot then M0M0
b1A1: CAO pivot row correct including change of b.v. (so \(r\) must be changed to \(z\))
b2M1: (ft) All values in one of the non-pivot rows correct or one of the non zero/one columns (\(x\), \(y\), \(r\) or value) correct following through their choice of pivot
b2A1: CAO on all values for the first iteration – ignore row ops and b.v. column for this mark
b3M1: Their correct pivot located following their first iteration, attempt to divide row. If choosing negative pivot M0M0 - however, allow recovery for the third and fourth M marks only if positive pivot chosen for the second iteration after a negative pivot chosen for the first iteration
b3A1ft: Their pivot row correct including change of b.v. following their first iteration
b4M1: (ft) All values in one of the non-pivot rows correct or one of the non zero/one columns (\(x\), \(r\), \(s\) or value) correct following through their choice of pivot
b4A1: CAO for all values and row operations for both iterations - including all eight row operations stated correctly (ignore b.v. column for this mark)
If pivoting on any other positive value for the first iteration then candidates can score in (b) and (c):
(b) M0A0M1A0 M1A1M0A0 (c) M1A0 (so max. of 4/10)
Mark scheme (c)
Scheme
Marks
\(P = 364;\ x = 0;\ y = 12;\ z = 68;\ r = s = 0;\ t = 164\)
M1 A1
(2)
13 marks
Notes
c1M1: Their correct values stated for at least \(P\), \(x\), \(y\), \(z\) from their ‘optimal’ iteration so there must be no negatives in the profit row. Two M marks in (b) must have been awarded – the numerical value of \(P\) must be explicitly stated and not as part of an equation
a1B1: Any two correct (accept strict inequalities) – accept equivalent inequalities
a2B1: CAO (accept equivalent inequalities)
Mark scheme (b)
Scheme
Marks
(4,2), (0,10)
B1
\(\left(\dfrac{100}{9},\ \dfrac{50}{9}\right)\) or \(\left(11\dfrac{1}{9},\ 5\dfrac{5}{9}\right)\)
M1 A1
(3)
Notes
b1B1: CAO for both integer coordinates – accept \(x = 4,\ y = 2\), etc.
b1M1: Using simultaneous equations to find the non-integer vertex – must get to \(x = \ldots\) and \(y = \ldots\) Must be a correct method to solve simultaneous equations but allow slips/errors. If no working present then this mark can be awarded for an awrt (11.1, 5.56) or (11.1, 5.55)
b1A1: CAO – must be exact (condone correct recurring decimal notation). If correct answer seen with no working then award M1 A1 in this part. ISW if correct exact answer seen which is then given in non-exact form
Mark scheme (c)
Scheme
Marks
\((0,10) \to P = 30\) \((4,2) \to P = 14\) \(\left(\dfrac{100}{9},\ \dfrac{50}{9}\right) \to P = \dfrac{350}{9}\) or \(38\dfrac{8}{9}\) so optimal vertex is \(\left(\dfrac{100}{9},\ \dfrac{50}{9}\right)\)
M1 A1
(2)
Notes
c1M1: Testing all three of their vertices in the correct objective function
c1A1: Correct three values for \(P\) (accept awrt 38.9 for 350/9) and correct optimal vertex either stated or clearly indicated (allow awrt (11.1, 5.56) or (11.1, 5.55))
Mark scheme (d)
Scheme
Marks
\(Q = 2x + \lambda y\)
\(2\left(\dfrac{100}{9}\right) + \lambda\left(\dfrac{50}{9}\right) \gt 2(0) + \lambda(10)\) or objective line method (see Way 2)
M1
\(\Rightarrow \lambda \lt 5\)
A1
\(2\left(\dfrac{100}{9}\right) + \lambda\left(\dfrac{50}{9}\right) \gt 2(4) + \lambda(2)\) or objective line method (see Way 2)
M1
\(\Rightarrow \lambda \gt -4\)
A1
\((-4 \lt \lambda \lt 5)\)
(4)
(11 marks)
Notes
d1M1:WAY 1 – point testing: Their attempt at \(\left(\dfrac{100}{9},\ \dfrac{50}{9}\right)\) evaluated in \(Q\) compared to (0, 10) evaluated in \(Q\) - allow any inequality sign or equals
d1A1: \(\lambda \lt 5\) (CAO so allow equals used throughout and then the correct inequality at the end but A0 if incorrect inequality seen in working or if non-exact values used in working)
d2M1: Their attempt at \(\left(\dfrac{100}{9},\ \dfrac{50}{9}\right)\) evaluated in \(Q\) compared to (4, 2) evaluated in \(Q\) – allow any inequality sign or equals
d2A1: \(\lambda \gt -4\) (CAO - see d1A1). Do not award this mark if candidates give both correct answers and then give an answer of \(0 \lt \lambda \lt 4\) or if any additional answers seen
SC for Way 1: If optimal vertex in (c) is either (4, 2) or (0, 10) then the M mark not awarded in (d) can be awarded for evaluating and comparing (4, 2) with (0, 10) in \(Q\). Therefore an incorrect optimal vertex in (c) can earn at most M1A0M1A0 in (d)NOTE that in WAY 2 the 2nd A mark is dependent on the correct three vertices of the feasible region
d1M1:WAY 2 – objective line: \(-\dfrac{2}{\lambda}\) compared to either \(-\dfrac{2}{5}\) or \(\dfrac{1}{2}\) or \(-2\) (oe e.g. \(\dfrac{2}{\lambda}\) with \(\dfrac{2}{5}\), \(\dfrac{\lambda}{2}\) with \(\dfrac{5}{2}\), etc.) so correctly comparing the gradient of the new objective line with any one of the three line segments that define \(R\) – accept any inequality or equals
d1A1: \(\lambda \lt 5\) or \(\lambda \gt -4\) (CAO so allow equals used throughout and then the correct inequality at the end but A0 if incorrect inequality seen in working)
d2M1: \(-\dfrac{2}{\lambda}\) compared to both \(-\dfrac{2}{5}\) and \(\dfrac{1}{2}\) (oe) – so correctly comparing the gradient of the new objective with the correct two line segments that give the correct optimal vertex - accept any inequality or equals
d2A1: \(\lambda \lt 5\) and \(\lambda \gt -4\) only (CAO - see d1A1) – note that this mark is dependent on all correct three vertices that define the feasible region and must come from correct comparisons with \(-\dfrac{2}{5}\) and \(\dfrac{1}{2}\). Do not award this mark if candidates give the correct answer and then give an answer of \(0 \lt \lambda \lt 4\) or if any additional answers seen
Note that the correct answers in Way 2 must come from \(-\dfrac{2}{\lambda} \lt -\dfrac{2}{5}\) and \(-\dfrac{2}{\lambda} \gt \dfrac{1}{2}\)
Correct answers with no workingAward d1M1 and d1A1 (first two marks) for one correct answer then d2M1 and d2A1 (full marks) for both correct answers only (so no additional answers) – if any of the three vertices of the feasible region are incorrect then award the first three marks for both correct answers only
There are two different types of storage container available, standard and deluxe.
Standard containers cost £20 and deluxe containers cost £65. Let \(x\) be the number of standard containers and \(y\) be the number of deluxe containers.
The maximum budget available is £520
(a) Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. (1)
(b) Add lines and shading to Diagram 1 in the answer book to represent all four constraints. Hence determine the feasible region and label it R. (4)
The capacity of a deluxe container is 50% greater than the capacity of a standard container. Charlie wishes to maximise the total capacity.
(c) State an objective function, in terms of \(x\) and \(y\). (1)
(d) Use the objective line method to find the optimal vertex, V, of the feasible region. You must make your objective line clear and label the optimal vertex V. (3)
(e) Calculate the exact coordinates of vertex V. (2)
(f) Determine the number of each type of container that Charlie should buy. You must make your method clear and calculate the cost of purchasing the storage containers. (3)
a1B1: CAO – accept any exact equivalent inequality (isw if simplified incorrectly)
Mark scheme (b)
Scheme
Marks
B1
B1
B1
DB1 (R)
(4)
Notes
In (b):
\(7x + 8y = 112\) must pass within one small square of its intersection with the axes – (0, 14) and (16, 0)
\(20x + 65y = 520\) must pass within one small square of its intersection with the axes – (0, 8) and (26, 0)
\(-x + 24y = 24\) must be sufficiently long to define the feasible region and pass within one small square of (0, 1) and (24, 2) if extended
\(x = 2\) must pass within one small square of (2, 0) and (2, 8)
b1B1: Any two lines correctly drawn
b2B1: Any three lines correctly drawn
b3B1: All four lines correctly drawn
b4DB1: Region, R, correctly labelled – not just implied by shading – dependent on scoring the first three marks in this part
Mark scheme (c)
Scheme
Marks
e.g. \((P =)\ 2x + 3y\)
B1
(1)
Notes
c1B1: CAO - \(k(2x + 3y)\) where \(k \in \mathbb{R}\) – condone equal to \(P\) or equal to a constant
Mark scheme (d)
Scheme
Marks
Drawing an objective line accept reciprocal gradient
M1
Correct objective line minimum length equivalent to (0, 1) to (1.5, 0)
A1
V correctly labelled
A1
(3)
Notes
d1M1: Drawing either the correct objective line or their objective line (based on their answer to (c)) or the reciprocal of the correct objective line or the reciprocal of their objective line – if their line is shorter than the length equivalent to that of the line from (0, 1) to (1.5, 0) then M0. Line must be correct to within one small square if extended from axis to axis
d1A1: Drawing the correct objective line – same condition that the line must be correct to within one small square if extended from axis to axis
d2A1: Correct V labelled clearly on their graph – please note that this mark is dependent on scoring at least B1B1B1B0 in (b) and the two previous marks in this part – by clearly labelled the vertex should either be labelled ‘V’ or circled or clearly distinguishable from the other three (but A0 if not clear e.g. other vertices circled too)
e1M1: Simultaneous equations being used to find V. Must have scored at least B1B1B0B0 in (b) and candidates must have labelled one of their vertices as V (oe – see above). Must be solving either the pair of simultaneous equations \(20x + 65y = 520\) and \(7x + 8y = 112\) or \(7x + 8y = 112\) and \(-x + 24y = 24\). Must be a correct method to solve simultaneous equations and must arrive at \(x = \ldots\) and \(y = \ldots\) but allow slips/errors. This mark can also be awarded for the correct exact coordinates stated with no working provided B1B1B0B0 in (b) and a vertex labelled as V
e1A1: Correct exact coordinates of the correct V derived with working (not just stated) as either \(\left(\dfrac{624}{59},\ \dfrac{280}{59}\right)\) or \(\left(10\dfrac{34}{59},\ 4\dfrac{44}{59}\right)\) or stated just in terms of \(x\) and \(y\). Note that this mark is dependent on B1B1B1B0 scored in (b) and all three marks in (d). ISW if correct exact values seen followed by decimal approximations
Mark scheme (f)
Scheme
Marks
Testing integer solutions around V, \(x = 11\) and \(y = 4\) is optimal integer solution, so they should buy 11 standard containers and 4 deluxe containers
M1 A1
Cost is (£) 480
B1
(3)
(14 marks)
Notes
f1M1: Testing any two of (11, 4) or (9, 5) or (10, 5) or (10, 4) or (11, 5) in a correct objective function or the correct pair of inequalities. Note candidates may reject a point after testing in only one correct inequality which is acceptable – this mark is not dependent on any previous mark
f1A1: CSO (all previous 12 marks must have been awarded) – must have tested (11, 4) in the correct objective function or correct pair of inequalities – accept \(x = 11\) and \(y = 4\) or stated as a pair of coordinates
f1B1: CAO – this mark is not dependent on any previous mark and condone lack of units
4. A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\). The following tableau is obtained after the first iteration.
Basic Variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
0
5
2
1
–3
0
10
\(x\)
1
2
3
0
1
0
18
\(t\)
0
1
–1
0
4
1
3
\(P\)
0
3
–4
0
1
0
7
(a) State which variable was increased first, giving a reason for your answer. (1)
(b) Perform one complete iteration of the simplex algorithm, to obtain a new tableau, T. Make your method clear by stating the row operations you use. (5)
(c) Write down the profit equation given by T. (1)
(d) State whether T is optimal. You must use your answer to (c) to justify your answer. (2)
Mark scheme (a)
Scheme
Marks
e.g. variable \(x\) was increased first, since it has become a basic variable
B1
(1)
Notes
a1B1: e.g. identifies \(x\), refers to basic variable (oe)
Mark scheme (b)
Scheme
Marks
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
row ops
\(z\)
0
2.5
1
0.5
−1.5
0
5
\(R_1 \div 2\)
\(x\)
1
−5.5
0
−1.5
5.5
0
3
\(R_2 - 3R_1\)
\(t\)
0
3.5
0
0.5
2.5
1
8
\(R_3 + R_1\)
\(P\)
0
13
0
2
−5
0
27
\(R_4 + 4R_1\)
M1 A1 M1 A1ft A1
(5)
Notes
If pivoting on a negative value or on a value from the \(x\) or \(y\) column then no marks in (b), (c) or (d)
b1M1: Correct pivot located (2 in column \(z\)), attempt to divide row
b1A1: Pivot row correct including change of b.v. (so the \(r\) must be replaced with a \(z\))
b2M1:All values in one of the non-pivot rows correct or one of the non zero-and-one columns (\(y\), \(r\), \(s\) or value) correct following through their choice of pivot from column \(z\)
b2A1ft: Row operations used correctly at least twice, i.e. two of the non zero-and-one columns (\(y\), \(r\), \(s\) or value) correct following through their choice of pivot from column \(z\)
b3A1: CAO – no follow through – all values and row operations correctly stated – allow if row operations given in terms of old row 1 – ignore b.v. column for this mark
Pivoting on the 3 in the \(z\) column (can score a maximum of B1 M0A0M1A1A0 B1 B0B0 – so 4/9)
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
−2/3
11/3
0
1
−11/3
0
−2
\(z\)
1/3
2/3
1
0
1/3
0
6
\(t\)
1/3
5/3
0
0
13/3
1
9
\(P\)
4/3
17/3
0
0
7/3
0
31
Mark scheme (c)
Scheme
Marks
\(P + 13y + 2r - 5s = 27\)
B1ft
(1)
Notes
c1B1ft: Dependent on the second M mark earned in (b) – must be an equation containing \(P\) (please note that \(P = 13y + 2r - 5s + 27\) is incorrect)
Mark scheme (d)
Scheme
Marks
\(P = 27 - 13y - 2r + 5s\), so we can increase the profit by increasing \(s\), hence not optimal
B2,1,0
(2)
9 marks
Notes
d1B1: Must have gained both M marks in (b) and must refer to increasing \(y\), \(r\) or \(s\). Do not accept ‘negatives in profit row’ with no further explanation given
d2B1: CAO – dependent on the correct profit equation in (c). Specifically identifies \(s\) as the next variable that could be increased and states ‘not optimal’ (oe)
6. A linear programming problem in \(x\) and \(y\) is described as follows.
Minimise \(C = 2x + 3y\)
subject to
\[\begin{aligned} x + y &\geqslant 8\\ x &\lt 8\\ 4y &\geqslant x\\ 3y &\leqslant 9 + 2x \end{aligned}\]
(a) Add lines and shading to Diagram 1 in the answer book to represent these constraints. (4)
(b) Hence determine the feasible region and label it R. (1)
(c) Use the objective line (ruler) method to find the exact coordinates of the optimal vertex, V, of the feasible region. You must draw and label your objective line clearly. (3)
(d) Calculate the corresponding value of \(C\) at V. (1)
The objective is now to maximise \(2x + 3y\), where \(x\) and \(y\) are integers.
(e) Write down the optimal values of \(x\) and \(y\) and the corresponding maximum value of \(2x + 3y\). (2)
A further constraint, \(y \leqslant kx\), where \(k\) is a positive constant, is added to the linear programming problem.
(f) Determine the least value of \(k\) for which this additional constraint does not affect the feasible region. (2)
Mark scheme (a)
Scheme
Marks
B1 \((x + y = 8)\)
B1 \((3y = 9 + 2x)\)
B1 \((4y = x)\)
B1 \((x = 8)\) - must be distinct from the other three lines
(4)
Notes
The line \(x = 8\) must be distinct from the other three lines in some way. Some candidates may show the strict inequality as a solid line and the other three lines as dashed lines – this is acceptable for all four marks in part (a). If a candidate has a mixture of dashed and solid lines (say two of each) then withold the final B mark earned
a1B1: \(x + y = 8\) correctly drawn. Must pass within one small square of (0, 8), (4, 4) and (8, 0)
a2B1: \(3y = 9 + 2x\) correctly drawn. Must pass within one small square (0, 3), (6, 7) and sufficiently long enough to define the feasible region
a3B1: \(4y = x\) correctly drawn. Must pass within one small square of the origin and (8, 2)
a4B1: \(x = 8\) correctly drawn. Must be sufficiently long enough to define the feasible region. This must be shown as a dashed line or distinctive from the other three lines (see note above)
Mark scheme (b)
Scheme
Marks
Correct R labelled
B1
(1)
Notes
b1B1: Region, R, correctly labelled – all lines must have been drawn correctly but condone \(x = 8\) not distinct from the other three lines (so must have scored either B1B1B1B1 or B1B1B1B0 in (a))
Note that if no objective line is drawn then no marks in (c)
c1B1: Drawing a correct objective line – if their line is shorter than the length equivalent to that of the line from (0, 1) to (1.5, 0) then B0. Line must be correct to within one small square if extended from axis to axis
c1M1: Candidates must have drawn either the correct objective line or its reciprocal. If they have drawn the correct objective line they must be solving \(x + y = 8\) and \(4y = x\). If they have drawn the reciprocal objective line line they must be solving \(x + y = 8\) and \(3y = 9 + 2x\). Must get to either \(x = \ldots\) or \(y = \ldots\) (condone one error in the solving of the simultaneous equations). The correct exact answer \(\left(\dfrac{32}{5},\ \dfrac{8}{5}\right)\), or for the reciprocal (3, 5), can imply this mark
c1dA1: CAO – the correct exact coordinate \(\left(\dfrac{32}{5},\ \dfrac{8}{5}\right)\) or \((6.4,\ 1.6)\) or \(\left(6\dfrac{2}{5},\ 1\dfrac{3}{5}\right)\) - this mark is dependent on the correct objective line seen (so must have scored the B mark). If B1 awarded then the correct answer with no working scores M1A1
Mark scheme (d)
Scheme
Marks
\((C =)\ \dfrac{88}{5}\) (oe)
B1
(1)
Notes
d1B1: CAO or 17.6 or \(17\dfrac{3}{5}\)
Mark scheme (e)
Scheme
Marks
(7,7)
B1
35
B1
(2)
Notes
e1B1: CAO vertex (7, 7) (accept \(x = 7,\ y = 7\))
e2B1: CAO value (35)
Mark scheme (f)
Scheme
Marks
\(y \leqslant \frac{5}{3}x \ \therefore\ k = \frac{5}{3}\) (oe)
M1 A1
(2)
(13 marks)
Notes
f1M1: \((k =)\ \dfrac{5}{3}\) or \(\dfrac{3}{5}\) or 1.6 or 0.6 or \(1\dfrac{2}{3}\)
1. The tableau below is the initial tableau for a linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
2
–4
1
1
0
0
15
\(s\)
4
2
–8
0
1
0
20
\(t\)
1
–1
4
0
0
1
8
\(P\)
–3
2
7
0
0
0
0
(a) Perform one iteration of the Simplex algorithm to obtain a new tableau, T. State the row operations you use. (5)
(b) Write down the profit equation given by T and state the current values of the slack variables. (2)
Mark scheme (a)
Scheme
Marks
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
Row ops
\(r\)
0
\(-5\)
5
1
\(-\frac{1}{2}\)
0
5
\(R_1 - 2R_2\)
\(x\)
1
\(\frac{1}{2}\)
\(-2\)
0
\(\frac{1}{4}\)
0
5
\(R_2 \div 4\)
\(t\)
0
\(-\frac{3}{2}\)
6
0
\(-\frac{1}{4}\)
1
3
\(R_3 - R_2\)
\(P\)
0
\(\frac{7}{2}\)
1
0
\(\frac{3}{4}\)
0
15
\(R_4 + 3R_2\)
M1 A1 M1 A1ft A1
(5)
Notes
a1M1: Correct pivot located (4 in column \(x\)), attempt to divide row
a1A1: Pivot row correct including change of b.v.
a2M1:All values in one of the non-pivot rows correct or one of the non zero and one columns (\(y\), \(z\), \(s\) or value) correct following through their choice of pivot from column \(x\)
a2A1ft: Row operations used correctly at least twice, i.e. two of the non zero and one columns (\(y\), \(z\), \(s\) or value) correct following through their choice of pivot from column \(x\)
a3A1: CAO – no follow through – all values and row operations correctly stated – allow if row operations given in terms of old row 2 – ignore b.v. column for this mark
Pivoting on the 1 in the \(x\)-column
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(S\)
\(t\)
V
\(r\)
0
−2
−7
1
0
−2
−1
\(s\)
0
6
−24
0
1
−4
−12
\(x\)
1
−1
4
0
0
1
8
\(P\)
0
−1
19
0
0
3
24
Pivoting on the 2 in the \(x\)-column
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
V
\(x\)
1
−2
0.5
0.5
0
0
7.5
\(s\)
0
10
−10
−2
1
0
−10
\(t\)
0
1
3.5
−0.5
0
1
0.5
\(P\)
0
−4
8.5
1.5
0
0
22.5
Mark scheme (b)
Scheme
Marks
\(P + \frac{7}{2}y + z + \frac{3}{4}s = 15\)
B1ft
\(r = 5,\ s = 0,\ t = 3\)
B1
(2)
7 marks
Notes
b1B1ft: Follow their profit equation from (a) dependent on scoring both M marks in (a)
b2B1: CAO (no follow through) for slack variables (\(r = 5\), \(s = 0\), \(t = 3\))
8. A manufacturer of frozen yoghurt is going to exhibit at a trade fair. He will take two types of frozen yoghurt, Banana Blast and Strawberry Scream.
He will take a total of at least 1000 litres of yoghurt.
He wants at least 25% of the yoghurt to be Banana Blast. He also wants there to be at most half as much Banana Blast as Strawberry Scream.
Each litre of Banana Blast costs £3 to produce and each litre of Strawberry Scream costs £2 to produce. The manufacturer wants to minimise his costs.
Let \(x\) represent the number of litres of Banana Blast and \(y\) represent the number of litres of Strawberry Scream.
Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients.
You should not attempt to solve the problem. (6)
Mark scheme
Scheme
Marks
Minimise \(C = 3x + 2y\)
B1
Subject to:
\(x + y \geqslant 1000\)
B1
\(\dfrac{1}{4}(x + y) \leqslant x,\) simplifies to \(y \leqslant 3x\)
M1 A1
\(2x \leqslant y\)
M1 A1
\((x,\ y \geqslant 0)\)
(6 marks)
Notes
1B1: CAO – expression correct and ‘minimise’.
2B1: CAO
1M1: Correct method – must see \(\frac{1}{4}(x + y) \blacksquare x\) where \(\blacksquare\) is any inequality or =. The bracket must be present or implied by later working.
1A1: CAO – simplified – answer must have integer coefficients.
2M1: Correct method – one of \(2x \blacksquare y\) or \(x \blacksquare 2y\) where \(\blacksquare\) is any inequality or =.
5. A linear programming problem in \(x\) and \(y\) is described as follows.
Maximise \(P = 2x + 3y\)
subject to
\[\begin{aligned} x &\geqslant 25\\ y &\geqslant 25\\ 7x + 8y &\leqslant 840\\ 4y &\leqslant 5x\\ 5y &\geqslant 3x\\ x,\ y &\geqslant 0 \end{aligned}\]
(a) Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R. (4)
(b) Use the objective line method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V. (3)
(c) Calculate the exact coordinates of vertex V. (2)
Given that an integer solution is required,
(d) determine the optimal solution with integer coordinates. You must make your method clear. (2)
Mark scheme (a)
Scheme
Marks
B1 B1 B1 B1 R
(4)
Notes
In (a) lines must pass through one small square of the points stated:
cM1: Simultaneous equation being used to find their V (but not from \(x = 25\) or \(y = 25\)). Must get to \(x = \ldots\) and \(y = \ldots\)
cA1: Correct coordinates of V stated exactly as \(\left(\dfrac{840}{17},\ \dfrac{1050}{17}\right)\) or \(\left(49\dfrac{7}{17},\ 61\dfrac{13}{17}\right)\). If the correct coordinates are stated exactly with no working then this scores M1A0.
Mark scheme (d)
Scheme
Marks
Testing the correct inequalities for points with integer coordinates
M1
(50, 61)
A1
(2)
(11 marks)
Notes
d1M1: Testing the correct inequalities for at least three of (49, 61), (49, 62), (50, 61), (50, 62).
4. The tableau below is the initial tableau for a three-variable linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).
Basic Variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
4
3
\(\frac{5}{2}\)
1
0
0
50
\(s\)
1
2
1
0
1
0
30
\(t\)
0
5
1
0
0
1
80
\(P\)
–25
–40
–35
0
0
0
0
(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm to obtain tableau T. Make your method clear by stating the row operations you use. (9)
(b) Write down the profit equation given by T. (1)
(c) Use your answer to (b) to determine whether T is optimal, justifying your answer. (2)
Mark scheme (a)
Scheme
Marks
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(\theta\) values
\(r\)
4
3
\(\frac{5}{2}\)
1
0
0
50
16.67
\(s\)
1
2
1
0
1
0
30
15
\(t\)
0
5
1
0
0
1
80
16
\(P\)
−25
−40
−35
0
0
0
0
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
Row ops
\(r\)
\(\frac{5}{2}\)
0
1
1
\(-\frac{3}{2}\)
0
5
R1 − 3R2
\(y\)
\(\frac{1}{2}\)
1
\(\frac{1}{2}\)
0
\(\frac{1}{2}\)
0
15
R2 ÷ 2
\(t\)
\(-\frac{5}{2}\)
0
\(-\frac{3}{2}\)
0
\(-\frac{5}{2}\)
1
5
R3 − 5R2
\(P\)
−5
0
−15
0
20
0
600
R4 + 40R2
M1 A1 B1 M1 A1
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
Row ops
\(z\)
\(\frac{5}{2}\)
0
1
1
\(-\frac{3}{2}\)
0
5
R1stet
\(y\)
\(-\frac{3}{4}\)
1
0
\(-\frac{1}{2}\)
\(\frac{5}{4}\)
0
12.5
R2 − \(\frac{1}{2}\)R1
\(t\)
\(\frac{5}{4}\)
0
0
\(\frac{3}{2}\)
\(-\frac{19}{4}\)
1
12.5
R3 + \(\frac{3}{2}\)R1
\(P\)
32.5
0
0
15
−2.5
0
675
R4 + 15R1
B1 B1 M1 A1
(9)
Notes
a1M1: Correct pivot located, attempt to divide row. If choosing negative pivot no marks.
a1A1: Pivot row correct including change of b.v.
a1B1: Row operations CAO – allow if given in terms of old row 2.
a2M1: (ft) Correct row operations used at least once, column \(x\), \(z\), \(s\) or value correct.
a2A1: CAO on numbers (ignore row operations and b.v.).
a2B1: Correct pivot located and b.v. changed. If choosing negative pivot 2B0 3M0.
a3B1: Row operations CAO.
a3M1: (ft) Correct row operations used at least once, column \(x\), \(r\), \(s\) or value correct.
a3A1: CAO on numbers (ignore row operations and b.v.).
Mark scheme (b)
Scheme
Marks
\(P + 32.5x + 15r - 2.5s = 675\)
B1
(1)
Notes
b1B1: CAO
Mark scheme (c)
Scheme
Marks
\(P = 675 - 32.5x - 15r + 2.5s\), so can increase profit by increasing \(s\), hence not optimal.
B2,1,0
(2)
12 marks
Notes
c1B1ft:Explanation. Must have gained at least 2 M marks in (a) must refer to increasing \(x\), \(r\) and \(s\), (condone no ref to \(y = z = t = 0\)), must have correct signs in equation in (b). Do not accept ‘negatives in profit row’ o.e. alone.
c2DB1: CAO – dependent on correct equation in (b). Specifically identifies \(s\) as the next variable that could be increased.
The graph in Figure 4 is being used to solve a linear programming problem. The four constraints have been drawn on the graph and the rejected regions have been shaded out. The four vertices of the feasible region \(R\) are labelled A, B, C and D.
(a) Write down the constraints represented on the graph. (2)
The objective function, P, is given by
\[P = x + ky\]
where \(k\) is a positive constant.
The minimum value of the function P is given by the coordinates of vertex A and the maximum value of the function P is given by the coordinates of vertex D.
(b) Find the range of possible values for \(k\). You must make your method clear. (6)
Mark scheme (a)
Scheme
Marks
\(y \leqslant 2x,\quad 5y \geqslant 2x,\quad 2x + y \leqslant 36,\quad 4x + y \geqslant 36\)
B2,1,0
(2)
Notes
a1B1 Any two correct inequalities (condone strict inequalities).
a2B1 CAO (equalities cannot be strict for this mark).
As there are a number of different methods that the candidates can adopt – consider the candidate’s full response and mark each attempt according to the notes below – award the candidate the marks for their best response/attempt. However, do not mix the approaches together e.g. if they find the exact coordinates of all four vertices and then state that the maximum gradient of P is \(-2\) then this would score the first two marks only (method 1).
Method 1 (point testing)
b1B1 The coordinates of B, C and D stated exactly.
b2B1 The coordinates of A stated exactly.
b3B1 The objective function calculated in terms of \(k\) at either A or B or C or D.
b1M1 Either (their objective function at A) < (their objective function at B) or (their objective function at C) < (their objective function at D) (condone equals sign or any inequality).
b1A1 Either \(k \gt \frac{1}{4}\) or \(k \lt \frac{1}{2}\) or \(k \geqslant \frac{1}{4}\) or \(k \leqslant \frac{1}{2}\).
b2A1 CAO \(\frac{1}{4} \lt k \lt \frac{1}{2}\) or \(\frac{1}{4} \leqslant k \leqslant \frac{1}{2}\) (or as separate inequalities)
Method 2 (objective line method I)
Comparing the gradient of the objective function to the gradient of the two lines with negative gradient.
b1B1 The minimum gradient (of P) stated as \(-4\) – must see explicit mention of minimum.
b2B1 The maximum gradient (of P) stated as \(-2\) – must see explicit mention of maximum.
b3B1 Gradient of objective function stated as \(-\frac{1}{k}\).
b1M1 Comparing gradient of objective function to either \(-2\) or \(-4\).
Final two marks as in method 1.
Method 3 (objective line method II)
b1B1Minimum P parallel to \(4x + y = \cdots\) (limiting case) – must see explicit mention of minimum.
b2B1Maximum P parallel to \(2x + y = \cdots\) (limiting case) – must see explicit mention of maximum.
b3B1 Re-arranging equations (either seen or implied) to give \(x + \frac{y}{4} = \cdots,\ x + \frac{y}{2} = \cdots\)
b1M1 Compare coefficients of \(y\) in the objective function & lines.
Final two marks as in method 1.
SC: If no working seen (max 3/6 marks)
\(k \blacksquare \frac{1}{2}\) or \(k \blacksquare \frac{1}{4}\) (where \(\blacksquare\) is any inequality or equals) award first B mark. \(k \gt \frac{1}{4}\) or \(k \lt \frac{1}{2}\) or \(k \geqslant \frac{1}{4}\) or \(k \leqslant \frac{1}{2}\) award the first two B marks. \(\frac{1}{4} \lt k \lt \frac{1}{2}\) or \(\frac{1}{4} \leqslant k \leqslant \frac{1}{2}\) award the first three B marks.
3. The tableau below is the initial tableau for a three-variable linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).
Basic Variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
5
3
\(-\frac{1}{2}\)
1
0
0
2500
\(s\)
3
2
1
0
1
0
1650
\(t\)
\(\frac{1}{2}\)
–1
2
0
0
1
800
\(P\)
–40
–50
–35
0
0
0
0
(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use. (10)
(b) State the final values of the objective function and each variable. (2)
Mark scheme (a)
Scheme
Marks
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(\theta\) values
\(r\)
5
3
\(-\frac{1}{2}\)
1
0
0
2500
833.3
\(s\)
3
2
1
0
1
0
1650
825
\(t\)
\(\frac{1}{2}\)
−1
2
0
0
1
800
n/a
\(P\)
−40
−50
−35
0
0
0
0
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
Row ops
\(r\)
\(\frac{1}{2}\)
0
−2
1
\(-\frac{3}{2}\)
0
25
R1 − 3R2
\(y\)
\(\frac{3}{2}\)
1
\(\frac{1}{2}\)
0
\(\frac{1}{2}\)
0
825
R2 ÷ 2
\(t\)
2
0
\(\frac{5}{2}\)
0
\(\frac{1}{2}\)
1
1625
R3 + R2
\(P\)
35
0
−10
0
25
0
41250
R4 + 50R2
M1 A1 B1 M1 A1 (5)
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
Row ops
\(r\)
\(\frac{21}{10}\)
0
0
1
\(-\frac{11}{10}\)
\(\frac{4}{5}\)
1325
R1 + 2R3
\(y\)
\(\frac{11}{10}\)
1
0
0
\(\frac{2}{5}\)
\(-\frac{1}{5}\)
500
R2 − \(\frac{1}{2}\)R3
\(z\)
\(\frac{4}{5}\)
0
1
0
\(\frac{1}{5}\)
\(\frac{2}{5}\)
650
R3 ÷ \(\frac{5}{2}\)
\(P\)
43
0
0
0
27
4
47750
R4 + 10R3
M1 A1ft B1 M1 A1 (5)
Notes
a1M1: Correct pivot located, attempt to divide row. If choosing negative pivot no marks.
a1A1: CAO pivot row correct including change of b.v.
a1B1: All row operations CAO – allow if given in terms of old row 2.
a2M1: (ft) The correct row operations used correctly at least once from their pivot, column \(x\), \(z\), \(s\) or value ‘correct’.
a2A1: CAO on numbers (ignore row operations and b.v.)
a3M1: Their correct pivot located, attempt to divide row. If choosing negative pivot M0M0.
a3A1ft: Pivot row correct on follow through including change of b.v.
a2B1: All row operations CAO – allow if given in terms of old row 3.
a4M1: (ft) The correct row operations used correctly at least once from their pivot, column \(x\), \(s\), \(t\) or value ‘correct’.
a4A1: CAO on numbers (ignore row operations and b.v.)
Mark scheme (b)
Scheme
Marks
\(P = 47750\quad x = 0\quad y = 500\quad z = 650\quad r = 1325\quad s = t = 0\)
B1ft B1
(2)
12 marks
Notes
b1B1ft: Their correct values stated for at least \(P\), \(x\), \(y\), \(z\) from their ‘optimal’ iteration. No negatives. Two M marks in (a) must have been awarded.
Allow implicit stating of \(P\) e.g. \(P + 43x + 27s + 4t = 47750\) with \(x, s, t = 0\).
b2B1: CAO For all 7 variables correct and given explicitly.
A company makes two types of garden bench, the ‘Rustic’ and the ‘Contemporary’. The company wishes to maximise its profit and decides to use linear programming.
Let \(x\) be the number of ‘Rustic’ benches made each week and \(y\) be the number of ‘Contemporary’ benches made each week.
The graph in Figure 6 is being used to solve this linear programming problem.
Two of the constraints have been drawn on the graph and the rejected region shaded out.
(a) Write down the constraints shown on the graph giving your answers as inequalities in terms of \(x\) and \(y\). (3)
It takes 4 working hours to make one ‘Rustic’ bench and 3 working hours to make one ‘Contemporary’ bench. There are 120 working hours available in each week.
(b) Write down an inequality to represent this information. (2)
Market research shows that ‘Rustic’ benches should be at most \(\dfrac{3}{4}\) of the total benches made each week.
(c) Write down, and simplify, an inequality to represent this information. Your inequality must have integer coefficients. (2)
(d) Add two lines and shading to Diagram 1 in your answer book to represent the inequalities of (b) and (c). Hence determine and label the feasible region, R. (3)
The profit on each ‘Rustic’ bench and each ‘Contemporary’ bench is £45 and £30 respectively.
(e) Write down the objective function, P, in terms of \(x\) and \(y\). (1)
(f) Determine the coordinates of each of the vertices of the feasible region and hence use the vertex method to determine the optimal point. (4)
(g) State the maximum weekly profit the company could make. (1)
Mark scheme (a)
Scheme
Marks
\(y \leqslant 16\) ; and \(y \leqslant 2x\)
B1; M1 A1
(3)
Notes
a1B1 CAO for \(y \leqslant 16\)
a1M1 Coefficients correct, accept =, <, >, \(\leqslant\), \(\geqslant\) here
a1A1 CAO
Mark scheme (b)
Scheme
Marks
\(4x + 3y \leqslant 120\)
M1 A1
(2)
Notes
b1M1 Coefficients correct and 120 accept =, <, >, \(\leqslant\), \(\geqslant\) here
b1A1 CAO
Mark scheme (c)
Scheme
Marks
\(x \leqslant \frac{3}{4}(x + y)\) so \(4x \leqslant 3x + 3y\) so \(x \leqslant 3y\)
The correct two lines (\(4x + 3y = 120\), \(x = 3y\))
B1 B1
R labelled correctly
B1
(3)
Notes
d1B1 \(4x + 3y = 120\) correctly drawn. The line must pass within one small square of the point (18, 16) and if line extended must go from axis to axis through the points of intersection with the axes within one small square. The line must be long enough to form the feasible region. Check using measurement tool if required. Ignore shading.
d2B1 \(x = 3y\) correctly drawn. The line must pass within one small square of the origin and the point (24, 8). The line must be long enough to form the feasible region. Ignore shading.
d3B1 R labelled (not just implied by shading) – must have scored the first two marks in this part.
Mark scheme (e)
Scheme
Marks
(P = ) \(45x + 30y\)
B1
(1)
Notes
e1B1 CAO (isw if (P =) \(45x + 30y\) is simplified to \(k(45x + 30y)\) but if \(45x + 30y\) not stated then B0)
Mark scheme (f)
Scheme
Marks
At (0,0) P = 0
M1
At (8, 16) P = 840
A1 (any 2)
At (18, 16) P = 1 290
A1 (any 3)
At (24, 8) P = 1 320
A1 (all 4)
(4)
Notes
f1M1 At least two of their, or the correct R vertices found (either by reading off their graph or using simultaneous equations) and tested using their P. Objective line method (only) is M0.
f1A1 Two vertices found and tested correctly CAO (must be using two of the correct vertices and the values for P must be correct).
f2A1 Three vertices found and tested correctly CAO (must be using three of the correct vertices and the values for P must be correct).
f3A1 All four vertices found and tested correctly CAO (all values of P must be correct).
The mark scheme prints one total of (5) for parts (f) and (g) together.
5. A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\).
The following tableau is obtained.
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
\(\frac{1}{2}\)
\(-\frac{1}{2}\)
0
1
0
\(-\frac{1}{2}\)
10
\(s\)
\(1\frac{1}{2}\)
\(2\frac{1}{2}\)
0
0
1
\(-\frac{1}{2}\)
5
\(z\)
\(\frac{1}{2}\)
\(\frac{1}{2}\)
1
0
0
\(\frac{1}{2}\)
5
\(P\)
–5
–10
0
0
0
20
220
(a) Starting by increasing \(y\), perform one complete iteration of the Simplex algorithm, to obtain a new tableau, T. State the row operations you use. (5)
(b) Write down the profit equation given by T. (1)
(c) Use the profit equation from part (b) to explain why T is optimal. (2)
Mark scheme (a)
Scheme
Marks
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
Row ops
\(r\)
\(\frac{4}{5}\)
0
0
1
\(\frac{1}{5}\)
\(-\frac{3}{5}\)
11
\(R_1 + \frac{1}{2}R_2\)
\(y\)
\(\frac{3}{5}\)
1
0
0
\(\frac{2}{5}\)
\(-\frac{1}{5}\)
2
\(R_2 \div 2.5\)
\(z\)
\(\frac{1}{5}\)
0
1
0
\(-\frac{1}{5}\)
\(\frac{3}{5}\)
4
\(R_3 - \frac{1}{2}R_2\)
\(P\)
1
0
0
0
4
18
240
\(R_4 + 10R_2\)
M1 A1 M1 A1 A1
(5)
Notes
a1M1: correct pivot located, attempt to divide row. If choosing negative pivot M0M0.
a1A1: pivot row correct including change of b.v.
a2M1: (ft) One row (excluding the pivot row) correct or one column either the value, \(x\), \(s\) or \(t\) column correct.
a2A1ft: Correct row operations used at least once. One column either the value, \(x\), \(s\) or \(t\) column correct on the ft.
a3A1: CAO.
Mark scheme (b)
Scheme
Marks
\(P + x + 4s + 18t = 240\)
B1
(1)
Notes
b1B1: CAO
Mark scheme (c)
Scheme
Marks
\(P = 240 - x - 4s - 18t\) and at present \(x\), \(s\) and \(t\) are zero. If we increase any of these the profit will decrease.
B2, 1, 0
(2)
8 marks
Notes
c1B1: Using their profit equation to make a pertinent statement. Maybe muddled, if bod give this mark only. No ‘negatives’ in their profit equation.
c2B1: Good explanation – dependent on the correct equation being stated in (b).
6. Harry wants to rent out boats at his local park. He can use linear programming to determine the number of each type of boat he should buy.
Let \(x\) be the number of 2-seater boats and \(y\) be the number of 4-seater boats.
One of the constraints is
\[x + y \geqslant 90\]
(a) Explain what this constraint means in the context of the question. (1)
Another constraint is
\[2x \leqslant 3y\]
(b) Explain what this constraint means in the context of the question. (2)
A third constraint is
\[y \leqslant x + 30\]
(c) Represent these three constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R. (4)
Each 2-seater boat costs £100 and each 4-seater boat costs £300 to buy. Harry wishes to minimise the total cost of buying the boats.
(d) Write down the objective function, C, in terms of \(x\) and \(y\). (1)
(e) Determine the number of each type of boat that Harry should buy. You must make your method clear and state the minimum cost. (4)
Mark scheme (a)
Scheme
Marks
He must buy at least 90 boats in total (\(\boldsymbol{x + y \geqslant 90}\))
B1
(1)
Notes
a1B1 CAO (must have ‘boats’, ‘least’, ‘90’, must be talking about boats not cost)
Mark scheme (b)
Scheme
Marks
E.g. The number of 2-seater boats(\(x\)) must be less than or equal to 1.5 times the number of 4-seater boats (\(y\)). (check: \(y = 2,\ x = 3, 2, 1, \ldots\)) (\(\boldsymbol{2x \leqslant 3y}\)) E.g. The number of 4-seater boats (\(y\)) must be greater than or equal to 2/3 the number of 2-seater boats (\(x\)). (check: \(x = 3,\ y = 2, 3, 4, \ldots\))
B1 B1
(2)
Notes
b1B1 For a statement in context with either the ratio of coefficients correct (the 2 with the 2-seater and the 3 with the 4-seater) or inequality correct with correct numbers present but not in the correct ratio.
b2B1 Clear accurate correct statement in context.
Examples for part (b) scoring B1 B1 (useful check: when \(y = 2,\ x = 3, 2, 1, \ldots\) or when \(x = 3,\ y = 2, 3, 4, \ldots\))
Twice the number of 2-seater boats must be at most three times the number of 4-seater boats
Three times the number of 4-seater must be at least twice the number of 2-seater boats
For every three 2-seater boats there must be at least two 4-seater boats (or multiple of this ratio)
For every two 4-seater boats there must be at most three 2-seater boats (or multiple of this ratio)
At most 60% of the total boats are 2-seater
At least 40% of the total boats are 4-seater
Examples of B1 B0 – in each case either the inequality is the correct way round OR the 2 is with 2-seater boats and the 3 is with the 4-seater boats (accept multiples of 2 and 3) (useful numbers: when \(y = 2,\ x = 3, 4, 5, \ldots\) when \(x = 3,\ y = 2, 1, \ldots\), when \(y = 3,\ x = 2, 1, \ldots\), when \(x = 2,\ y = 3, 4, 5, \ldots\))
Twice the number of 2-seater boats must be at least three times the number of 4-seater boats
Three times the number of 4-seater must be at most twice the number of 2-seater boats
Three times the number of 2-seater must be at least twice the number of 4-seater boats
For every three 2-seater boats there must be at most two 4-seater boats (or multiple of this ratio)
For every two 4-seater boats there must be at least three 2-seater boats (or multiple of this ratio)
For every two 2-seater boats there must be at least three 4-seater boats (or multiple of this ratio)
For every three 4-seater boats there must be at most two 2-seater boats (or multiple of this ratio)
At least 60% of the total boats are 2-seater
At most 40% of the total boats are 4-seater
At least 60% of the total boats are 4-seater
At most 40% of the total boats are 2-seater
Mark scheme (c)
Scheme
Marks
The correct 3 lines added; \(x + y = 90\); \(3y = 2x\); \(y = x + 30\)
B1; B1; B1
Region, R labelled
B1
(4)
Notes
c1B1 \(x + y = 90\) correctly drawn. Must pass within one small square of the points of intersection with the axes
c2B1 \(3y = 2x\) correctly drawn. Must pass within one small square of the origin and (90, 60).
c3B1 \(y = x + 30\) correctly drawn. Must pass within one small square of (0, 30) and (60, 90).
c4B1 Region, R, correctly labelled – not just implied by shading – must have scored all three previous marks in this part.
Mark scheme (d)
Scheme
Marks
(minimise C = ) \(100x + 300y\)
B1
(1)
Notes
d1B1 CAO (isw if \(100x + 300y\) ‘simplified’ to \(k(100x + 300y)\) but if \(100x + 300y\) not stated then B0)
Mark scheme (e)
Scheme
Marks
Method clear – either at least 2 vertices tested or objective line drawn
M1 A1
(54, 36), so 54 2-seater and 36 4-seater
B1
At a cost of £16 200
B1
(4)
(12 marks)
Notes
e1M1 Line must be correct to within one small square if extended from axis to axis OR attempting to find two vertices of their R (or the correct R) by either reading off their graph or using simultaneous equations and testing using their objective function.
e1A1 Correct objective line (same condition that the line must be correct to within one small square if extended from axis to axis) OR testing (30, 60) correctly (giving 21 000) and testing (54, 36) correctly (giving 16 200).
e1B1 Correct point identified. (Condone in terms of \(x\) and \(y\) rather than in terms of boats.)
e2B1 CAO – condone lack of/incorrect units on the cost.
5. In solving a three-variable maximising linear programming problem, the following tableau was obtained after the first iteration.
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
−1
2
0
1
0
1
8
\(s\)
−1
3
0
0
1
1
22
\(z\)
−2
1
1
0
0
1
11
\(P\)
2
−5
0
0
0
\(\tfrac{1}{2}\)
15
(a) State which variable was increased first, giving a reason for your answer. (1)
(b) Solve this linear programming problem. Make your method clear by stating the row operations you use. (8)
(c) State the final value of the objective function and the final values of each variable. (2)
Mark scheme (a)
Scheme
Marks
Variable \(z\) was increased first, since it has become a basic variable.
B1
(1)
Notes
a1B1 Identifies \(z\), refers to basic variable.
Mark scheme (b)
Scheme
Marks
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(r\)
−1
2
0
1
0
1
8
\(s\)
−1
3
0
0
1
1
22
\(z\)
−2
1
1
0
0
1
11
\(P\)
2
−5
0
0
0
\(\tfrac{1}{2}\)
15
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
row ops
\(y\)
\(-\tfrac{1}{2}\)
1
0
\(\tfrac{1}{2}\)
0
\(\tfrac{1}{2}\)
4
\(R_1 \div 2\)
\(s\)
\(\tfrac{1}{2}\)
0
0
\(-\tfrac{3}{2}\)
1
\(-\tfrac{1}{2}\)
10
\(R_2 - 3R_1\)
\(z\)
\(-\tfrac{3}{2}\)
0
1
\(-\tfrac{1}{2}\)
0
\(\tfrac{1}{2}\)
7
\(R_3 - R_1\)
\(P\)
\(-\tfrac{1}{2}\)
0
0
\(\tfrac{5}{2}\)
0
3
35
\(R_4 + 5R_1\)
1M1 A1 2M1 A1
(4)
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
row ops
\(y\)
0
1
0
−1
1
0
14
\(R_1 + \tfrac{1}{2}R_2\)
\(x\)
1
0
0
−3
2
−1
20
\(R_2 \div \tfrac{1}{2}\)
\(z\)
0
0
1
−5
3
−1
37
\(R_3 + \tfrac{3}{2}R_2\)
\(P\)
0
0
0
1
1
\(\tfrac{5}{2}\)
45
\(R_4 + \tfrac{1}{2}R_2\)
3M1 A1ft 4M1 A1
(4)
(8)
Notes
The pivot is boxed in the printed scheme (shown in bold).
b1M1 Correct pivot located, attempt to divide row. If choosing negative pivot M0M0.
b1A1 CAO pivot row correct including change of b.v.
b2M1 (ft) Correct row operations used at least once, column \(x\), \(r\), \(t\) or value correct.
b2A1 CAO including row operations
b3M1 Their correct pivot located, attempt to divide row. If choosing negative pivot M0M0.
b3A1ft pivot row correct including change of b.v.
b4M1 (ft) Correct row operations used at least once, column \(r\), \(s\), \(t\) or value correct.
b4A1 CAO
Mark scheme (c)
Scheme
Marks
\(P = 45;\ x = 20;\ y = 14;\ z = 37;\ r = s = t = 0.\)
M1 A1
(2)
(11 marks)
Notes
c1M1 Their correct values stated for at least \(P\), \(x\), \(y\), \(z\) from their ‘optimal’ iteration. No negatives. Two M marks in part (b) must have been awarded
Lethna is producing floral arrangements for an awards ceremony. She will produce two types of arrangement, Celebration and Party. Let \(x\) be the number of Celebration arrangements made. Let \(y\) be the number of Party arrangements made.
Figure 6 shows three constraints, other than \(x, y \geqslant 0\)
The rejected region has been shaded.
Given that two of the three constraints are \(y \leqslant 30\) and \(x \leqslant 60\),
(a) write down, as an inequality, the third constraint shown in Figure 6. (2)
Each Celebration arrangement includes 2 white roses and 4 red roses.
Each Party arrangement includes 1 white rose and 5 red roses.
Lethna wishes to use at least 70 white roses and at least 200 red roses.
(b) Write down two further inequalities to represent this information. (3)
(c) Add two lines and shading to Diagram 1 in the answer book to represent these two inequalities. (2)
(d) Hence determine the feasible region and label it \(R\). (1)
The times taken to produce each Celebration arrangement and each Party arrangement are 10 minutes and 4 minutes respectively. Lethna wishes to minimise the total time taken to produce the arrangements.
(e) Write down the objective function, \(T\), in terms of \(x\) and \(y\). (1)
(f) Use point testing to find the optimal number of each type of arrangement Lethna should produce, and find the total time she will take. (4)
Mark scheme (a)
Scheme
Marks
\(5y \geqslant x\)
B1 B1
(2)
Notes
a1B1 Ratio of coefficients correct (i.e. equation of line correct)
a2B1 Inequality correct way round (\(ay \geqslant bx\) o.e.) do not accept a strict inequality
Mark scheme (b)
Scheme
Marks
\(2x + y \geqslant 70\) and \(4x + 5y \geqslant 200\)
B3,2,1
(3)
Notes
b1B1 One equation correct
b2B1 One constraint correct, including inequality (but accept strict inequality here)
b3B1 Both constraints correct, including correct inequalities
Mark scheme (c)
Scheme
Marks
Two lines correctly added
B1 B1
(2)
Notes
c1B1 One line drawn correctly. Must pass within one small square of (25, 20) and if line extended must go from axis to axis through the points of intersection with the axes within one small square. Line must be long enough to form the feasible region. Check using length measurement tool if required. Ignore shading.
c2B1 Both lines drawn correctly. See above for accuracy. Ignore shading.
Mark scheme (d)
Scheme
Marks
R correctly labelled
B1
(1)
Notes
d1B1 R labelled (not just implied by shading) – must have scored both marks in (c).
Mark scheme (e)
Scheme
Marks
\((T =)\ 10x + 4y\)
B1
(1)
Notes
e1B1 CAO (isw if \((T =)\,10x + 4y\) ‘simplified’ to \(k(10x + 4y)\) but if \((T =)\,10x + 4y\) not stated then B0)
Mark scheme (f)
Scheme
Marks
Vertex
Time (mins)
(20,30)
320
(25, 20)
330
(40, 8)
432
(60,12)
648
(60,30)
720
M1 A1 A1
So produce 20 celebration arrangements, 30 party arrangements taking 320 (minutes)
A1
(4)
(13 marks)
Notes
f1M1 At least three of their (or the correct) R vertices found (by either reading off their graph or using simultaneous equations) and tested using their (or the correct T). Objective line method (only) is M0.
f1A1 Three vertices found and tested correctly CAO (must be using three of the correct vertices (see table above) and the values for T must be correct).
f2A1 All five vertices found and tested correctly CAO (all values of T must be correct).
f3A1 CAO number of each and time, both correct and it must be clear that \(x = 20\) and \(y = 30\) (accept as coordinates). If values appear in e.g. a table it must be clear that (20, 30) and 320 has been selected (condone lack of/incorrect units on the time).
A company is going to hire out two types of car, standard and luxury.
Let \(x\) be the number of standard cars it should buy. Let \(y\) be the number of luxury cars it should buy.
Figure 6 shows three constraints, other than \(x,\ y \geqslant 0\) Two of these are \(x \geqslant 20\) and \(y \geqslant 8\)
(a) Write, as an inequality, the third constraint shown in Figure 6. (1)
The company decides that at least \(\dfrac{1}{6}\) of the cars must be luxury cars.
(b) Express this information as an inequality and show that it simplifies to\[5y \geqslant x\]You must make the steps in your working clear. (2)
Each time the cars are hired they need to be prepared. It takes 5 hours to prepare a standard car and it takes 6 hours to prepare a luxury car. There are 300 hours available each week to prepare the cars.
(c) Express this information as an inequality. (1)
(d) Add two lines and shading to Diagram 1 in the answer book to illustrate the constraints found in parts (b) and (c). (2)
(e) Hence determine the feasible region and label it \(R\). (1)
The company expects to make £80 profit per week on each car.
It therefore wishes to maximise \(P = 80x + 80y\), where \(P\) is the profit per week.
(f) Use the objective line (ruler) method to find the optimal vertex, \(V\), of the feasible region. You must clearly draw and label your objective line and the vertex \(V\). (3)
(g) Given that \(P\) is the expected profit, in pounds, per week, find the number of each type of car that the company should buy and the maximum expected profit. (3)
b1B1 Either of my first two lines. Must have three terms, two in \(y\) and one in \(x\).
b2B1 CSO. (Answer given) must have \(\geqslant\) throughout.
Mark scheme (c)
Scheme
Marks
\(5x + 6y \leqslant 300\)
B1
(1)
Notes
c1B1 CAO
Mark scheme (d)
Scheme
Marks
Two lines and shading correctly added
B1 B1
(2)
Notes
In (d) If lines do not meet both axis then extend as necessary, but must extend beyond the feasible region. Use the line drawing tool to check.
d1B1 \(5y = x\) drawn correctly, passes within a small square of (0,0) and (50, 10). Ignore shading.
d2B1 \(5x + 6y = 300\) drawn correctly, passes within a small square of (0, 50), (30, 25) and (60, 0) Ignore shading.
Mark scheme (e)
Scheme
Marks
R correctly labelled
B1
(1)
Notes
e1B1 CAO – but must have scored both marks in (d)
Mark scheme (f)
Scheme
Marks
Objective line correctly drawn and labelled
M1 A1
Optimal vertex labelled
A1
(3)
Notes
f1M1 Drawing objective line with correct gradient, use line drawing tool to check if necessary. You can give BOD here if it is close. If their line is shorter than the length equivalent to that of line (0, 5) to (5, 0), please send to review.
f1A1 Correct objective line drawn (so no BOD) and their correct V labelled, or clearly indicated, or coordinates written to 1 dp.
f2A1 CSO, R correct, my V labelled or clearly indicated, or coordinates written to 1dp so awrt (48.4, 9.7).
(Corrected from the printed mark scheme: the coordinates of V are printed the wrong way round as (9.7, 48.4).)
Mark scheme (g)
Scheme
Marks
Buy 48 standard and 10 luxury cars, Expected profit £4640 per week
1B1 2B1, 3B1
(3)
(13 marks)
Notes
g1B1 Finding vertex, in my R, with integer coordinates. Must be within 2 small squares of their V and must be maximising, so accept only; (48, 10), (47, 10), (46, 11), (27, 27), (28, 26).
b1M1 One equal sign, P, terms in \(x\), \(z\), \(t\) plus a non-zero number term.
b1A1 CAO
Mark scheme (c)
Scheme
Marks
\(P = \tfrac{21}{2} - 9x - \tfrac{13}{2}z - \tfrac{7}{4}t\), so increasing \(x\) or \(z\) or \(t\) would decrease P
B1
(1)
(8 marks)
Notes
c1B1Explanation, must refer to increasing \(x\), \(z\) and \(t\), condone no ref to \(x = z = t = 0\), must have correct signs in equation in (b). Do not accept ‘no negatives in profit row’ o.e. alone.
Edgar has recently bought a field in which he intends to plant apple trees and plum trees.
He can use linear programming to determine the number of each type of tree he should plant.
Let \(x\) be the number of apple trees he plants and \(y\) be the number of plum trees he plants.
Two of the constraints are
\[\begin{aligned}x &\geqslant 40\\ y &\leqslant 50\end{aligned}\]
These are shown on the graph in Figure 6, where the rejected region is shaded out.
(a) Use these two constraints to write down two statements that describe the number of apple trees and plum trees Edgar can plant. (1)
Two further constraints are
\[\begin{aligned}3x + 4y &\leqslant 360\\ x &\leqslant 2y\end{aligned}\]
(b) Add two lines and shading to Diagram 1 in your answer book to represent these inequalities. Hence determine the feasible region and label it R. (4)
Edgar will make a profit of £60 from each apple tree and £20 from each plum tree. He wishes to maximise his profit, P.
(c) Write down the objective function. (1)
(d) Use an objective line to determine the optimal point of the feasible region, R. You must make your method clear. (4)
(e) Find Edgar’s maximum profit. (1)
Mark scheme (a)
Scheme
Marks
(Edgar should plant) at least 40 apple trees. (Edgar should plant) at most 50 plum trees.
B1
(1)
Notes
a1B1: CAO, both. Must be \(\leqslant\) and \(\geqslant\) not < and >.
Mark scheme (b)
Scheme
Marks
B1 B1 B1ft B1
(4)
Notes
b1B1: \(3x + 4y = 360\) CAO. If extended it must go axis to axis within one small square. Must be long enough to form the correct feasible region. Lines should be drawn with a ruler.
b2B1: \(x = 2y\) If extended must go through (0,0) and (120, 60) within one small square. Must be long enough to form the correct feasible region. Lines should be drawn with a ruler.
b3B1ft: ft their lines for correct shading on one of their lines. Implicit if R is correct.
b4B1: Region R correct, CAO. Must be labelled.
Mark scheme (c)
Scheme
Marks
(P = ) \(60x + 20y\)
B1
(1)
Notes
c1B1: CAO
Mark scheme (d)
Scheme
Marks
Drawing objective line
M1 A1
Calculating optimal point
DM1
(72, 36)
A1
(4)
Notes
d1M1: Drawing objective line or its reciprocal.
d1A1: Correct objective line. Axis to axis (0, 30) to (10, 0) minimum.
d2DM1: Depends on 1st M and correct region. Finding their correct optimal point.
1B1 Defining \(x\) and \(y\); Must see ‘number of’
2B1 CAO objective function \(15x + 12y\)
3B1 CAO \(x \geqslant 50\)
4B1 CAO o.e \(\tfrac{1}{5}(x + y) \lt x \Rightarrow y \lt 4x\)
5B1 CAO o.e \(\tfrac{2}{5}(x + y) \gt x \Rightarrow 2y \gt 3x\) (corrected from the printed mark scheme: the notes print \(\tfrac{2}{3}(x + y)\); the scheme above has \(\tfrac{2}{5}(x + y)\), i.e. 40%)
3. A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\).
The following tableau is obtained.
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
\(-\tfrac{1}{2}\)
0
2
1
\(-\tfrac{1}{2}\)
0
10
\(y\)
\(\tfrac{1}{2}\)
1
\(\tfrac{3}{4}\)
0
\(\tfrac{1}{4}\)
0
5
\(t\)
\(\tfrac{1}{2}\)
0
1
0
\(-\tfrac{1}{4}\)
1
4
\(P\)
−7
0
1
0
4
0
320
(a) Write down the profit equation represented in the tableau. (2)
(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use. (5)
(c) State the value of the objective function and of each variable. (3)
Mark scheme (a)
Scheme
Marks
\(P - 7x + z + 4s = 320\)
M1 A1
(2)
Notes
1M1: One equal sign, P and 320 present
1A1: cao
Mark scheme (b)
Scheme
Marks
b.v
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
\(-\tfrac{1}{2}\)
0
2
1
\(-\tfrac{1}{2}\)
0
10
\(y\)
\(\tfrac{1}{2}\)
1
\(\tfrac{3}{4}\)
0
\(\tfrac{1}{4}\)
0
5
\(t\)
\(\tfrac{1}{2}\)
0
1
0
\(-\tfrac{1}{4}\)
1
4
\(P\)
−7
0
1
0
4
0
320
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
Row ops.
\(r\)
0
0
3
1
\(-\tfrac{3}{4}\)
1
14
\(R_1 + \tfrac{1}{2}R_3\)
\(y\)
0
1
\(-\tfrac{1}{4}\)
0
\(\tfrac{1}{2}\)
−1
1
\(R_2 - \tfrac{1}{2}R_3\)
\(x\)
1
0
2
0
\(-\tfrac{1}{2}\)
2
8
\(R_3 \div \tfrac{1}{2}\)
\(P\)
0
0
15
0
\(\tfrac{1}{2}\)
14
376
\(R_4 + 7R_3\)
2M1 2A1ft 1M1 2A1 3A1
(5)
Notes
1M1: correct pivot located, attempt to divide row. If choosing negative pivot M0M0 in (b)
1A1: pivot row correct including change of b.v.
2M1: (ft) Correct row operations used at least once or stated correctly.
2A1ft: Looking at non zero-and-one columns, one column ft correct
3A1: cao.
Mark scheme (c)
Scheme
Marks
\(P = 376\quad x = 8\quad y = 1\quad z = 0\quad r = 14\quad s = 0\quad t = 0\)
M1 A1ft A1
(3)
(10 marks)
Notes
1M1: At least 4 values stated. Reading off bottom row, or negative values get M0.
1A1ft: Their four basic variables correct ft from their table.
(b)1M1 Drawing objective line or its reciprocal OR testing two vertices in the feasible region (see list above) points correct to 1 dp.
1A1 Correct objective line OR two points correctly tested (1 dp ok)
2DM1 Calculating optimal point either answer to 2 dp or better or using S.E’s (correct 2 equations for their point + attempt to eliminate one variable.); OR Testing three points correctly and optimal one to 2dp.
(Corrected from the printed mark scheme: the scheme prints \(\dfrac{240}{17}\); \(24\dfrac{12}{17} = \dfrac{420}{17}\), as in the list of points above.)
The graph in Figure 6 is being used to solve a linear programming problem. Two of the constraints have been drawn on the graph and the rejected regions shaded out.
(a) Write down the constraints shown on the graph. (4)
Keith organises two types of children’s activity, ‘Sports Mad’ and ‘Circus Fun’. He needs to determine the number of times each type of activity is to be offered.
Let \(x\) be the number of times he offers the ‘Sports Mad’ activity. Let \(y\) be the number of times he offers the ‘Circus Fun’ activity.
Two constraints are
\[\begin{aligned}x &\leqslant 15\\ \text{and}\quad y &\gt 6\end{aligned}\]
These constraints are shown on the graph in Figure 6, where the rejected regions are shaded out.
(a) Explain why \(y = 6\) is shown as a dotted line. (1)
(b) Add two lines and shading to Diagram 1 in the answer book to represent these inequalities. Hence determine the feasible region and label it R. (3)
Each ‘Sports Mad’ activity costs £500.
Each ‘Circus Fun’ activity costs £800.
Keith wishes to minimise the total cost.
(c) Write down the objective function, C, in terms of \(x\) and \(y\). (2)
(d) Use your graph to determine the number of times each type of activity should be offered and the total cost. You must show sufficient working to make your method clear. (5)
Mark scheme (a)
Scheme
Marks
To indicate the strict inequality
B1
(1)
Notes
1B1: CAO
Mark scheme (b)
Scheme
Marks
\(3x = 2y\) and \(5x + 4y = 80\) added to the diagram.
B1, B1
R correctly labelled.
B1
(3)
Notes
1B1: \(3x = 2y\) passing through 1 small square of (0,0) and (12, 18), but must reach x = 15
2B1: \(5x + 4y = 80\) passing through 1 small square of (0, 20) and (16, 0) (extended if necessary) but must reach y = 6
3B1: R CAO (condoning slight line inaccuracy as above.)
Mark scheme (c)
Scheme
Marks
[Minimise C =] \(500x + 800y\)
B1, B1
(2)
Notes
1B1: Accept expression and swapped coefficients. Accept 5x + 8y for 1 mark
2B1: CAO (expression still ok here)
Mark scheme (d)
Scheme
Marks
Point testing or Profit line
M1 A1
Seeking integer solutions
M1
(11, 7) at a cost of £ 11 100.
B1, B1
(5)
(11 marks)
Notes
1M1: Profit line [gradient accept reciprocal, minimum length line passes through (0, 2.5) (4, 0)] OR testing 2 points in their FR near two different vertices.
1A1: Correct profit line OR 2 points correctly tested in correct FR (my points)
6. The tableau below is the initial tableau for a linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).
Basic Variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
0
1
2
1
0
0
24
\(s\)
2
1
4
0
1
0
28
\(t\)
−1
\(\tfrac{1}{2}\)
3
0
0
1
22
\(P\)
−1
−2
−6
0
0
0
0
(a) Write down the profit equation represented in the initial tableau. (1)
(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use. (9)
(c) State the final value of the objective function and of each variable. (3)
Mark scheme (a)
Scheme
Marks
\(P - x - 2y - 6z = 0\)
B1
(1)
Notes
1B1: cao
Mark scheme (b)
Scheme
Marks
b.v
x
y
z
r
s
t
Value
r
0
1
2
1
0
0
24
s
2
1
4
0
1
0
28
t
−1
\(\tfrac{1}{2}\)
3
0
0
1
22
P
−1
−2
−6
0
0
0
0
b.v.
x
y
z
r
s
t
Value
Row Ops.
r
−1
\(\tfrac{1}{2}\)
0
1
\(-\tfrac{1}{2}\)
0
10
\(R_1 - 2R_2\)
z
\(\tfrac{1}{2}\)
\(\tfrac{1}{4}\)
1
0
\(\tfrac{1}{4}\)
0
7
\(R_2 \div 4\)
t
\(-\tfrac{5}{2}\)
\(-\tfrac{1}{4}\)
0
0
\(-\tfrac{3}{4}\)
1
1
\(R_3 - 3R_2\)
P
2
\(-\tfrac{1}{2}\)
0
0
\(\tfrac{3}{2}\)
0
42
\(R_4 + 6R_2\)
M1 A1 M1 A1ft A1
(5)
b.v.
x
y
z
r
s
t
Value
Row Ops.
y
−2
1
0
2
−1
0
20
\(R_1 \div \tfrac{1}{2}\)
z
1
0
1
\(-\tfrac{1}{2}\)
\(\tfrac{1}{2}\)
0
2
\(R_2 - \tfrac{1}{4}R_1\)
t
−3
0
0
\(\tfrac{1}{2}\)
−1
1
6
\(R_3 + \tfrac{1}{4}R_1\)
P
1
0
0
1
1
0
52
\(R_4 + \tfrac{1}{2}R_1\)
M1 A1ft M1 A1
(4)
(9)
Notes
Pivots are shown in bold (highlighted in the printed scheme).
1M1: correct pivot located, attempt to divide row
1A1: pivot row correct including change of b.v.
2M1: (ft) Correct row operations used at least once or stated correctly.
1A1ft: Looking at non zero-and-one columns, one column ft correct
7. You are in charge of buying new cupboards for a school laboratory. The cupboards are available in two different sizes, standard and large. The maximum budget available is £1800. Standard cupboards cost £150 and large cupboards cost £300. Let \(x\) be the number of standard cupboards and \(y\) be the number of large cupboards.
(a) Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. (2)
The cupboards will be fitted along a wall 9 m long. Standard cupboards are 90 cm long and large cupboards are 120 cm long.
(b) Show that this constraint can be modelled by \[3x + 4y \leqslant 30.\] You must make your reasoning clear. (2)
Given also that \(y \geqslant 2\),
(c) explain what this constraint means in the context of the question. (1)
The capacity of a large cupboard is 40% greater than the capacity of a standard cupboard. You wish to maximise the total capacity.
(d) Show that your objective can be expressed as \[\text{maximise } 5x + 7y\] (2)
(e) Represent your inequalities graphically, on the axes in your answer booklet, indicating clearly the feasible region, R. (6)
(f) Find the number of standard cupboards and large cupboards that need to be purchased. Make your method clear. (4)
3B1 – correctly drawing \(x + 2y = 12\) [\(150x + 300y = 1800\)], ft only if swapped coefficients in (a) (6,0) (2,8).
These next 3 marks are only available for candidates who have drawn at least 2 lines, including at least one ‘diagonal’ line with negative gradient.
4B1 – Ruler used. At least 2 lines labelled including one ‘diagonal’ line.
5B1 – Shading, or R correct, b.o.d. on their lines.
6B1 – all lines and R correct.
(Corrected from the printed mark scheme: the scheme prints \(0.9x + 1.2y \leqslant 12\) and \([0.9x + 1.2y = 12]\); the wall constraint from (b) is \(0.9x + 1.2y \leqslant 9\).)
Mark scheme (f)
Scheme
Marks
Consider points and value of \(5x + 7y\): Or draw a clear profit line
M1A1
(7,2) \(\rightarrow\) 49 or \((7\tfrac{1}{3}, 2) \rightarrow 50\tfrac{2}{3}\), or \((7.3, 2) \rightarrow 50.5\) (6,3) \(\rightarrow\) 51 (0,6) \(\rightarrow\) 42
(0,2) \(\rightarrow\) 14
A1
Best option is to buy 6 standard cupboards and 3 large cupboards.
A1
(4)
(17 marks)
Notes
1M1 At least 2 points tested or objective line drawn with correct m or 1/m, minimum intercepts 3.5 and 2.5.
1A1 – 2 points correctly tested or objective line correct.
2A1 – 3 points correctly tested or objective line correct and distinct/labelled.
3A1 – 6 standard and 3 large, accept (6,3) if very clearly selected in some way.
(b) Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make. (2)
(c) On the grid provided, show these three constraints and \(x \geqslant 0\), \(y \geqslant 0\). Hence label the feasible region, R. (4)
Rose makes a profit of £2 on each large basket and £3 on each small basket. Rose wishes to maximise her profit, £\(P\).
(d) Write down the objective function. (1)
(e) Use your graph to determine the optimal numbers of large and small baskets Rose should make, and state the optimal profit. (5)
Mark scheme (a)
Scheme
Marks
\(7x + 5y \leqslant 350\)
M1 A1
(2)
Notes
(a) 1M1: Coefficients correct (condone swapped \(x\) and \(y\) coefficients) need 350 and any inequality
1A1: cso.
Mark scheme (b)
Scheme
Marks
\(y \leqslant 20\) e.g. make at most 20 small baskets
B1
\(y \leqslant 4x\) e.g. the number of small (\(y\)) baskets is at most 4 times the number of large baskets (\(x\)). {E.g if \(y = 40\), \(x = 10, 11, 12\) etc. or if \(x = 10\), \(y = 40, 39, 38\)}
B1
(2)
Notes
(b) 1B1: cao
2B1: cao, test their statement, need both = and < aspects.
Mark scheme (c)
Scheme
Marks
(see graph) Draw three lines correctly Label R
B3, 2, 1, 0 B1
(4)
Notes
(c) 1B1: One line drawn correctly
2B1: Two lines drawn correctly
3B1: Three lines drawn correctly. Check (10, 40) (0, 0) and axes
4B1: R correct, but allow if one line is slightly out (1 small square).
Mark scheme (d)
Scheme
Marks
\((P =)\ 2x + 3y\)
B1
(1)
Notes
(d) 1B1: cao accept an expression.
Mark scheme (e)
Scheme
Marks
Profit line or point testing.
M1 A1
\(x = 35.7\) \(y = 20\) precise point found.
B1
Need integers so optimal point in R is (35, 20); Profit (£)130
B1;B1
(5)
(14 marks)
Notes
(e) 1M1: Attempt at profit line or attempt to test at least two vertices in their feasible region.
1A1: Correct profit line or correct testing of at least three vertices.
Point testing: (0,0) P= 0; (5,20) P = 70; (50,0) P = 100
8. The tableau below is the initial tableau for a maximising linear programming problem in \(x\), \(y\) and \(z\).
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
4
\(\dfrac{7}{3}\)
\(\dfrac{5}{2}\)
1
0
0
64
\(s\)
1
3
0
0
1
0
16
\(t\)
4
2
2
0
0
1
60
\(P\)
−5
\(-\dfrac{7}{2}\)
−4
0
0
0
0
(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use. (9)
(b) Explain how you know that your solution is not optimal. (1)
Mark scheme (a)
Scheme
Marks
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
\(4\)
\(\tfrac{7}{3}\)
\(\tfrac{5}{2}\)
\(1\)
\(0\)
\(0\)
\(64\)
\(s\)
\(1\)
\(3\)
\(0\)
\(0\)
\(1\)
\(0\)
\(16\)
\(t\)
\(\boxed{4}\)
\(2\)
\(2\)
\(0\)
\(0\)
\(1\)
\(60\)
\(P\)
\(-5\)
\(-\tfrac{7}{2}\)
\(-4\)
\(0\)
\(0\)
\(0\)
\(0\)
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
Row ops
\(r\)
\(0\)
\(\tfrac{1}{3}\)
\(\boxed{\tfrac{1}{2}}\)
\(1\)
\(0\)
\(-1\)
\(4\)
\(\text{R}_1 - 4\text{R}_3\)
\(s\)
\(0\)
\(\tfrac{5}{2}\)
\(-\tfrac{1}{2}\)
\(0\)
\(1\)
\(-\tfrac{1}{4}\)
\(1\)
\(\text{R}_2 - \text{R}_3\)
\(x\)
\(1\)
\(\tfrac{1}{2}\)
\(\tfrac{1}{2}\)
\(0\)
\(0\)
\(\tfrac{1}{4}\)
\(15\)
\(\text{R}_3 \div 4\)
\(P\)
\(0\)
\(-1\)
\(-\tfrac{3}{2}\)
\(0\)
\(0\)
\(\tfrac{5}{4}\)
\(75\)
\(\text{R}_4 + 5\text{R}_3\)
M1 A1 M1 A1ft A1
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
Row ops
\(z\)
\(0\)
\(\tfrac{2}{3}\)
\(1\)
\(2\)
\(0\)
\(-2\)
\(8\)
\(\text{R}_1 \div \tfrac{1}{2}\)
\(s\)
\(0\)
\(\tfrac{17}{6}\)
\(0\)
\(1\)
\(1\)
\(-\tfrac{5}{4}\)
\(5\)
\(\text{R}_2 + \tfrac{1}{2}\text{R}_1\)
\(x\)
\(1\)
\(\tfrac{1}{6}\)
\(0\)
\(-1\)
\(0\)
\(\tfrac{5}{4}\)
\(11\)
\(\text{R}_3 - \tfrac{1}{2}\text{R}_1\)
\(P\)
\(0\)
\(0\)
\(0\)
\(3\)
\(0\)
\(-\tfrac{7}{4}\)
\(87\)
\(\text{R}_4 + \tfrac{3}{2}\text{R}_1\)
M1 A1ft M1 A1
(9)
Notes
Pivots are boxed (shaded in the scheme).
Mark scheme (b)
Scheme
Marks
There is still negative numbers in the profit row.
8. Class 8B has decided to sell apples and bananas at morning break this week to raise money for charity. The profit on each apple is 20p, the profit on each banana is 15p. They have done some market research and formed the following constraints.
They will sell at most 800 items of fruit during the week.
They will sell at least twice as many apples as bananas.
They will sell between 50 and 100 bananas.
Assuming they will sell all their fruit, formulate the above information as a linear programming problem, letting \(a\) represent the number of apples they sell and \(b\) represent the number of bananas they sell.
Write your constraints as inequalities. (7)
Mark scheme
Scheme
Marks
Maximise \((P=)\ 0.2a + 0.15b\) or \(20a + 15b\) o.e.
B1 B1
(2)
Subject to \[\begin{aligned} a + b &\leqslant 800\\ a &\geqslant 2b\\ 50 \leqslant b &\leqslant 100\\ a &\geqslant 0\end{aligned}\]
B1 B2, 1, 0 B1 B1
(5)
(7 marks)
Notes
1B1: ‘Maximise’
2B1: ratio of coefficients correct
3B1: cao
4B1: ratio of coefficients of \(a\) and \(b\) correct.
5B1: inequality correct way round i.e. \(a \geqslant \ldots b\)
6B1: cao accept < – accept two separate inequalities here
7B1: cao
Penalise < and > only once with last B mark earned
Be generous on letters a, b, A, B, x, y etc and mixed, but remove last B mark earned if inconsistent or 3 letters in the ones marked.
6. The tableau below is the initial tableau for a maximising linear programming problem in \(x\), \(y\) and \(z\).
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
4
\(\dfrac{7}{3}\)
\(\dfrac{5}{2}\)
1
0
0
64
\(s\)
1
3
0
0
1
0
16
\(t\)
4
2
2
0
0
1
60
\(P\)
−5
\(-\dfrac{7}{2}\)
−4
0
0
0
0
(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use. (9)
(b) Explain how you know that your solution is not optimal. (1)
Mark scheme (a)
Scheme
Marks
b.v
x
y
z
R
s
t
value
r
4
\(\dfrac{7}{3}\)
\(\dfrac{5}{2}\)
1
0
0
64
s
1
3
0
0
1
0
16
t
4
2
2
0
0
1
60
P
-5
\(-\dfrac{7}{2}\)
−4
0
0
0
0
b.v
x
y
z
R
s
t
value
Row ops
r
0
\(\dfrac{1}{3}\)
\(\dfrac{1}{2}\)
1
0
−1
4
\(\text{R}_1 - 4\text{R}_3\)
s
0
\(\dfrac{5}{2}\)
\(-\dfrac{1}{2}\)
0
1
\(-\dfrac{1}{4}\)
1
\(\text{R}_2 - \text{R}_3\)
x
1
\(\dfrac{1}{2}\)
\(\dfrac{1}{2}\)
0
0
\(\dfrac{1}{4}\)
15
\(\text{R}_3 \div 4\)
P
0
−1
\(-\dfrac{3}{2}\)
0
0
\(\dfrac{5}{4}\)
75
\(\text{R}_4 + 5\text{R}_3\)
M1 A1 M1 A1ft A1
b.v
x
y
z
R
s
t
value
Row ops
z
0
\(\dfrac{2}{3}\)
1
2
0
−2
8
\(\text{R}_1 \div \tfrac{1}{2}\)
s
0
\(\dfrac{17}{6}\)
0
1
1
\(-\dfrac{5}{4}\)
5
\(\text{R}_2 + \tfrac{1}{2}\text{R}_1\)
x
1
\(\dfrac{1}{6}\)
0
−1
0
\(\dfrac{5}{4}\)
11
\(\text{R}_3 - \tfrac{1}{2}\text{R}_1\)
P
0
0
0
3
0
\(-\dfrac{7}{4}\)
87
\(\text{R}_4 + \tfrac{3}{2}\text{R}_1\)
M1 A1ft M1 A1
(9)
Mark scheme (b)
Scheme
Marks
There is still a negative number in the profit row.
Phil sells boxed lunches to travellers at railway stations. Customers can select either the vegetarian box or the non-vegetarian box.
Phil decides to use graphical linear programming to help him optimise the numbers of each type of box he should produce each day.
Each day Phil produces \(x\) vegetarian boxes and \(y\) non-vegetarian boxes.
One of the constraints limiting the number of boxes is
\[x + y \geqslant 70.\]
This, together with \(x \geqslant 0\), \(y \geqslant 0\) and a fourth constraint, has been represented in Figure 7. The rejected region has been shaded.
(a) Write down the inequality represented by the fourth constraint. (2)
Two further constraints are:
\[x + 2y \leqslant 160\]\[\text{and} \quad y \gt 60.\]
(b) Add two lines and shading to Diagram 4 in your answer book to represent these inequalities. (4)
(c) Hence determine and label the feasible region, R. (1)
(d) Use your graph to determine the minimum total number of boxes he needs to prepare each day. Make your method clear. (3)
Phil makes a profit of £1.20 on each vegetarian box and £1.40 on each non-vegetarian box. He wishes to maximise his profit.
(e) Write down the objective function. (1)
(f) Use your graph to obtain the optimal number of vegetarian and non-vegetarian boxes he should produce each day. You must make your method clear. (4)
(g) Find Phil’s maximum daily profit. (1)
Mark scheme (a)
Scheme
Marks
\(y \geqslant 2x\)
B2, 1, 0
(2)
Notes
Q7(a) 1B1 2 (or ½) one correct side, condone any inequality or equals, or bod
(b) 1B1–4B1 −1 e.e. Errors to look for: \(y = 60\) distinct in some way; lines correct to \(\leqslant\) 1 small square 1 at axis; Labels on lines; Ruler
Mark scheme (c)
Scheme
Marks
R correct
B1ft
(1)
Notes
(c) 1B1ft R ‘correct’, ft their lines, but shading needs to be correct
Mark scheme (d)
Scheme
Marks
Profit line added or Point testing seen
M1
correctly done
A1
70 boxes identified
A1
(3)
Notes
(d) 1M1 Attempt at profit line (axis to axis) or point testing 2 points
1A1 Profit line correct (within 1 sm square) or three points tested correctly
2A1 cao
Mark scheme (e)
Scheme
Marks
\((P =)\ 1.2x + 1.4y\)
B1
(1)
Notes
(e) 1B1 cao
Mark scheme (f)
Scheme
Marks
Profit line added or Point testing seen
M1
correctly done
A1ft A1
(32, 64) identified.
A1
(4)
Notes
(f) 1M1 Attempt at profit line (axis to axis) or point testing 2 points
1A1ft correct but ft their R and their (e) for profit line and 3 point testing
2A1 correct (so a mark for correct with no need to ft)
8. The tableau below is the initial tableau for a linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).
basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
12
4
5
1
0
0
246
\(s\)
9
6
3
0
1
0
153
\(t\)
5
2
−2
0
0
1
171
\(P\)
−2
−4
−3
0
0
0
0
Using the information in the tableau, write down
(a) the objective function, (2)
(b) the three constraints as inequalities with integer coefficients. (3)
Taking the most negative number in the profit row to indicate the pivot column at each stage,
(c) solve this linear programming problem. Make your method clear by stating the row operations you use. (9)
(d) State the final values of the objective function and each variable. (3)
(e) One of the constraints is not at capacity. Explain how it can be identified. (1)
7. The tableau below is the initial tableau for a linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).
basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
12
4
5
1
0
0
246
\(s\)
9
6
3
0
1
0
153
\(t\)
5
2
−2
0
0
1
171
\(P\)
−2
−4
−3
0
0
0
0
Using the information in the tableau, write down
(a) the objective function, (2)
(b) the three constraints as inequalities with integer coefficients. (3)
Taking the most negative number in the profit row to indicate the pivot column at each stage,
(c) solve this linear programming problem. Make your method clear by stating the row operations you use. (9)
(d) State the final values of the objective function and each variable. (3)
One of the constraints is not at capacity.
(e) Explain how it can be identified. (1)
Mark scheme (a)
Scheme
Marks
\(P - 2x - 4y - 3z = 0\) (o.e.)
B2, 0
(2)
Mark scheme (b)
Scheme
Marks
\(12x + 4y + 5z \leqslant 246\)
B1
\(9x + 6y + 3z \leqslant 153\)
B1
\(5x + 2y - 2z \leqslant 171\)
B1
(3)
Mark scheme (c)
Scheme
Marks
basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
12
4
5
1
0
0
246
\(s\)
9
6
3
0
1
0
153
\(t\)
5
2
−2
0
0
1
171
\(P\)
−2
−4
−3
0
0
0
0
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
Row operations
\(r\)
6
0
3
1
\(-\dfrac{2}{3}\)
0
144
\(R_1 - 4R_2\)
\(y\)
\(\dfrac{3}{2}\)
1
\(\dfrac{1}{2}\)
0
\(\dfrac{1}{6}\)
0
25.5
\(R_2 \div 6\)
\(t\)
2
0
−3
0
\(-\dfrac{1}{3}\)
1
120
\(R_3 - 2R_2\)
\(P\)
4
0
−1
0
\(\dfrac{2}{3}\)
0
102
\(R_4 + 4R_2\)
M1 A1 M1 A1ft B1ft
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
Row operations
\(z\)
2
0
1
\(\dfrac{1}{3}\)
\(-\dfrac{2}{9}\)
0
48
\(R_1 \div 3\)
\(y\)
\(\dfrac{1}{2}\)
1
0
\(-\dfrac{1}{6}\)
\(\dfrac{5}{18}\)
0
1.5
\(R_2 - \tfrac{1}{2}R_1\)
\(t\)
8
0
0
1
−1
1
264
\(R_3 + 3R_1\)
\(P\)
6
0
0
\(\dfrac{1}{3}\)
\(\dfrac{4}{9}\)
0
150
\(R_4 + R_1\)
M1 A1 M1 A1
(9)
Mark scheme (d)
Scheme
Marks
\(P = 150 \quad x = 0 \quad y = 1.5 \quad z = 48\) \(r = 0 \quad s = 0 \quad t = 264\)
The captain of the Malde Mare takes passengers on trips across the lake in her boat.
The number of children is represented by \(x\) and the number of adults by \(y\).
Two of the constraints limiting the number of people she can take on each trip are
\[x \lt 10\]
and
\[2 \leqslant y \leqslant 10\]
These are shown on the graph in Figure 6, where the rejected regions are shaded out.
(a) Explain why the line \(x = 10\) is shown as a dotted line. (1)
(b) Use the constraints to write down statements that describe the number of children and the number of adults that can be taken on each trip. (3)
For each trip she charges £2 per child and £3 per adult. She must take at least £24 per trip to cover costs. The number of children must not exceed twice the number of adults.
(c) Use this information to write down two inequalities. (2)
(d) Add two lines and shading to Diagram 1 in your answer book to represent these inequalities. Hence determine the feasible region and label it R. (4)
(e) Use your graph to determine how many children and adults would be on the trip if the captain takes:
4. A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit \(P\). The following initial tableau was obtained.
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
Value
\(r\)
2
0
4
1
0
80
\(s\)
1
4
2
0
1
160
\(P\)
\(-2\)
\(-8\)
\(-20\)
0
0
0
(a) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm, to obtain tableau \(T\). State the row operations that you use. (5)
(b) Write down the profit equation shown in tableau \(T\). (1)
(c) State whether tableau \(T\) is optimal. Give a reason for your answer. (1)
Mark scheme (a)
Scheme
Marks
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
Value
Row ops
\(z\)
\(\tfrac{1}{2}\)
0
1
\(\tfrac{1}{4}\)
0
20
\((R_1 \div 4)\)
\(s\)
0
4
0
\(-\tfrac{1}{2}\)
1
120
\(R_2 - 2R_1\)
\(P\)
8
\(-8\)
0
5
0
400
\(R_3 + 20R_1\)
M1 A1 M1 A1ft A1ft
(5)
Mark scheme (b)
Scheme
Marks
\(P + 8x - 8y + 5r = 400\)
B1ft
(1)
Mark scheme (c)
Scheme
Marks
Not optimal since there is a negative number in the profit row
8. The tableau below is the initial tableau for a maximising linear programming problem.
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
7
10
10
1
0
0
3600
\(s\)
6
9
12
0
1
0
3600
\(t\)
2
3
4
0
0
1
2400
\(P\)
−35
−55
−60
0
0
0
0
(a) Write down the four equations represented in the initial tableau above. (4)
(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. (9)
(c) State the values of the objective function and each variable. (3)
Mark scheme (a)
Scheme
Marks
\(7x + 10y + 10z + r = 3600\) \(6x + 9y + 12z + s = 3600\) \(2x + 3y + 4z + t = 2400\)
B2, 1, 0
\(\text{P} - 35x - 55y - 60z = 0\)
B2, 0
(4)
Mark scheme (b)
Scheme
Marks
(i)
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
Row ops
\(r\)
\(2\)
\(\boldsymbol{\tfrac{5}{2}}\)
\(0\)
\(1\)
\(-\tfrac{5}{6}\)
\(0\)
\(600\)
\(\text{R}_1 - 10\text{R}_2\)
\(z\)
\(\tfrac{1}{2}\)
\(\tfrac{3}{4}\)
\(1\)
\(0\)
\(\tfrac{1}{12}\)
\(0\)
\(300\)
\(\text{R}_2 \div 12\)
\(t\)
\(0\)
\(0\)
\(0\)
\(0\)
\(-\tfrac{1}{3}\)
\(1\)
\(1200\)
\(\text{R}_3 - 4\text{R}_2\)
\(P\)
\(-5\)
\(-10\)
\(0\)
\(0\)
\(5\)
\(0\)
\(18000\)
\(\text{R}_4 + 60\text{R}_2\)
A1 M1 A1ft B1 (5)
(ii)
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
Row ops
\(y\)
\(\tfrac{4}{5}\)
\(1\)
\(0\)
\(\tfrac{2}{5}\)
\(-\tfrac{1}{3}\)
\(0\)
\(240\)
\(\text{R}_1 \div \tfrac{5}{2}\)
\(z\)
\(-\tfrac{1}{10}\)
\(0\)
\(1\)
\(-\tfrac{3}{10}\)
\(\tfrac{1}{3}\)
\(0\)
\(120\)
\(\text{R}_2 - \tfrac{3}{4}\text{R}_1\)
\(t\)
\(0\)
\(0\)
\(0\)
\(0\)
\(-\tfrac{1}{3}\)
\(1\)
\(1200\)
\(\text{R}_3\ \text{stet}\)
\(P\)
\(3\)
\(0\)
\(0\)
\(4\)
\(\tfrac{5}{3}\)
\(0\)
\(20400\)
\(\text{R}_4 + 10\text{R}_1\)
M1 M1 A1ft M1 A1 (4)
(9)
Notes
(Corrected from the printed mark scheme: the value in the P row of the first tableau is printed as 1800; it is \(60 \times 300 = 18000\), consistent with 20400 in the second tableau.)
Mark scheme (c)
Scheme
Marks
\(\text{P} = 20400\quad x = 0\quad y = 240\quad z = 120\)
M1
\(r = 0\quad s = 0\quad t = 1200\)
A2ft, A1ft, 0
(3)
(16 marks)
Notes
(The printed mark scheme shows a part total of 2 here; the codes M1 A2 make 3, as on the paper.)
6. The tableau below is the initial tableau for a maximising linear programming problem.
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
7
10
10
1
0
0
3600
\(s\)
6
9
12
0
1
0
3600
\(t\)
2
3
4
0
0
1
2400
\(P\)
\(-35\)
\(-55\)
\(-60\)
0
0
0
0
(a) Write down the four equations represented in the initial tableau above. (4)
(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. (9)
(c) State the values of the objective function and each variable. (3)
Mark scheme (a)
Scheme
Marks
\(7x + 10y + 10z + r = 3600\) \(6x + 9y + 12z + s = 3600\) \(2x + 3y + 4z + t = 2400\)
B2,1,0
\(P - 35x - 55y - 60z = 0\)
B2,0
(4)
Notes
B2, B1 First 3 equations c.a.o. – 1 each error, but penalise only 1 error per equation. Inequalities get B0
B2 c.a.o. (B1 for a ‘little slip’)
Mark scheme (b)
Scheme
Marks
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
Row ops.
\(r\)
2
\(\tfrac{5}{2}\) (pivot)
0
1
\(-\tfrac{5}{6}\)
0
600
\(R_1 - 10R_2\)
\(z\)
\(\tfrac{1}{2}\)
\(\tfrac{3}{4}\)
1
0
\(\tfrac{1}{12}\)
0
300
\(R_2 \div 12\)
\(t\)
0
0
0
0
\(-\tfrac{1}{3}\)
1
1200
\(R_3 - 4R_2\)
\(P\)
\(-5\)
\(-10\)
0
0
5
0
18000
\(R_4 + 60R_2\)
M1 A1 M1 A1ft B1 (5)
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
Row ops.
\(y\)
\(\tfrac{4}{5}\)
1
0
\(\tfrac{2}{5}\)
\(-\tfrac{1}{3}\)
0
240
\(R_1 \div \tfrac{5}{2}\)
\(z\)
\(-\tfrac{1}{10}\)
0
1
\(-\tfrac{3}{10}\)
\(\tfrac{1}{3}\)
0
120
\(R_2 - \tfrac{3}{4}R_1\)
\(t\)
0
0
0
0
\(-\tfrac{1}{3}\)
1
1200
\(R_3\) stet
\(P\)
3
0
0
4
\(\tfrac{5}{3}\)
0
20400
\(R_4 + 10R_1\)
M1 A1ft M1 A1 (4)
(9)
Notes
M1 Correct pivot chosen and some attempt to deal with whole row
A1 pivot row correct c.a.o. including b.v.
M1 correct row operations used (all 3) – at least 1 non-zero or 1 term correct in each row
A1ft non-pivoted rows correct; ft on error in pivot choice only
B1 Row operations correctly stated (condone lack of \(R_2 \div 12\)); must be in terms of new pivot row
M1ft Correct pivot chosen + some attempt to deal with whole row, ft from previous tableau. No negatives in value of previous tableau or M0
A1ft c.a.o. including b.v. but ft from previous tableau
M1 Correct row operations used (all 3) – at least 1 non-zero or 1 term correct in each row
A1 c.a.o.
Mark scheme (c)
Scheme
Marks
\(P = 20\,400\quad x = 0\quad y = 240\quad z = 120\) \(r = 0\quad s = 0\quad t = 1200\)
M1 A2ft,1ft,0
(3)
(16 marks)
Notes
M1 3 variables stated – must have completed b.v. and value columns (or 1s and zeros) on tableau. If reading top → bottom M0. Must be a final tableau. Any negative M0
6. A company produces two types of party bag, Infant and Junior. Both types of bag contain a balloon, a toy and a whistle. In addition the Infant bag contains 3 sweets and 3 stickers and the Junior bag contains 10 sweets and 2 stickers.
The sweets and stickers are produced in the company’s factory. The factory can produce up to 3000 sweets per hour and 1200 stickers per hour. The company buys a large supply of balloons, toys and whistles.
Market research indicates that at least twice as many Infant bags as Junior bags should be produced.
Both types of party bag are sold at a profit of 15p per bag. All the bags are sold.
The company wishes to maximise its profit.
Let \(x\) be the number of Infant bags produced and \(y\) be the number of Junior bags produced per hour.
(a) Formulate the above situation as a linear programming problem. (5)
(b) Represent your inequalities graphically, indicating clearly the feasible region. (6)
(c) Find the number of Infant bags and Junior bags that should be produced each hour and the maximum hourly profit. Make your method clear. (3)
In order to increase the profit further, the company decides to buy additional equipment. It can buy equipment to increase the production of either sweets or stickers, but not both.
(d) Using your graph, explain which equipment should be bought, giving your reasoning. (2)
The manager of the company does not understand why the balloons, toys and whistles have not been considered in the above calculations.
(e) Explain briefly why they do not need to be considered. (2)
Mark scheme (a)
Scheme
Marks
Maximise, \((P =)\ 15x + 15y\)
B1, B1
subject to \(\quad 3x + 10y \leqslant 3000\) \(\phantom{\text{subject to}\quad} 3x + 2y \leqslant 1200\) \(\phantom{\text{subject to}\quad} x \geqslant 2y\) \(\phantom{\text{subject to}\quad} x, y \geqslant 0\)
B3,2,1,0
(5)
Mark scheme (b)
Scheme
Marks
B6,5,4,3,2,1,0
(6)
Mark scheme (c)
Scheme
Marks
Profit line or vertex testing, \((300, 150)\), profit \(=\) £67.50
M1 A1ft A1ft
(3)
Mark scheme (d)
Scheme
Marks
Production of stickers should be increased since this would move the intersection point further from the origin.
B2,1ft,0
(2)
Mark scheme (e)
Scheme
Marks
e.g. The constraint lines would be far outside the feasible region – so they would not affect it.
8. Polly has a bird food stall at the local market. Each week she makes and sells three types of packs \(A\), \(B\) and \(C\).
Pack \(A\) contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts.
Pack \(B\) contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts.
Pack \(C\) contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts.
Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs.
The profit made on each pack of \(A\), \(B\) and \(C\) sold is £3.50, £3.50 and £6.50 respectively. Polly sells every pack on her stall and wishes to maximise her profit, \(P\) pence.
Let \(x\), \(y\) and \(z\) be the numbers of packs \(A\), \(B\) and \(C\) sold each week.
An initial Simplex tableau for the above situation is
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
\(4\)
\(5\)
\(10\)
\(1\)
\(0\)
\(0\)
\(140\)
\(s\)
\(2\)
\(1\)
\(4\)
\(0\)
\(1\)
\(0\)
\(60\)
\(t\)
\(1\)
\(2\)
\(3\)
\(0\)
\(0\)
\(1\)
\(60\)
\(P\)
\(-350\)
\(-350\)
\(-650\)
\(0\)
\(0\)
\(0\)
\(0\)
(a) Explain the meaning of the variables \(r\), \(s\) and \(t\) in the context of this question. (2)
(b) Perform one complete iteration of the Simplex algorithm to form a new tableau \(T\). Take the most negative number in the profit row to indicate the pivotal column. (5)
(c) State the value of every variable as given by tableau \(T\). (3)
(d) Write down the profit equation given by tableau \(T\). (2)
(e) Use your profit equation to explain why tableau \(T\) is not optimal. (1)
Taking the most negative number in the profit row to indicate the pivotal column,
(f) identify clearly the location of the next pivotal element. (2)
Mark scheme (a)
Scheme
Marks
\(r\), \(s\) and \(t\) are unused amounts of bird seed (in kg), suet blocks and peanuts (in kg) that Polly has at the end of each week after she has made up and sold her packs
B2, 1, 0
(2)
Notes
B2 Ref to “unused” “bird seed, suet blocks & peanuts”
B1 Ref to “unused” or bird seed etc or muddled explanation.
“bad” gets B1 must engage with context
Mark scheme (b)
Scheme
Marks
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(z\)
\(\tfrac{2}{5}\)
\(\tfrac{1}{2}\)
\(1\)
\(\tfrac{1}{10}\)
\(0\)
\(0\)
\(14\)
\(\text{R}_1 \div 10\)
\(s\)
\(\boxed{\tfrac{2}{5}}\)
\(-1\)
\(0\)
\(-\tfrac{2}{5}\)
\(1\)
\(0\)
\(4\)
\(\text{R}_2 - 4\text{R}_1\)
\(t\)
\(-\tfrac{1}{5}\)
\(\tfrac{1}{2}\)
\(0\)
\(-\tfrac{3}{10}\)
\(0\)
\(1\)
\(18\)
\(\text{R}_3 - 3\text{R}_1\)
\(p\)
\(-90\)
\(-25\)
\(0\)
\(65\)
\(0\)
\(0\)
\(9100\)
\(\text{R}_4 + 650\text{R}_1\)
M1 A1 M1 A2ft, 1ft, 0
(5)
Notes
The boxed entry is ringed in the mark scheme (the next pivot).
M1 correct pivot
A1 pivot row correct c.a.o. incl. b.v
M1ft correct row operations used (all 3) – at least 1 non zero or 1 term correct in each row. Where row not ft \(\Rightarrow\) M0
A2ft non-pivoted rows correct; –1 each error ft on error in pivot choice only. Penalise b.v once only
(b) Notes
1. Wrong pivot chosen in col 2 (–usually 4) M0 then for M1A2ft
(a)
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(r\)
\(-1\)
\(2\tfrac{1}{2}\)
\(0\)
\(1\)
\(-2\tfrac{1}{2}\)
\(0\)
\(-10\)
\(\text{R}_1 - 10\text{R}_2\)
\(z\)
\(\tfrac{1}{2}\)
\(\tfrac{1}{4}\)
\(1\)
\(0\)
\(\tfrac{1}{4}\)
\(0\)
\(15\)
\(\text{R}_2 \div 4\)
\(t\)
\(-\tfrac{1}{2}\)
\(\boxed{1\tfrac{1}{4}}\)
\(0\)
\(0\)
\(-\tfrac{3}{4}\)
\(1\)
\(15\)
\(\text{R}_3 - 3\text{R}_2\)
\(p\)
\(-25\)
\(-187\tfrac{1}{2}\)
\(0\)
\(0\)
\(162\tfrac{1}{2}\)
\(0\)
\(9750\)
\(\text{R}_4 + 650\text{R}_2\)
(b)
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(r\)
\(\tfrac{2}{3}\)
\(-1\tfrac{2}{3}\)
\(0\)
\(1\)
\(0\)
\(\tfrac{-10}{3}\)
\(-60\)
\(\text{R}_1 - 10\text{R}_3\)
\(s\)
\(\tfrac{2}{3}\)
\(-1\tfrac{2}{3}\)
\(0\)
\(0\)
\(1\)
\(\tfrac{-4}{3}\)
\(-20\)
\(\text{R}_2 - 4\text{R}_3\)
\(z\)
\(\boxed{\tfrac{1}{3}}\)
\(\tfrac{2}{3}\)
\(1\)
\(0\)
\(0\)
\(\tfrac{1}{3}\)
\(20\)
\(\text{R}_3 \div 3\)
\(p\)
\(-133\tfrac{1}{3}\)
\(83\tfrac{1}{3}\)
\(0\)
\(0\)
\(0\)
\(216\tfrac{2}{3}\)
\(13000\)
\(\text{R}_4 + 650\text{R}_3\)
2. MISREADS – use col \(x\) or col \(y\) (–2 A marks if earned)
(a)
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(r\)
\(0\)
\(\boxed{3}\)
\(2\)
\(1\)
\(-2\)
\(0\)
\(20\)
\(\text{R}_1 - 4\text{R}_2\)
\(x\)
\(1\)
\(\tfrac{1}{2}\)
\(2\)
\(0\)
\(\tfrac{1}{2}\)
\(0\)
\(30\)
\(\text{R}_2 \div 2\)
\(t\)
\(0\)
\(1\tfrac{1}{2}\)
\(1\)
\(0\)
\(-\tfrac{1}{2}\)
\(1\)
\(30\)
\(\text{R}_3 - \text{R}_2\)
\(p\)
\(0\)
\(-175\)
\(50\)
\(0\)
\(175\)
\(0\)
\(10500\)
\(\text{R}_4 + 350\text{R}_2\)
(b)
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(y\)
\(\tfrac{4}{5}\)
\(1\)
\(2\)
\(\tfrac{1}{5}\)
\(0\)
\(0\)
\(28\)
\(\text{R}_1 - 5\)
\(s\)
\(\boxed{1\tfrac{1}{5}}\)
\(0\)
\(2\)
\(-\tfrac{1}{5}\)
\(1\)
\(0\)
\(32\)
\(\text{R}_2 - \text{R}_1\)
\(t\)
\(-\tfrac{3}{5}\)
\(0\)
\(-1\)
\(-\tfrac{2}{5}\)
\(0\)
\(1\)
\(4\)
\(\text{R}_3 - 2\text{R}_1\)
\(p\)
\(-70\)
\(0\)
\(50\)
\(70\)
\(0\)
\(0\)
\(9800\)
\(\text{R}_4 + 350\text{R}_2\)
Mark scheme (c)
Scheme
Marks
\(x = 0\quad y = 0\quad z = 14\quad r = 0\quad s = 4\quad t = 18\quad p =\) £91
M1 A2ft, 1ft, 0
(3)
Notes
M1 3 variables stated – must have completed b.v. + value columns on tableau. Any negatives M0
A1ft all 7 c.a.o. Need £91 ft but accept 9100
A1ft at least 4 c.a.o. (condone \(P = 9100\)ft)
Mark scheme (d)
Scheme
Marks
\(p - 90x - 25y + 65r = 9100\) (o.e.)
M1 A1ft
(2)
Notes
M1ft \(P\), \((-)90x\), \((-)25y\), \(65r\) and 9100 (or 91) all present and one = sign
A1ft c.a.o. (o.e.)
(Corrected from the printed mark scheme: the \(y\) term is printed garbled as “\(-2\sqrt{y}\)”; it is \(-25y\), as in the notes and part (e).)
Mark scheme (e)
Scheme
Marks
\(p = 9100 + 90x + 25y - 65r\) So increasing \(x\) or \(y\) would increase the profit
B1ft
(1)
Notes
B1ft stating that increasing \(x\) or \(y\) would increase profit, probably re-arranging profit equation. Generous.
(The printed mark scheme shows a part total of 3 here; the part is worth 1 mark.)
Mark scheme (f)
Scheme
Marks
The \(\dfrac{2}{5}\) in the \(x\) column and 2nd (\(s\)) row.
B2ft, 1ft, 0
(2)
(15 marks)
Notes
B2ft \(\dfrac{2}{5}\) identified, \(x\) column and 2nd (\(s\)) row.
Accept ringed in last tableau
B1ft “bad” gets B1, if ft their “optional” tableau B1.
7. Polly has a bird food stall at the local market. Each week she makes and sells three types of packs A, B and C.
Pack A contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts. Pack B contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts. Pack C contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts.
Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs.
The profit made on each pack of A, B and C sold is £3.50, £3.50 and £6.50 respectively. Polly sells every pack on her stall and wishes to maximise her profit, \(P\) pence.
Let \(x\), \(y\) and \(z\) be the numbers of packs A, B and C sold each week.
An initial Simplex tableau for the above situation is
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
4
5
10
1
0
0
140
\(s\)
2
1
4
0
1
0
60
\(t\)
1
2
3
0
0
1
60
\(P\)
\(-350\)
\(-350\)
\(-650\)
0
0
0
0
(a) Explain the meaning of the variables \(r\), \(s\) and \(t\) in the context of this question. (2)
(b) Perform one complete iteration of the Simplex algorithm to form a new tableau \(T\). Take the most negative number in the profit row to indicate the pivotal column. (5)
(c) State the value of every variable as given by tableau \(T\). (3)
(d) Write down the profit equation given by tableau \(T\). (2)
(e) Use your profit equation to explain why tableau \(T\) is not optimal. (1)
Taking the most negative number in the profit row to indicate the pivotal column,
(f) identify clearly the location of the next pivotal element. (2)
Mark scheme (a)
Scheme
Marks
\(r\), \(s\) and \(t\) are unused amounts of bird seed (in kg), suet blocks and peanuts (in kg) that Polly has at the end of each week after she has made up and sold her packs.
B2,1,0
(2)
Mark scheme (b)
Scheme
Marks
b.v.
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
value
\(z\)
\(\tfrac{2}{5}\)
\(\tfrac{1}{2}\)
1
\(\tfrac{1}{10}\)
0
0
14
\(R_1 \div 10\)
\(s\)
\(\tfrac{2}{5}\) (circled)
\(-1\)
0
\(-\tfrac{2}{5}\)
1
0
4
\(R_2 - 4R_1\)
\(t\)
\(-\tfrac{1}{5}\)
\(\tfrac{1}{2}\)
0
\(-\tfrac{3}{10}\)
0
1
18
\(R_3 - 3R_1\)
\(P\)
\(-90\)
\(-25\)
0
65
0
0
9100
\(R_4 + 650R_1\)
M1 A1 M1 A2ft,1ft,0
(5)
Mark scheme (c)
Scheme
Marks
\(x = 0\quad y = 0\quad z = 14\quad r = 0\quad s = 4\quad t = 18\quad P =\) £91
M1 A2ft,1ft,0
(3)
Mark scheme (d)
Scheme
Marks
\(P - 90x - 25y + 65r = 9100\) (o.e.)
M1 A1ft
Notes
Parts (d) and (e) are marked together: (3) in total.
Mark scheme (e)
Scheme
Marks
\(P = 9100 + 90x + 25y - 65r\) So increasing \(x\) or \(y\) would increase the profit
B1ft
(3)
Notes
The B1ft depends on the M1 in (d). The (3) covers parts (d) and (e).
Mark scheme (f)
Scheme
Marks
The \(\tfrac{2}{5}\) in the \(x\) column and 2nd (\(s\)) row.
7. Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool.
For each roll of carpet, the Lincoln requires 1 unit of black, 1 of green and 3 of red, the Norfolk requires 1 unit of black, 2 of green and 2 of red, and the Suffolk requires 2 units of black, 1 of green and 1 of red.
There are up to 30 units of black, 40 units of green and 50 units of red available each day. Profits of £50, £80 and £60 are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit.
Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x\), \(y\) and \(z\) respectively.
(a) Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. (4)
This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.
(b) Stating your row operations, show that after one complete iteration the tableau becomes
Basic variable
\(x\)
\(y\)
\(z\)
\(r\)
\(s\)
\(t\)
Value
\(r\)
\(\tfrac{1}{2}\)
0
\(1\tfrac{1}{2}\)
1
\(-\tfrac{1}{2}\)
0
10
\(y\)
\(\tfrac{1}{2}\)
1
\(\tfrac{1}{2}\)
0
\(\tfrac{1}{2}\)
0
20
\(t\)
2
0
0
0
\(-1\)
1
10
\(P\)
\(-10\)
0
\(-20\)
0
40
0
1600
(4)
(c) Explain the practical meaning of the value 10 in the top row. (2)
(d)
(i) Perform one further complete iteration of the Simplex algorithm.
(ii) State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
(iii) Interpret your current tableau, giving the value of each variable. (8)
Mark scheme (a)
Scheme
Marks
maximise \(P = 50x + 80y + 60z\)
B1
subject to \(\quad x + y + 2z \leqslant 30\) \(\phantom{\text{subject to}\quad} x + 2y + z \leqslant 40\) \(\phantom{\text{subject to}\quad} 3x + 2y + z \leqslant 50\)