| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 17 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Linear Programming |
| Type | Formulation from word problem |
| Difficulty | Moderate -0.3 This is a standard D1 linear programming question requiring formulation of constraints and application of the simplex algorithm. While multi-part with several marks, it follows a completely routine template: extract constraints from word problem, set up tableau (which is given), perform pivot operations (mechanical process), and interpret results. The formulation is straightforward with no tricks, and the simplex method is algorithmic rather than requiring insight. Slightly easier than average A-level due to being purely procedural. |
| 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.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations |
| Basic Variable | \(x\) | \(y\) | \(z\) | \(s\) | \(t\) | \(u\) | Value |
| \(s\) | 1 | 2 | 4 | 1 | 0 | 0 | 20 |
| \(t\) | 4 | 3 | 14 | 0 | 1 | 0 | 75 |
| \(u\) | 5 | 2 | 10 | 0 | 0 | 1 | 60 |
| \(R\) | \({ } ^ { - } 10\) | \({ } ^ { - } 12\) | \({ } ^ { - } 8\) | 0 | 0 | 0 | 0 |
| Answer | Marks |
|---|---|
| (a) Maximise \(P = 10x + 12y + 8z\) given \(x + 2y + 4z \leq 20\); \(4x + 3y + 14z \leq 75\); \(5x + 2y + 10z \leq 60\); \(x \geq 0, y \geq 0, z \geq 0\) | M2 A2 |
| Answer | Marks |
|---|---|
| Objective function becomes \(R - 10x - 12y - 8z = 0\), hence the given initial tableau | M1 A1 |
| (c) To change inequalities into equations | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Basic Var. | \(x\) | \(y\) |
| \(y\) | \(\frac{1}{2}\) | 1 |
| \(t\) | \(\frac{5}{2}\) | 0 |
| \(u\) | 4 | 0 |
| \(R\) | \(-4\) | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Basic Var. | \(x\) | \(y\) |
| \(y\) | 0 | 1 |
| \(t\) | 0 | 0 |
| \(x\) | 1 | 0 |
| \(R\) | 0 | 0 |
| M2 A2 | ||
| (e) Optimal solution as all values on the objective row are \(\geq 0\); company donates 10 two-person and 5 four-person boats | B1, B1 | (17) |
| Answer | Marks |
|---|---|
| Total | (75) |
**(a)** Maximise $P = 10x + 12y + 8z$ given $x + 2y + 4z \leq 20$; $4x + 3y + 14z \leq 75$; $5x + 2y + 10z \leq 60$; $x \geq 0, y \geq 0, z \geq 0$ | M2 A2 |
**(b)** Using slack variables $s, t, u$ gives:
- $x + 2y + 4z + s = 20$
- $4x + 3y + 14z + t = 75$
- $5x + 2y + 10z + u = 60$
Objective function becomes $R - 10x - 12y - 8z = 0$, hence the given initial tableau | M1 A1 |
**(c)** To change inequalities into equations | B1 |
**(d)** $\theta$ values are 10, 25 and 30 so pivot row is 1st row
2nd tableau is:
| Basic Var. | $x$ | $y$ | $z$ | $s$ | $t$ | $u$ | Value |
|---|---|---|---|---|---|---|---|
| $y$ | $\frac{1}{2}$ | 1 | 2 | $\frac{1}{2}$ | 0 | 0 | 10 |
| $t$ | $\frac{5}{2}$ | 0 | 8 | $-\frac{3}{2}$ | 1 | 0 | 45 |
| $u$ | 4 | 0 | 6 | $-1$ | 0 | 1 | 40 |
| $R$ | $-4$ | 0 | 16 | 6 | 0 | 0 | 120 |
Choose to increase $x$ next. $\theta$ values are 20, 18 and 10 so pivot row is 3rd row
3rd tableau is:
| Basic Var. | $x$ | $y$ | $z$ | $s$ | $t$ | $u$ | Value |
|---|---|---|---|---|---|---|---|
| $y$ | 0 | 1 | $\frac{5}{4}$ | $\frac{5}{8}$ | 0 | $-\frac{1}{8}$ | 5 |
| $t$ | 0 | 0 | $\frac{17}{4}$ | $-\frac{7}{8}$ | 1 | $-\frac{5}{8}$ | 20 |
| $x$ | 1 | 0 | $\frac{3}{2}$ | $-\frac{1}{4}$ | 0 | $\frac{1}{4}$ | 10 |
| $R$ | 0 | 0 | 22 | 5 | 0 | 1 | 160 |
| M2 A2 |
**(e)** Optimal solution as all values on the objective row are $\geq 0$; company donates 10 two-person and 5 four-person boats | B1, B1 | (17)
---
**Total** | (75)7. 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 a maximum 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 simplifying your expressions so that they have integer coefficients.\\
(4 marks)
\item Show that the initial tableau, when using the simplex algorithm, can be written as:
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
Basic Variable & $x$ & $y$ & $z$ & $s$ & $t$ & $u$ & Value \\
\hline
$s$ & 1 & 2 & 4 & 1 & 0 & 0 & 20 \\
\hline
$t$ & 4 & 3 & 14 & 0 & 1 & 0 & 75 \\
\hline
$u$ & 5 & 2 & 10 & 0 & 0 & 1 & 60 \\
\hline
$R$ & ${ } ^ { - } 10$ & ${ } ^ { - } 12$ & ${ } ^ { - } 8$ & 0 & 0 & 0 & 0 \\
\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.
Sheet for answering question 3\\
NAME
\section*{Please hand this sheet in for marking}
(a)\\
(b)\\
(c)\\
\includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-08_2017_1051_462_244}\\
\section*{Please hand this sheet in for marking}
(a) $F \quad \bullet$
\begin{itemize}
\item $W$\\
$G \quad \bullet$
\item $S$
\end{itemize}
H •
\begin{itemize}
\item $C$
\end{itemize}
I •
\begin{itemize}
\item $O$
\end{itemize}
J •
\begin{itemize}
\item $D$\\
(b) Initial matching:\\
$\begin{array} { l l l l } F & \bullet & \bullet & W \\ G & \bullet & \bullet & S \\ H & \bullet & \bullet & C \\ I & \bullet & \bullet & O \\ J & \bullet & \bullet & D \end{array}$ $\_\_\_\_$\\
\end{itemize}
Complete matching:\\
F •
\begin{itemize}
\item $W$\\
$G \quad \bullet$
\item $S$\\
H •
\item $C$\\
I •
\item $O$\\
J •
\item $D$
\end{itemize}
\section*{Sheet for answering question 5}
NAME
\section*{Please hand this sheet in for marking}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-10_2398_643_248_1224}
\end{center}
Sheet for answering question 6\\
NAME
\section*{Please hand this sheet in for marking}
(a) $\_\_\_\_$\\
(b) $\_\_\_\_$\\
(c) $\_\_\_\_$\\
(d)\\
\includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-11_592_1292_1078_312}\\
Sheet for answering question 6 (cont.)\\
\includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_595_1299_351_312}\\
\includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_597_1298_1409_308}
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q7 [17]}}