| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2019 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Big-M method setup |
| Difficulty | Standard +0.8 This is a multi-part Further Maths question requiring understanding of why standard Simplex fails, setting up Big-M tableau with artificial variables, interpreting tableau results, and selecting pivots. While methodical, it demands solid grasp of Decision Maths theory and careful algebraic manipulation across multiple steps—significantly above average A-level difficulty but follows standard Big-M procedure taught in FD1. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.07a Simplex tableau: initial setup in standard format |
| b.v. | \(x\) | \(y\) | \(z\) | \(s _ { 1 }\) | \(S _ { 2 }\) | \(S _ { 3 }\) | \(a _ { 1 }\) | \(a _ { 2 }\) | Value |
| \(s _ { 1 }\) | 3 | 0 | 1.5 | 1 | 0 | 0.25 | 0 | -0.25 | 26.25 |
| \(a _ { 1 }\) | 1 | 0 | 1.5 | 0 | -1 | -0.25 | 1 | 0.25 | 11.75 |
| \(y\) | 0 | 1 | 0.5 | 0 | 0 | -0.25 | 0 | 0.25 | 3.75 |
| \(P\) | \(- ( 2 + M )\) | 0 | 2-1.5M | 0 | M | \(- 0.5 + 0.25 M\) | 0 | \(0.5 + 0.75 M\) | 7.5-11.75M |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Simplex can only be applied when the non-negativity constraints are \(\leq\) | B1 | e.g. not all constraints are \(\leq\), origin is not a basic feasible solution |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(3x + y + 2z \leq 30 \Rightarrow 3x + y + 2z + s_1 = 30\) | B1 | May be seen in simplex tableau |
| \(x - y + z \geq 8 \Rightarrow x - y + z - s_2 + a_1 = 8\) | B1 | Allow any consistent \(s_i\) for \(s_2\); allow any \(a_i\) for \(a_1\) |
| \(4y + 2z \geq 15 \Rightarrow 4y + 2z - s_3 + a_2 = 15\) | B1 | |
| \(P = 2x + 2y - z \Rightarrow P = 2x + 2y - z - M(a_1 + a_2)\) with \(a_1 + a_2 = 23 - x - 3y - 3z + s_2 + s_3\) | M1 | If no working then correct objective line in tableau implies this mark |
| \(P - (2+M)x - (2+3M)y - (-1+3M)z + Ms_2 + Ms_3 = -23M\) | A1 | Any equivalent form; need not be factorised |
| Initial tableau with all four rows complete, two correct rows | M1 | Ignore b.v. column |
| CAO (any equivalent correct form) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(s_1 = 26.25,\ a_1 = 11.75,\ y = 3.75,\ x = z = s_2 = s_3 = a_2 = 0\) | B1 | Ignore expression for \(P\) if given |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Solution after 1st iteration is not feasible because \(a_1 = 11.75\) is an artificial variable which must be zero in a feasible solution | B1 | Must state \(a_1\) is non-zero (not just "artificial variable is non-zero"); B0 for just stating artificial variable is non-zero without specifying \(a_1\) or 11.75 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Most negative value in objective row is \(2 - 1.5M\), so pivot is from \(z\)-column | B1 | Must say most negative value is \(2 - 1.5M\) or this clearly implied |
| \(\frac{3.75}{0.5}\) is less than both \(\frac{26.25}{1.5}\) and \(\frac{11.75}{1.5}\), so 0.5 in \(y\)-row is the pivot | dB1 | Dependent on previous B; must compare or state \(\frac{3.75}{0.5}\) (or 7.5) is less than \(\frac{26.25}{1.5}\) (or 17.5) and \(\frac{11.75}{1.5}\) (or 7.833...); just stating 0.5 is pivot without reasoning scores no marks |
# Question 6:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Simplex can only be applied when the non-negativity constraints are $\leq$ | B1 | e.g. not all constraints are $\leq$, origin is not a basic feasible solution |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $3x + y + 2z \leq 30 \Rightarrow 3x + y + 2z + s_1 = 30$ | B1 | May be seen in simplex tableau |
| $x - y + z \geq 8 \Rightarrow x - y + z - s_2 + a_1 = 8$ | B1 | Allow any consistent $s_i$ for $s_2$; allow any $a_i$ for $a_1$ |
| $4y + 2z \geq 15 \Rightarrow 4y + 2z - s_3 + a_2 = 15$ | B1 | |
| $P = 2x + 2y - z \Rightarrow P = 2x + 2y - z - M(a_1 + a_2)$ with $a_1 + a_2 = 23 - x - 3y - 3z + s_2 + s_3$ | M1 | If no working then correct objective line in tableau implies this mark |
| $P - (2+M)x - (2+3M)y - (-1+3M)z + Ms_2 + Ms_3 = -23M$ | A1 | Any equivalent form; need not be factorised |
| Initial tableau with all four rows complete, two correct rows | M1 | Ignore b.v. column |
| CAO (any equivalent correct form) | A1 | |
## Part (c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $s_1 = 26.25,\ a_1 = 11.75,\ y = 3.75,\ x = z = s_2 = s_3 = a_2 = 0$ | B1 | Ignore expression for $P$ if given |
## Part (d):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Solution after 1st iteration is not feasible because $a_1 = 11.75$ is an artificial variable which must be zero in a feasible solution | B1 | Must state $a_1$ is non-zero (not just "artificial variable is non-zero"); B0 for just stating artificial variable is non-zero without specifying $a_1$ or 11.75 |
## Part (e):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Most negative value in objective row is $2 - 1.5M$, so pivot is from $z$-column | B1 | Must say most negative value is $2 - 1.5M$ or this clearly implied |
| $\frac{3.75}{0.5}$ is less than both $\frac{26.25}{1.5}$ and $\frac{11.75}{1.5}$, so 0.5 in $y$-row is the pivot | dB1 | Dependent on previous B; must compare or state $\frac{3.75}{0.5}$ (or 7.5) is less than $\frac{26.25}{1.5}$ (or 17.5) and $\frac{11.75}{1.5}$ (or 7.833...); just stating 0.5 is pivot without reasoning scores no marks |
---6. A linear programming problem in $x , y$ and $z$ is described as follows.
Maximise $\quad P = 2 x + 2 y - z$\\
subject to $\quad 3 x + y + 2 z \leqslant 30$
$$\begin{aligned}
x - y + z & \geqslant 8 \\
4 y + 2 z & \geqslant 15 \\
x , y , z & \geqslant 0
\end{aligned}$$
\begin{enumerate}[label=(\alph*)]
\item Explain why the Simplex algorithm cannot be used to solve this linear programming problem.
\item Set up the initial tableau for solving this linear programming problem using the big-M method.
After a first iteration of the big-M method, the tableau is
\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
$s _ { 1 }$ & 3 & 0 & 1.5 & 1 & 0 & 0.25 & 0 & -0.25 & 26.25 \\
\hline
$a _ { 1 }$ & 1 & 0 & 1.5 & 0 & -1 & -0.25 & 1 & 0.25 & 11.75 \\
\hline
$y$ & 0 & 1 & 0.5 & 0 & 0 & -0.25 & 0 & 0.25 & 3.75 \\
\hline
$P$ & $- ( 2 + M )$ & 0 & 2-1.5M & 0 & M & $- 0.5 + 0.25 M$ & 0 & $0.5 + 0.75 M$ & 7.5-11.75M \\
\hline
\end{tabular}
\end{center}
\item State the value of each variable after the first iteration.
\item Explain why the solution given by the first iteration is not feasible.
Taking the most negative entry in the profit row to indicate the pivot column,
\item obtain the most efficient pivot for a second iteration. You must give reasons for your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2019 Q6 [12]}}