OCR D1 (Decision Mathematics 1) 2012 June

1 Satellite navigation systems (sat navs) use a version of Dijkstra's algorithm to find the shortest route between two places. A simplified map is shown below. The values marked represent road distances, in km , for that section of road (from a place to a road junction, or between two places). \begin{figure}[h] \end{figure}

1. Use the map to construct a network with exactly 10 arcs to show the direct distances between these places, with no road junctions shown. For example, there will need to be an arc connecting \(A\) to \(B\) of weight 22, and also arcs connecting \(A\) to \(C , D\), and \(E\). There is no arc connecting \(A\) to \(F\) (because there is no route from \(A\) to \(F\) that does not pass through another place).
2. Apply Dijkstra's algorithm, starting at \(A\), to find the shortest route from \(A\) to \(F\). Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ).
3. If it takes 3 seconds for a certain sat nav to find the shortest route between two places when it has to process 200 places, calculate approximately how many minutes it will take when it has to process 4000 places.

2 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.

1. (a) Draw a simply connected Eulerian graph with exactly five vertices and five arcs.
   (b) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which one of the vertices has order 4.
   (c) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which none of the vertices have order 4. A teacher is organising revision classes for her students. There will be ten revision classes scheduled into a number of sessions. Each class will run in one session only. Each student has chosen two classes to attend. The table shows which classes each student has chosen. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Revision classes}

   Student number	C1	C2	C3	C4	M1	M2	S1	S2	D1	D2
   1	✓	✓
   2				✓						✓
   3			✓	✓
   4			✓			✓
   5								✓	✓
   6		✓				✓
   7					✓			✓
   8	✓						✓
   9						✓				✓
   10					✓		✓

   \end{table}
2. (a) Draw a graph to show this information. Each vertex represents a class. Each arc links the two classes chosen by a student.
   (b) Show how the teacher can arrange the classes in just two sessions, which satisfy all student choices. For example, C1 and C2 cannot be in the same session. An extra student joins the group. This student chooses to attend the revision classes in M1 and D1.
   (c) Explain why the teacher cannot now arrange the classes in just two sessions. Do not amend your graph from part (ii)(a).

3 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries.
\includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-4_919_917_322_575}

1. Obtain the four inequalities that define the feasible region.
2. Calculate the coordinates of the vertices of the feasible region, giving your values as fractions. The objective is to maximise \(P = x + 4 y\).
3. Calculate the value of \(P\) at each vertex of the feasible region. Hence write down the coordinates of the optimal point, and the corresponding value of \(P\). Suppose that the solution must have integer values for both \(x\) and \(y\).
4. Find the coordinates of the optimal point with integer-valued \(x\) and \(y\), and the corresponding value of \(P\). Explain how you know that this is the optimal solution.

4 Consider the following linear programming problem. $$\begin{array} { l r } \text { Maximise } & P = - 5 x - 6 y + 4 z ,
\text { subject to } & 3 x - 4 y + z \leqslant 12 ,
& 6 x + 2 z \leqslant 20 ,
& - 10 x - 5 y + 5 z \leqslant 30 ,
& x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$

1. Use slack variables \(s , t\) and \(u\) to rewrite the first three constraints as equations. What restrictions are there on the values of \(s , t\) and \(u\) ?
2. Represent the problem as an initial Simplex tableau.
3. Show why the pivot for the first iteration of the Simplex algorithm must be the coefficient of \(z\) in the third constraint.
4. Perform one iteration of the Simplex algorithm, showing how the elements of the pivot row were calculated and how this was used to calculate the other rows.
5. Perform a second iteration of the Simplex algorithm and record the values of \(x , y , z\) and \(P\) at the end of this iteration.
6. Write down the values of \(s , t\) and \(u\) from your final tableau and explain what they mean in terms of the original constraints.

5 Jess and Henry are out shopping. The network represents the main routes between shops in a shopping arcade. The arcs represent pathways and escalators, the vertices represent some of the shops and the weights on the arcs represent distances in metres.
\includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-6_586_1084_367_495} The total weight of all the arcs is 1200 metres.
The table below shows the shortest distances between vertices; some of these are indirect distances.

1. Use a standard algorithm to find the shortest distance that Jess must travel to cover every arc in the original network, starting and ending at \(M\).
2. Find the shortest distance that Jess must travel if she just wants to cover every arc, but does not mind where she starts and where she finishes. Which two points are her start and finish? Henry suggests that Jess only needs to visit each shop.
3. Apply the nearest neighbour method to the network, starting at \(M\), to write down a closed tour through all the vertices. Calculate the weight of this tour. What does this value tell you about the length of the shortest closed route that passes through every vertex? Henry thinks that Jess does not need to visit shop \(W\). He uses the table of shortest distances to list all the possible connections between \(M , N , P , R , S\) and \(V\) by increasing order of weight. Henry's list is given in your answer book.
4. Use Kruskal's algorithm on Henry's list to find a minimum spanning tree for \(M , N , P , R , S , T\) and \(V\). Draw the tree and calculate its total weight. Jess insists that they must include shop \(W\).
5. Use the weight of the minimum spanning tree for \(M , N , P , R , S , T\) and \(V\), and the table of shortest distances, to find a lower bound for the length of the shortest closed route that passes through all eight vertices.

6 The following flow chart has been written to find a root of the cubic equation \(x ^ { 3 } + A x ^ { 2 } + B x + C = 0\), given a starting value \(X\) that is thought to be near the root.
\includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-8_1410_1648_324_212}

1. Work through the algorithm, recording the values of \(X , Y , Z\) and \(W\) each time they change, for the equation \(x ^ { 3 } - 4 x ^ { 2 } + 5 x + 1 = 0\), with a starting value of \(X = 0\).
2. Show what happens when the algorithm is used for the equation \(x ^ { 3 } - 4 x ^ { 2 } + 5 x + 1 = 0\), with a starting value of \(X = 1\).
3. Show what happens when the algorithm is used for the equation \(x ^ { 3 } - 4 x ^ { 2 } + 5 x + 1 = 0\), with a starting value of \(X = - 1\).
4. Identify a possible problem with using this algorithm.