D2 June 2013 Q5

EdexcelOld spec11 marksLinear Programming

5. In solving a three-variable maximising linear programming problem, the following tableau was obtained after the first iteration.

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	−1	2	0	1	0	1	8
\(s\)	−1	3	0	0	1	1	22
\(z\)	−2	1	1	0	0	1	11
\(P\)	2	−5	0	0	0	\(\tfrac{1}{2}\)	15

(a) State which variable was increased first, giving a reason for your answer. (1)

(b) Solve this linear programming problem. Make your method clear by stating the row operations you use. (8)

Scheme	Marks
Variable \(z\) was increased first, since it has become a basic variable.	B1
	(1)

Mark scheme (b)

Scheme

Marks

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value
\(r\)	−1	2	0	1	0	1	8
\(s\)	−1	3	0	0	1	1	22
\(z\)	−2	1	1	0	0	1	11
\(P\)	2	−5	0	0	0	\(\tfrac{1}{2}\)	15

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	row ops
\(y\)	\(-\tfrac{1}{2}\)	1	0	\(\tfrac{1}{2}\)	0	\(\tfrac{1}{2}\)	4	\(R_1 \div 2\)
\(s\)	\(\tfrac{1}{2}\)	0	0	\(-\tfrac{3}{2}\)	1	\(-\tfrac{1}{2}\)	10	\(R_2 - 3R_1\)
\(z\)	\(-\tfrac{3}{2}\)	0	1	\(-\tfrac{1}{2}\)	0	\(\tfrac{1}{2}\)	7	\(R_3 - R_1\)
\(P\)	\(-\tfrac{1}{2}\)	0	0	\(\tfrac{5}{2}\)	0	3	35	\(R_4 + 5R_1\)

1M1 A1
2M1 A1

(4)

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	row ops
\(y\)	0	1	0	−1	1	0	14	\(R_1 + \tfrac{1}{2}R_2\)
\(x\)	1	0	0	−3	2	−1	20	\(R_2 \div \tfrac{1}{2}\)
\(z\)	0	0	1	−5	3	−1	37	\(R_3 + \tfrac{3}{2}R_2\)
\(P\)	0	0	0	1	1	\(\tfrac{5}{2}\)	45	\(R_4 + \tfrac{1}{2}R_2\)

3M1 A1ft
4M1 A1

(4)

(8)

Notes

The pivot is boxed in the printed scheme (shown in bold).

b1M1 Correct pivot located, attempt to divide row. If choosing negative pivot M0M0.

b1A1 CAO pivot row correct including change of b.v.

b2M1 (ft) Correct row operations used at least once, column \(x\), \(r\), \(t\) or value correct.

b2A1 CAO including row operations

b3M1 Their correct pivot located, attempt to divide row. If choosing negative pivot M0M0.

b3A1ft pivot row correct including change of b.v.

b4M1 (ft) Correct row operations used at least once, column \(r\), \(s\), \(t\) or value correct.

b4A1 CAO

Mark scheme (c)

Scheme	Marks
\(P = 45;\ x = 20;\ y = 14;\ z = 37;\ r = s = t = 0.\)	M1 A1
	(2)
	(11 marks)

Notes

c1M1 Their correct values stated for at least \(P\), \(x\), \(y\), \(z\) from their ‘optimal’ iteration. No negatives. Two M marks in part (b) must have been awarded

c1A1 CAO for all 7 values.