\(\mathbf { 4 }\) & 9 & 7 & 6 & 12
\hline
\end{tabular}
\end{center}
Route Matrix
| \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) |
| \(\mathbf { 1 }\) | 2 | 2 | 2 | 2 |
| \(\mathbf { 2 }\) | \(\mathbf { 1 }\) | 3 | 3 | 3 |
| \(\mathbf { 3 }\) | 2 | 2 | 2 | 4 |
| \(\mathbf { 4 }\) | 3 | 3 | 3 | 3 |
Fig. 3.1
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ab28be76-9329-41c8-90fe-ff1bdb28f788-4_296_310_918_904}
\captionsetup{labelformat=empty}
\caption{Fig. 3.2}
\end{figure}
- Draw the complete network of shortest distances.
- Explain how to use the route matrix to find the shortest route from vertex 4 to vertex 1 in the original incomplete network.
A new vertex, vertex 5, is added to the original network. Its distances from vertices to which it is connected are shown in Fig. 3.3.
\begin{table}[h]
| \cline { 2 - 5 }
\multicolumn{1}{c|}{} | 1 | 2 | 3 | 4 |
| 5 | - | 3 | - | 1 |
\captionsetup{labelformat=empty}
\caption{Fig. 3.3}
- Draw the extended network and the complete 5 -node network of shortest distances. (You are not required to use an algorithm to find the shortest distances.)
- Produce the shortest distance matrix and the route matrix for the extended 5-node network.
- Apply the nearest neighbour algorithm to your \(5 \times 5\) distance matrix, starting at vertex 1. Give the length of the cycle produced, together with the actual cycle in the original 5-node network.
- By deleting vertex 1 and its arcs, and by using Prim's algorithm on the reduced distance matrix, produce a lower bound for the solution to the practical travelling salesperson problem in the original 5-node network. Show clearly your use of the matrix form of Prim's algorithm.
- In the original 5-node network find a shortest route starting at vertex \(\mathbf { 1 }\) and using each of the 6 arcs at least once. Give the length of your route.
4 Kassi and Theo are discussing how much oil and how much vinegar to use to dress their salad. They agree to use between 5 and 10 ml of oil and between 3 and 6 ml of vinegar and that the amount of oil should not exceed twice the amount of vinegar.
Theo prefers to have more oil than vinegar. He formulates the following problem to maximise the proportion of oil:
$$\begin{array} { l c }
\text { Maximise } & \frac { x } { x + y }
\text { subject to } & 0 \leqslant x \leqslant 10 ,
& 0 \leqslant y \leqslant 6 ,
& x - 2 y \leqslant 0 .
\end{array}$$ - Explain why this problem is not an LP.
- Use the simplex method to solve the following LP.
$$\begin{array} { l c }
\text { Maximise } & x - y
\text { subject to } & 0 \leqslant x \leqslant 10
& 0 \leqslant y \leqslant 6
& x - 2 y \leqslant 0
\end{array}$$ - Kassi prefers to have more vinegar than oil. She formulates the following LP.
$$\begin{array} { l l }
\text { Maximise } & y - x
\text { subject to } & 5 \leqslant x \leqslant 10 ,
& 3 \leqslant y \leqslant 6 ,
& x - 2 y \leqslant 0 .
\end{array}$$
Draw separate graphs to show the feasible regions for this problem and for the problem in part (ii). - Explain why the formulation in part (ii) produced a solution for Theo's problem, and why it is more difficult to use the simplex method to solve Kassi's problem in part (iii).
- Produce an initial tableau for using the two-stage simplex method to solve Kassi's problem.
Explain briefly how to proceed.