D2 June 2015 Q1

EdexcelOld spec7 marksLinear Programming

1. 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\)	2	–4	1	1	0	0	15
\(s\)	4	2	–8	0	1	0	20
\(t\)	1	–1	4	0	0	1	8
\(P\)	–3	2	7	0	0	0	0

(a) Perform one iteration of the Simplex algorithm to obtain a new tableau, T. State the row operations you use. (5)

(b) Write down the profit equation given by T and state the current values of the slack variables. (2)

Mark scheme (a)

Scheme

Marks

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row ops
\(r\)	0	\(-5\)	5	1	\(-\frac{1}{2}\)	0	5	\(R_1 - 2R_2\)
\(x\)	1	\(\frac{1}{2}\)	\(-2\)	0	\(\frac{1}{4}\)	0	5	\(R_2 \div 4\)
\(t\)	0	\(-\frac{3}{2}\)	6	0	\(-\frac{1}{4}\)	1	3	\(R_3 - R_2\)
\(P\)	0	\(\frac{7}{2}\)	1	0	\(\frac{3}{4}\)	0	15	\(R_4 + 3R_2\)

M1
A1
M1
A1ft
A1

(5)

Notes

a1M1: Correct pivot located (4 in column \(x\)), attempt to divide row

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

a2M1: All values in one of the non-pivot rows correct or one of the non zero and one columns (\(y\), \(z\), \(s\) or value) correct following through their choice of pivot from column \(x\)

a2A1ft: Row operations used correctly at least twice, i.e. two of the non zero and one columns (\(y\), \(z\), \(s\) or value) correct following through their choice of pivot from column \(x\)

a3A1: CAO – no follow through – all values and row operations correctly stated – allow if row operations given in terms of old row 2 – ignore b.v. column for this mark

Pivoting on the 1 in the \(x\)-column

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(S\)	\(t\)	V
\(r\)	0	−2	−7	1	0	−2	−1
\(s\)	0	6	−24	0	1	−4	−12
\(x\)	1	−1	4	0	0	1	8
\(P\)	0	−1	19	0	0	3	24

Pivoting on the 2 in the \(x\)-column

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	V
\(x\)	1	−2	0.5	0.5	0	0	7.5
\(s\)	0	10	−10	−2	1	0	−10
\(t\)	0	1	3.5	−0.5	0	1	0.5
\(P\)	0	−4	8.5	1.5	0	0	22.5

Mark scheme (b)

Scheme	Marks
\(P + \frac{7}{2}y + z + \frac{3}{4}s = 15\)	B1ft
\(r = 5,\ s = 0,\ t = 3\)	B1
	(2)
	7 marks

Notes

b1B1ft: Follow their profit equation from (a) dependent on scoring both M marks in (a)

b2B1: CAO (no follow through) for slack variables (\(r = 5\), \(s = 0\), \(t = 3\))