D1 January 2005 Q7

EdexcelOld spec18 marksLinear Programming

7. Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool.

For each roll of carpet,
the Lincoln requires 1 unit of black, 1 of green and 3 of red,
the Norfolk requires 1 unit of black, 2 of green and 2 of red,
and the Suffolk requires 2 units of black, 1 of green and 1 of red.

There are up to 30 units of black, 40 units of green and 50 units of red available each day.
Profits of £50, £80 and £60 are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit.

Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x\), \(y\) and \(z\) respectively.

(a) Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. (4)

This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.

(b) Stating your row operations, show that after one complete iteration the tableau becomes

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	\(\tfrac{1}{2}\)	0	\(1\tfrac{1}{2}\)	1	\(-\tfrac{1}{2}\)	0	10
\(y\)	\(\tfrac{1}{2}\)	1	\(\tfrac{1}{2}\)	0	\(\tfrac{1}{2}\)	0	20
\(t\)	2	0	0	0	\(-1\)	1	10
\(P\)	\(-10\)	0	\(-20\)	0	40	0	1600

(4)

(d)

(i) Perform one further complete iteration of the Simplex algorithm.

(ii) State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.

(iii) Interpret your current tableau, giving the value of each variable. (8)

Mark scheme (a)

Scheme	Marks
maximise \(P = 50x + 80y + 60z\)	B1
subject to \(\quad x + y + 2z \leqslant 30\) \(\phantom{\text{subject to}\quad} x + 2y + z \leqslant 40\) \(\phantom{\text{subject to}\quad} 3x + 2y + z \leqslant 50\)	B3,2,1,0
where \(x, y, z \geqslant 0\)
	(4)

Mark scheme (b)

Scheme

Marks

Initialising tableau

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value
\(r\)	1	1	2	1	0	0	30
\(s\)	1	2 (pivot)	1	0	1	0	40
\(t\)	3	2	1	0	0	1	50
\(P\)	\(-50\)	\(-80\)	\(-60\)	0	0	0	0

B1ft

chooses correct pivot, divides \(R_2\) by 2

M1 A1ft

states correct row operations \(R_1 - R_2,\ R_3 - 2R_2,\ R_4 + 80R_2,\ R_2 \div 2\)

(4)

Scheme	Marks
The solution found after one iteration has a slack of 10 units of black per day	B2,1,0
	(2)

Mark scheme (d)

Scheme

Marks

(i)

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	\(\tfrac{1}{2}\)	0	\(1\tfrac{1}{2}\) (pivot)	1	\(-\tfrac{1}{2}\)	0	10
\(y\)	\(\tfrac{1}{2}\)	1	\(\tfrac{1}{2}\)	0	\(\tfrac{1}{2}\)	0	20
\(t\)	2	0	0	0	\(-1\)	1	10
\(P\)	\(-10\)	0	\(-20\)	0	40	0	1600

(given)

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	value
\(z\)	\(\tfrac{1}{3}\)	0	1	\(\tfrac{2}{3}\)	\(-\tfrac{1}{3}\)	0	\(6\tfrac{2}{3}\)	\(R_1 \div \tfrac{3}{2}\)
\(y\)	\(\tfrac{1}{3}\)	1	0	\(-\tfrac{1}{3}\)	\(\tfrac{2}{3}\)	0	\(16\tfrac{2}{3}\)	\(R_2 - \tfrac{1}{2}R_1\)
\(t\)	2	0	0	0	\(-1\)	1	10	\(R_3\) — no change
\(P\)	\(-3\tfrac{1}{3}\)	0	0	\(13\tfrac{1}{3}\)	\(33\tfrac{1}{3}\)	0	\(1733\tfrac{1}{3}\)	\(R_4 + 20R_1\)

M1 A1
M1 A1 (4)

(ii) Not optimal, a negative value in profit row

B1ft

(iii) \(x = 0\quad y = 16\tfrac{2}{3}\quad z = 6\tfrac{2}{3}\)

M1 A1ft

\(P =\) £1733.33 \(\quad r = 0,\ s = 0,\ t = 10\)

A1ft (4)

(8)

(18 marks)

Notes

The pivot is circled in the scheme (\(\tfrac{3}{2}\) in (i)); it is marked here as (pivot).