Lucy is making party bags which she will sell to raise money for charity. She has three colours of party bag: red, yellow and blue. The bags contain balloons, sweets and toys. Lucy has a stock of 40 balloons, 80 sweets and 30 toys. The table shows how many balloons, sweets and toys are needed for one party bag of each colour.

\begin{tabular}{|l|c|c|c|}
\hline
Colour of party bag & Balloons & Sweets & Toys \\
\hline
Red & 5 & 3 & 5 \\
\hline
Yellow & 4 & 7 & 2 \\
\hline
Blue & 6 & 6 & 3 \\
\hline
\end{tabular}

Lucy will raise £1 for each bag that she sells, irrespective of its colour. She wants to calculate how many bags of each colour she should make to maximise the total amount raised for charity.

Lucy has started to model the problem as an LP formulation.

Maximise \quad $P = x + y + z$,

subject to \quad $3x + 7y + 6z \leq 80$.

\begin{enumerate}[label=(\roman*)]
\item What does the variable $x$ represent in Lucy's formulation? [1]

\item Explain why the constraint $3x + 7y + 6z \leq 80$ must hold and write down another two similar constraints. [3]

\item What other constraints and restrictions apply to the values of $x$, $y$ and $z$? [1]

\item What assumption is needed for the objective to be valid? [1]

\item Represent the problem as an initial Simplex tableau. Do not carry out any iterations yet. [3]

\item Perform one iteration of the Simplex algorithm, choosing a pivot from the $x$ column. Explain how the choice of pivot row was made and show how each row was calculated. [6]

\item Write down the values of $x$, $y$ and $z$ from the first iteration of the Simplex algorithm and hence find the number of bags of each colour that Lucy should make according to this non-optimal tableau. [2]
\end{enumerate}

In the optimal solution Lucy makes 10 bags.

\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{7}
\item Without carrying out further iterations of the Simplex algorithm, find a solution in which Lucy should make 10 bags. [1]
\end{enumerate}

\hfill \mbox{\textit{OCR D1 2012 Q4 [18]}}