D2 June 2007 Q8

EdexcelOld spec18 marksLinear Programming

8. The tableau below is the initial tableau for a 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\)	12	4	5	1	0	0	246
\(s\)	9	6	3	0	1	0	153
\(t\)	5	2	−2	0	0	1	171
\(P\)	−2	−4	−3	0	0	0	0

Using the information in the tableau, write down

(a) the objective function, (2)

(b) the three constraints as inequalities with integer coefficients. (3)

Taking the most negative number in the profit row to indicate the pivot column at each stage,

(d) State the final values of the objective function and each variable. (3)

(e) One of the constraints is not at capacity. Explain how it can be identified. (1)

Scheme	Marks
\(P - 2x - 4y - 3z = 0\) (o.e.)	B2, 0
	(2)

Scheme	Marks
\(12x + 4y + 5z \leqslant 246\)	B1
\(9x + 6y + 3z \leqslant 153\)	B1
\(5x + 2y - 2z \leqslant 171\)	B1
	(3)

Mark scheme (c)

Scheme

Marks

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	\(12\)	\(4\)	\(5\)	\(1\)	\(0\)	\(0\)	\(246\)
\(s\)	\(9\)	\(\boxed{6}\)	\(3\)	\(0\)	\(1\)	\(0\)	\(153\)
\(t\)	\(5\)	\(2\)	\(-2\)	\(0\)	\(0\)	\(1\)	\(171\)
\(P\)	\(-2\)	\(-4\)	\(-3\)	\(0\)	\(0\)	\(0\)	\(0\)

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

M1 A1
M1 A1ft
B1ft

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row ops
\(z\)	\(2\)	\(0\)	\(1\)	\(\tfrac{1}{3}\)	\(-\tfrac{2}{9}\)	\(0\)	\(48\)	\(\text{R}_1 \div 3\)
\(y\)	\(\tfrac{1}{2}\)	\(1\)	\(0\)	\(-\tfrac{1}{6}\)	\(\tfrac{5}{18}\)	\(0\)	\(1.5\)	\(\text{R}_2 - \tfrac{1}{2}\text{R}_1\)
\(t\)	\(8\)	\(0\)	\(0\)	\(1\)	\(-1\)	\(1\)	\(264\)	\(\text{R}_3 + 3\text{R}_1\)
\(P\)	\(6\)	\(0\)	\(0\)	\(\tfrac{1}{3}\)	\(\tfrac{4}{9}\)	\(0\)	\(150\)	\(\text{R}_4 + \text{R}_1\)

M1 A1
M1 A1

(9)

Notes

Pivots are boxed (ringed in the scheme).

Scheme	Marks
\(P = 150\quad x = 0\quad y = 1.5\quad z = 48\)	M1 A1ft
\(r = 0\quad s = 0\quad t = 264\)	A1ft
	(3)

Scheme	Marks
(The third constraint) \(t \neq 0\)	B1ft
	(1)
	(18 marks)