D2 June 2016 Q4

EdexcelOld spec9 marksLinear Programming

4. A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\). The following tableau is obtained after the first iteration.

Basic Variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	0	5	2	1	–3	0	10
\(x\)	1	2	3	0	1	0	18
\(t\)	0	1	–1	0	4	1	3
\(P\)	0	3	–4	0	1	0	7

(a) State which variable was increased first, giving a reason for your answer. (1)

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

(d) State whether T is optimal. You must use your answer to (c) to justify your answer. (2)

Scheme	Marks
e.g. variable \(x\) was increased first, since it has become a basic variable	B1
	(1)

Mark scheme (b)

Scheme

Marks

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	row ops
\(z\)	0	2.5	1	0.5	−1.5	0	5	\(R_1 \div 2\)
\(x\)	1	−5.5	0	−1.5	5.5	0	3	\(R_2 - 3R_1\)
\(t\)	0	3.5	0	0.5	2.5	1	8	\(R_3 + R_1\)
\(P\)	0	13	0	2	−5	0	27	\(R_4 + 4R_1\)

M1 A1
M1
A1ft A1

(5)

Notes

If pivoting on a negative value or on a value from the \(x\) or \(y\) column then no marks in (b), (c) or (d)

b1M1: Correct pivot located (2 in column \(z\)), attempt to divide row

b1A1: Pivot row correct including change of b.v. (so the \(r\) must be replaced with a \(z\))

b2M1: All values in one of the non-pivot rows correct or one of the non zero-and-one columns (\(y\), \(r\), \(s\) or value) correct following through their choice of pivot from column \(z\)

b2A1ft: Row operations used correctly at least twice, i.e. two of the non zero-and-one columns (\(y\), \(r\), \(s\) or value) correct following through their choice of pivot from column \(z\)

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

Pivoting on the 3 in the \(z\) column (can score a maximum of B1 M0A0M1A1A0 B1 B0B0 – so 4/9)

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	−2/3	11/3	0	1	−11/3	0	−2
\(z\)	1/3	2/3	1	0	1/3	0	6
\(t\)	1/3	5/3	0	0	13/3	1	9
\(P\)	4/3	17/3	0	0	7/3	0	31

Mark scheme (c)

Scheme	Marks
\(P + 13y + 2r - 5s = 27\)	B1ft
	(1)

Notes

c1B1ft: Dependent on the second M mark earned in (b) – must be an equation containing \(P\) (please note that \(P = 13y + 2r - 5s + 27\) is incorrect)

Mark scheme (d)

Scheme	Marks
\(P = 27 - 13y - 2r + 5s\), so we can increase the profit by increasing \(s\), hence not optimal	B2,1,0
	(2)
	9 marks

Notes

d1B1: Must have gained both M marks in (b) and must refer to increasing \(y\), \(r\) or \(s\). Do not accept ‘negatives in profit row’ with no further explanation given

d2B1: CAO – dependent on the correct profit equation in (c). Specifically identifies \(s\) as the next variable that could be increased and states ‘not optimal’ (oe)