Edexcel FD1 2020 June — Question 7 17 marks

Exam BoardEdexcel
ModuleFD1 (Further Decision 1)
Year2020
SessionJune
Marks17
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicThe Simplex Algorithm
TypeTwo-stage Simplex method
DifficultyChallenging +1.2 This is a standard two-stage simplex question from Further Maths Decision module requiring tableau interpretation, constraint formulation, and completing the auxiliary row. While it involves multiple parts and fractional arithmetic, it follows a completely routine algorithmic procedure with no novel problem-solving. The techniques are mechanical applications of the simplex method taught directly in FD1, making it moderately easier than average A-level questions which typically require more conceptual insight.
Spec7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations
7. A maximisation linear programming problem in \(x , y\) and \(z\) is to be solved using the two-stage simplex method. The partially completed initial tableau is shown below.
Basic variable\(x\)\(y\)\(z\)\(S _ { 1 }\)\(S _ { 2 }\)\(S _ { 3 }\)\(a _ { 1 }\)\(a _ { 2 }\)Value
\(S _ { 1 }\)1231000045
\(a _ { 1 }\)3200-10109
\(a _ { 2 }\)-10400-1014
\(P\)-2-1-3000000
A
  1. Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities.
  2. Complete the bottom row of Table 1 in the answer book. You should make your method and working clear. The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.
    Basic variable\(x\)\(y\)\(z\)\(S _ { 1 }\)\(S _ { 2 }\)\(S _ { 3 }\)\(a _ { 1 }\)\(a _ { 2 }\)Value
    \(S _ { 1 }\)0\(\frac { 5 } { 6 }\)01\(\frac { 7 } { 12 }\)\(\frac { 3 } { 4 }\)\(- \frac { 7 } { 12 }\)\(- \frac { 3 } { 4 }\)\(\frac { 147 } { 4 }\)
    \(x\)1\(\frac { 2 } { 3 }\)00\(- \frac { 1 } { 3 }\)0\(\frac { 1 } { 3 }\)03
    \(z\)0\(\frac { 1 } { 6 }\)10\(- \frac { 1 } { 12 }\)\(- \frac { 1 } { 4 }\)\(\frac { 1 } { 12 }\)\(\frac { 1 } { 4 }\)\(\frac { 7 } { 4 }\)
    \(P\)0\(\frac { 5 } { 6 }\)00\(- \frac { 11 } { 12 }\)\(- \frac { 3 } { 4 }\)\(\frac { 11 } { 12 }\)\(\frac { 3 } { 4 }\)\(\frac { 45 } { 4 }\)
    A000000110
    1. Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem.
    2. Write down the basic feasible solution for the second stage.
  4. Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method, to obtain a new tableau, \(T\). Make your method clear by stating the row operations you use.
    1. Explain, using \(T\), whether or not an optimal solution to the original linear programming problem has been found.
    2. Write down the value of the objective function.
    3. State the values of the basic variables.
