\(\mathbf { 4 }\) & 5 & 2 & 1 & 2
\hline
\end{tabular}
\end{center}
| \cline { 2 - 5 }
\multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) |
| \(\mathbf { 1 }\) | 2 | 2 | 2 | 2 |
| \(\mathbf { 2 }\) | 1 | 1 | 3 | 4 |
| \(\mathbf { 3 }\) | 2 | 2 | 2 | 4 |
| \(\mathbf { 4 }\) | 2 | 2 | 3 | 3 |
- Perform the fourth (final) iteration of the algorithm.
- Explain how to use the final matrices to find the shortest distance and the shortest route from vertex \(\mathbf { 1 }\) to vertex \(\mathbf { 3 }\), and give the distance and route.
- Draw the complete network of shortest distances.
- Apply the nearest neighbour algorithm, starting at vertex \(\mathbf { 1 }\), to your complete network of shortest distances. Give the Hamilton cycle it produces, its length, and the corresponding route through the original network.
- By considering vertex 2 and its arcs, construct a lower bound for the length of the solution to the travelling salesperson problem in the original network.
- Explain what you can deduce from your answers to parts (iv) and (v).
4 Noel is designing a hotel patio. It will consist of decking and paving.
Decking costs \(\pounds 4\) per \(\mathrm { m } ^ { 2 }\) and paving costs \(\pounds 2\) per \(\mathrm { m } ^ { 2 }\). He has a budget of \(\pounds 2500\).
Noel prefers paving to decking, and he wants the area given to paving to be at least twice that given to decking.
He wants to have as large a patio as possible.
Noel's problem is formulated as the following LP.
Let \(x\) be the number of \(\mathrm { m } ^ { 2 }\) of decking.
Let \(y\) be the number of \(\mathrm { m } ^ { 2 }\) of paving.
$$\begin{aligned}
\text { Maximise } \quad P & = x + y
\text { subject to } 2 x + y & \leqslant 1250
2 x - y & \leqslant 0
x & \geqslant 0
y & \geqslant 0
\end{aligned}$$ - Use the simplex algorithm to solve this LP. Pivot first on the positive element in the \(y\) column.
Noel would like to have at least \(200 \mathrm {~m} ^ { 2 }\) of decking.
- Add a line corresponding to this constraint to your solution tableau from part (i), and modify the resulting table either for two-stage simplex or the big-M method. Hence solve the problem.
Noel finally decides that he will minimise the annual cost of maintenance, which is given by \(\pounds ( 0.75 x + 1.25 y )\), subject to the additional constraint that there is at least \(1000 \mathrm {~m} ^ { 2 }\) of patio.
- Starting from your solution to part (ii), use simplex to solve this problem.