| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | March |
| Marks | 14 |
| Topic | The Simplex Algorithm |
| Type | Complete Simplex solution |
| Difficulty | Challenging +1.2 This is a standard Further Maths linear programming question requiring routine application of the simplex algorithm (a mechanical procedure taught explicitly) followed by branch-and-bound for integer programming. While it involves multiple steps and careful bookkeeping, both techniques are algorithmic procedures that students practice extensively. The question provides the feasible region vertices and clear instructions, making it more straightforward than questions requiring novel problem-solving insight or proof. |
| Spec | 7.06f Integer programming: branch-and-bound method7.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 |
| Answer | Marks | Guidance |
|---|---|---|
| Initial tableau with correct P row and constraint rows. Pivot on column \(x\) row 3. Subsequent tableaus showing pivots on column \(y\) row 2 with final result \(P = 184\) when \(x = 46\frac{2}{3}\), \(y = \frac{2}{3}\), \(z = 0\) | B1, B1, M1, A1, M1, A1, B1 ft | Objective row correct; Rest of table correct; Their pivot row correct; Tableau with correct structure and final column \(> 0\); Their pivot row correct; Final tableau with correct structure, final column \(> 0\) and no negative values in objective row; \(P\), \(x\), and \(z\) = 0 ft their final tableau. Accept awrt 46.67 and 2.67 |
| Answer | Marks | Guidance |
|---|---|---|
| Branch-and-bound tree with root \(P = 184\) at \(x = 46\frac{2}{3}\), \(y = \frac{2}{3}\). First branching: \(x \leq 46\) gives \(P = 181.6\) at \(x = 46\), \(y = 2.4\); \(x \geq 47\) gives Infeasible. Second branching: \(y \leq 2\) gives \(P = 178\) at \(x = 45\), \(y = 2\) with \(x\) and \(y\) integers; \(y \geq 3\) gives \(P = 177\) at \(x = 45\), \(y = 3\) with \(x\) and \(y\) integers but \(P < 178\) (at solution already found). Solution is \(P = 178\) at \(x = 45\), \(y = 2\). | B1 ft, M1 ft, A1, B1 ft, M1 ft, A1, A1 | Structure of branch-and-bound; First branching correct; First box correct; Second box correct; Second branching correct; Either first or second box correct; Both boxes correct plus conclusion |
## (i)
| Initial tableau with correct P row and constraint rows. Pivot on column $x$ row 3. Subsequent tableaus showing pivots on column $y$ row 2 with final result $P = 184$ when $x = 46\frac{2}{3}$, $y = \frac{2}{3}$, $z = 0$ | B1, B1, M1, A1, M1, A1, B1 ft | Objective row correct; Rest of table correct; Their pivot row correct; Tableau with correct structure and final column $> 0$; Their pivot row correct; Final tableau with correct structure, final column $> 0$ and no negative values in objective row; $P$, $x$, and $z$ = 0 ft their final tableau. Accept awrt 46.67 and 2.67 |
## (ii)
| Branch-and-bound tree with root $P = 184$ at $x = 46\frac{2}{3}$, $y = \frac{2}{3}$. First branching: $x \leq 46$ gives $P = 181.6$ at $x = 46$, $y = 2.4$; $x \geq 47$ gives Infeasible. Second branching: $y \leq 2$ gives $P = 178$ at $x = 45$, $y = 2$ with $x$ and $y$ integers; $y \geq 3$ gives $P = 177$ at $x = 45$, $y = 3$ with $x$ and $y$ integers but $P < 178$ (at solution already found). Solution is $P = 178$ at $x = 45$, $y = 2$. | B1 ft, M1 ft, A1, B1 ft, M1 ft, A1, A1 | Structure of branch-and-bound; First branching correct; First box correct; Second box correct; Second branching correct; Either first or second box correct; Both boxes correct plus conclusion |
---A linear programming problem is
\begin{align}
\text{Maximise } P &= 4x - y - 2z \\
\text{subject to } x + 5y + 3z &\leq 60 \\
2x - 5y &\leq 80 \\
2y + z &\leq 10 \\
x \geq 0, y &\geq 0, z \geq 0
\end{align}
\begin{enumerate}[label=(\roman*)]
\item Use the simplex algorithm to solve the problem. [7]
\end{enumerate}
In the case when $z = 0$ the feasible region can be represented graphically.
\includegraphics{figure_1}
The vertices of the feasible region are $(0, 0)$, $(40, 0)$, $(46.67, 2.67)$, $(35, 5)$ and $(0, 5)$, where non-integer values are given to 2 decimal places. The linear programming problem is given the additional constraint that $x$ and $y$ are integers.
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{1}
\item Use branch-and-bound, branching on $x$ first, to show that the optimum solution with this additional constraint is $x = 45, y = 2$. [7]
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q2 [14]}}