D2 June 2014 (R) Q4

EdexcelOld spec12 marksLinear Programming

4. 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\)	4	3	\(\frac{5}{2}\)	1	0	0	50
\(s\)	1	2	1	0	1	0	30
\(t\)	0	5	1	0	0	1	80
\(P\)	–25	–40	–35	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 to obtain tableau T. Make your method clear by stating the row operations you use. (9)

(b) Write down the profit equation given by T. (1)

Mark scheme (a)

Scheme

Marks

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	\(\theta\) values
\(r\)	4	3	\(\frac{5}{2}\)	1	0	0	50	16.67
\(s\)	1	2	1	0	1	0	30	15
\(t\)	0	5	1	0	0	1	80	16
\(P\)	−25	−40	−35	0	0	0	0

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	Row ops
\(r\)	\(\frac{5}{2}\)	0	1	1	\(-\frac{3}{2}\)	0	5	R1 − 3R2
\(y\)	\(\frac{1}{2}\)	1	\(\frac{1}{2}\)	0	\(\frac{1}{2}\)	0	15	R2 ÷ 2
\(t\)	\(-\frac{5}{2}\)	0	\(-\frac{3}{2}\)	0	\(-\frac{5}{2}\)	1	5	R3 − 5R2
\(P\)	−5	0	−15	0	20	0	600	R4 + 40R2

M1 A1
B1
M1 A1

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value	Row ops
\(z\)	\(\frac{5}{2}\)	0	1	1	\(-\frac{3}{2}\)	0	5	R1stet
\(y\)	\(-\frac{3}{4}\)	1	0	\(-\frac{1}{2}\)	\(\frac{5}{4}\)	0	12.5	R2 − \(\frac{1}{2}\)R1
\(t\)	\(\frac{5}{4}\)	0	0	\(\frac{3}{2}\)	\(-\frac{19}{4}\)	1	12.5	R3 + \(\frac{3}{2}\)R1
\(P\)	32.5	0	0	15	−2.5	0	675	R4 + 15R1

B1
B1
M1 A1

(9)

Notes

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

a1A1: Pivot row correct including change of b.v.

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

a2M1: (ft) Correct row operations used at least once, column \(x\), \(z\), \(s\) or value correct.

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

a2B1: Correct pivot located and b.v. changed. If choosing negative pivot 2B0 3M0.

a3B1: Row operations CAO.

a3M1: (ft) Correct row operations used at least once, column \(x\), \(r\), \(s\) or value correct.

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

Scheme	Marks
\(P + 32.5x + 15r - 2.5s = 675\)	B1
	(1)

Mark scheme (c)

Scheme	Marks
\(P = 675 - 32.5x - 15r + 2.5s\), so can increase profit by increasing \(s\), hence not optimal.	B2,1,0
	(2)
	12 marks

Notes

c1B1ft: Explanation. Must have gained at least 2 M marks in (a) must refer to increasing \(x\), \(r\) and \(s\), (condone no ref to \(y = z = t = 0\)), must have correct signs in equation in (b). Do not accept ‘negatives in profit row’ o.e. alone.

c2DB1: CAO – dependent on correct equation in (b). Specifically identifies \(s\) as the next variable that could be increased.