| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2024 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Big-M method setup |
| Difficulty | Standard +0.3 This is a straightforward application of the big-M method requiring students to translate word problems into constraints, introduce slack/surplus/artificial variables, and set up the initial tableau—all standard procedures covered in FD1. Part (b) involves simple reading from the tableau and basic substitution. While it requires careful bookkeeping with multiple variable types, it demands no novel insight or problem-solving beyond routine application of a taught algorithm. |
| Spec | 7.06f Integer programming: branch-and-bound method |
| b.v. | \(x\) | \(y\) | \(s _ { 1 }\) | \(S _ { 2 }\) | \(\mathrm { S } _ { 3 }\) | \(a _ { 1 }\) | \(a _ { 2 }\) | Value |
| \(x\) | 1 | 0 | \(- \frac { 3 } { 5 }\) | 0 | \(- \frac { 1 } { 5 }\) | \(\frac { 3 } { 5 }\) | \(\frac { 1 } { 5 }\) | 130 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(x-y \geqslant 100 \Rightarrow x-y-s_1+a_1=100\) | B3,2,1 | B1: one correct equation or two correct inequalities (do not accept strict inequalities); B1: two correct equations or three correct inequalities; B1: all three equations correct |
| \(x-5y \leqslant 0 \Rightarrow x-5y+s_2=0\) | Check suffixes on \(s\) and \(a\) terms carefully | |
| \(2x+3y \geqslant 350 \Rightarrow 2x+3y-s_3+a_2=350\) | ||
| \(P=-x-y-M(a_1+a_2)\) and substitute expressions for \(a_1\) and \(a_2\): \((P+(1-3M)x+(1-2M)y+Ms_1+Ms_3=-450M)\) | M1 | Setting up the new objective which must be \(P=-x-y-M(a_1+a_2)\) and an attempt to substitute for \(a_1\) and \(a_2\). Accept use of \(Q\) instead of \(P\) |
| Initial tableau with all four rows complete | M1 | Setting up initial tableau – all four rows complete with two correct rows (ignore b.v. column). Check that slack, surplus and artificial variables correspond to their equations |
| Correct final tableau as shown | A1 | CAO (any equivalent correct form, but terms in objective row must be simplified) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(x=130\) | B1 | CAO (\(x=130\)) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| When \(x=130 \Rightarrow y \leqslant 30, y \geqslant 26, y < 130\) and \(y \geqslant 30\) | M1 | Substitute \(x=130\) into candidate's inequalities from (a) (at least 3 inequalities seen or both \(y \geqslant 30\) and \(y \leqslant 30\)) (condone \(y \leqslant 130\)) |
| \(y=30\) | A1 | CAO (\(y=30\)) – must see both \(y \geqslant 30\) and \(y \leqslant 30\) explicitly stated. Must not follow from any incorrect working |
# Question 5:
## Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| $x-y \geqslant 100 \Rightarrow x-y-s_1+a_1=100$ | B3,2,1 | B1: one correct equation or two correct inequalities (do not accept strict inequalities); B1: two correct equations or three correct inequalities; B1: all three equations correct |
| $x-5y \leqslant 0 \Rightarrow x-5y+s_2=0$ | | Check suffixes on $s$ and $a$ terms carefully |
| $2x+3y \geqslant 350 \Rightarrow 2x+3y-s_3+a_2=350$ | | |
| $P=-x-y-M(a_1+a_2)$ and substitute expressions for $a_1$ and $a_2$: $(P+(1-3M)x+(1-2M)y+Ms_1+Ms_3=-450M)$ | M1 | Setting up the new objective which must be $P=-x-y-M(a_1+a_2)$ and an attempt to substitute for $a_1$ and $a_2$. Accept use of $Q$ instead of $P$ |
| Initial tableau with all four rows complete | M1 | Setting up initial tableau – all four rows complete with two correct rows (ignore b.v. column). **Check that slack, surplus and artificial variables correspond to their equations** |
| Correct final tableau as shown | A1 | CAO (any equivalent correct form, but terms in objective row must be simplified) |
## Part (b)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| $x=130$ | B1 | CAO ($x=130$) |
## Part (b)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| When $x=130 \Rightarrow y \leqslant 30, y \geqslant 26, y < 130$ and $y \geqslant 30$ | M1 | Substitute $x=130$ into candidate's inequalities from (a) (at least 3 inequalities seen or both $y \geqslant 30$ and $y \leqslant 30$) (condone $y \leqslant 130$) |
| $y=30$ | A1 | CAO ($y=30$) – must see both $y \geqslant 30$ and $y \leqslant 30$ explicitly stated. Must not follow from any incorrect working |5. Two friends, Anaira and Tommi, play a game involving two positive numbers $x$ and $y$ Anaira gives Tommi the following clues to see if he can correctly determine the value of $x$ and the value of $y$
\begin{itemize}
\item $x$ is greater than $y$ and the difference between the two is at least 100
\item $x$ is at most 5 times as large as $y$
\item the sum of $2 x$ and $3 y$ is at least 350
\item the sum of $x$ and $y$ is as small as possible
\end{itemize}
Tommi decides to solve this problem by using the big-M method.
\begin{enumerate}[label=(\alph*)]
\item Set up an initial tableau for solving this problem using the big-M method.
As part of your solution, you must show
\begin{itemize}
\item how the constraints were made into equations using one slack variable, exactly two surplus variables and exactly two artificial variables
\item how the objective function was formed
\end{itemize}
The big-M method is applied until the tableau containing the optimal solution to the problem is found. One row of this final tableau is as follows.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $s _ { 1 }$ & $S _ { 2 }$ & $\mathrm { S } _ { 3 }$ & $a _ { 1 }$ & $a _ { 2 }$ & Value \\
\hline
$x$ & 1 & 0 & $- \frac { 3 } { 5 }$ & 0 & $- \frac { 1 } { 5 }$ & $\frac { 3 } { 5 }$ & $\frac { 1 } { 5 }$ & 130 \\
\hline
\end{tabular}
\end{center}
\item \begin{enumerate}[label=(\roman*)]
\item State the value of $x$
\item Hence deduce the value of $y$, making your reasoning clear.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2024 Q5 [9]}}