| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2022 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Big-M method setup |
| Difficulty | Standard +0.8 This is a Further Maths D1 question requiring reverse-engineering of the original LP problem from a big-M tableau, then identifying the pivot element. While the big-M method is an advanced topic, the question is largely procedural: reading constraints from rows, deducing the objective from the P-row, and applying standard pivot selection rules. It requires careful attention to detail with artificial variables and M-terms but doesn't demand novel problem-solving insight beyond applying learned algorithms. |
| Spec | 7.07a Simplex tableau: initial setup in standard format |
| b.v. | \(x\) | \(y\) | \(z\) | \(S _ { 1 }\) | \(s _ { 2 }\) | \(S _ { 3 }\) | \(a _ { 1 }\) | \(a _ { 2 }\) | Value |
| \(\mathrm { S } _ { 1 }\) | 2 | 3 | 4 | 1 | 0 | 0 | 0 | 0 | 13 |
| \(a _ { 1 }\) | 1 | -2 | 2 | 0 | -1 | 0 | 1 | 0 | 8 |
| \(a _ { 2 }\) | 3 | 0 | -4 | 0 | 0 | -1 | 0 | 1 | 12 |
| P | 2-4M | \(- 3 + 2 M\) | \(- 1 + 2 M\) | 0 | M | M | 0 | 0 | \(- 20 M\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| One correct non-trivial inequality (e.g. \(2x + 3y + 4z \leqslant 13\)) | B1 | 3.4 |
| All three non-trivial inequalities correct: \(2x+3y+4z \leqslant 13\); \(x-2y+2z \leqslant 8\); \(3x-4z \leqslant 12\); \((x,y,z \geqslant 0)\) | B1 | 2.5 |
| Either objective function stated correctly: Maximise \(-2x+3y+z\) | M1 | 3.1a |
| Both correct with max/min correctly matched: Maximise \(-2x+3y+z\); Minimise \(2x-3y-z\) | A1 | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| (Because \(M\) is big) the only negative in the objective row is \(2-4M\) so the pivot is from the \(x\)-column | B1 | 2.4 |
| The 3 in the \(a_2\) row is the pivot as \(\frac{12}{3}\) is less than both \(\frac{8}{1}\) and \(\frac{13}{2}\) | B1 | 2.2a |
## Question 4:
### Part (a)
| Answer/Working | Mark | Guidance |
|---|---|---|
| One correct non-trivial inequality (e.g. $2x + 3y + 4z \leqslant 13$) | B1 | 3.4 |
| All three non-trivial inequalities correct: $2x+3y+4z \leqslant 13$; $x-2y+2z \leqslant 8$; $3x-4z \leqslant 12$; $(x,y,z \geqslant 0)$ | B1 | 2.5 |
| Either objective function stated correctly: Maximise $-2x+3y+z$ | M1 | 3.1a |
| Both correct with max/min correctly matched: Maximise $-2x+3y+z$; Minimise $2x-3y-z$ | A1 | 2.2a |
### Part (b)
| Answer/Working | Mark | Guidance |
|---|---|---|
| (Because $M$ is big) the only negative in the objective row is $2-4M$ so the pivot is from the $x$-column | B1 | 2.4 |
| The 3 in the $a_2$ row is the pivot as $\frac{12}{3}$ is less than both $\frac{8}{1}$ and $\frac{13}{2}$ | B1 | 2.2a |4. A linear programming problem in $x , y$ and $z$ is to be solved using the big-M method. The initial tableau is shown below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $z$ & $S _ { 1 }$ & $s _ { 2 }$ & $S _ { 3 }$ & $a _ { 1 }$ & $a _ { 2 }$ & Value \\
\hline
$\mathrm { S } _ { 1 }$ & 2 & 3 & 4 & 1 & 0 & 0 & 0 & 0 & 13 \\
\hline
$a _ { 1 }$ & 1 & -2 & 2 & 0 & -1 & 0 & 1 & 0 & 8 \\
\hline
$a _ { 2 }$ & 3 & 0 & -4 & 0 & 0 & -1 & 0 & 1 & 12 \\
\hline
P & 2-4M & $- 3 + 2 M$ & $- 1 + 2 M$ & 0 & M & M & 0 & 0 & $- 20 M$ \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Using the information in the above tableau, formulate the linear programming problem. You should
\begin{itemize}
\item list each of the constraints as an inequality
\item state the two possible objectives
\item Obtain the most efficient pivot for a first iteration of the big-M method. You must give reasons for your answer.
\end{itemize}
\section*{Please turn over for Question 5}
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2022 Q4 [6]}}