OCR D1 (Decision Mathematics 1) 2011 January

1 In the network below, the arcs represent the roads in Ayton, the vertices represent roundabouts, and the arc weights show the number of traffic lights on each road. Sam is an evening class student at Ayton Academy ( \(A\) ). She wants to drive from the academy to her home ( \(H\) ). Sam hates waiting at traffic lights so she wants to find the route for which the number of traffic lights is a minimum.
\includegraphics[max width=\textwidth, alt={}, center]{bb7fb141-ef42-42af-b052-d8e20d6e5157-02_786_1097_482_523}

1. Apply Dijkstra's algorithm to find the route that Sam should use to travel from \(A\) to \(H\). At each vertex, show the temporary labels, the permanent label and the order of permanent labelling. In the daytime, Sam works for the highways department. After an electrical storm, the highways department wants to check that all the traffic lights are working. Sam is sent from the depot ( \(D\) ) to drive along every road and return to the depot. Sam needs to pass every traffic light, but wants to repeat as few as possible.
2. Find the minimum number of traffic lights that must be repeated. Show your working. Suppose, instead, that Sam wants to start at the depot, drive along every road and end at her home, passing every traffic light but repeating as few as possible.
3. Find a route on which the minimum number of traffic lights must be repeated. Explain your reasoning.

2 Five rooms, \(A , B , C , D , E\), in a building need to be connected to a computer network using expensive cabling. Rob wants to find the cheapest way to connect the rooms by finding a minimum spanning tree for the cable lengths. The length of cable, in metres, needed to connect each pair of rooms is given in the table below.

1. Apply Prim's algorithm in matrix (table) form, starting at vertex \(A\) and showing all your working. Write down the order in which arcs were added to the tree. Draw the resulting tree and state the length of cable needed. A sixth room, \(F\), is added to the computer network. The distances from \(F\) to each of the other rooms are \(A F = 32 , B F = 29 , C F = 31 , D F = 35 , E F = 30\).
2. Use your answer to part (i) to write down a lower bound for the length of the minimum tour that visits every vertex of the extended network, finishing where it starts. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the length of this tour.

3

1. Explain why it is impossible to draw a graph with exactly four vertices of orders 1, 2, 3 and 3 . A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
   A simply connected graph is one that is both simple and connected.
2. Explain why there is no simply connected graph with exactly four vertices of orders \(1,1,2\) and 4.
3. A connected graph has four vertices \(A , B , C\) and \(D\), in which \(A , B\) and \(C\) have order 2 and \(D\) has order 4. Explain how you know that the graph is Eulerian. Draw an example of such a graph and write down an Eulerian trail for your graph. A graph has three vertices, \(A , B\) and \(C\) of orders \(a , b\) and \(c\), respectively.
4. What restrictions on the values of \(a , b\) and \(c\) follow from the graph being
   (a) simple,
   (b) connected,
   (c) semi-Eulerian?
5. Describe carefully how to carry out the first pass through bubble sort when we are using it to sort a list of \(n\) numbers into increasing order. State which value is guaranteed to be in its correct final position after the first pass and hence explain how to carry out the second pass on a reduced list. Write down the stopping condition for bubble sort.
6. Show the list of six values that results at the end of each pass when we use bubble sort to sort this list into increasing order. $$\begin{array} { l l l l l l } 3 & 10 & 8 & 2 & 6 & 11 \end{array}$$ You do not need to count the number of comparisons and the number of swaps that are used. Zack wants to cut lengths of wood from planks that are 20 feet long. The following lengths, in feet, are required. $$\begin{array} { l l l l l l } 3 & 10 & 8 & 2 & 6 & 11 \end{array}$$
7. Use the first-fit method to find a way to cut the pieces.
8. Use the first-fit decreasing method to find a way to cut the pieces. Give a reason why this might be a more useful cutting plan than that from part (iii).
9. Find a more efficient way to cut the pieces. How many planks will Zack need with this cutting plan and how many cuts will he need to make? 5 An online shopping company selects some of its parcels to be checked before posting them. Each selected parcel must pass through three checks, which may be carried out in any order. One person must check the contents, another must check the postage and a third person must check the address. The parcels are classified according to the type of customer as 'new', 'occasional' or 'regular'. The table shows the time taken, in minutes, for each check on each type of parcel.
10. Since \(a \leqslant 6\) it follows that \(6 - a \geqslant 0\), and similarly for \(b\) and \(c\). Let \(6 - a = x\) (so that \(a\) is replaced by \(6 - x ) , 8 - b = y\) and \(10 - c = z\) to show that the problem can be expressed as $$\begin{array} { l l } \text { Maximise } & 2 x - 4 y + 5 z ,
    \text { subject to } & 3 x + 2 y - z \leqslant 14 ,
    & 2 x - 4 z \leqslant 7 ,
    & - 4 x + y \leqslant 4 ,
    \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
11. Represent the problem as an initial Simplex tableau. Perform two iterations of the Simplex algorithm, showing how each row was obtained. Hence write down the values of \(a , b\) and \(c\) after two iterations. Find the value of the objective for the original problem at this stage.
    [0pt] [10]

5 An online shopping company selects some of its parcels to be checked before posting them. Each selected parcel must pass through three checks, which may be carried out in any order. One person must check the contents, another must check the postage and a third person must check the address. The parcels are classified according to the type of customer as 'new', 'occasional' or 'regular'. The table shows the time taken, in minutes, for each check on each type of parcel. The manager in charge of checking at the company has allocated each type of parcel a 'value' to represent how useful it is for generating additional income. In suitable units, these values are as follows. $$\text { new } = 8 \text { points } \quad \text { occasional } = 7 \text { points } \quad \text { regular } = 4 \text { points }$$ The manager wants to find out how many parcels of each type her department should check each hour, on average, to maximise the total value. She models this objective as $$\text { Maximise } P = 8 x + 7 y + 4 z .$$

1. What do the variables \(x , y\) and \(z\) represent?
2. Write down the constraints on the values of \(x , y\) and \(z\). The manager changes the value of parcels for regular customers to 0 points.
3. Explain what effect this has on the objective and simplify the constraints.
4. Use a graphical method to represent the feasible region for the manager's new problem. You should choose scales so that the feasible region can be clearly seen. Hence determine the optimal strategy. Now suppose that there is exactly one hour available for checking and the manager wants to find out how many parcels of each type her department should check in that hour to maximise the total value. The value of parcels for regular customers is still 0 points.
5. Find the optimal strategy in this situation.
6. Give a reason why, even if all the timings and values are correct, the total value may be less than this maximum. \section*{Question 6 is printed overleaf.}

6 Consider the following LP problem.

1. Since \(a \leqslant 6\) it follows that \(6 - a \geqslant 0\), and similarly for \(b\) and \(c\). Let \(6 - a = x\) (so that \(a\) is replaced by \(6 - x ) , 8 - b = y\) and \(10 - c = z\) to show that the problem can be expressed as $$\begin{array} { l l } \text { Maximise } & 2 x - 4 y + 5 z ,
   \text { subject to } & 3 x + 2 y - z \leqslant 14 ,
   & 2 x - 4 z \leqslant 7 ,
   & - 4 x + y \leqslant 4 ,
   \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
2. Represent the problem as an initial Simplex tableau. Perform two iterations of the Simplex algorithm, showing how each row was obtained. Hence write down the values of \(a , b\) and \(c\) after two iterations. Find the value of the objective for the original problem at this stage.
   [0pt] [10]

8 \href{http://physicsandmathstutor.com}{physicsandmathstutor.com} 6

(continued)

\multirow[t]{24}{*}{ 6 6 }	(ontnued)