Question 7:
Part (a):
AnswerMarks Guidance
Answer/WorkingMark Guidance
Maximise \((P =) 2x + y + 3z\)B1 CAO – including maximise (or max)
\(x + 2y + 3z \leq 45\)B1 CAO (oe)
\(3x + 2y \geq 9\)B1 CAO (oe)
\(-x + 4z \geq 4\)B1 CAO (oe)
Total(4)
Part (b):
AnswerMarks Guidance
Answer/WorkingMark Guidance
\(A = -(a_1 + a_2) \Rightarrow -(9-3x-2y+s_2+4+x-4z+s_3)\)M1 Setting up new objective and substituting for \(a_1\) and \(a_2\)
\(A - 2x - 2y - 4z + s_2 + s_3 = -13\), bottom row: \(A \mid -2 \mid -2 \mid -4 \mid 0 \mid 1 \mid 1 \mid 0 \mid 0 \mid -13\)A1 Correct values substituted into Table 1
Total(2)
Part (c)(i):
AnswerMarks Guidance
Answer/WorkingMark Guidance
In the given tableau the value of objective \(A\) is equal to zero, indicating a basic feasible solution has been foundB1 CAO – mention that \(A = 0\)
Total(1)
Part (c)(ii):
AnswerMarks Guidance
Answer/WorkingMark Guidance
\(x=3,\ y=0,\ z=\dfrac{7}{4},\ s_1=\dfrac{147}{4},\ s_2=s_3=0\)B1 At least three values stated correctly
B1All six values correct (ignore values for \(a_1, a_2\) and \(P\))
Total(2)
Part (d):
AnswerMarks Guidance
Answer/WorkingMark Guidance
Pivot correctly located, attempt to divide rowM1 Correct pivot located
Pivot row correct including change of b.v.A1
All values in one non-pivot row correct or one of the non-zero and one columns (\(y, s_1, s_3\) or value) correct following through choice of pivot from column \(s_2\) or \(s_3\)M1
Row operations used correctly at least twice; two of non-zero and one columns (\(y, s_1, s_3\) or value) correctA1
CAO all values and row operations correctly stated (allow row operations given in terms of old row 1 – ignore b.v. column for this mark)A1
Final tableau:
AnswerMarks Guidance
b.v.\(x\) \(y\)
\(s_2\)0 \(\frac{10}{7}\)
\(x\)1 \(\frac{8}{7}\)
\(z\)0 \(\frac{2}{7}\)
\(P\)0 \(\frac{15}{7}\)
Total(5)
Part (e)(i):
AnswerMarks Guidance
Answer/WorkingMark Guidance
Yes, optimal solution found as there are no negative values in the objective (\(P\)) rowB1 Correct reasoning; or using \(P = 69 - \frac{15}{7}y - \frac{11}{7}s_1 - \frac{3}{7}s_3\) and mentioning increasing \(y, s_1, s_3\) would decrease \(P\) (oe)
Total(1)
Part (e)(ii):
AnswerMarks Guidance
Answer/WorkingMark Guidance
\(P = 69\)B1ft Their value of \(P\) – dependent on both M marks in (d)
Total(1)
Part (e)(iii):
AnswerMarks Guidance
Answer/WorkingMark Guidance
\(s_2 = 63,\ x = 24,\ z = 7\)B1ft Their values of basic variables only – dependent on both M marks in (d)
Total(1) 
# Question 7:

## Part (a):

| Answer/Working | Mark | Guidance |
|---|---|---|
| Maximise $(P =) 2x + y + 3z$ | B1 | CAO – including maximise (or max) |
| $x + 2y + 3z \leq 45$ | B1 | CAO (oe) |
| $3x + 2y \geq 9$ | B1 | CAO (oe) |
| $-x + 4z \geq 4$ | B1 | CAO (oe) |
| **Total** | **(4)** | |

## Part (b):

| Answer/Working | Mark | Guidance |
|---|---|---|
| $A = -(a_1 + a_2) \Rightarrow -(9-3x-2y+s_2+4+x-4z+s_3)$ | M1 | Setting up new objective and substituting for $a_1$ and $a_2$ |
| $A - 2x - 2y - 4z + s_2 + s_3 = -13$, bottom row: $A \mid -2 \mid -2 \mid -4 \mid 0 \mid 1 \mid 1 \mid 0 \mid 0 \mid -13$ | A1 | Correct values substituted into Table 1 |
| **Total** | **(2)** | |

## Part (c)(i):

| Answer/Working | Mark | Guidance |
|---|---|---|
| In the given tableau the value of objective $A$ is equal to zero, indicating a basic feasible solution has been found | B1 | CAO – mention that $A = 0$ |
| **Total** | **(1)** | |

## Part (c)(ii):

| Answer/Working | Mark | Guidance |
|---|---|---|
| $x=3,\ y=0,\ z=\dfrac{7}{4},\ s_1=\dfrac{147}{4},\ s_2=s_3=0$ | B1 | At least three values stated correctly |
| | B1 | All six values correct (ignore values for $a_1, a_2$ and $P$) |
| **Total** | **(2)** | |

## Part (d):

| Answer/Working | Mark | Guidance |
|---|---|---|
| Pivot correctly located, attempt to divide row | M1 | Correct pivot located |
| Pivot row correct including change of b.v. | A1 | |
| All values in one non-pivot row correct **or** one of the non-zero and one columns ($y, s_1, s_3$ or value) correct following through choice of pivot from column $s_2$ or $s_3$ | M1 | |
| Row operations used correctly at least twice; **two** of non-zero and one columns ($y, s_1, s_3$ or value) correct | A1 | |
| CAO all values and row operations correctly stated (allow row operations given in terms of old row 1 – **ignore b.v. column for this mark**) | A1 | |

Final tableau:

