OCR D1 (Decision Mathematics 1) 2011 June

1 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]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-2_885_873_388_635}

1. Write down the inequalities that define the feasible region. The objective is to maximise \(P _ { m } = x + m y\), where \(m\) is a positive, real-valued constant.
2. In the case when \(m = 2\), calculate the values of \(x\) and \(y\) at the optimal point, and the corresponding value of \(P _ { 2 }\).
3. (a) Write down the values of \(m\) for which point \(A\) is optimal.
   (b) Write down the values of \(m\) for which point \(B\) is optimal.

2 Consider the following algorithm.
STEP 1 Input a number \(N\)
STEP 2 Calculate \(R = N \div 2\)
STEP 3 Calculate \(S = ( ( N \div R ) + R ) \div 2\)
STEP 4 If \(R\) and \(S\) are the same when rounded to 2 decimal places, go to STEP 7
STEP 5 Replace \(R\) with the value of \(S\)
STEP 6 Go to STEP 3
STEP 7 Output the value of \(R\) correct to 2 decimal places

1. Work through the algorithm starting with \(N = 16\). Record the values of \(R\) and \(S\) each time they change and show the value of the output.
2. Work through the algorithm starting with \(N = 2\). Record the values of \(R\) and \(S\) each time they change and show the value of the output.
3. What does the algorithm achieve for positive inputs?
4. Show that the algorithm fails when it is applied to \(N = - 4\).
5. Describe what happens when the algorithm is applied to \(N = - 2\). Suggest how the algorithm could be improved to avoid this problem, without imposing a restriction on the allowable input values.

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.

1. Explain why it is impossible to draw a graph with exactly five vertices of orders \(1,2,3,4\) and 5.
2. Explain why there is no simply connected graph with exactly five vertices of orders \(2,2,3,4\) and 5 . State which of the properties 'simple' and 'connected' cannot be achieved.
3. Calculate the number of arcs in a simply connected graph with exactly five vertices of orders 1 , 1, 2, 2 and 4 . Hence explain why such a graph cannot be a tree.
4. Draw a simply connected semi-Eulerian graph with exactly five vertices that is also a tree. By considering the orders of the vertices, explain why it is impossible to draw a simply connected Eulerian graph with exactly five vertices that is also a tree. In the graph below the vertices represent buildings and the arcs represent pathways between those buildings.
   \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-4_426_1081_1297_532}
5. By considering the orders of the vertices, explain why it is impossible to walk along these pathways in a continuous route that uses every arc once and only once. Write down the minimum number of arcs that would need to be travelled twice to walk in a continuous route that uses every arc at least once.

4 Consider the following LP problem.

1. Represent the problem as an initial Simplex tableau. Explain why the pivot can only be chosen from the \(x\) column.
2. Perform one iteration of the Simplex algorithm. Show how each row was obtained and write down the values of \(w , x , y , z\) and \(P\) at this stage.
3. Perform a second iteration of the Simplex algorithm. Write down the values of \(w , x , y , z\) and \(P\) at this stage and explain how you can tell from this tableau that \(P\) can be increased without limit. How could you have known from the LP formulation above that \(P\) could be increased without limit?

5 The arcs in the network below represent the tracks in a forest and the weights on the arcs represent distances in km.
\includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_543_1269_392_438} Dijkstra's algorithm is to be used to find the shortest path from \(A\) to \(G\).

1. Apply Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). Show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Do not cross out your working values. Write down the route of the shortest path from \(A\) to \(G\) and give its length. The track joining \(B\) and \(D\) is washed away in a flood. It is replaced by a new track of unknown length, \(x \mathrm {~km}\).
   \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_544_1271_1480_438}
2. What is the smallest value that \(x\) can take so that the route found in part (i) is still a shortest path? If the value of \(x\) is smaller than this, what is the weight of the shortest path from \(A\) to \(G\) ?
3. (a) For what values of \(x\) will vertex \(E\) have two temporary labels? Write down the values of these temporary labels.
   (b) For what values of \(x\) will vertex \(C\) have two temporary labels? Write down the values of these temporary labels. Dijkstra's algorithm has quadratic order.
4. If a computer takes 20 seconds to apply Dijkstra's algorithm to a complete network with 50 vertices, approximately how long will it take for a complete network with 100 vertices?

6 The arcs in the network represent the tracks in a forest. The weights on the arcs represent distances in km .
\includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-7_535_1267_395_440} Richard wants to walk along every track in the forest. The total weight of the arcs is \(26.7 + x\).

1. Find, in terms of \(x\), the length of the shortest route that Richard could use to walk along every track, starting at \(A\) and ending at \(G\). Show all of your working.
2. Now suppose that Richard wants to find the length of the shortest route that he could use to walk along every track, starting and ending at \(A\). Show that for \(x \leqslant 1.8\) this route has length \(( 32.4 + 2 x ) \mathrm { km }\), and for \(x \geqslant 1.8\) it has length \(( 34.2 + x ) \mathrm { km }\). Whenever two tracks join there is an information board for visitors to the forest. Shauna wants to check that the information boards have not been vandalised. She wants to find the length of the shortest possible route that starts and ends at \(A\), passing through every vertex at least once. Consider first the case when \(x\) is less than 3.2.
3. (a) Apply Prim's algorithm to the network, starting from vertex \(A\), to find a minimum spanning tree. Draw the minimum spanning tree and state its total weight. Explain why the solution to Shauna's problem must be longer than this.
   (b) Use the nearest neighbour strategy, starting from vertex \(A\), and show that it stalls before it has visited every vertex. Now consider the case when \(x\) is greater than 3.2 but less than 4.6.
4. (a) Draw the minimum spanning tree and state its total weight.
   (b) Use the nearest neighbour strategy, starting from vertex \(A\), to find a route from \(A\) to \(G\) passing through each vertex once. Write down the route obtained and its total weight. Show how a shortcut can give a shorter route from \(A\) to \(G\) passing through each vertex. Hence, explaining your method, find an upper bound for Shauna's problem.