D1 June 2007 Q7

EdexcelOld spec18 marksLinear Programming

7. 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)

One of the constraints is not at capacity.

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

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

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations
\(r\)	6	0	3	1	\(-\dfrac{2}{3}\)	0	144	\(R_1 - 4R_2\)
\(y\)	\(\dfrac{3}{2}\)	1	\(\dfrac{1}{2}\)	0	\(\dfrac{1}{6}\)	0	25.5	\(R_2 \div 6\)
\(t\)	2	0	−3	0	\(-\dfrac{1}{3}\)	1	120	\(R_3 - 2R_2\)
\(P\)	4	0	−1	0	\(\dfrac{2}{3}\)	0	102	\(R_4 + 4R_2\)

M1 A1
M1 A1ft
B1ft

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations
\(z\)	2	0	1	\(\dfrac{1}{3}\)	\(-\dfrac{2}{9}\)	0	48	\(R_1 \div 3\)
\(y\)	\(\dfrac{1}{2}\)	1	0	\(-\dfrac{1}{6}\)	\(\dfrac{5}{18}\)	0	1.5	\(R_2 - \tfrac{1}{2}R_1\)
\(t\)	8	0	0	1	−1	1	264	\(R_3 + 3R_1\)
\(P\)	6	0	0	\(\dfrac{1}{3}\)	\(\dfrac{4}{9}\)	0	150	\(R_4 + R_1\)

M1 A1
M1 A1

(9)

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

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