| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Complete Simplex solution |
| Difficulty | Standard +0.8 This is a standard Simplex algorithm question requiring multiple iterations with three variables. While the procedure is algorithmic and well-practiced in D2, it demands careful arithmetic across several tableaux, correct pivot selection, and systematic row operations. The multi-step nature and potential for computational errors place it above average difficulty, though it remains a textbook application without novel problem-solving. |
| Spec | 7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations |
| basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value |
| \(r\) | 12 | 4 | 5 | 1 | 0 | 0 | 246 |
| \(s\) | 9 | 6 | 3 | 0 | 1 | 0 | 153 |
| \(t\) | 5 | 2 | - 2 | 0 | 0 | 1 | 171 |
| \(P\) | - 2 | - 4 | - 3 | 0 | 0 | 0 | 0 |
| b.v. | x | y | z | r | s | t | Value | Row operations |
| b.v. | x | y | z | r | s | t | Value | Row operations |
| b.v. | x | y | z | r | s | t | Value | Row operations |
| b.v. | x | y | z | r | s | t | Value | Row operations |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(P - 2x - 4y - 3z = 0\) (o.e.) | B2,0 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(12x + 4y + 5z \leq 246\) | B1 | |
| \(9x + 6y + 3z \leq 153\) | B1 | |
| \(5x + 2y - 2z \leq 171\) | B1 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial tableau with basic variables \(r, s, t, P\) | ||
| Pivot on \(y\) column (circled 6): \(R_2 \div 6\); \(R_1 - 4R_2\); \(R_3 - 2R_2\); \(R_4 + 4R_2\) | M1A1, M1A1ft, B1ft | |
| Giving \(r: 6,0,3,1,-\frac{2}{3},0,144\); \(y: \frac{3}{2},1,\frac{1}{2},0,\frac{1}{6},0,25.5\); \(t: 2,0,-3,0,-\frac{1}{3},1,120\); \(P: 4,0,-1,0,\frac{2}{3},0,102\) | ||
| Pivot on \(z\) column: \(R_1 \div 3\); \(R_2 - \frac{1}{2}R_1\); \(R_3 + 3R_1\); \(R_4 + R_1\) | M1A1, M1A1 | |
| Giving \(z: 2,0,1,\frac{1}{3},-\frac{2}{9},0,48\); \(y: \frac{1}{2},1,0,-\frac{1}{6},\frac{5}{18},0,1.5\); \(t: 8,0,0,1,-1,1,264\); \(P: 6,0,0,\frac{1}{3},\frac{4}{9},0,150\) | 9 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(P=150\), \(x=0\), \(y=1.5\), \(z=48\); \(r=0\), \(s=0\), \(t=264\) | M1A1ft, A1ft | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (The third constraint) \(t \neq 0\) | B1ft | 1 |
# Question 8:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $P - 2x - 4y - 3z = 0$ (o.e.) | B2,0 | 2 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $12x + 4y + 5z \leq 246$ | B1 | |
| $9x + 6y + 3z \leq 153$ | B1 | |
| $5x + 2y - 2z \leq 171$ | B1 | 3 |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial tableau with basic variables $r, s, t, P$ | | |
| Pivot on $y$ column (circled 6): $R_2 \div 6$; $R_1 - 4R_2$; $R_3 - 2R_2$; $R_4 + 4R_2$ | M1A1, M1A1ft, B1ft | |
| Giving $r: 6,0,3,1,-\frac{2}{3},0,144$; $y: \frac{3}{2},1,\frac{1}{2},0,\frac{1}{6},0,25.5$; $t: 2,0,-3,0,-\frac{1}{3},1,120$; $P: 4,0,-1,0,\frac{2}{3},0,102$ | | |
| Pivot on $z$ column: $R_1 \div 3$; $R_2 - \frac{1}{2}R_1$; $R_3 + 3R_1$; $R_4 + R_1$ | M1A1, M1A1 | |
| Giving $z: 2,0,1,\frac{1}{3},-\frac{2}{9},0,48$; $y: \frac{1}{2},1,0,-\frac{1}{6},\frac{5}{18},0,1.5$; $t: 8,0,0,1,-1,1,264$; $P: 6,0,0,\frac{1}{3},\frac{4}{9},0,150$ | | 9 |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $P=150$, $x=0$, $y=1.5$, $z=48$; $r=0$, $s=0$, $t=264$ | M1A1ft, A1ft | 3 |
## Part (e)
| Answer | Marks | Guidance |
|--------|-------|----------|
| (The third constraint) $t \neq 0$ | B1ft | 1 |
---8. The tableau below is the initial tableau for a linear programming problem in $x , y$ and $z$. The objective is to maximise the profit, $P$.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | }
\hline
basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & 12 & 4 & 5 & 1 & 0 & 0 & 246 \\
\hline
$s$ & 9 & 6 & 3 & 0 & 1 & 0 & 153 \\
\hline
$t$ & 5 & 2 & - 2 & 0 & 0 & 1 & 171 \\
\hline
$P$ & - 2 & - 4 & - 3 & 0 & 0 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
Using the information in the tableau, write down
\begin{enumerate}[label=(\alph*)]
\item the objective function,
\item the three constraints as inequalities with integer coefficients.
Taking the most negative number in the profit row to indicate the pivot column at each stage,
\item solve this linear programming problem. Make your method clear by stating the row operations you use.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & x & y & z & r & s & t & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & x & y & z & r & s & t & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & x & y & z & r & s & t & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & x & y & z & r & s & t & Value & Row operations \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
\end{tabular}
\end{center}
\item State the final values of the objective function and each variable.
\item One of the constraints is not at capacity. Explain how it can be identified.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2007 Q8 [18]}}