OCR D1 (Decision Mathematics 1) 2009 June

1 The memory requirements, in KB , for eight computer files are given below. $$\begin{array} { l l l l l l l l } 43 & 172 & 536 & 17 & 314 & 462 & 220 & 231 \end{array}$$ The files are to be grouped into folders. No folder is to contain more than 1000 KB , so that the folders are small enough to transfer easily between machines.

1. Use the first-fit method to group the files into folders.
2. Use the first-fit decreasing method to group the files into folders. First-fit decreasing is a quadratic order algorithm.
3. A computer takes 1.3 seconds to apply first-fit decreasing to a list of 500 numbers. Approximately how long will it take to apply first-fit decreasing to a list of 5000 numbers?
4. Explain why it is impossible to draw a graph with four vertices in which the vertex orders are 1, 2, 3 and 3 . A simple graph is one in which any two vertices are directly joined by at most one arc and no vertex is directly joined 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.
5. (a) Draw a graph with five vertices of orders \(1,1,2,2\) and 4 that is neither simple nor connected.
   (b) Explain why your graph from part (a) is not semi-Eulerian.
   (c) Draw a semi-Eulerian graph with five vertices of orders 1, 1, 2, 2 and 4. Six people (Ann, Bob, Caz, Del, Eric and Fran) are represented by the vertices of a graph. Each pair of vertices is joined by an arc, forming a complete graph. If an arc joins two vertices representing people who have met it is coloured blue, but if it joins two vertices representing people who have not met it is coloured red.
6. (a) Explain why the vertex corresponding to Ann must be joined to at least three of the others by arcs that are the same colour.
   (b) Now assume that Ann has met Bob, Caz and Del. Bob, Caz and Del may or may not have met one another. Explain why the graph must contain at least one triangle of arcs that are all the same colour.

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]{fe06fa02-9f5d-4082-8e96-feea705d3fa2-3_933_935_397_605}

1. Write down the inequalities that define the feasible region.
2. Write down the coordinates of the three vertices of the feasible region. The objective is to maximise \(2 x + 3 y\).
3. Find the values of \(x\) and \(y\) at the optimal point, and the corresponding maximum value of \(2 x + 3 y\). The objective is changed to maximise \(2 x + k y\), where \(k\) is positive.
4. Find the range of values of \(k\) for which the optimal point is the same as in part (iii).

4 Answer this question on the insert provided. The vertices in the network below represent the junctions between main roads near Ayton ( \(A\) ). The arcs represent the roads and the weights on the arcs represent distances in miles.
\includegraphics[max width=\textwidth, alt={}, center]{fe06fa02-9f5d-4082-8e96-feea705d3fa2-4_812_1198_443_475}

1. On the diagram in the insert, use Dijkstra's algorithm to find the shortest path from \(A\) to \(H\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from \(A\) to \(H\) and give its length in miles. Simon is a highways surveyor. He needs to check that there are no potholes in any of the roads. He will start and end at Ayton.
2. Which standard network problem does Simon need to solve to find the shortest route that uses every arc? The total weight of all the arcs is 67.5 miles.
3. Use an appropriate algorithm to find the length of the shortest route that Simon can use. Show all your working. (You may find the lengths of shortest paths between nodes by using your answer to part (i) or by inspection.) Suppose that, instead, Simon wants to find the shortest route that uses every arc, starting from \(A\) and ending at \(H\).
4. Which arcs does Simon need to travel twice? What is the length of the shortest route that he can use? There is a set of traffic lights at each junction. Simon's colleague Amber needs to check that all the traffic lights are working correctly. She will start and end at the same junction.
5. Show that the nearest neighbour method fails on this network if it is started from \(A\).
6. Apply the nearest neighbour method starting from \(C\) to find an upper bound for the distance that Amber must travel.
7. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting node \(A\) and all the arcs that are directly joined to node \(A\). Start building your tree at node B. (You do not need to represent the network as a matrix.) Mark the arcs in your tree on the diagram in the insert. Give the order in which nodes are added to your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Amber must travel.

5 Badgers is a small company that makes badges to customers' designs. Each badge must pass through four stages in its production: printing, stamping out, fixing pin and checking. The badges can be laminated, metallic or plastic. The times taken for \(\mathbf { 1 0 0 }\) badges of each type to pass through each of the stages and the profits that Badgers makes on every 100 badges are shown in the table below. The table also shows the total time available for each of the production stages. Suppose that the company makes \(x\) hundred laminated badges, \(y\) hundred metallic badges and \(z\) hundred plastic badges.

1. Show that the printing time leads to the constraint \(x + y + 2 z \leqslant 600\). Write down and simplify constraints for the time spent on each of the other production stages.
2. What other constraint is there on the values of \(x , y\) and \(z\) ? The company wants to maximise the profit from the sale of badges.
3. Write down an appropriate objective function, to be maximised.
4. Represent Badgers' problem as an initial Simplex tableau.
5. Use the Simplex algorithm, pivoting first on a value chosen from the \(x\)-column and then on a value chosen from the \(y\)-column. Interpret your solution and the values of the slack variables in the context of the original problem.