D2 June 2011 Q3

EdexcelOld spec10 marksLinear Programming

3. 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 tableau is obtained.

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	\(-\tfrac{1}{2}\)	0	2	1	\(-\tfrac{1}{2}\)	0	10
\(y\)	\(\tfrac{1}{2}\)	1	\(\tfrac{3}{4}\)	0	\(\tfrac{1}{4}\)	0	5
\(t\)	\(\tfrac{1}{2}\)	0	1	0	\(-\tfrac{1}{4}\)	1	4
\(P\)	−7	0	1	0	4	0	320

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

(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. (5)

Scheme	Marks
\(P - 7x + z + 4s = 320\)	M1 A1
	(2)

Mark scheme (b)

Scheme

Marks

b.v	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	\(-\tfrac{1}{2}\)	0	2	1	\(-\tfrac{1}{2}\)	0	10
\(y\)	\(\tfrac{1}{2}\)	1	\(\tfrac{3}{4}\)	0	\(\tfrac{1}{4}\)	0	5
\(t\)	\(\tfrac{1}{2}\)	0	1	0	\(-\tfrac{1}{4}\)	1	4
\(P\)	−7	0	1	0	4	0	320

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

2M1 2A1ft
1M1 2A1
3A1

(5)

Notes

1M1: correct pivot located, attempt to divide row. If choosing negative pivot M0M0 in (b)

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

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

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

3A1: cao.

Mark scheme (c)

Scheme	Marks
\(P = 376\quad x = 8\quad y = 1\quad z = 0\quad r = 14\quad s = 0\quad t = 0\)	M1 A1ft A1
	(3)
	(10 marks)

Notes

1M1: At least 4 values stated. Reading off bottom row, or negative values get M0.

1A1ft: Their four basic variables correct ft from their table.

2A1: cao