D2 June 2008 Q8

EdexcelOld spec10 marksLinear Programming

8. The tableau below is the initial tableau for a maximising linear programming problem in \(x\), \(y\) and \(z\).

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	4	\(\dfrac{7}{3}\)	\(\dfrac{5}{2}\)	1	0	0	64
\(s\)	1	3	0	0	1	0	16
\(t\)	4	2	2	0	0	1	60
\(P\)	−5	\(-\dfrac{7}{2}\)	−4	0	0	0	0

(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use. (9)

(b) Explain how you know that your solution is not optimal. (1)

Mark scheme (a)

Scheme

Marks

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	\(4\)	\(\tfrac{7}{3}\)	\(\tfrac{5}{2}\)	\(1\)	\(0\)	\(0\)	\(64\)
\(s\)	\(1\)	\(3\)	\(0\)	\(0\)	\(1\)	\(0\)	\(16\)
\(t\)	\(\boxed{4}\)	\(2\)	\(2\)	\(0\)	\(0\)	\(1\)	\(60\)
\(P\)	\(-5\)	\(-\tfrac{7}{2}\)	\(-4\)	\(0\)	\(0\)	\(0\)	\(0\)

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row ops
\(r\)	\(0\)	\(\tfrac{1}{3}\)	\(\boxed{\tfrac{1}{2}}\)	\(1\)	\(0\)	\(-1\)	\(4\)	\(\text{R}_1 - 4\text{R}_3\)
\(s\)	\(0\)	\(\tfrac{5}{2}\)	\(-\tfrac{1}{2}\)	\(0\)	\(1\)	\(-\tfrac{1}{4}\)	\(1\)	\(\text{R}_2 - \text{R}_3\)
\(x\)	\(1\)	\(\tfrac{1}{2}\)	\(\tfrac{1}{2}\)	\(0\)	\(0\)	\(\tfrac{1}{4}\)	\(15\)	\(\text{R}_3 \div 4\)
\(P\)	\(0\)	\(-1\)	\(-\tfrac{3}{2}\)	\(0\)	\(0\)	\(\tfrac{5}{4}\)	\(75\)	\(\text{R}_4 + 5\text{R}_3\)

M1 A1
M1 A1ft A1

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row ops
\(z\)	\(0\)	\(\tfrac{2}{3}\)	\(1\)	\(2\)	\(0\)	\(-2\)	\(8\)	\(\text{R}_1 \div \tfrac{1}{2}\)
\(s\)	\(0\)	\(\tfrac{17}{6}\)	\(0\)	\(1\)	\(1\)	\(-\tfrac{5}{4}\)	\(5\)	\(\text{R}_2 + \tfrac{1}{2}\text{R}_1\)
\(x\)	\(1\)	\(\tfrac{1}{6}\)	\(0\)	\(-1\)	\(0\)	\(\tfrac{5}{4}\)	\(11\)	\(\text{R}_3 - \tfrac{1}{2}\text{R}_1\)
\(P\)	\(0\)	\(0\)	\(0\)	\(3\)	\(0\)	\(-\tfrac{7}{4}\)	\(87\)	\(\text{R}_4 + \tfrac{3}{2}\text{R}_1\)

M1 A1ft
M1 A1

(9)

Notes

Pivots are boxed (shaded in the scheme).

Scheme	Marks
There is still negative numbers in the profit row.	B1
	(1)
	(10 marks)