| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | December |
| Marks | 22 |
| Topic | Linear Programming |
| Type | Formulation from word problem |
| Difficulty | Standard +0.3 This is a standard linear programming formulation and simplex algorithm question from Further Maths Decision module. Part (a) requires translating word constraints into inequalities (routine for this topic), part (b) involves setting up and performing one simplex iteration (mechanical process), and part (c) reads the solution from a given tableau. While it requires careful attention to detail and understanding of the simplex method, it follows a well-established procedure with no novel problem-solving required. Slightly easier than average A-level difficulty due to its procedural nature. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06d Graphical solution: feasible region, two variables7.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 |
| Suitable for vegans | Suitable for vegetarians | Suitable for meat eaters | |
| Type X | ✓ | ||
| Type Y | ✓ | ✓ | |
| Type Z | ✓ | ✓ | ✓ |
| \(P\) | \(x\) | \(y\) | \(z\) | \(s\) | \(t\) | \(u\) | \(v\) | RHS |
| 1 | 0 | 0 | 0 | 0 | 0 | \(\frac { 3 } { 7 }\) | \(\frac { 2 } { 7 }\) | \(28 \frac { 4 } { 7 }\) |
| 0 | 0 | 0 | 0 | 1 | 0 | \(- \frac { 3 } { 7 }\) | \(- \frac { 2 } { 7 }\) | \(1 \frac { 3 } { 7 }\) |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 2 |
| 0 | 1 | 0 | 0 | 0 | 0 | \(\frac { 5 } { 7 }\) | \(\frac { 1 } { 7 }\) | \(14 \frac { 2 } { 7 }\) |
| 0 | 0 | 1 | 1 | 0 | 0 | \(- \frac { 2 } { 7 }\) | \(\frac { 1 } { 7 }\) | \(14 \frac { 2 } { 7 }\) |
6 Jack is making pizzas for a party.
He can make three types of pizza:
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
& Suitable for vegans & Suitable for vegetarians & Suitable for meat eaters \\
\hline
Type X & & & ✓ \\
\hline
Type Y & & ✓ & ✓ \\
\hline
Type Z & ✓ & ✓ & ✓ \\
\hline
\end{tabular}
\end{center}
\begin{itemize}
\item There is enough dough to make 30 pizzas.
\item Type Z pizzas use vegan cheese. Jack only has enough vegan cheese to make 2 type Z pizzas.
\item At least half the pizzas made must be suitable for vegetarians.
\item Jack has enough onions to make 50 type X pizzas or 20 type Y pizzas or 20 type Z pizzas or some mixture of the three types.
\end{itemize}
Suppose that Jack makes $x$ type X pizzas, $y$ type Y pizzas and $z$ type Z pizzas.
\begin{enumerate}[label=(\alph*)]
\item Formulate the constraints above in terms of the non-negative, integer valued variables $x , y$ and $z$, together with non-negative slack variables $s , t , u$ and $v$.
Jack wants to find out the maximum total number of pizzas that he can make.
\item \begin{enumerate}[label=(\roman*)]
\item Set up an initial simplex tableau for Jack's problem.
\item Carry out one iteration of the simplex algorithm, choosing your pivot so that $x$ becomes a basic variable.
When Jack carries out the simplex algorithm his final tableau is:
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
$P$ & $x$ & $y$ & $z$ & $s$ & $t$ & $u$ & $v$ & RHS \\
\hline
1 & 0 & 0 & 0 & 0 & 0 & $\frac { 3 } { 7 }$ & $\frac { 2 } { 7 }$ & $28 \frac { 4 } { 7 }$ \\
\hline
0 & 0 & 0 & 0 & 1 & 0 & $- \frac { 3 } { 7 }$ & $- \frac { 2 } { 7 }$ & $1 \frac { 3 } { 7 }$ \\
\hline
0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 2 \\
\hline
0 & 1 & 0 & 0 & 0 & 0 & $\frac { 5 } { 7 }$ & $\frac { 1 } { 7 }$ & $14 \frac { 2 } { 7 }$ \\
\hline
0 & 0 & 1 & 1 & 0 & 0 & $- \frac { 2 } { 7 }$ & $\frac { 1 } { 7 }$ & $14 \frac { 2 } { 7 }$ \\
\hline
\end{tabular}
\end{center}
\end{enumerate}\item Use this final tableau to deduce how many pizzas of each type Jack should make.
Jack knows that some of the guests are vegans. He decides to make 2 pizzas of type $Z$.
\item \begin{enumerate}[label=(\roman*)]
\item Plot the feasible region for $x$ and $y$.
\item Complete the branch-and-bound formulation in the Printed Answer Booklet to find the number of pizzas of each type that Jack should make.\\
You should branch on $x$ first.
\section*{END OF QUESTION PAPER}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q6 [22]}}