A2 June 2019 Q6

EdexcelCurrent spec12 marksLinear Programming

6. A linear programming problem in \(x\), \(y\) and \(z\) is described as follows.

Maximise	\(P = 2x + 2y - z\)
subject to	\(\begin{aligned} 3x + y + 2z &\leqslant 30 \\ x - y + z &\geqslant 8 \\ 4y + 2z &\geqslant 15 \\ x, y, z &\geqslant 0 \end{aligned}\)

(a) Explain why the Simplex algorithm cannot be used to solve this linear programming problem. (1)

(b) Set up the initial tableau for solving this linear programming problem using the big-M method. (7)

After a first iteration of the big-M method, the tableau is

b.v.	\(x\)	\(y\)	\(z\)	\(s_1\)	\(s_2\)	\(s_3\)	\(a_1\)	\(a_2\)	Value
\(s_1\)	3	0	1.5	1	0	0.25	0	\(-0.25\)	26.25
\(a_1\)	1	0	1.5	0	\(-1\)	\(-0.25\)	1	0.25	11.75
\(y\)	0	1	0.5	0	0	\(-0.25\)	0	0.25	3.75
\(P\)	\(-(2 + M)\)	0	\(2 - 1.5M\)	0	\(M\)	\(-0.5 + 0.25M\)	0	\(0.5 + 0.75M\)	\(7.5 - 11.75M\)

(d) Explain why the solution given by the first iteration is not feasible. (1)

Taking the most negative entry in the profit row to indicate the pivot column,

(e) obtain the most efficient pivot for a second iteration. You must give reasons for your answer. (2)

Mark scheme (a)

Scheme	Marks	AO
Simplex can only be applied when the non-negativity constraints are \(\leqslant\)	B1	3.5b
	(1)

Notes

(a) B1: CAO – e.g. not all of the constraints are \(\leqslant\), the origin is not a (basic feasible) solution of the LP

Mark scheme (b)

Scheme

Marks

\(3x + y + 2z \leqslant 30 \Rightarrow 3x + y + 2z + s_1 = 30\)

1.1b

\(x - y + z \geqslant 8 \Rightarrow x - y + z - s_2 + a_1 = 8\)

2.5

\(4y + 2z \geqslant 15 \Rightarrow 4y + 2z - s_3 + a_2 = 15\)

1.1b

\(P = 2x + 2y - z \Rightarrow P = 2x + 2y - z - M(a_1 + a_2)\) together with
\(a_1 + a_2 = 23 - x - 3y - 3z + s_2 + s_3\)

2.1

\(P - (2 + M)x - (2 + 3M)y - (-1 + 3M)z + Ms_2 + Ms_3 = -23M\)

1.1b

b.v	\(x\)	\(y\)	\(z\)	\(s_1\)	\(s_2\)	\(s_3\)	\(a_1\)	\(a_2\)	Value
\(s_1\)	3	1	2	1	0	0	0	0	30
\(a_1\)	1	\(-1\)	1	0	\(-1\)	0	1	0	8
\(a_2\)	0	4	2	0	0	\(-1\)	0	1	15
\(P\)	\(-(2 + M)\)	\(-(2 + 3M)\)	\(-(3M - 1)\)	0	\(M\)	\(M\)	0	0	\(-23M\)

M1
A1

3.3
2.2a

(7)

Notes

(b) B1: CAO \(3x + y + 2z + s_1 = 30\) (may be seen in the simplex tableau – allow any \(s_i\) (or \(s\)) for \(s_1\))

B1: CAO \(x - y + z - s_2 + a_1 = 8\) (may be seen in the simplex tableau – allow any consistent \(s_i\) for \(s_2\) (or \(t\) say) but not the same \(s_i\) as in the previous mark and allow any \(a_i\) for \(a_1\))

B1: CAO \(4y + 2z - s_3 + a_2 = 15\) (may be seen in the simplex tableau – same conditions as above)

M1: setting up the new objective which must be \(P = 2x + 2y - z - M(a_1 + a_2)\) and substituting for their \(a_1\) and \(a_2\) (if no working then the correct objective line in the tableau implies this mark)

A1: CAO \(P - (2 + M)x - (2 + 3M)y - (-1 + 3M)z + Ms_2 + Ms_3 = -23M\) (any equivalent form – need not be factorised and does not need to be re-arranged into this form - if no working then the correct objective line in the tableau implies this mark)

M1: setting up initial tableau – all four rows complete with two correct rows (but ignore b.v. column for this mark)

A1: CAO (any equivalent correct form)

Mark scheme (c)

Scheme	Marks	AO
\(s_1 = 26.25,\ a_1 = 11.75,\ y = 3.75,\ x = z = s_2 = s_3 = a_2 = 0\)	B1	3.4
	(1)

Notes

(c) B1: CAO \(s_1 = 26.25,\ a_1 = 11.75,\ y = 3.75,\ x = z = s_2 = s_3 = a_2 = 0\) (ignore expression for \(P\) if given)

Mark scheme (d)

Scheme	Marks	AO
The solution after the 1^st iteration is not feasible because \(a_1 = 11.75\) is an artificial variable which must be zero in a feasible solution	B1	2.4
	(1)

Notes

(d) B1: correct reasoning of why the solution is not feasible e.g. \(a_1\) is not zero but B0 for just stating that the artificial variable is non-zero (so must see either \(a_1\) or 11.75 being stated as non-zero)

Mark scheme (e)

Scheme	Marks	AO
The most negative value in the objective row is \(2 - 1.5M\) so the pivot is a value from the \(z\)-column	B1	2.4
The 0.5 in the \(y\) row is the pivot because \(\dfrac{3.75}{0.5}\) is less than both \(\dfrac{26.25}{1.5}\) and \(\dfrac{11.75}{1.5}\)	dB1	2.2a
	(2)
	(12 marks)

Notes

(e) B1: correct reasoning of why the pivot comes from a value from the \(z\)-column so must say that the most negative value (in the objective row) is \(2 - 1.5M\) (or this expression clearly implied)

dB1: correct justification of why the 0.5 in the third row is the next pivot (dependent on previous B mark) – so must compare or state that \(\dfrac{3.75}{0.5}\) or 7.5 is less than both \(\dfrac{26.25}{1.5}\) or 17.5 and \(\dfrac{11.75}{1.5}\) or 7.8(3333….) – just stating that the 0.5 in the third row is the next pivot without reasoning is no marks in this part