| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2021 |
| Session | November |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Write constraints from tableau |
| Difficulty | Moderate -0.5 Part (a) is a straightforward reading of a simplex tableau to extract the objective function and constraints - a routine mechanical task requiring only knowledge of how slack variables work. Parts (b) and (c) involve standard branch-and-bound procedure and interpreting a parameter change, both algorithmic processes covered in the syllabus. While this is Further Maths content, the question requires minimal problem-solving or insight, making it easier than average overall. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06d Graphical solution: feasible region, two variables7.06f Integer programming: branch-and-bound method |
| \(P\) | \(x\) | \(y\) | \(s\) | \(t\) | \(u\) | RHS |
| 1 | 2 | -5 | 0 | 0 | 0 | 0 |
| 0 | 2 | 1 | 1 | 0 | 0 | 25.8 |
| 0 | -1 | 3 | 0 | 1 | 0 | 13.8 |
| 0 | 4 | -3 | 0 | 0 | 1 | 18.8 |
| Answer | Marks | Guidance |
|---|---|---|
| 6 | (a) | Maximise P = –2x + 5y |
| Answer | Marks |
|---|---|
| 4x – 3y ≤ 18.8 | B1 |
| Answer | Marks |
|---|---|
| [2] | 3.3 |
| 3.3 | –2x + 5y or 5y – 2x or either of these + a constant, |
| Answer | Marks | Guidance |
|---|---|---|
| 6 | (b) | An optimal solution to the constrained problem is |
| P = 21 when x = 2 and y = 5 | M1 |
| Answer | Marks |
|---|---|
| [6] | 1.1 |
| Answer | Marks |
|---|---|
| 3.4 | y ≤ 4 and y ≥ 5, or implied from values in next row |
| Answer | Marks | Guidance |
|---|---|---|
| 6 | (c) | The boundary of the feasible region will change |
| Answer | Marks |
|---|---|
| Solution does not change, P = 21 when x = 2 and y = 5 | B1 |
| Answer | Marks |
|---|---|
| [3] | 3.5c |
| Answer | Marks |
|---|---|
| 1.1 | Answer may be given in space for 6(b), allow this |
Question 6:
6 | (a) | Maximise P = –2x + 5y
Subject to 2x + y ≤ 25.8
–x + 3y ≤ 13.8
4x – 3y ≤ 18.8 | B1
B1
[2] | 3.3
3.3 | –2x + 5y or 5y – 2x or either of these + a constant,
but not 2x – 5y, and not for P + 2x – 5y = 0 (or a constant)
All three constraints in this form, or 2x + y – 25.8 ≤ 0 etc.
Not for expressions that use the slack variables
Non-negativity given in Printed Answer Booklet
6 | (b) | An optimal solution to the constrained problem is
P = 21 when x = 2 and y = 5 | M1
A1
M1
A1
M1
A1
[6] | 1.1
3.4
1.1
2.1
2.1
3.4 | y ≤ 4 and y ≥ 5, or implied from values in next row
Either of “P = 20 at x = 0, y = 4” or
“P = 22.6 at x = 1.2, y = 5”
Branching on x-values appropriately
(x ≤ 1 and y ≥ 5 is) infeasible, or no solutions, or equivalent
Values for third branching and branching on y-values
appropriately
P = 22.3 (221) at x = 2, y = 5.27 (54) and branching on y-
3 15
values appropriately
P = 21 when x = 2 and y = 5 identified as solution
6 | (c) | The boundary of the feasible region will change
The line through (4.7, 0) will have the same gradient but will pass
through (0, 0)
The upper boundary (–x + 3y ≤ 13.8) is unchanged in the region of the
solution, 4×2 – 3×5 < 0
Solution does not change, P = 21 when x = 2 and y = 5 | B1
M1ft
A1
[3] | 3.5c
3.3
1.1 | Answer may be given in space for 6(b), allow this
Showing or describing change to feasible region
Verifying that (2, 5) is still feasible or explaining why the
change to the boundary does not affect the solution
Saying that solution is unchanged or stating solution
Correct solution only6 An initial simplex tableau is shown below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
$P$ & $x$ & $y$ & $s$ & $t$ & $u$ & RHS \\
\hline
1 & 2 & -5 & 0 & 0 & 0 & 0 \\
\hline
0 & 2 & 1 & 1 & 0 & 0 & 25.8 \\
\hline
0 & -1 & 3 & 0 & 1 & 0 & 13.8 \\
\hline
0 & 4 & -3 & 0 & 0 & 1 & 18.8 \\
\hline
\end{tabular}
\end{center}
The variables $s , t$ and $u$ are slack variables.
\begin{enumerate}[label=(\alph*)]
\item For the LP problem that this tableau represents, write down the following, in terms of $x$ and $y$ only.
\begin{itemize}
\item The objective function, $P$, to be maximised.
\item The constraints as inequalities.
\end{itemize}
The graph below shows the feasible region for the problem (as the unshaded region, and its boundaries), and objective lines $P = 10$ and $P = 20$ (shown as dotted lines).\\
\includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-7_883_1043_1272_244}
The optimal solution is $P = 23$, when $x = 0$ and $y = 4.6$.
\item Complete the first three rows of branch-and-bound in the Printed Answer Booklet, branching on $y$ first, to determine an optimal solution when $x$ and $y$ are constrained to take integer values. In your working, you should show non-integer values to $\mathbf { 2 }$ decimal places.
The tableau entry 18.8 is reduced to 0 .
\item Describe carefully what changes, if any, this makes to the following.
\begin{itemize}
\item The graph of the feasible region.
\item The optimal integer valued solution.
\end{itemize}
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2021 Q6 [11]}}