D2 June 2017 Q5

EdexcelOld spec13 marksLinear Programming

5. The tableau below is the initial tableau for a three-variable linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	15	–2	3	1	0	0	180
\(s\)	10	1	1	0	1	0	80
\(t\)	1	6	–2	0	0	1	100
\(P\)	–1	–2	–5	0	0	0	0

(a) Using the information in the tableau, write down

(i) the objective function,

(ii) the three constraints as inequalities.

(3)

(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use. (8)

Mark scheme (a)

Scheme	Marks
(i) \(P = x + 2y + 5z\)	B1
(ii) \(15x - 2y + 3z \leqslant 180\) \(10x + y + z \leqslant 80\) \(x + 6y - 2z \leqslant 100\)	M1 A1
	(3)

Notes

ai1B1: CAO - allow in any equivalent form e.g. \(P - x - 2y - 5z = 0\) but not say \(P = x + 2y + 5z = 0\)

aii1M1: Two inequalities (or equations with slack variables) correct

aii1A1: CAO

Mark scheme (b)

Scheme

Marks

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value
\(r\)	15	-2	3	1	0	0	180
\(s\)	10	1	1	0	1	0	80
\(t\)	1	6	-2	0	0	1	100
\(P\)	-1	-2	-5	0	0	0	0

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	row ops
\(z\)	5	\(-\frac{2}{3}\)	1	\(\frac{1}{3}\)	0	0	60	\(R_1 \div 3\)
\(s\)	5	\(\boldsymbol{\frac{5}{3}}\)	0	\(-\frac{1}{3}\)	1	0	20	\(R_2 - R_1\)
\(t\)	11	\(\frac{14}{3}\)	0	\(\frac{2}{3}\)	0	1	220	\(R_3 + 2R_1\)
\(P\)	24	\(-\frac{16}{3}\)	0	\(\frac{5}{3}\)	0	0	300	\(R_4 + 5R_1\)

M1 A1
M1 A1

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	row ops
\(z\)	7	0	1	\(\frac{1}{5}\)	\(\frac{2}{5}\)	0	68	\(R_1 + \frac{2}{3}R_2\)
\(y\)	3	1	0	\(-\frac{1}{5}\)	\(\frac{3}{5}\)	0	12	\(R_2 \div \frac{5}{3}\)
\(t\)	-3	0	0	\(\frac{8}{5}\)	\(-\frac{14}{5}\)	1	164	\(R_3 - \frac{14}{3}R_2\)
\(P\)	40	0	0	\(\frac{3}{5}\)	\(\frac{16}{5}\)	0	364	\(R_4 + \frac{16}{3}R_2\)

M1 A1ft
M1 A1

(8)

Notes

b1M1: Correct pivot located (3 in the \(z\) column), attempt to divide row. If choosing negative pivot then M0M0

b1A1: CAO pivot row correct including change of b.v. (so \(r\) must be changed to \(z\))

b2M1: (ft) All values in one of the non-pivot rows correct or one of the non zero/one columns (\(x\), \(y\), \(r\) or value) correct following through their choice of pivot

b2A1: CAO on all values for the first iteration – ignore row ops and b.v. column for this mark

b3M1: Their correct pivot located following their first iteration, attempt to divide row. If choosing negative pivot M0M0 - however, allow recovery for the third and fourth M marks only if positive pivot chosen for the second iteration after a negative pivot chosen for the first iteration

b3A1ft: Their pivot row correct including change of b.v. following their first iteration

b4M1: (ft) All values in one of the non-pivot rows correct or one of the non zero/one columns (\(x\), \(r\), \(s\) or value) correct following through their choice of pivot

b4A1: CAO for all values and row operations for both iterations - including all eight row operations stated correctly (ignore b.v. column for this mark)

If pivoting on any other positive value for the first iteration then candidates can score in (b) and (c):

(b) M0A0M1A0 M1A1M0A0 (c) M1A0 (so max. of 4/10)

Mark scheme (c)

Scheme	Marks
\(P = 364;\ x = 0;\ y = 12;\ z = 68;\ r = s = 0;\ t = 164\)	M1 A1
	(2)
	13 marks

Notes

c1M1: Their correct values stated for at least \(P\), \(x\), \(y\), \(z\) from their ‘optimal’ iteration so there must be no negatives in the profit row. Two M marks in (b) must have been awarded – the numerical value of \(P\) must be explicitly stated and not as part of an equation

c1A1: CAO for all seven values explicitly stated