OCR D1 (Decision Mathematics 1) 2008 January

1 Five boxes weigh \(5 \mathrm {~kg} , 2 \mathrm {~kg} , 4 \mathrm {~kg} , 3 \mathrm {~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. 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.
3. Why might the first-fit decreasing method not be practical?
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.

2 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. \begin{table}[h]

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.
2. Explain what happens when the algorithm is applied with the inputs \(B = 2\) and \(N = - 5\).
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?

3

1. 
   \includegraphics[max width=\textwidth, alt={}, center]{1ecf9738-d968-49f6-8c70-0aa50b57cb69-10_629_951_276_596}
   \(A D = 16\)
   \(C D = 18\)
   \(C F = 21\)
   \(A C = 23\)
   \(D F = 34\)
   \(B E = 35\)
   \(B G = 46\)
   \(C \bullet \quad \bullet D\)
   B
   \(A B = 50\)
   \(E G = 55\)
   \(F G = 58\)
   \(A E = 80\)
   \(A F = 100\)
   \includegraphics[max width=\textwidth, alt={}, center]{1ecf9738-d968-49f6-8c70-0aa50b57cb69-10_497_56_1073_1084}
   • \(E\)
     G
   Total weight of arcs in minimum spanning tree \(=\) \(\_\_\_\_\)
2. \(\_\_\_\_\)
   Weight of spanning tree for the network with vertex \(G\) removed = \(\_\_\_\_\)
   Lower bound for travelling salesperson problem on original network = \(\_\_\_\_\)
3. \(\_\_\_\_\) Upper bound for travelling salesperson problem on original network = \(\_\_\_\_\)

5 Mark wants to decorate the walls of his study. The total wall area is \(24 \mathrm {~m} ^ { 2 }\). Mark can cover the walls using any combination of three materials: panelling, paint and pinboard. He wants at least \(2 \mathrm {~m} ^ { 2 }\) of pinboard and at least \(10 \mathrm {~m} ^ { 2 }\) of panelling. Panelling costs \(\pounds 8\) per \(\mathrm { m } ^ { 2 }\) and it will take Mark 15 minutes to put up \(1 \mathrm {~m} ^ { 2 }\) of panelling. Paint costs \(\pounds 4\) per \(\mathrm { m } ^ { 2 }\) and it will take Mark 30 minutes to paint \(1 \mathrm {~m} ^ { 2 }\). Pinboard costs \(\pounds 10\) per \(\mathrm { m } ^ { 2 }\) and it will take Mark 20 minutes to put up \(1 \mathrm {~m} ^ { 2 }\) of pinboard. He has all the equipment that he will need for the decorating jobs. Mark is able to spend up to \(\pounds 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: $$\begin{aligned} & x + y + z = 24
& 4 x + 2 y + 5 z \leqslant 75
& x \geqslant 10
& y \geqslant 0
& z \geqslant 2 \end{aligned}$$

1. Identify the meaning of each of the variables \(x , y\) and \(z\).
2. Show how the constraint \(4 x + 2 y + 5 z \leqslant 75\) was formed.
3. Write down an objective function, to be minimised. Mark rewrites the first constraint as \(z = 24 - x - y\) and uses this to eliminate \(z\) from the problem.
4. Rewrite and simplify the objective and the remaining four constraints as functions of \(x\) and \(y\) only.
5. Represent your constraints from part (iv) graphically and identify the feasible region. Your graph should show \(x\) and \(y\) values from 9 to 15 only.

6

1. Represent the linear programming problem below by an initial Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 25 x + 14 y - 32 z ,
   \text { subject to } & 6 x - 4 y + 3 z \leqslant 24 ,
   & 5 x - 3 y + 10 z \leqslant 15 ,
   \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
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. 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.
4. Explain why the Simplex algorithm cannot be used to find the optimal value of \(P\) for this problem.

7 In this question, the function INT( \(X\) ) is the largest integer less than or equal to \(X\). For example, $$\begin{aligned} & \operatorname { INT } ( 3.6 ) = 3 ,
& \operatorname { INT } ( 3 ) = 3 ,
& \operatorname { INT } ( - 3.6 ) = - 4 . \end{aligned}$$ Consider the following algorithm.

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.
2. Explain what happens when the algorithm is applied with the inputs \(B = 2\) and \(N = - 5\).
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?