D2 June 2014 Q3

EdexcelOld spec12 marksLinear Programming

3. The tableau below is the initial tableau for a three-variable 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\)	5	3	\(-\frac{1}{2}\)	1	0	0	2500
\(s\)	3	2	1	0	1	0	1650
\(t\)	\(\frac{1}{2}\)	–1	2	0	0	1	800
\(P\)	–40	–50	–35	0	0	0	0

(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use. (10)

(b) State the final values of the objective function and each variable. (2)

Mark scheme (a)

Scheme

Marks

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	\(\theta\) values
\(r\)	5	3	\(-\frac{1}{2}\)	1	0	0	2500	833.3
\(s\)	3	2	1	0	1	0	1650	825
\(t\)	\(\frac{1}{2}\)	−1	2	0	0	1	800	n/a
\(P\)	−40	−50	−35	0	0	0	0

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	Row ops
\(r\)	\(\frac{1}{2}\)	0	−2	1	\(-\frac{3}{2}\)	0	25	R1 − 3R2
\(y\)	\(\frac{3}{2}\)	1	\(\frac{1}{2}\)	0	\(\frac{1}{2}\)	0	825	R2 ÷ 2
\(t\)	2	0	\(\frac{5}{2}\)	0	\(\frac{1}{2}\)	1	1625	R3 + R2
\(P\)	35	0	−10	0	25	0	41250	R4 + 50R2

M1 A1
B1
M1 A1
(5)

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	Row ops
\(r\)	\(\frac{21}{10}\)	0	0	1	\(-\frac{11}{10}\)	\(\frac{4}{5}\)	1325	R1 + 2R3
\(y\)	\(\frac{11}{10}\)	1	0	0	\(\frac{2}{5}\)	\(-\frac{1}{5}\)	500	R2 − \(\frac{1}{2}\)R3
\(z\)	\(\frac{4}{5}\)	0	1	0	\(\frac{1}{5}\)	\(\frac{2}{5}\)	650	R3 ÷ \(\frac{5}{2}\)
\(P\)	43	0	0	0	27	4	47750	R4 + 10R3

M1 A1ft
B1
M1 A1
(5)

Notes

a1M1: Correct pivot located, attempt to divide row. If choosing negative pivot no marks.

a1A1: CAO pivot row correct including change of b.v.

a1B1: All row operations CAO – allow if given in terms of old row 2.

a2M1: (ft) The correct row operations used correctly at least once from their pivot, column \(x\), \(z\), \(s\) or value ‘correct’.

a2A1: CAO on numbers (ignore row operations and b.v.)

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

a3A1ft: Pivot row correct on follow through including change of b.v.

a2B1: All row operations CAO – allow if given in terms of old row 3.

a4M1: (ft) The correct row operations used correctly at least once from their pivot, column \(x\), \(s\), \(t\) or value ‘correct’.

a4A1: CAO on numbers (ignore row operations and b.v.)

Mark scheme (b)

Scheme	Marks
\(P = 47750\quad x = 0\quad y = 500\quad z = 650\quad r = 1325\quad s = t = 0\)	B1ft B1
	(2)
	12 marks

Notes

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

Allow implicit stating of \(P\) e.g. \(P + 43x + 27s + 4t = 47750\) with \(x, s, t = 0\).

b2B1: CAO For all 7 variables correct and given explicitly.