3 Neil is refurbishing a listed building. There are two types of paint that he can use for the inside walls. One costs $\pounds 1.45$ per $\mathrm { m } ^ { 2 }$ and the other costs $\pounds 0.95$ per $\mathrm { m } ^ { 2 }$. He must paint the lower half of each wall in the more expensive paint. He has $350 \mathrm {~m} ^ { 2 }$ of wall to paint. He has a budget of $\pounds 400$ for wall paint. The more expensive paint is easier to use, and so Neil wants to use as much of it as possible.

Initially, the following LP is constructed to help Neil with his purchasing of paint.\\
Let $x$ be the number of $\mathrm { m } ^ { 2 }$ of wall painted with the expensive paint.\\
Let $y$ be the number of $\mathrm { m } ^ { 2 }$ of wall painted with the less expensive paint.

$$\begin{array} { l l } 
\text { Maximise } & P = x + y \\
\text { subject to } & 1.45 x + 0.95 y \leqslant 400 \\
& y - x \leqslant 0 \\
& x \geqslant 0 \\
& y \geqslant 0
\end{array}$$

(i) Explain the purpose of the inequality $y - x \leqslant 0$.\\
(ii) The formulation does not include the inequality $x + y \geqslant 350$. State what this constraint models and why it has been omitted from the formulation.\\
(iii) Use the simplex algorithm to solve the LP. Pivot first on the "1" in the $y$ column. Interpret your solution.

The solution shows that Neil needs to buy more paint. He negotiates an increase in his budget to $\pounds 450$.\\
(iv) Find the solution to the LP given by changing $1.45 x + 0.95 y \leqslant 400$ to $1.45 x + 0.95 y \leqslant 450$, and interpret your solution.

Neil realises that although he now has a solution, that solution is not the best for his requirements.\\
(v) Explain why the revised solution is not optimal for Neil.

In order to move to an optimal solution Neil needs to change the objective of the LP and add another constraint to it.\\
(vi) Write down the new LP and the initial tableau for using two-stage simplex to solve it. Give a brief description of how to use two-stage simplex to solve it.\\
\includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-5_497_558_269_751}
\begin{enumerate}[label=(\alph*)]
\item Solve the route inspection problem in the network above, showing the methodology you used to ensure that your solution is optimal. Show your route.
\item Floyd's algorithm is applied to the same network to find the complete network of shortest distances. After three iterations the distance and route matrices are as follows.

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ & $\mathbf { 5 }$ \\
\hline
$\mathbf { 1 }$ & 48 & 24 & 28 & 11 & 15 \\
\hline
$\mathbf { 2 }$ & 24 & 8 & 4 & 11 & 16 \\
\hline
$\mathbf { 3 }$ & 28 & 4 & 8 & 7 & 12 \\
\hline
\end{tabular}
\end{center}
\end{enumerate}

\hfill \mbox{\textit{OCR MEI D2 2016 Q3 [20]}}