D2 June 2019 Q5

EdexcelOld spec11 marksLinear Programming

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)

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