OCR D1 (Decision Mathematics 1) 2012 January

1 Tom has some packages that he needs to sort into order of decreasing weight. The weights, in kg , given on the packages are as follows. $$\begin{array} { l l l l l l l l l } 3 & 6 & 2 & 6 & 5 & 7 & 1 & 4 & 9 \end{array}$$ Use shuttle sort to put the weights into decreasing order (from largest to smallest). Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass. Write down the total number of passes, the total number of comparisons and the total number of swaps used.

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. What is the minimum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph.
2. What is the maximum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph.
3. What is the maximum number of arcs that a simply connected Eulerian graph with six vertices can have? Explain your reasoning.
4. State how you know that the graph below is semi-Eulerian and write down a semi-Eulerian trail for the graph.
   \includegraphics[max width=\textwidth, alt={}, center]{f0ac479b-2187-4335-bcb9-c0e354145bca-2_654_887_1457_587}
   \includegraphics[max width=\textwidth, alt={}, center]{f0ac479b-2187-4335-bcb9-c0e354145bca-3_549_1360_324_347}
5. Apply Dijkstra's algorithm to the copy of this network in the answer booklet to find the least weight path from \(A\) to \(F\). State the route of the path and give its weight. In the remainder of this question, any least weight paths required may be found without using a formal algorithm.
6. Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once.
7. Find the weight of the least weight route that uses every arc at least once, starting at \(A\) and ending at \(F\). Explain how you reached your answer.

4 Lucy is making party bags which she will sell to raise money for charity. She has three colours of party bag: red, yellow and blue. The bags contain balloons, sweets and toys. Lucy has a stock of 40 balloons, 80 sweets and 30 toys. The table shows how many balloons, sweets and toys are needed for one party bag of each colour. Lucy will raise \(\pounds 1\) for each bag that she sells, irrespective of its colour. She wants to calculate how many bags of each colour she should make to maximise the total amount raised for charity. Lucy has started to model the problem as an LP formulation. $$\begin{array} { l l } \text { Maximise } & P = x + y + z ,
\text { subject to } & 3 x + 7 y + 6 z \leqslant 80 . \end{array}$$

1. What does the variable \(x\) represent in Lucy's formulation?
2. Explain why the constraint \(3 x + 7 y + 6 z \leqslant 80\) must hold and write down another two similar constraints.
3. What other constraints and restrictions apply to the values of \(x , y\) and \(z\) ?
4. What assumption is needed for the objective to be valid?
5. Represent the problem as an initial Simplex tableau. Do not carry out any iterations yet.
6. Perform one iteration of the Simplex algorithm, choosing a pivot from the \(\boldsymbol { x }\) column. Explain how the choice of pivot row was made and show how each row was calculated.
7. Write down the values of \(x , y\) and \(z\) from the first iteration of the Simplex algorithm and hence find the number of bags of each colour that Lucy should make according to this non-optimal tableau. In the optimal solution Lucy makes 10 bags.
8. Without carrying out further iterations of the Simplex algorithm, find a solution in which Lucy should make 10 bags.

5 The table shows the road distances in miles between five places in Great Britain. For example, the distance between Birmingham and Cardiff is 103 miles. Ayr \(\quad\) Exeter

1. Complete the network in the answer booklet to show this information. The vertices are labelled by using the initial letter of each place.
2. List the ten arcs by increasing order of weight. Apply Kruskal's algorithm to the list. Any entries that are crossed out should still be legible. Draw the resulting minimum spanning tree and give its total weight. A sixth vertex, \(F\), is added to the network. The distances, in miles, between \(F\) and each of the other places are shown in the table below.

   \(A\)	\(B\)	\(C\)	\(D\)	\(E\)
   Distance from \(F\)	200	50	150	59	250

3. Use the weight of the minimum spanning tree from part (ii) to find a lower bound for the length of the minimum tour (cycle) that visits every vertex of the extended network with six vertices.
4. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the length of the minimum tour (cycle) through the six vertices.
5. Use the two least weight arcs through \(A\) to form a least weight path of the form \(S A T\), where \(S\) and \(T\) are two of \(\{ B , C , D , E , F \}\), and give the weight of this path. Similarly write down a least weight path of the form \(U E V\), where \(U\) and \(V\) are two of \(\{ A , B , C , D , F \}\), and give the weight of this path. You should find that the two paths that you have written down use all six vertices.
   Now find the least weight way in which the two paths can be joined together to form a cycle through all six vertices. Hence write down a tour through the six vertices that has total weight less than the upper bound. Write down the total weight of this tour.

6 The function \(\operatorname { INT } ( C )\) gives the largest integer that is less than or equal to \(C\).
For example: \(\operatorname { INT } ( 4.8 ) = 4 , \operatorname { INT } ( 7 ) = 7 , \operatorname { INT } ( 0.8 ) = 0 , \operatorname { INT } ( - 0.8 ) = - 1 , \operatorname { INT } ( - 2.4 ) = - 3\).
Consider the following algorithm.

1. Apply the algorithm using the inputs \(A = 10\) and \(B = 128\). Record the values of \(A , B , C , D , E\), and \(F\) every time they change. Record the output each time line 60 is reached.
2. Show what happens when the input values are \(A = 10\) and \(B = - 13\).