A2 June 2022 Q4

EdexcelCurrent spec6 marksLinear Programming

4. A linear programming problem in \(x\), \(y\) and \(z\) is to be solved using the big-M method. The initial tableau is shown below.

b.v.	\(x\)	\(y\)	\(z\)	\(s_1\)	\(s_2\)	\(s_3\)	\(a_1\)	\(a_2\)	Value
\(s_1\)	2	3	4	1	0	0	0	0	13
\(a_1\)	1	\(-2\)	2	0	\(-1\)	0	1	0	8
\(a_2\)	3	0	\(-4\)	0	0	\(-1\)	0	1	12
\(P\)	\(2 - 4M\)	\(-3 + 2M\)	\(-1 + 2M\)	0	\(M\)	\(M\)	0	0	\(-20M\)

(a) Using the information in the above tableau, formulate the linear programming problem. You should

list each of the constraints as an inequality
state the two possible objectives

(4)

(b) Obtain the most efficient pivot for a first iteration of the big-M method. You must give reasons for your answer. (2)

Mark scheme (a)

Scheme	Marks	AO
Constraints: \(2x + 3y + 4z \leqslant 13\) \(x - 2y + 2z \geqslant 8\) \(3x - 4z \geqslant 12\) \((x, y, z \geqslant 0)\)	B1 B1	3.4 2.5
Objective functions: Maximise \(-2x + 3y + z\) Minimise \(2x - 3y - z\)	M1 A1	3.1a 2.2a
	(4)

Notes

(a) B1: One correct non-trivial inequality (allow strict inequality provided direction of inequality sign is correct) – equations with slack variables etc. scores no marks unless replaced with correct inequalities

B1: All three non-trivial inequalities correct

M1: Either expression stated correctly (allow equal to (or an inequality with) any letter e.g. \(P = -2x + 3y + z\) but not equal to a value e.g. = 0) – ignore any mention of maximum/minimum for this mark

A1: Both expressions correct including max/min correctly matched with each expression (allow equal to any letter only) – do not isw if they continue and place their expression(s) equal to a value(s)

Mark scheme (b)

Scheme	Marks	AO
(Because \(M\) is big) the only negative in the objective row is the \(2 - 4M\) so the pivot is from the \(x\)-column	B1	2.4
The 3 in the \(a_2\) row is the pivot as \(\dfrac{12}{3}\) is less than both \(\dfrac{8}{1}\) and \(\dfrac{13}{2}\)	B1	2.2a
	(2)
	(6 marks)

Notes

(b) B1: Correct reasoning that the pivot is a value from the \(x\)-column – as a minimum must state that the \(2 - 4M\) is the only negative (condone most negative) in the objective row (allow profit row or \(P\) row, condone ‘bottom row’)

B1: Correct justification of why the 3 in the \(a_2\) row or the 3 in the \(x\) column is the pivot – so must state the correct pivot in a clear unambiguous way (so just saying the pivot is ‘the 3’ is B0) and comparing or stating that \(\dfrac{12}{3}\) or 4 is less than/least positive for both \(\dfrac{8}{1}\) or 8 and \(\dfrac{13}{2}\) or 6.5 – must see all three values so do check the table for possibly stating the \(\theta\) values there. However, just stating that the 3 is the pivot because it is the smallest \(\theta\) value (without seeing anywhere these \(\theta\) values) is B0