| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Perform one Simplex iteration |
| Difficulty | Moderate -0.5 This is a routine mechanical application of the Simplex algorithm requiring identification of pivot column (given), pivot row (via ratio test), and row operations. While it requires careful arithmetic across multiple steps, it follows a completely standard procedure taught in D2 with no problem-solving or insight needed beyond executing the algorithm correctly. |
| Spec | 7.07b Simplex iterations: pivot choice and row operations7.07c Interpret simplex: values of variables, slack, and objective7.07d Simplex terminology: basic feasible solution, basic/non-basic variable |
| Basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value |
| \(r\) | 5 | \(\frac { 1 } { 2 }\) | 0 | 1 | 0 | 0 | 5 |
| \(s\) | 1 | -2 | 4 | 0 | 1 | 0 | 3 |
| \(t\) | 8 | 4 | 6 | 0 | 0 | 1 | 6 |
| \(P\) | -5 | -7 | -4 | 0 | 0 | 0 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| (a) Tableau: \(\begin{array}{c\ | cccccc} \text{b.v} & x & y & z & r & s & t & \text{value} & 0 \text{ values} \\ r & 5 & \frac{1}{2} & 0 & 1 & 0 & 0 & 5 & 10 \\ s & 1 & -2 & 4 & 0 & 1 & 0 & 3 & -\frac{3}{2} \\ t & 8 & 4 & 6 & 0 & 0 & 1 & 6 & \frac{3}{2} \leftarrow \\ P & -5 & -7 & -4 & 0 & 0 & 0 & 0 & \end{array}\) | 1M1 1A1 |
| \(\begin{array}{c\ | cccccc} \text{b.v.} & x & y & z & r & s & t & \text{value} & \text{Row ops} \\ r & 4 & 0 & -\frac{3}{4} & 1 & 0 & -\frac{1}{8} & \frac{17}{4} & R1 - \frac{1}{2}R3 \\ s & 5 & 0 & 7 & 0 & 1 & \frac{1}{2} & 6 & R2 + 2R3 \\ y & 2 & 1 & \frac{3}{2} & 0 & 0 & \frac{1}{4} & \frac{3}{2} & R3 \div 4 \\ P & 9 & 0 & \frac{13}{2} & 0 & 0 & \frac{7}{4} & \frac{21}{2} & R4 + 7R3 \end{array}\) | 2M1 2A1 B1 |
| (b) \(P + 9x + \frac{13}{2}z + \frac{7}{4}t = \frac{21}{2}\) | M1 A1 | 2 |
| (c) \(P = \frac{21}{2} - 9x - \frac{13}{2}z - \frac{7}{4}t\), so increasing x or z or t would decrease P | B1 | 1 |
| Total 8 |
| Answer/Working | Marks | Guidance |
|---|---|---|
| **(a)** Tableau: $\begin{array}{c\|cccccc} \text{b.v} & x & y & z & r & s & t & \text{value} & 0 \text{ values} \\ r & 5 & \frac{1}{2} & 0 & 1 & 0 & 0 & 5 & 10 \\ s & 1 & -2 & 4 & 0 & 1 & 0 & 3 & -\frac{3}{2} \\ t & 8 & 4 & 6 & 0 & 0 & 1 & 6 & \frac{3}{2} \leftarrow \\ P & -5 & -7 & -4 & 0 & 0 & 0 & 0 & \end{array}$ | 1M1 1A1 | a1M1: Correct pivot located, attempt to divide row. If choosing negative number as pivot M0B0M0 a1A1: pivot row correct including change of b.v. |
| $\begin{array}{c\|cccccc} \text{b.v.} & x & y & z & r & s & t & \text{value} & \text{Row ops} \\ r & 4 & 0 & -\frac{3}{4} & 1 & 0 & -\frac{1}{8} & \frac{17}{4} & R1 - \frac{1}{2}R3 \\ s & 5 & 0 & 7 & 0 & 1 & \frac{1}{2} & 6 & R2 + 2R3 \\ y & 2 & 1 & \frac{3}{2} & 0 & 0 & \frac{1}{4} & \frac{3}{2} & R3 \div 4 \\ P & 9 & 0 & \frac{13}{2} & 0 & 0 & \frac{7}{4} & \frac{21}{2} & R4 + 7R3 \end{array}$ | 2M1 2A1 B1 | a2M1: (ft) Correct row operations used at least once, column x, z, t or value correct. a2A1: CAO on the three non-pivot rows. a1B1: Row operations CAO – allow if given in terms of old row 3. |
| **(b)** $P + 9x + \frac{13}{2}z + \frac{7}{4}t = \frac{21}{2}$ | M1 A1 | **2** |
| **(c)** $P = \frac{21}{2} - 9x - \frac{13}{2}z - \frac{7}{4}t$, so increasing x or z or t would decrease P | B1 | **1** |
| | | **Total 8** |
**Notes for question 4:**
- a1M1: Correct pivot located, attempt to divide row. If choosing negative number as pivot M0B0M0
- a1A1: pivot row correct including change of b.v.
- a1B1: Row operations CAO – allow if given in terms of old row 3.
- a2M1: (ft) Correct row operations used at least once, column x, z, t or value correct.
- a2A1: CAO on the three non-pivot rows.
- b1M1: One equal sign, P, terms in x, z, t plus a non-zero number term.
- c1B1: Explanation, must refer to increasing x, z and t, condone no ref to x = z = t = 0, must have correct signs in equation in (b). Do not accept 'no negatives in profit row' o.e. alone.
---4. The tableau below is the initial tableau for a maximising linear programming problem in $x , y$ and $z$ which is to be solved.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
Basic variable & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & 5 & $\frac { 1 } { 2 }$ & 0 & 1 & 0 & 0 & 5 \\
\hline
$s$ & 1 & -2 & 4 & 0 & 1 & 0 & 3 \\
\hline
$t$ & 8 & 4 & 6 & 0 & 0 & 1 & 6 \\
\hline
$P$ & -5 & -7 & -4 & 0 & 0 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Starting by increasing $y$, perform one complete iteration of the simplex algorithm, to obtain tableau T. State the row operations you use.
\item Write down the profit equation given by tableau T .
\item Use the profit equation from part (b) to explain why tableau T is optimal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2012 Q4 [8]}}