D2 June 2010 Q6

EdexcelOld spec13 marksLinear Programming

6. 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\)	0	1	2	1	0	0	24
\(s\)	2	1	4	0	1	0	28
\(t\)	−1	\(\tfrac{1}{2}\)	3	0	0	1	22
\(P\)	−1	−2	−6	0	0	0	0

(a) Write down the profit equation represented in the initial tableau. (1)

(b) 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. (9)

Scheme	Marks
\(P - x - 2y - 6z = 0\)	B1
	(1)

Mark scheme (b)

Scheme

Marks

b.v	x	y	z	r	s	t	Value
r	0	1	2	1	0	0	24
s	2	1	4	0	1	0	28
t	−1	\(\tfrac{1}{2}\)	3	0	0	1	22
P	−1	−2	−6	0	0	0	0

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

M1 A1
M1 A1ft
A1

(5)

b.v.	x	y	z	r	s	t	Value	Row Ops.
y	−2	1	0	2	−1	0	20	\(R_1 \div \tfrac{1}{2}\)
z	1	0	1	\(-\tfrac{1}{2}\)	\(\tfrac{1}{2}\)	0	2	\(R_2 - \tfrac{1}{4}R_1\)
t	−3	0	0	\(\tfrac{1}{2}\)	−1	1	6	\(R_3 + \tfrac{1}{4}R_1\)
P	1	0	0	1	1	0	52	\(R_4 + \tfrac{1}{2}R_1\)

M1 A1ft
M1 A1

(4)

(9)

Notes

Pivots are shown in bold (highlighted in the printed scheme).

1M1: correct pivot located, attempt to divide row

1A1: pivot row correct including change of b.v.

2M1: (ft) Correct row operations used at least once or stated correctly.

1A1ft: Looking at non zero-and-one columns, one column ft correct

2A1: cao.

3M1: (ft)Correct pivot identified – negative pivot gets M0 M0

1A1: ft pivot row correct including change of bv – but don’t penalise b.v. twice.

4M1: (ft) Correct row operations used at least once or stated correctly.

1A1: cao

Mark scheme (c)

Scheme	Marks
\(P = 52\quad x = 0\quad y = 20\quad z = 2\quad r = 0\quad s = 0\quad t = 6\)	M1 A1ft A1
	(3)
	(13 marks)

Notes

1M1: At least 4 values stated. No negative. Reading off bottom row gets M0.

1A1ft: At least 4 values correct.

2A1: cao