| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2022 |
| Session | June |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Linear Programming |
| Type | Simplex tableau setup |
| Difficulty | Standard +0.3 This is a standard Further Maths Decision 1 simplex algorithm question requiring tableau setup, reading values, and performing one iteration with a parameter k. While it involves more steps than basic C1/C2 questions, the techniques are routine for FD1 students: setting up slack variables, identifying pivot elements, and performing row operations. The parameter k adds mild complexity but the method is algorithmic rather than requiring novel insight. |
| Spec | 7.06d Graphical solution: feasible region, two variables7.07a Simplex tableau: initial setup in standard format |
| b.v. | \(x\) | \(y\) | \(S _ { 1 }\) | \(s _ { 2 }\) | \(S _ { 3 }\) | \(s _ { 4 }\) | Value |
| \(s _ { 1 }\) | 0 | 0 | 1 | \(- \frac { 3 } { 5 }\) | 0 | \(\frac { 1 } { 5 }\) | 1 |
| \(x\) | 1 | 0 | 0 | \(\frac { 1 } { 5 }\) | 0 | \(- \frac { 2 } { 5 }\) | 2 |
| \(S _ { 3 }\) | 0 | 0 | 0 | \(- \frac { 11 } { 5 }\) | 1 | \(\frac { 12 } { 5 }\) | 22 |
| \(y\) | 0 | 1 | 0 | \(\frac { 2 } { 5 }\) | 0 | \(\frac { 1 } { 5 }\) | 5 |
| \(P\) | 0 | 0 | 0 | \(\frac { 1 } { 5 } + \frac { 2 } { 5 } k\) | 0 | \(- \frac { 2 } { 5 } + \frac { 1 } { 5 } k\) | \(5 k + 2\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(x+y \leq 8 \Rightarrow x+y+s_1=8\) | M1 | Correctly re-writing any two inequalities as equations with slack variables |
| \(x+2y \leq 12 \Rightarrow x+2y+s_2=12\) | A1 | Correctly re-writing all inequalities as equations with slack variables |
| \(7x+2y \leq 46 \Rightarrow 7x+2y+s_3=46\) | ||
| \(y \leq 2x+1 \Rightarrow -2x+y+s_4=1\) | B1 | Correctly re-writes objective function \(P=x+ky \Rightarrow P-x-ky=0\) |
| Initial tableau with all correct rows | M1 | Any two rows correct including consistent b.v. column entries, or any three rows correct (ignoring b.v. column) |
| Complete correct initial tableau | A1 | cao including consistent b.v. column — candidate's row order and slack variable letter may differ; correct tableau implies full marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(x=2,\ y=5,\ s_1=1,\ s_2=0,\ s_3=22,\ s_4=0\ (P=5k+2)\) | B1 | cao for \(x, y, s_1, s_2, s_3, s_4\) only (ignore any mention of \(P\)) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Pivot row correct including change of b.v. | B1 | Pivot row completely correct including change of b.v. |
| Row operations: \(5r1\); \(r2+0.4R1\); \(r3-2.4R1\); \(r4-0.2R1\); \(r5-(0.2k-0.4)R1\) | M1 | All values in one non-pivot row correct (ignore b.v. and Row Ops columns), or one of the 'non zero and one' columns (\(s_1, s_2\) or Value) correct |
| Second tableau rows correct | A1 | Row operations used correctly at least twice — two of the 'non zero and one' columns correct |
| Second tableau fully correct | A1 | cao all values including b.v. column |
| Row operations stated | B1 | Correct row operations stated (alternatives: \(5r1\); \(r2+2r1\); \(r3-12r1\); \(r4-r1\); \(r5-(k-2)r1\)) |
| Optimal value of \(P\) is \(4k+4\) (at \(x=y=4\)) | M1 | Optimal value as linear expression in \(k\) stated correctly following third iteration |
| Second iteration not optimal \(\Rightarrow -\frac{2}{5}+\frac{1}{5}k < 0 \therefore k<2\) | B1 | Correctly inferring \(k<2\) either from \(-\frac{2}{5}+\frac{1}{5}k<0\) or from \(4k+4>5k+2\) |
| Third iteration optimal \(\Rightarrow 2-k \geq 0\) and \(k-1 \geq 0\) \((\therefore k \geq 1)\) | dM1 | Considering at least two linear expressions in \(k\) from objective row after third iteration \(\geq 0\) (dependent on previous M mark) |
| \(1 \leq k < 2 \Rightarrow 8 \leq P < 12\) | A1 | cao for range of values of \(P\) — dependent on correct objective row and previous three marks |
# Question 7:
## Part (a)
| Answer/Working | Mark | Guidance |
|---|---|---|
| $x+y \leq 8 \Rightarrow x+y+s_1=8$ | M1 | Correctly re-writing any two inequalities as equations with slack variables |
| $x+2y \leq 12 \Rightarrow x+2y+s_2=12$ | A1 | Correctly re-writing all inequalities as equations with slack variables |
| $7x+2y \leq 46 \Rightarrow 7x+2y+s_3=46$ | | |
| $y \leq 2x+1 \Rightarrow -2x+y+s_4=1$ | B1 | Correctly re-writes objective function $P=x+ky \Rightarrow P-x-ky=0$ |
| Initial tableau with all correct rows | M1 | Any two rows correct including consistent b.v. column entries, or any three rows correct (ignoring b.v. column) |
| Complete correct initial tableau | A1 | cao including consistent b.v. column — candidate's row order and slack variable letter may differ; correct tableau implies full marks |
## Part (b)
| Answer/Working | Mark | Guidance |
|---|---|---|
| $x=2,\ y=5,\ s_1=1,\ s_2=0,\ s_3=22,\ s_4=0\ (P=5k+2)$ | B1 | cao for $x, y, s_1, s_2, s_3, s_4$ only (ignore any mention of $P$) |
## Part (c)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Pivot row correct including change of b.v. | B1 | Pivot row completely correct including change of b.v. |
| Row operations: $5r1$; $r2+0.4R1$; $r3-2.4R1$; $r4-0.2R1$; $r5-(0.2k-0.4)R1$ | M1 | All **values** in one non-pivot row correct (ignore b.v. and Row Ops columns), or one of the 'non zero and one' columns ($s_1, s_2$ or Value) correct |
| Second tableau rows correct | A1 | Row operations used correctly at least twice — two of the 'non zero and one' columns correct |
| Second tableau fully correct | A1 | cao all values including b.v. column |
| Row operations stated | B1 | Correct row operations stated (alternatives: $5r1$; $r2+2r1$; $r3-12r1$; $r4-r1$; $r5-(k-2)r1$) |
| Optimal value of $P$ is $4k+4$ (at $x=y=4$) | M1 | Optimal value as linear expression in $k$ stated correctly following third iteration |
| Second iteration not optimal $\Rightarrow -\frac{2}{5}+\frac{1}{5}k < 0 \therefore k<2$ | B1 | Correctly inferring $k<2$ either from $-\frac{2}{5}+\frac{1}{5}k<0$ or from $4k+4>5k+2$ |
| Third iteration optimal $\Rightarrow 2-k \geq 0$ and $k-1 \geq 0$ $(\therefore k \geq 1)$ | dM1 | Considering at least two linear expressions in $k$ from objective row after third iteration $\geq 0$ (dependent on previous M mark) |
| $1 \leq k < 2 \Rightarrow 8 \leq P < 12$ | A1 | cao for range of values of $P$ — dependent on correct objective row and previous three marks |7.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-12_885_1130_210_456}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}
Figure 5 shows the constraints of a linear programming problem in $x$ and $y$ where $R$ is the feasible region.
The objective is to maximise $P = x + k y$, where $k$ is a positive constant.\\
The optimal vertex of $R$ is to be found using the Simplex algorithm.
\begin{enumerate}[label=(\alph*)]
\item Set up an initial tableau for solving this linear programming problem using the Simplex algorithm.
After two iterations of the Simplex algorithm a possible tableau $T$ is
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
b.v. & $x$ & $y$ & $S _ { 1 }$ & $s _ { 2 }$ & $S _ { 3 }$ & $s _ { 4 }$ & Value \\
\hline
$s _ { 1 }$ & 0 & 0 & 1 & $- \frac { 3 } { 5 }$ & 0 & $\frac { 1 } { 5 }$ & 1 \\
\hline
$x$ & 1 & 0 & 0 & $\frac { 1 } { 5 }$ & 0 & $- \frac { 2 } { 5 }$ & 2 \\
\hline
$S _ { 3 }$ & 0 & 0 & 0 & $- \frac { 11 } { 5 }$ & 1 & $\frac { 12 } { 5 }$ & 22 \\
\hline
$y$ & 0 & 1 & 0 & $\frac { 2 } { 5 }$ & 0 & $\frac { 1 } { 5 }$ & 5 \\
\hline
$P$ & 0 & 0 & 0 & $\frac { 1 } { 5 } + \frac { 2 } { 5 } k$ & 0 & $- \frac { 2 } { 5 } + \frac { 1 } { 5 } k$ & $5 k + 2$ \\
\hline
\end{tabular}
\end{center}
\item State the value of each variable after the second iteration.\\
(1)
It is given that $T$ does not give an optimal solution to the linear programming problem.\\
After a third iteration of the Simplex algorithm the resulting tableau does give an optimal solution to the problem.
\item Perform the third iteration of the Simplex algorithm and hence determine the range of possible values for $P$. You should state the row operations you use and make your method and working clear.\\
(9)
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2022 Q7 [15]}}