A2 June 2025 Q7
7.
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.
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\) |
| Scheme | Marks | AO | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(3x + 4y \leqslant 20 \Rightarrow 3x + 4y + s_1 = 20\) \(3x + y \leqslant 8 \Rightarrow 3x + y + s_4 = 8\) | B1 | 2.5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| \(x \geqslant 1 \Rightarrow x - s_2 + a_1 = 1\) | B1 | 2.5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| \(2x + 3y \geqslant 6 \Rightarrow 2x + 3y - s_3 + a_2 = 6\) | B1 | 1.1b | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| \(P = 11x + ky - M(a_1 + a_2)\) \(a_1 + a_2 = 7 - 3x - 3y + s_2 + s_3\) \(P = 11x + ky - M(7 - 3x - 3y + s_2 + s_3)\) | M1 | 2.1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| \(P - (11 + 3M)x - (k + 3M)y + Ms_2 + Ms_3 = -7M\) | A1 | 2.2a | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
e.g.
| M1 A1 | 3.3 2.2a | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (7) |
Notes
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
| 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\))