| b.v. | $x$ | $y$ | $z$ | $s_1$ | $s_2$ | $s_3$ | Value | Row Ops |
|---|---|---|---|---|---|---|---|---|
| $s_2$ | 0 | $\frac{10}{7}$ | 0 | $\frac{12}{7}$ | 1 | $\frac{9}{7}$ | 63 | $R1 \div \frac{7}{12}$ |
| $x$ | 1 | $\frac{8}{7}$ | 0 | $\frac{4}{7}$ | 0 | $\frac{3}{7}$ | 24 | $R2 + \frac{1}{3}R1$ |
| $z$ | 0 | $\frac{2}{7}$ | 1 | $\frac{1}{7}$ | 0 | $-\frac{1}{7}$ | 7 | $R3 + \frac{1}{12}R1$ |
| $P$ | 0 | $\frac{15}{7}$ | 0 | $\frac{11}{7}$ | 0 | $\frac{3}{7}$ | 69 | $R4 + \frac{11}{12}R1$ |

| **Total** | **(5)** | |

## Part (e)(i):

| Answer/Working | Mark | Guidance |
|---|---|---|
| Yes, optimal solution found as there are no negative values in the objective ($P$) row | B1 | Correct reasoning; or using $P = 69 - \frac{15}{7}y - \frac{11}{7}s_1 - \frac{3}{7}s_3$ and mentioning increasing $y, s_1, s_3$ would decrease $P$ (oe) |
| **Total** | **(1)** | |

## Part (e)(ii):

| Answer/Working | Mark | Guidance |
|---|---|---|
| $P = 69$ | B1ft | Their value of $P$ – dependent on both M marks in (d) |
| **Total** | **(1)** | |

## Part (e)(iii):

| Answer/Working | Mark | Guidance |
|---|---|---|
| $s_2 = 63,\ x = 24,\ z = 7$ | B1ft | Their values of basic variables **only** – dependent on both M marks in (d) |
| **Total** | **(1)** | |
7. A maximisation linear programming problem in $x , y$ and $z$ is to be solved using the two-stage simplex method.

The partially completed initial tableau is shown below.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
Basic variable & $x$ & $y$ & $z$ & $S _ { 1 }$ & $S _ { 2 }$ & $S _ { 3 }$ & $a _ { 1 }$ & $a _ { 2 }$ & Value \\
\hline
$S _ { 1 }$ & 1 & 2 & 3 & 1 & 0 & 0 & 0 & 0 & 45 \\
\hline
$a _ { 1 }$ & 3 & 2 & 0 & 0 & -1 & 0 & 1 & 0 & 9 \\
\hline
$a _ { 2 }$ & -1 & 0 & 4 & 0 & 0 & -1 & 0 & 1 & 4 \\
\hline
$P$ & -2 & -1 & -3 & 0 & 0 & 0 & 0 & 0 & 0 \\
\hline
A &  &  &  &  &  &  &  &  &  \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities.
\item Complete the bottom row of Table 1 in the answer book. You should make your method and working clear.

The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
Basic variable & $x$ & $y$ & $z$ & $S _ { 1 }$ & $S _ { 2 }$ & $S _ { 3 }$ & $a _ { 1 }$ & $a _ { 2 }$ & Value \\
\hline
$S _ { 1 }$ & 0 & $\frac { 5 } { 6 }$ & 0 & 1 & $\frac { 7 } { 12 }$ & $\frac { 3 } { 4 }$ & $- \frac { 7 } { 12 }$ & $- \frac { 3 } { 4 }$ & $\frac { 147 } { 4 }$ \\
\hline
$x$ & 1 & $\frac { 2 } { 3 }$ & 0 & 0 & $- \frac { 1 } { 3 }$ & 0 & $\frac { 1 } { 3 }$ & 0 & 3 \\
\hline
$z$ & 0 & $\frac { 1 } { 6 }$ & 1 & 0 & $- \frac { 1 } { 12 }$ & $- \frac { 1 } { 4 }$ & $\frac { 1 } { 12 }$ & $\frac { 1 } { 4 }$ & $\frac { 7 } { 4 }$ \\
\hline
$P$ & 0 & $\frac { 5 } { 6 }$ & 0 & 0 & $- \frac { 11 } { 12 }$ & $- \frac { 3 } { 4 }$ & $\frac { 11 } { 12 }$ & $\frac { 3 } { 4 }$ & $\frac { 45 } { 4 }$ \\
\hline
A & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\item \begin{enumerate}[label=(\roman*)]
\item Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem.
\item Write down the basic feasible solution for the second stage.
\end{enumerate}\item Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method, to obtain a new tableau, $T$. Make your method clear by stating the row operations you use.
\item \begin{enumerate}[label=(\roman*)]
\item Explain, using $T$, whether or not an optimal solution to the original linear programming problem has been found.
\item Write down the value of the objective function.
\item State the values of the basic variables.
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{Edexcel FD1 2020 Q7 [17]}}
This paper (7 questions)
View full paper
Q1 6 Q2 15 Q3 9 Q4 10 Q5 7 Q6 11 Q7 17