OCR D1 (Decision Mathematics 1) 2008 January

Five boxes weigh 5 kg, 2 kg, 4 kg, 3 kg and 8 kg. They are stacked, in the order given, with the first box at the top of the stack. The boxes are to be packed into bins that can each hold up to 10 kg.

1. Use the first-fit method to put the boxes into bins. Show clearly which boxes are packed in which bins. [2]
2. Use the first-fit decreasing method to put the boxes into bins. You do not need to use an algorithm for sorting. Show clearly which boxes are packed in which bins. [2]
3. Why might the first-fit decreasing method not be practical? [1]
4. Show that if the bins can only hold up to 8 kg each it is still possible to pack the boxes into three bins. [1]

A puzzle involves a 3 by 3 grid of squares, numbered 1 to 9, as shown in Fig. 1a below. Eight of the squares are covered by blank tiles. Fig. 1b shows the puzzle with all of the squares covered except for square 4. This arrangement of tiles will be called position 4. \includegraphics{figure_1} A move consists of sliding a tile into the empty space. From position 4, the next move will result in position 1, position 5 or position 7.

1. Draw a graph with nine vertices to represent the nine positions and arcs that show which positions can be reached from one another in one move. What is the least number of moves needed to get from position 1 to position 9? [3]
2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is. [2]

Answer this question on the insert provided. \includegraphics{figure_2}

1. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight. [5]
2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(G\), and all the arcs joined to \(G\), removed. Hence find a lower bound for the travelling salesperson problem on the original network. [3]
3. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the travelling salesperson problem on the original network. [3]

Answer this question on the insert provided. Jenny needs to travel to London to arrive in time for a morning meeting. The graph below represents the various travel options that are available to her. \includegraphics{figure_3} It takes Jenny 120 minutes to drive from her home to the local airport and check in (arc \(JA\)). The journey from the local airport to Gatwick takes 80 minutes. From Gatwick to the underground station takes 60 minutes, and walking from the underground station to the meeting venue takes 15 minutes. Alternatively, Jenny could get a taxi from Gatwick to the meeting venue; this takes 80 minutes. It takes Jenny 15 minutes to drive from her house to the train station. Alternatively, she can walk to the bus stop, which takes 5 minutes, and then get a bus to the train station, taking another 20 minutes. From the train station to Paddington takes 300 minutes, and from Paddington to the underground station takes a further 20 minutes. Alternatively, Jenny could walk from Paddington to the meeting venue, taking 30 minutes. Jenny can catch a coach from her local bus stop to Victoria, taking 400 minutes. From Victoria she can either travel to the underground station, which takes 10 minutes, or she can walk to the meeting venue, which takes 15 minutes. The final option available to Jenny is to drive to a friend's house, taking 240 minutes, and then continue the journey into London by train. The journey from her friend's house to Waterloo takes Jenny 30 minutes. From here she can either go to the underground station, which takes 20 minutes, or walk to the meeting venue, which takes 40 minutes.

1. Weight the arcs on the graph in the insert to show these times. Apply Dijkstra's algorithm, starting from \(J\), to give a permanent label and order of becoming permanent at each vertex. Stop when you have assigned a permanent label to vertex \(M\). Write down the route of the shortest path from \(J\) to \(M\). [9]
2. What does the value of the permanent label at \(M\) represent? [1]
3. Give two reasons why Jenny might choose to use a different route from \(J\) to \(M\). [2]

Mark wants to decorate the walls of his study. The total wall area is 24 m\(^2\). Mark can cover the walls using any combination of three materials: panelling, paint and pinboard. He wants at least 2 m\(^2\) of pinboard and at least 10 m\(^2\) of panelling. Panelling costs £8 per m\(^2\) and it will take Mark 15 minutes to put up 1 m\(^2\) of panelling. Paint costs £4 per m\(^2\) and it will take Mark 30 minutes to paint 1 m\(^2\). Pinboard costs £10 per m\(^2\) and it will take Mark 20 minutes to put up 1 m\(^2\) of pinboard. He has all the equipment that he will need for the decorating jobs. Mark is able to spend up to £150 on the materials for the decorating. He wants to know what area should be covered with each material to enable him to complete the whole job in the shortest time possible. Mark models the problem as an LP with five constraints. His constraints are: $$x + y + z = 24,$$ $$4x + 2y + 5z \leqslant 75,$$ $$x \geqslant 10,$$ $$y \geqslant 0,$$ $$z \geqslant 2.$$

1. Identify the meaning of each of the variables \(x\), \(y\) and \(z\). [2]
2. Show how the constraint \(4x + 2y + 5z \leqslant 75\) was formed. [2]
3. Write down an objective function, to be minimised. [1]

Mark rewrites the first constraint as \(z = 24 - x - y\) and uses this to eliminate \(z\) from the problem.

1. Rewrite and simplify the objective and the remaining four constraints as functions of \(x\) and \(y\) only. [3]
2. Represent your constraints from part (iv) graphically and identify the feasible region. Your graph should show \(x\) and \(y\) values from 0 to 15 only. [4]

1. Represent the linear programming problem below by an initial Simplex tableau. [2] Maximise \quad \(P = 25x + 14y - 32z\), subject to \quad \(6x - 4y + 3z \leqslant 24\), \qquad\qquad\quad \(5x - 3y + 10z \leqslant 15\), and \qquad\qquad \(x \geqslant 0\), \(y \geqslant 0\), \(z \geqslant 0\).
2. Explain how you know that the first iteration will use a pivot from the \(x\) column. Show the calculations used to find the pivot element. [3]
3. Perform one iteration of the Simplex algorithm. Show how each row was calculated and write down the values of \(x\), \(y\), \(z\) and \(P\) that result from this iteration. [7]
4. Explain why the Simplex algorithm cannot be used to find the optimal value of \(P\) for this problem. [1]

In this question, the function INT(\(X\)) is the largest integer less than or equal to \(X\). For example, $$\text{INT}(3.6) = 3,$$ $$\text{INT}(3) = 3,$$ $$\text{INT}(-3.6) = -4.$$ Consider the following algorithm. \begin{align} \text{Step 1} \quad & \text{Input } B
\text{Step 2} \quad & \text{Input } N
\text{Step 3} \quad & \text{Calculate } F = N \div B
\text{Step 4} \quad & \text{Let } G = \text{INT}(F)
\text{Step 5} \quad & \text{Calculate } H = B \times G
\text{Step 6} \quad & \text{Calculate } C = N - H
\text{Step 7} \quad & \text{Output } C
\text{Step 8} \quad & \text{Replace } N \text{ by the value of } G
\text{Step 9} \quad & \text{If } N = 0 \text{ then stop, otherwise go back to Step 3} \end{align}

1. Apply the algorithm with the inputs \(B = 2\) and \(N = 5\). Record the values of \(F\), \(G\), \(H\), \(C\) and \(N\) each time Step 9 is reached. [5]
2. Explain what happens when the algorithm is applied with the inputs \(B = 2\) and \(N = -5\). [4]
3. Apply the algorithm with the inputs \(B = 10\) and \(N = 37\). Record the values of \(F\), \(G\), \(H\), \(C\) and \(N\) each time Step 9 is reached. What are the output values when \(B = 10\) and \(N\) is any positive integer? [4]