A2 October 2021 Q8

EdexcelCurrent spec18 marksLinear Programming

8. Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running.

Susie decides that in her training next week she should

maximise the total time spent cycling and running
train for at most 39 hours
spend at least 40% of her time swimming
spend a total of at least 28 hours of her time swimming and running

Susie needs to determine how long she should spend next week training for each activity. Let

\(x\) represent the number of hours swimming
\(y\) represent the number of hours cycling
\(z\) represent the number of hours running

(a) Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. (5)

Susie decides to solve this linear programming problem by using the two-stage Simplex method.

(b) Set up an initial tableau for solving this problem using the two-stage Simplex method.
As part of your solution you must show how

the constraints have been made into equations using slack variables, exactly one surplus variable and exactly one artificial variable
the rows for the two objective functions are formed

(6)

The following tableau \(T\) is obtained after one iteration of the second stage of the two-stage Simplex method.

b.v.	\(x\)	\(y\)	\(z\)	\(s_1\)	\(s_2\)	\(s_3\)	Value
\(y\)	0	1	0	1	0	1	11
\(s_2\)	0	0	5	\(-2\)	1	\(-5\)	62
\(x\)	1	0	1	0	0	\(-1\)	28
\(P\)	0	0	\(-1\)	1	0	1	11

(d) Starting from tableau \(T\), solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use. (5)

Mark scheme (a)

Scheme	Marks	AO
\(x + y + z \leqslant 39\)	B1	3.3
\(\tfrac{2}{5}(x + y + z) \leqslant x \quad (\Rightarrow -3x + 2y + 2z \leqslant 0)\)	M1 A1	3.3 1.1b
\(x + z \geqslant 28\)	B1	1.1b
Maximise \(P = y + z \quad (\Rightarrow P - y - z = 0)\)	B1	3.3
	(5)

Notes

(a) B1: cao (\(x + y + z \leqslant 39\))

M1: \(\tfrac{2}{5}(x + y + z) \,\square\, x\) where \(\square\) is any inequality or equals

A1: cao

B1: cao (\(x + z \geqslant 28\))

B1: Correct objective function (\(P = y + z\)) plus ‘maximise’ or ‘max’ but not ‘maximum’

Mark scheme (b)

Scheme

Marks

\(x + y + z \leqslant 39 \;\Rightarrow\; x + y + z + s_1 = 39\)
\(-3x + 2y + 2z \leqslant 0 \;\Rightarrow\; -3x + 2y + 2z + s_2 = 0\)

M1
A1

2.1
1.1b

\(x + z \geqslant 28 \;\Rightarrow\; x + z - s_3 + a_1 = 28\)

2.5

\(I = -a_1 \;\Rightarrow\; I - x - z + s_3 = -28\)

2.1

e.g.

b.v	\(x\)	\(y\)	\(z\)	\(s_1\)	\(s_2\)	\(s_3\)	\(a_1\)	Value
\(s_1\)	1	1	1	1	0	0	0	39
\(s_2\)	\(-3\)	2	2	0	1	0	0	0
\(a_1\)	1	0	1	0	0	\(-1\)	1	28
\(P\)	0	\(-1\)	\(-1\)	0	0	0	0	0
\(I\)	\(-1\)	0	\(-1\)	0	0	1	0	\(-28\)

M1
A1

3.3
2.2a

(6)

Notes

(b) M1: One \(\leqslant\) constraint re-formulated as an equation using slack variables – dependent on either the first B mark in (a) or the M mark in (a)

A1: cao (both \(\leqslant\) constraints)

B1: \(\geqslant\) constraint re-formulated as an equation using one surplus and one artificial variable

M1: Formulates second objective with \(I = -a_1\) and their expression for \(a_1\)

M1: Setting up the initial tableau – all five rows complete with two correct rows (but ignore b.v. column for this mark)

A1: cao (any equivalent correct form)

Mark scheme (c)

Scheme	Marks	AO
The only negative in the objective row is the \(-1\) so the pivot is from the \(z\)-column	B1	2.4
The 5 in the \(s_2\) row is the pivot because \(\dfrac{62}{5}\) is less than \(\dfrac{28}{1}\)	B1	2.2a
	(2)

Notes

(c) B1: Correct reasoning that the pivot is a value from the \(z\)-column – condone any mention of negative value in \(P\) row

B1: Correct justification of why the 5 in the \(s_2\) row is the next pivot – so must compare or state that 12.4 is less than 28 (not sufficient to just say that 12.4 (oe) is the least)

Mark scheme (d)

Scheme

Marks

b.v.	\(x\)	\(y\)	\(z\)	\(s_1\)	\(s_2\)	\(s_3\)	Value	Row Ops
\(y\)	0	1	0	1	0	1	11	R1
\(z\)	0	0	1	\(-\frac{2}{5}\)	\(\frac{1}{5}\)	\(-1\)	\(\frac{62}{5}\)	\(\tfrac{1}{5}\text{R2}\)
\(x\)	1	0	0	\(\frac{2}{5}\)	\(-\frac{1}{5}\)	0	\(\frac{78}{5}\)	R3 − R2
\(P\)	0	0	0	\(\frac{3}{5}\)	\(\frac{1}{5}\)	0	\(\frac{117}{5}\)	R4 + R2

B1
M1
A1
A1

1.1b
2.1
1.1b
1.1b

Spend 15.6 hours swimming, 11 hours cycling and 12.4 hours running

3.2a

(5)

(18 marks)

Notes

(d) B1: Pivot row correct including change of b.v.

M1: All values in one of the non-pivot rows correct or one of the non zero and one columns (\(s_1, s_2\) or value) correct (from their choice of pivot)

A1: Row operations used correctly at least twice, i.e. two of the non zero and one columns (\(s_1, s_2\) or value)

A1: For all values and row operations correctly stated – do not penalise lack of correct b.v. in pivot row twice. Condone blank Row Ops in the first row only

A1: Correct allocation of training times – must be in context (so not just in terms of \(x\), \(y\) and \(z\))