D2 June 2018 Q5

EdexcelOld spec17 marksLinear Programming

5. The initial tableau for a linear programming problem in \(x\), \(y\) and \(z\) is shown below. The objective function to be maximised is \(P = 4x + 2y + kz\), where \(k\) is a positive constant.

Basic Variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	−2	−6	1	1	0	0	40
\(s\)	2	3	2	0	1	0	80
\(t\)	1	2	2	0	0	1	50
\(P\)	−4	−2	\(-k\)	0	0	0	0

(a) Using the information in the tableau, write down the three constraints as inequalities. (2)

(b) By increasing \(x\), perform one complete iteration of the simplex algorithm to obtain tableau T1 and state the row operations you use. (4)

(d) Perform a second complete iteration of the simplex algorithm to obtain tableau T2 and state the row operations you use. (4)

(e) Given that T2 is optimal, find a second inequality for the value of \(k\). (2)

(f) State the final value of each variable and give an expression for the final value of \(P\) in terms of \(k\). (2)

(g) Hence find the range of possible values of \(P\). (2)

Mark scheme (a)

Scheme	Marks
\(-2x - 6y + z \leqslant 40\) \(2x + 3y + 2z \leqslant 80\) \(x + 2y + 2z \leqslant 50\)	M1 A1
	(2)

Notes

a1M1: Two correct equations (e.g. \(-2x - 6y + z + r = 40\)) or inequalities

a1A1: CAO (not equations)

Mark scheme (b)

Scheme

Marks

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	row ops
\(r\)	0	–3	3	1	1	0	120	\(R_1 + 2R_2\)
\(x\)	1	3/2	1	0	1/2	0	40	\(0.5R_2\)
\(t\)	0	1/2	1	0	–1/2	1	10	\(R_3 - R_2\)
\(P\)	0	4	\(4-k\)	0	2	0	160	\(R_4 + 4R_2\)

M1 A1
M1 A1

(4)

Notes

b1M1: Correct pivot located (2 in \(x\) column), attempt to divide row. If choosing negative pivot M0M0

b1A1: CAO pivot row correct including change of b.v. (\(s\) must be changed to \(x\))

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

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

Scheme	Marks
\(4 - k \lt 0 \;(\Rightarrow k \gt 4)\)	B1
	(1)

Mark scheme (d)

Scheme

Marks

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	row ops
\(r\)	0	–9/2	0	1	5/2	–3	90	\(R_1 - 3R_3\)
\(x\)	1	1	0	0	1	–1	30	\(R_2 - R_3\)
\(z\)	0	1/2	1	0	–1/2	1	10	\(R_3\)
\(P\)	0	\(2+k/2\)	0	0	\(4-k/2\)	\(-4+k\)	\(120+10k\)	\(R_4 - (4-k)R_3\)

B1 M1
A1 A1

(4)

Notes

d1B1: CAO pivot row correct including change of b.v.

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

d1A1: Row operations used correctly at least twice, i.e. two of the non zero and one columns (\(y\), \(s\), \(t\) or value) correct

d2A1: CAO – both iterations - all values correct and all eight row operations correctly stated – allow if row operations given in terms of old row 2 – ignore b.v. columns for this mark

Mark scheme (e)

Scheme	Marks
\(4 - k/2 \geqslant 0 \;(\Rightarrow k \leqslant 8)\)	M1 A1
	(2)

Notes

e1M1: Setting any of the expressions in terms of \(k\) from the \(P\) row from their second iteration > or \(\geqslant\) 0 - dependent on all M marks in (b) and (d) and both correct pivot rows (but ignore b.v. label)

e1A1: CAO (oe) – need not be simplified but must not be strict inequality – if no working shown and fully correct award both marks, if no working shown and incorrect M0 A0

Mark scheme (f)

Scheme	Marks
\((P =)\, 120 + 10k\)	B1
\(x = 30,\ y = 0,\ z = 10,\ r = 90,\ s = t = 0\)	B1ft
	(2)

Notes

f1B1: CAO

f2B1ft: Follow through their values - dependent on all M marks earned in (b) and (d)