OCR Further Discrete 2019 June — Question 3 9 marks

Exam BoardOCR
ModuleFurther Discrete (Further Discrete)
Year2019
SessionJune
Marks9
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicThe Simplex Algorithm
TypePerform one Simplex iteration
DifficultyModerate -0.5 This is a routine Simplex algorithm question requiring standard mechanical steps: reading off the LP formulation from a tableau, identifying the pivot element using standard rules, and performing row operations. While it requires careful arithmetic and understanding of the algorithm, it involves no problem-solving or novel insight—just direct application of a learned procedure with multiple marks available for showing working.
Spec7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations7.07c Interpret simplex: values of variables, slack, and objective
3 A problem is represented as the initial simplex tableau below.
\(\mathbf { P }\)\(\mathbf { x }\)\(\mathbf { y }\)\(\mathbf { z }\)\(\mathbf { s }\)\(\mathbf { t }\)RHS
1- 201000
01111060
02340160
  1. Write the problem as a linear programming formulation in the standard algebraic form with no slack variables.
  2. Carry out one iteration of the simplex algorithm.
  3. Show algebraically how each row of the tableau found in part (b) is calculated.
Question 3:
AnswerMarks Guidance
3(a) Maximise P = 2x – z
subject to x + y + z < 60
2x + 3y + 4z < 60
AnswerMarks
and x > 0, y > 0, z > 0B1
M1
AnswerMarks
A13.1a
1.1
AnswerMarks
1.1‘Max’ and objective function 2x – z
or any non-negative multiple of this
Either constraint correct in this form
Both constraints and non-negativity
AnswerMarks
(trivial constraints) correct‘Max’ and P – 2x + z = 0
Form ax + by + cz < d
May have non-negative
multiples of constraints
AnswerMarks
(b)P x y z s t RHS
1 -2 0 1 0 0 0
0 1 1 1 1 0 60
0 2 3 4 0 1 60
Pivot on 2 in row 3 of column x
P x y z s t RHS
1 0 3 5 0 1 60
0 0 -0.5 -1 1 -0.5 30
AnswerMarks
0 1 1.5 2 0 0.5 30B1
M1
AnswerMarks
A11.1
1.1
AnswerMarks
1.1May be implied from iterated
tableau
Dealing with (their) pivot in 3rd row
AnswerMarks
All correct60 ÷ 2 = 30 < 60 ÷ 1
Using decimals or fractions
AnswerMarks
(c)2x + 3y + 4z + t = 60 ⇒ x = 30 – 1.5y – 2z – 0.5t
Substitute for x:
P – 2x + z = 0
⇒ P – (60 – 3y – 4z – t) + z = 0
⇒ P + 3y + 5z + t = 60
x + y + z + s = 60
⇒ (30 – 1.5y – 2z – 0.5t) + y + z + s = 60
AnswerMarks
⇒ – 0.5y – z + s – 0.5t = 30M1
A1
AnswerMarks
A12.1
2.2a
AnswerMarks
2.2aEliminate x by substitution
Showing substitution for x
P + 3y + 5z + t = 60 o.e.
from algebraic substitution seen
– 0.5y – z + s – 0.5t = 30 o.e.
AnswerMarks
from algebraic substitution seenNot showing calculation of
each row as a linear
combination of other rows
Not just algebraic
interpretation of tableau
[9]
AnswerMarks Guidance
Px y 
Question 3:
3 | (a) | Maximise P = 2x – z
subject to x + y + z < 60
2x + 3y + 4z < 60
and x > 0, y > 0, z > 0 | B1
M1
A1 | 3.1a
1.1
1.1 | ‘Max’ and objective function 2x – z
or any non-negative multiple of this
Either constraint correct in this form
Both constraints and non-negativity
(trivial constraints) correct | ‘Max’ and P – 2x + z = 0
Form ax + by + cz < d
May have non-negative
multiples of constraints
(b) | P x y z s t RHS
1 -2 0 1 0 0 0
0 1 1 1 1 0 60
0 2 3 4 0 1 60
Pivot on 2 in row 3 of column x
P x y z s t RHS
1 0 3 5 0 1 60
0 0 -0.5 -1 1 -0.5 30
0 1 1.5 2 0 0.5 30 | B1
M1
A1 | 1.1
1.1
1.1 | May be implied from iterated
tableau
Dealing with (their) pivot in 3rd row
All correct | 60 ÷ 2 = 30 < 60 ÷ 1
Using decimals or fractions
(c) | 2x + 3y + 4z + t = 60 ⇒ x = 30 – 1.5y – 2z – 0.5t
Substitute for x:
P – 2x + z = 0
⇒ P – (60 – 3y – 4z – t) + z = 0
⇒ P + 3y + 5z + t = 60
x + y + z + s = 60
⇒ (30 – 1.5y – 2z – 0.5t) + y + z + s = 60
⇒ – 0.5y – z + s – 0.5t = 30 | M1
A1
A1 | 2.1
2.2a
2.2a | Eliminate x by substitution
Showing substitution for x
P + 3y + 5z + t = 60 o.e.
from algebraic substitution seen
– 0.5y – z + s – 0.5t = 30 o.e.
from algebraic substitution seen | Not showing calculation of
each row as a linear
combination of other rows
Not just algebraic
interpretation of tableau
[9]
P | x | y | z | s | t | RHS
3 A problem is represented as the initial simplex tableau below.

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
$\mathbf { P }$ & $\mathbf { x }$ & $\mathbf { y }$ & $\mathbf { z }$ & $\mathbf { s }$ & $\mathbf { t }$ & RHS \\
\hline
1 & - 2 & 0 & 1 & 0 & 0 & 0 \\
\hline
0 & 1 & 1 & 1 & 1 & 0 & 60 \\
\hline
0 & 2 & 3 & 4 & 0 & 1 & 60 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Write the problem as a linear programming formulation in the standard algebraic form with no slack variables.
\item Carry out one iteration of the simplex algorithm.
\item Show algebraically how each row of the tableau found in part (b) is calculated.
\end{enumerate}

\hfill \mbox{\textit{OCR Further Discrete 2019 Q3 [9]}}
This paper (7 questions)
View full paper
Q1 8 Q2 7 Q3 9 Q4 12 Q5 14 Q6 13 Q7 12