| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Session | Specimen |
| 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 on the big-M method requiring understanding of why standard simplex fails, conceptual explanation of M, derivation of tableau rows, and performing simplex iterations with row operations. While systematic, it demands both theoretical understanding and computational accuracy across multiple steps, placing it moderately above average difficulty. |
| Spec | 7.06f Integer programming: branch-and-bound method7.07a Simplex tableau: initial setup in standard format |
| b.v. | \(x\) | \(y\) | \(z\) | \(s _ { 1 }\) | \(s _ { 2 }\) | \(s _ { 3 }\) | \(t _ { 1 }\) | Value |
| \(s _ { 1 }\) | 2 | 2 | 1 | 1 | 0 | 0 | 0 | 25 |
| \(s _ { 2 }\) | 1 | 4 | 0 | 0 | 1 | 0 | 0 | 15 |
| \(t _ { 1 }\) | 1 | 0 | 0 | 0 | 0 | -1 | 1 | 3 |
| \(P\) | \(- ( 3 + M )\) | -2 | -2 | 0 | 0 | M | 0 | \(- 3 M\) |
| b.v. | \(x\) | \(y\) | \(z\) | \(s _ { 1 }\) | \(s _ { 2 }\) | \(s _ { 3 }\) | \(t _ { 1 }\) | Value |
| \(s _ { 1 }\) | 0 | 2 | 1 | 1 | 0 | 2 | -2 | 19 |
| \(s _ { 2 }\) | 0 | 4 | 0 | 0 | 1 | 1 | -1 | 12 |
| \(x\) | 1 | 0 | 0 | 0 | 0 | -1 | 1 | 3 |
| P | 0 | -2 | -2 | 0 | 0 | -3 | \(3 +\) M | 9 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Simplex can only work with \(\leq\) constraints | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(M\) is an arbitrary large real number | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(x \geq 3 \Rightarrow x - s_3 + t_1 = 3\) where \(s_3\) is a surplus variable and \(t_1\) is an artificial variable | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(P = 3x + 2y + 2z - Mt_1\) and substituting \(t_1 = 3 - x + s_3\) | M1 | |
| \(\Rightarrow P - (3+M)x - 2y - 2z + Ms_3 = -3M\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| First tableau with correct structure | M1 | |
| \(s_3\): row \(= \frac{1}{2}R_1\); \(r_1 = (1/2)R_1\) giving values \(0,1,\frac{1}{2},\frac{1}{2},0,1,-1,\frac{19}{2}\) | A1 | |
| \(s_2\) row: \(R_2 - r_1\) giving \(0,3,-\frac{1}{2},-\frac{1}{2},1,0,0,\frac{5}{2}\) | A1 | |
| Second tableau with correct structure | M1 | |
| \(z\) row: \(r_1 = 2R_1\) giving \(0,2,1,1,0,2,-2,19\) | A1 | |
| \(x\) row: \(R_3 - (1/2)r_1\) giving \(1,0,0,0,0,-1,1,3\) | ||
| \(P\) row: \(R_4 + (1/2)r_1\) giving \(0,2,0,2,0,1,M-1,47\) | B1 | AO 2.4 |
| \(P = 47,\ x = 3,\ y = 0,\ z = 19\) | B1ft | Follow through from their tableau |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Correctly states the limitation of the Simplex model – Simplex involves iterations which allow movement from one vertex in the feasible region to another vertex. If all constraints are of the form \(\leq\) this means the origin is always a feasible solution and can act as the initial starting point. However, the constraint \(x \geqslant 3\) means that the origin is not feasible and so the algorithm is unable to begin. | B1 | Must correctly identify why \(x \geqslant 3\) prevents the algorithm from starting |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Correct description using appropriate mathematical language | B1 | cao - must include the words 'arbitrary', 'large' and 'real' |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Correctly states both the inequality \(x \geq 3\) and the equation \(x - s_3 + t_1 = 3\) together with an explanation of the meaning behind the variables \(s_3\) and \(t_1\) | B1 | Must state both the inequality and equation with explanation of variables |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(P = 3x + 2y + 2z - Mt_1\) and substitutes their expression for \(t_1\) | M1 | Must substitute expression for \(t_1\) |
| Correct mathematical argument including sufficient detail to allow the line of reasoning to be followed to the correct conclusion | A1 | Dependent on previous B mark in (c) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Correct pivot located, attempt to divide row | M1 | If negative value used then no marks |
| Pivot row correct (including change of b.v.) and row operations used at least once, one of columns \(y, z, s_1, t_1\) or Value correct | A1 | |
| cao for values (ignore b.v. column and Row Ops) | A1 | |
| Pivot row consistent (following their previous table) including change of b.v. and row operations used at least once, one of columns \(y, s_1, s_3, t_1\) or Value correct | M1 | |
| cao on final table (ignore Row Ops) | A1 | |
| The correct Row Operations explained either in terms of the 'old' or 'new' pivot rows | B1 | |
| Correctly states the final values of \(P\), \(x\), \(y\) and \(z\) from their correct corresponding rows of the final table | B1ft | ft from correct final table |
# Question 7:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Simplex can only work with $\leq$ constraints | B1 | |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| $M$ is an arbitrary large real number | B1 | |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| $x \geq 3 \Rightarrow x - s_3 + t_1 = 3$ where $s_3$ is a surplus variable and $t_1$ is an artificial variable | B1 | |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| $P = 3x + 2y + 2z - Mt_1$ and substituting $t_1 = 3 - x + s_3$ | M1 | |
| $\Rightarrow P - (3+M)x - 2y - 2z + Ms_3 = -3M$ | A1 | |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| First tableau with correct structure | M1 | |
| $s_3$: row $= \frac{1}{2}R_1$; $r_1 = (1/2)R_1$ giving values $0,1,\frac{1}{2},\frac{1}{2},0,1,-1,\frac{19}{2}$ | A1 | |
| $s_2$ row: $R_2 - r_1$ giving $0,3,-\frac{1}{2},-\frac{1}{2},1,0,0,\frac{5}{2}$ | A1 | |
| Second tableau with correct structure | M1 | |
| $z$ row: $r_1 = 2R_1$ giving $0,2,1,1,0,2,-2,19$ | A1 | |
| $x$ row: $R_3 - (1/2)r_1$ giving $1,0,0,0,0,-1,1,3$ | | |
| $P$ row: $R_4 + (1/2)r_1$ giving $0,2,0,2,0,1,M-1,47$ | B1 | AO 2.4 |
| $P = 47,\ x = 3,\ y = 0,\ z = 19$ | B1ft | Follow through from their tableau |
# Question 7:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Correctly states the limitation of the Simplex model – Simplex involves iterations which allow movement from one vertex in the feasible region to another vertex. If all constraints are of the form $\leq$ this means the origin is always a feasible solution and can act as the initial starting point. However, the constraint $x \geqslant 3$ means that the origin is not feasible and so the algorithm is unable to begin. | B1 | Must correctly identify why $x \geqslant 3$ prevents the algorithm from starting |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Correct description using appropriate mathematical language | B1 | cao - must include the words 'arbitrary', 'large' and 'real' |
## Part (c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Correctly states both the inequality $x \geq 3$ and the equation $x - s_3 + t_1 = 3$ together with an explanation of the meaning behind the variables $s_3$ and $t_1$ | B1 | Must state both the inequality and equation with explanation of variables |
## Part (d):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $P = 3x + 2y + 2z - Mt_1$ and substitutes their expression for $t_1$ | M1 | Must substitute expression for $t_1$ |
| Correct mathematical argument including sufficient detail to allow the line of reasoning to be followed to the correct conclusion | A1 | Dependent on previous B mark in (c) |
## Part (e):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Correct pivot located, attempt to divide row | M1 | If negative value used then no marks |
| Pivot row correct (including change of b.v.) and row operations used at least once, one of columns $y, z, s_1, t_1$ or Value correct | A1 | |
| cao for values (ignore b.v. column and Row Ops) | A1 | |
| Pivot row consistent (following their previous table) including change of b.v. and row operations used at least once, one of columns $y, s_1, s_3, t_1$ or Value correct | M1 | |
| cao on final table (ignore Row Ops) | A1 | |
| The correct Row Operations explained either in terms of the 'old' or 'new' pivot rows | B1 | |
| Correctly states the final values of $P$, $x$, $y$ and $z$ from their correct corresponding rows of the final table | B1ft | ft from correct final table |7. A linear programming problem in $x , y$ and $z$ is described as follows.
Maximise $P = 3 x + 2 y + 2 z$\\
subject to
$$\begin{aligned}
& 2 x + 2 y + z \leqslant 25 \\
& x + 4 y \leqslant 15 \\
& x \geqslant 3
\end{aligned}$$
\begin{enumerate}[label=(\alph*)]
\item Explain why the Simplex algorithm cannot be used to solve this linear programming problem.
The big-M method is to be used to solve this linear programming problem.
\item Define, in this context, what M represents. You must use correct mathematical language in your answer.
The initial tableau for a big-M solution to the problem is shown below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $z$ & $s _ { 1 }$ & $s _ { 2 }$ & $s _ { 3 }$ & $t _ { 1 }$ & Value \\
\hline
$s _ { 1 }$ & 2 & 2 & 1 & 1 & 0 & 0 & 0 & 25 \\
\hline
$s _ { 2 }$ & 1 & 4 & 0 & 0 & 1 & 0 & 0 & 15 \\
\hline
$t _ { 1 }$ & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 3 \\
\hline
$P$ & $- ( 3 + M )$ & -2 & -2 & 0 & 0 & M & 0 & $- 3 M$ \\
\hline
\end{tabular}
\end{center}
\item Explain clearly how the equation represented in the b.v. $t _ { 1 }$ row was derived.
\item Show how the equation represented in the b.v. $P$ row was derived.
The tableau obtained from the first iteration of the big-M method is shown below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $z$ & $s _ { 1 }$ & $s _ { 2 }$ & $s _ { 3 }$ & $t _ { 1 }$ & Value \\
\hline
$s _ { 1 }$ & 0 & 2 & 1 & 1 & 0 & 2 & -2 & 19 \\
\hline
$s _ { 2 }$ & 0 & 4 & 0 & 0 & 1 & 1 & -1 & 12 \\
\hline
$x$ & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 3 \\
\hline
P & 0 & -2 & -2 & 0 & 0 & -3 & $3 +$ M & 9 \\
\hline
\end{tabular}
\end{center}
\item Solve the linear programming problem, starting from this second tableau. You must
\begin{itemize}
\item give a detailed explanation of your method by clearly stating the row operations you use and
\item state the solution by deducing the final values of $P , x , y$ and $z$.
\end{itemize}
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 Q7 [12]}}