A2 June 2025 Q5

EdexcelCurrent spec12 marksLinear Programming

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}\)

(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\))

Mark scheme (b)

Scheme	Marks	AO
\(2(X+4) + 2(Y+1) + 2(-Z-3) \leqslant 21 \;\Rightarrow\; 2X + 2Y - 2Z \leqslant 17\)	M1	3.3
\(2(X+4) - (Y+1) - (-Z-3) \leqslant 18 \;\Rightarrow\; 2X - Y + Z \leqslant 8\)	A1	1.1b
\(-3(X+4) + (Y+1) - 2(-Z-3) \leqslant 1 \;\Rightarrow\; -3X + Y + 2Z \leqslant 6\) \(Q + 10 = 3(X+4) + 4(Y+1) + 2(-Z-3) \;\Rightarrow\; Q = 3X + 4Y - 2Z\) \((X \geqslant 0,\ Y \geqslant 0,\ Z \geqslant 0)\)	A1	1.1b
	(3)

Notes

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

Scheme	Marks	AO
\(Q - \frac{5}{4}Z + \frac{15}{8}s_1 + \frac{1}{4}s_3 = \frac{267}{8}\)	B1	3.4
	(1)

Mark scheme (d)

Scheme	Marks	AO
\(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

(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\)