5 Consider the problem given below:
$$\begin{array} { l l }
\text { Minimise } & 4 \mathrm { AB } + 7 \mathrm { AC } + 8 \mathrm { BD } + 5 \mathrm { CD } + 5 \mathrm { CE } + 6 \mathrm { DF } + 3 \mathrm { EF }
\text { subject to } & \mathrm { AB } , \mathrm { AC } , \mathrm { BD } , \mathrm { CD } , \mathrm { CE } , \mathrm { DF } \text { and } \mathrm { EF } \text { are each either } 0 \text { or } 1
& \mathrm { AB } + \mathrm { AC } + \mathrm { BD } + \mathrm { CD } + \mathrm { CE } + \mathrm { DF } + \mathrm { EF } = 5
& \mathrm { AB } + \mathrm { AC } \geqslant 1 , \quad \mathrm { AB } + \mathrm { BD } \geqslant 1 , \quad \mathrm { AC } + \mathrm { CD } + \mathrm { CE } \geqslant 1 ,
& \mathrm { BD } + \mathrm { CD } + \mathrm { DF } \geqslant 1 , \quad \mathrm { CE } + \mathrm { EF } \geqslant 1 , \quad \mathrm { DF } + \mathrm { EF } \geqslant 1
\end{array}$$
- Explain why this is not a standard LP formulation that could be set up as a Simplex tabulation. The variables \(\mathrm { AB } , \mathrm { AC } , \ldots\) correspond to arcs in a network.
The weight on each arc is the coefficient of the corresponding variable in the objective function.
- Draw the network on the vertices in the Printed Answer Booklet.
A variable that takes the value 1 corresponds to an arc that is used in the solution and a variable with the value 0 corresponds to an arc that is not used in the solution.
- Explain what is ensured by the constraint \(\mathrm { AB } + \mathrm { AC } \geqslant 1\).
Julie claims that the solution to the problem will give the minimum spanning tree for the network.
- Find the minimum spanning tree for the network.
- State the algorithm you have used.
- Show your method clearly.
- Draw the tree.
- State the total weight of the tree.
- Find the solution to the problem given at the start of the question.
- You do not need to use a formal method.
- Draw the arcs in the solution.
- State the minimum value of the objective function.
Kim has a different network, exactly one of the arcs in this network is a directed arc.
Kim wants to find a minimum weight set of arcs such that it is possible to get from any vertex to any other vertex. - Explain why, if Kim's problem has a solution, the directed arc cannot be part of it.