A2 June 2022 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 = x + ky\), where \(k\) is a positive constant.
The optimal vertex of \(R\) is to be found using the Simplex algorithm.
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\) |
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.
| 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.
| 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
| Scheme | Marks | AO |
|---|---|---|
| \(x = 2,\ y = 5,\ s_1 = 1,\ s_2 = 0,\ s_3 = 22,\ s_4 = 0\) \((P = 5k + 2)\) | B1 | 3.4 |
| (1) |
Notes
(b) B1: cao for \(x\), \(y\), \(s_1, s_2, s_3\) and \(s_4\) only (ignore any mention of \(P\))
| Scheme | Marks | AO | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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
B1: Correct row operations stated
(alternatives row operations are 5r1; r2 + 2r1; r3 – 12r1; r4 – r1; r5 – \((k - 2)\)r1)
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