| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Interpret optimal tableau |
| Difficulty | Moderate -0.8 This is a routine Simplex algorithm question requiring standard procedures: reading off the objective function and constraints from a tableau, performing one iteration (a mechanical process), and interpreting the optimal tableau. All parts involve direct application of learned techniques with no problem-solving or novel insight required. The calculations are straightforward, making this easier than average for A-level. |
| Spec | 7.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 |
| \(P\) | \(x\) | \(y\) | \(z\) | \(s\) | \(t\) | RHS |
| 1 | - 10 | 2 | 3 | 0 | 0 | 0 |
| 0 | 5 | 0 | - 5 | 1 | 0 | 60 |
| 0 | 4 | 3 | 0 | 0 | 1 | 100 |
| \(P\) | \(x\) | \(y\) | \(z\) | \(s\) | \(t\) | RHS |
| 1 | 0 | 7.25 | 0 | 0.6 | 1.75 | 211 |
| 0 | 1 | 0.75 | 0 | 0 | 0.25 | 25 |
| 0 | 0 | 0.75 | 1 | - 0.2 | 0.25 | 13 |
| Answer | Marks |
|---|---|
| \(P = 10x - 2y - 3z\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| \(5x - 5z \leq 60\) (i.e. \(x - z \leq 12\)) | B1 | |
| \(4x + 3y \leq 100\) | B1 | |
| \(x \geq 0,\ y \geq 0,\ z \geq 0\) | B1 | All three non-negativity constraints |
| Answer | Marks | Guidance |
|---|---|---|
| Pivot on column \(x\) (most negative in P-row = \(-10\)) | M1 | Correct pivot column identified |
| Ratios: \(60/5 = 12\), \(100/4 = 25\); minimum ratio = 12, so pivot on row 2 element (5) | M1 | Correct pivot row identified |
| Divide pivot row by 5 | M1 | Correct row operations |
| Update all rows correctly to produce new tableau | A1 | Correct tableau after one iteration |
| Answer | Marks |
|---|---|
| All values in the P-row (for variables) are \(\geq 0\) (non-negative), so no further improvement is possible | B1 |
| Answer | Marks |
|---|---|
| \(x = 25,\ y = 0,\ z = 13\) | B1 |
| \(P = 211\) | B1 |
# Question 3:
**(i)**
| $P = 10x - 2y - 3z$ | B1 | |
**(ii)**
| $5x - 5z \leq 60$ (i.e. $x - z \leq 12$) | B1 | |
| $4x + 3y \leq 100$ | B1 | |
| $x \geq 0,\ y \geq 0,\ z \geq 0$ | B1 | All three non-negativity constraints |
**(iii)**
| Pivot on column $x$ (most negative in P-row = $-10$) | M1 | Correct pivot column identified |
| Ratios: $60/5 = 12$, $100/4 = 25$; minimum ratio = 12, so pivot on row 2 element (5) | M1 | Correct pivot row identified |
| Divide pivot row by 5 | M1 | Correct row operations |
| Update all rows correctly to produce new tableau | A1 | Correct tableau after one iteration |
**(iv)**
| All values in the P-row (for variables) are $\geq 0$ (non-negative), so no further improvement is possible | B1 | |
**(v)**
| $x = 25,\ y = 0,\ z = 13$ | B1 | |
| $P = 211$ | B1 | |
---3 A problem to maximise $P$ as a function of $x , y$ and $z$ is represented by the initial Simplex tableau below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
$P$ & $x$ & $y$ & $z$ & $s$ & $t$ & RHS \\
\hline
1 & - 10 & 2 & 3 & 0 & 0 & 0 \\
\hline
0 & 5 & 0 & - 5 & 1 & 0 & 60 \\
\hline
0 & 4 & 3 & 0 & 0 & 1 & 100 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Write down $P$ as a function of $x , y$ and $z$.
\item Write down the constraints as inequalities involving $x , y$ and $z$.
\item Carry out one iteration of the Simplex algorithm.
After a second iteration of the Simplex algorithm the tableau is as given below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
$P$ & $x$ & $y$ & $z$ & $s$ & $t$ & RHS \\
\hline
1 & 0 & 7.25 & 0 & 0.6 & 1.75 & 211 \\
\hline
0 & 1 & 0.75 & 0 & 0 & 0.25 & 25 \\
\hline
0 & 0 & 0.75 & 1 & - 0.2 & 0.25 & 13 \\
\hline
\end{tabular}
\end{center}
\item Explain how you know that the optimal solution has been achieved.
\item Write down the values of $x , y$ and $z$ that maximise $P$. Write down the optimal value of $P$.
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2016 Q3 [11]}}