A2 June 2024 Q7

EdexcelCurrent spec14 marksLinear Programming

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

\(x\)-row: \(4x + y - z \leqslant 40\) or \(s_3\)- row: \(y + z \leqslant 26\)

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

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

1.1b

For either \(P - 3x - y - 2z = 0\) or \(2x + z + s_1 = 50\)

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

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

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