| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Formulate LP from context |
| Difficulty | Moderate -0.3 This is a standard D2 simplex question requiring LP formulation from a word problem and mechanical application of the simplex algorithm. The context is straightforward, the tableau is provided, and students follow a routine procedure with no novel problem-solving required. Slightly easier than average due to the structured guidance and typical textbook format. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.06c Working with constraints: algebra and ad hoc methods7.06d Graphical solution: feasible region, two variables7.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 |
| \(R\) | \(x\) | \(y\) | \(z\) | \(s\) | \(t\) | \(u\) | |
| 1 | \({ } ^ { - } 10\) | \({ } ^ { - } 12\) | \({ } ^ { - } 8\) | 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 4 | 1 | 0 | 0 | 20 |
| 0 | 4 | 3 | 14 | 0 | 1 | 0 | 75 |
| 0 | 5 | 2 | 10 | 0 | 0 | 1 | 60 |
| Answer | Marks | Guidance |
|---|---|---|
| Content | Marks | Guidance |
| (a) Maximise \(R = 10x + 12y + 8z\) given constraints: \(x + 2y + 4z \leq 20\); \(4x + 3y + 14z \leq 75\); \(5x + 2y + 10z \leq 60\); \(x \geq 0, y \geq 0, z \geq 0\) | M1 A1 | |
| (b) to change inequalities into equations | B1 | |
| (c) \(\theta\) values are 10, 25 and 30 so pivot row is 2nd row; 2nd tableau shown with entries: R row: \(-4, 0, 16, 6, 0, 0 \mid 120\); row 1: \(\frac{1}{2}, 1, 2, \frac{1}{2}, 0, 0 \mid 10\); row 2: \(\frac{3}{2}, 0, 8, -\frac{3}{2}, 1, 0 \mid 45\); row 3: \(4, 0, 6, -1, 0, 1 \mid 40\) | M2 A2 | |
| choose to increase x next; \(\theta\) values are 20, 18 and 10 so pivot row is 4th row; 3rd tableau shown with entries: R row: \(0, 0, 22, 5, 0, 1 \mid 160\); row 1: \(0, 1, \frac{3}{4}, \frac{5}{8}, 0, -\frac{1}{8} \mid 5\); row 2: \(0, 0, \frac{17}{4}, -\frac{7}{8}, 1, -\frac{5}{8} \mid 20\); row 3: \(1, 0, \frac{3}{2}, -\frac{1}{4}, 0, \frac{1}{4} \mid 10\) | M1 A2 | |
| (d) optimal solution as all values on the objective row are \(\geq 0\); company donates 10 two-person and 5 four-person boats | B1 B1 | (12) |
| Content | Marks | Guidance |
|---------|-------|----------|
| (a) Maximise $R = 10x + 12y + 8z$ given constraints: $x + 2y + 4z \leq 20$; $4x + 3y + 14z \leq 75$; $5x + 2y + 10z \leq 60$; $x \geq 0, y \geq 0, z \geq 0$ | M1 A1 | |
| (b) to change inequalities into equations | B1 | |
| (c) $\theta$ values are 10, 25 and 30 so pivot row is 2nd row; 2nd tableau shown with entries: R row: $-4, 0, 16, 6, 0, 0 \mid 120$; row 1: $\frac{1}{2}, 1, 2, \frac{1}{2}, 0, 0 \mid 10$; row 2: $\frac{3}{2}, 0, 8, -\frac{3}{2}, 1, 0 \mid 45$; row 3: $4, 0, 6, -1, 0, 1 \mid 40$ | M2 A2 | |
| choose to increase x next; $\theta$ values are 20, 18 and 10 so pivot row is 4th row; 3rd tableau shown with entries: R row: $0, 0, 22, 5, 0, 1 \mid 160$; row 1: $0, 1, \frac{3}{4}, \frac{5}{8}, 0, -\frac{1}{8} \mid 5$; row 2: $0, 0, \frac{17}{4}, -\frac{7}{8}, 1, -\frac{5}{8} \mid 20$; row 3: $1, 0, \frac{3}{2}, -\frac{1}{4}, 0, \frac{1}{4} \mid 10$ | M1 A2 | |
| (d) optimal solution as all values on the objective row are $\geq 0$; company donates 10 two-person and 5 four-person boats | B1 B1 | (12) |5. A leisure company owns boats of each of the following types:
2-person boats which are 4 metres long and weigh 50 kg .\\
4-person boats which are 3 metres long and weigh 20 kg .\\
8-person boats which are 14 metres long and weigh 100 kg .\\
The leisure company is willing to donate boats to a local sports club to accommodate up to 40 people at any one time. However, storage facilities mean that the combined length of the boats must not be more than 75 metres. Also, it must be possible to transport all the boats on a single trailer which has a maximum load capacity of 600 kg .
The club intends to hire the boats out to help with the cost of maintaining them. It plans to charge $\pounds 10 , \pounds 12$ and $\pounds 8$ per day, for the 2 -, 4 - and 8 -person boats respectively and wishes to maximise its daily revenue ( $\pounds R$ ).
Let $x , y$ and $z$ represent the number of 2-, 4- and 8-person boats respectively given to the club.
\begin{enumerate}[label=(\alph*)]
\item Model this as a linear programming problem.
Using the Simplex algorithm the following initial tableau is obtained:
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
$R$ & $x$ & $y$ & $z$ & $s$ & $t$ & $u$ & \\
\hline
1 & ${ } ^ { - } 10$ & ${ } ^ { - } 12$ & ${ } ^ { - } 8$ & 0 & 0 & 0 & 0 \\
\hline
0 & 1 & 2 & 4 & 1 & 0 & 0 & 20 \\
\hline
0 & 4 & 3 & 14 & 0 & 1 & 0 & 75 \\
\hline
0 & 5 & 2 & 10 & 0 & 0 & 1 & 60 \\
\hline
\end{tabular}
\end{center}
\item Explain the purpose of the variables $s , t$ and $u$.
\item By increasing the value of $y$ first, work out the next two complete tableaus.
\item Explain how you know that your final tableau gives an optimal solution and state this solution in practical terms.
\end{enumerate}
\hfill \mbox{\textit{OCR D2 Q5 [12]}}