| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Write constraints from tableau |
| Difficulty | Moderate -0.3 This is a standard simplex algorithm question requiring routine application of the method. Parts (a)-(b) involve reading the tableau (trivial), part (c) requires mechanical pivot operations following a prescribed rule, and parts (d)-(e) involve interpreting the final tableau. While lengthy (18 marks), it requires no problem-solving insight—just careful execution of a learned algorithm, making it slightly easier than average. |
| Spec | 7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations7.07c Interpret simplex: values of variables, slack, and objective |
| Answer | Marks |
|---|---|
| B2, 0 (1) |
| Answer | Marks |
|---|---|
| B1 / B1 / B1 (2) |
| Answer | Marks |
|---|---|
| m1 A1 / m1 B1^ / B1' |
| Answer | Marks |
|---|---|
| m1 A1^ / A1^ (2) |
| Answer | Marks |
|---|---|
| B1' (1) |
## (a)
$P - 2x - 4y - 3z = 0$ (o.e.)
| B2, 0 (1) |
## (b)
$12x + 4y + 5z \leq 246$
$9x + 6y + 3z \leq 152$
$5x + 2y - 2z \leq 171$
| B1 / B1 / B1 (2) |
## (c)
[Simplex tableaux showing initial tableau and subsequent iterations with row operations]
| m1 A1 / m1 B1^ / B1' |
## (d)
$P = 150$, $x = 0$, $w = 1.5$, $z = 4.8$
$f = 0$, $s = 0$, $k = 264$
| m1 A1^ / A1^ (2) |
## (e)
(The third constraint) $E \neq 0$
| B1' (1) |
---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{array}{c|c|c|c|c|c|c|c}
\text{basic variable} & x & y & z & r & s & t & \text{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
\end{array}$$
Using the information in the tableau, write down
\begin{enumerate}[label=(\alph*)]
\item the objective function, [2]
\item the three constraints as inequalities with integer coefficients. [3]
\end{enumerate}
Taking the most negative number in the profit row to indicate the pivot column at each stage,
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item solve this linear programming problem. Make your method clear by stating the row operations you use. [9]
\item State the final values of the objective function and each variable. [3]
\end{enumerate}
One of the constraints is not at capacity.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{4}
\item Explain how it can be identified. [1]
\end{enumerate}
(Total 18 marks)
\hfill \mbox{\textit{Edexcel D1 2007 Q7 [18]}}