D1 January 2007 Q4

EdexcelOld spec7 marksLinear Programming

4. A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit \(P\). The following initial tableau was obtained.

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value
\(r\)	2	0	4	1	0	80
\(s\)	1	4	2	0	1	160
\(P\)	\(-2\)	\(-8\)	\(-20\)	0	0	0

(a) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm, to obtain tableau \(T\). State the row operations that you use. (5)

(b) Write down the profit equation shown in tableau \(T\). (1)

Mark scheme (a)

Scheme

Marks

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value	Row ops
\(z\)	\(\tfrac{1}{2}\)	0	1	\(\tfrac{1}{4}\)	0	20	\((R_1 \div 4)\)
\(s\)	0	4	0	\(-\tfrac{1}{2}\)	1	120	\(R_2 - 2R_1\)
\(P\)	8	\(-8\)	0	5	0	400	\(R_3 + 20R_1\)

M1 A1
M1 A1ft
A1ft

(5)

Scheme	Marks
\(P + 8x - 8y + 5r = 400\)	B1ft
	(1)

Scheme	Marks
Not optimal since there is a negative number in the profit row	B1ft
	(1)
	(7 marks)