OCR D1 (Decision Mathematics 1) 2006 June

1

1. Use the first-fit method to pack the following weights in kg into boxes that can hold 8 kg each. $$\begin{array} { l l l l l l l } 2 & 4 & 3 & 3 & 2 & 5 & 4 \end{array}$$ Show clearly which weights are packed into which boxes.
2. Use the first-fit decreasing method to pack the same weights into boxes that can hold 8 kg each. You do not need to use an algorithm to sort the list into decreasing order.
3. First-fit decreasing is a quadratic order method. A computer takes 15 seconds to apply the first-fit decreasing method to a list of 1000 items; approximately how long will it take to apply the first-fit decreasing method to a list of 2000 items?

2

1. Draw three mathematically different graphs, labelled graph \(A\), graph \(B\) and graph \(C\), each with four vertices, of orders 1, 3, 3 and 3, and five arcs.
2. Explain how you know that none of the graphs from part (i) is Eulerian.

3 The network below represents a system of roads. The vertices represent villages and the arcs represent the roads between the villages. The weights on the arcs represent travel times by bicycle between villages, in minutes.
\includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-02_531_1113_1304_516} Alf wants to cycle from his home at \(A\) to visit each of the other villages and return to \(A\) in the shortest possible time.

1. Which standard network problem does Alf need to solve to find the quickest tour through all the villages?
2. Apply the nearest neighbour method starting at \(A\) to find a tour through all the villages that starts and ends at \(A\). Calculate the journey time for this tour. What can you deduce from this about the shortest possible time for Alf's tour?
3. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex \(A\) and all the arcs that are directly joined to \(A\). Start building your tree at vertex \(B\). (You do not need to represent the network as a matrix.) Give the order in which vertices are added to your tree and draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Alf's journey time.
4. Write down a route for Alf that would take him 125 minutes.

4 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]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-03_1025_826_374_657}

1. Write down inequalities that define the feasible region.
2. Find the coordinates of the four vertices of the feasible region. The objective is to maximise \(P\), where \(P = x + 2 y\).
3. Find the values of \(x\) and \(y\) that maximise \(P\), and the corresponding maximum value of \(P\). The objective is changed to minimise \(Q\), where \(Q = 2 x - y\).
4. Find the minimum value of \(Q\) and describe the set of feasible points for which \(Q\) takes this value.
5. Show that there are no points in the feasible region for which the value of \(P\) is the same as the value of \(Q\).

5 Consider the linear programming problem:

1. Using slack variables, \(s \geqslant 0\) and \(t \geqslant 0\), express the two non-trivial constraints as equations.
2. Represent the problem as an initial Simplex tableau.
3. Explain why the pivot element must be chosen from the \(x\)-column and show the calculations that are used to choose the pivot.
4. Perform one iteration of the Simplex algorithm. Show how you obtained each row of your tableau and write down the values of \(x , y , z\) and \(P\) that result from this iteration. State whether or not this is the maximum feasible value of \(P\) and describe how you know this from the values in the tableau.

1. Calculate the shortest distance that the mole must travel if it starts and ends at vertex \(A\).
2. The pipe connecting \(B\) to \(H\) is removed for repairs. By considering every possible pairing of odd vertices, and showing your working clearly, calculate the shortest distance that the mole must travel to pass along each pipe on this reduced network, starting and finishing at \(A\).

12 JUNE 2006
Afternoon
1 hour 30 minutes

• This insert should be used to answer Question 6.
• Write your name, centre number and candidate number in the spaces provided at the top of this page.
• Write your answers to Question 6 in the spaces provided in this insert, and attach it to your answer booklet.

6

1. 
   Key:
   \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_193_949_214_712} Do not cross out your working values (temporary labels)
   \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_1157_1600_648_303} Route of shortest path from \(A\) to \(J =\) \(\_\_\_\_\)
   Length of shortest path from \(A\) to \(J =\) \(\_\_\_\_\) metres
2. 1. \(\_\_\_\_\)
      Shortest distance \(=\) \(\_\_\_\_\) metres
   2. 
      \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-11_979_1429_276_440}
      Shortest distance = \(\_\_\_\_\) metres