Questions (33218 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 Unit 1 Unit 2 Unit 3 Unit 4
Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 PURE S1 S2 S3 S4 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
Sort by: Default | Easiest first | Hardest first
AQA D1 2011 January Q5
8 marks Moderate -0.3
Norris delivers newspapers to houses on an estate. The network shows the streets on the estate. The number on each edge shows the length of the street, in metres. Norris starts from the newsagents located at vertex \(A\), and he must walk along all the streets at least once before returning to the newsagents. \includegraphics{figure_5} The total length of the streets is 1215 metres.
  1. Give a reason why it is not possible to start at \(A\), walk along each street once only, and return to \(A\). [1]
  2. Find the length of an optimal Chinese postman route around the estate, starting and finishing at \(A\). [5]
  3. For an optimal Chinese postman route, state:
    1. the number of times that the vertex \(F\) would occur; [1]
    2. the number of times that the vertex \(H\) would occur. [1]
AQA D1 2011 January Q6
5 marks Easy -1.2
  1. The complete graph \(K_n\) has every one of its \(n\) vertices connected to each of the other vertices by a single edge.
    1. Find the total number of edges in the graph \(K_5\). [1]
    2. State the number of edges in a minimum spanning tree for the graph \(K_5\). [1]
    3. State the number of edges in a Hamiltonian cycle for the graph \(K_5\). [1]
  2. A simple graph \(G\) has six vertices and nine edges, and \(G\) is Eulerian. Draw a sketch to show a possible graph \(G\). [2]
AQA D1 2011 January Q7
10 marks Moderate -0.8
Fred delivers bread to five shops, \(A\), \(B\), \(C\), \(D\) and \(E\). Fred starts his deliveries at shop \(B\), and travels to each of the other shops once before returning to shop \(B\). Fred wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the shops. $$\begin{array}{c|ccccc} & A & B & C & D & E \\ \hline A & - & 3 & 11 & 15 & 5 \\ B & 3 & - & 18 & 12 & 4 \\ C & 11 & 18 & - & 5 & 16 \\ D & 15 & 12 & 5 & - & 10 \\ E & 5 & 4 & 16 & 10 & - \end{array}$$
  1. Find the travelling time for the tour \(BACDEB\). [1]
  2. Use the nearest neighbour algorithm, starting at \(B\), to find another upper bound for the travelling time for Fred's tour. [3]
  3. By deleting \(C\), find a lower bound for the travelling time for Fred's tour. [4]
  4. Sketch a network showing the edges that give you the lower bound in part (c) and comment on its significance. [2]
AQA D1 2011 January Q8
7 marks Easy -1.2
A student is tracing the following algorithm with positive integer values of \(A\) and \(B\). The function INT gives the integer part of a number, eg INT(2.3) = 2 and INT(3.8) = 3. Line 10: Let \(X = 0\) Line 20: Input \(A\), \(B\) Line 30: If INT\((A/2) = A/2\) then go to Line 50 Line 40: Let \(X = X + B\) Line 50: If \(A = 1\) then go to Line 90 Line 60: Let \(A =\) INT\((A/2)\) Line 70: Let \(B = 2 \times B\) Line 80: Go to Line 30 Line 90: Print \(X\) Line 100: End
  1. Trace the algorithm in the case where the input values are \(A = 20\) and \(B = 8\). [4]
  2. State the purpose of the algorithm. [1]
  3. Another student changed Line 50 to Line 50: If \(A = 1\) then go to Line 80 Explain what would happen if this algorithm were traced. [2]
AQA D1 2011 January Q9
13 marks Moderate -0.3
Herman is packing some hampers. Each day, he packs three types of hamper: basic, standard and luxury. Each basic hamper has 6 tins, 9 packets and 6 bottles. Each standard hamper has 9 tins, 6 packets and 12 bottles. Each luxury hamper has 9 tins, 9 packets and 18 bottles. Each day, Herman has 600 tins and 600 packets available, and he must use at least 480 bottles. Each day, Herman packs \(x\) basic hampers, \(y\) standard hampers and \(z\) luxury hampers.
  1. In addition to \(x \geqslant 0\), \(y \geqslant 0\) and \(z \geqslant 0\), find three inequalities in \(x\), \(y\) and \(z\) that model the above constraints, simplifying each inequality. [4]
  2. On a particular day, Herman packs the same number of standard hampers as luxury hampers.
    1. Show that your answers in part (a) become \(x + 3y \leqslant 100\) \(3x + 5y \leqslant 200\) \(x + 5y \geqslant 80\) [2]
    2. On the grid opposite, draw a suitable diagram to represent Herman's situation, indicating the feasible region. [4]
    3. Use your diagram to find the maximum total number of hampers that Herman can pack on that day. [2]
    4. Find the number of each type of hamper that Herman packs that corresponds to your answer to part (b)(iii). [1]
AQA D1 2010 June Q1
4 marks Easy -1.2
  1. Draw a bipartite graph representing the following adjacency matrix. [2 marks] $$\begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\ \hline A & 1 & 0 & 0 & 0 & 1 \\ B & 0 & 1 & 1 & 1 & 0 \\ C & 0 & 1 & 1 & 1 & 0 \\ D & 1 & 0 & 0 & 0 & 1 \\ E & 1 & 0 & 0 & 0 & 1 \\ \end{array}$$
  2. If \(A\), \(B\), \(C\), \(D\) and \(E\) represent five people and 1, 2, 3, 4 and 5 represent five tasks to which they are to be assigned, explain why a complete matching is impossible. [2 marks]
AQA D1 2010 June Q2
9 marks Easy -1.8
    1. Use a bubble sort to rearrange the following numbers into ascending order, showing the list of numbers after each pass. 6 \quad 2 \quad 3 \quad 5 \quad 4 [3 marks]
    2. Write down the number of comparisons on the first pass. [1 mark]
    1. Use a shuttle sort to rearrange the following numbers into ascending order, showing the list of numbers after each pass. 6 \quad 2 \quad 3 \quad 5 \quad 4 [4 marks]
    2. Write down the number of comparisons on the first pass. [1 mark]
AQA D1 2010 June Q3
11 marks Easy -1.2
The network shows 10 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. \includegraphics{figure_3}
  1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the 10 towns. [6 marks]
  2. State the length of your minimum spanning tree. [1 mark]
  3. Draw your minimum spanning tree. [3 marks]
  4. If Prim's algorithm, starting at \(B\), had been used to find the minimum spanning tree, state which edge would have been the final edge to complete the minimum spanning tree. [1 mark]
AQA D1 2010 June Q4
14 marks Moderate -0.3
The network below shows 13 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. The total of all the times is 384 minutes.
  1. Use Dijkstra's algorithm on the network below, starting from \(M\), to find the minimum time to travel from \(M\) to each of the other towns. [7 marks]
    1. Find the travelling time of an optimum Chinese postman route around the network, starting and finishing at \(M\). [6 marks]
    2. State the number of times that the vertex \(F\) would appear in a corresponding route. [1 mark]
\includegraphics{figure_4}
AQA D1 2010 June Q5
10 marks Moderate -0.8
Phil, a squash coach, wishes to buy some equipment for his club. In a town centre, there are six shops, \(G\), \(I\), \(N\), \(R\), \(S\) and \(T\), that sell the equipment. The time, in seconds, to walk between each pair of shops is shown in the table. Phil intends to check prices by visiting each of the six shops before returning to his starting point. $$\begin{array}{c|cccccc} & G & I & N & R & S & T \\ \hline G & - & 81 & 82 & 86 & 72 & 76 \\ I & 81 & - & 80 & 82 & 68 & 73 \\ N & 82 & 80 & - & 84 & 70 & 74 \\ R & 86 & 82 & 84 & - & 74 & 70 \\ S & 72 & 68 & 70 & 74 & - & 64 \\ T & 76 & 73 & 74 & 70 & 64 & - \\ \end{array}$$
  1. Use the nearest neighbour algorithm starting from \(S\) to find an upper bound for Phil's minimum walking time. [4 marks]
  2. Write down a tour starting from \(N\) which has a total walking time equal to your answer to part (a). [1 mark]
  3. By deleting \(S\), find a lower bound for Phil's minimum walking time. [5 marks]
AQA D1 2010 June Q6
17 marks Standard +0.3
Phil is to buy some squash balls for his club. There are three different types of ball that he can buy: slow, medium and fast. He must buy at least 190 slow balls, at least 50 medium balls and at least 50 fast balls. He must buy at least 300 balls in total. Each slow ball costs £2.50, each medium ball costs £2.00 and each fast ball costs £2.00. He must spend no more than £1000 in total. At least 60% of the balls that he buys must be slow balls. Phil buys \(x\) slow balls, \(y\) medium balls and \(z\) fast balls.
  1. Find six inequalities that model Phil's situation. [4 marks]
  2. Phil decides to buy the same number of medium balls as fast balls.
    1. Show that the inequalities found in part (a) simplify to give $$x \geq 190, \quad y \geq 50, \quad x + 2y \geq 300, \quad 5x + 8y \leq 2000, \quad y \leq \frac{1}{3}x$$ [2 marks]
    2. Phil sells all the balls that he buys to members of the club. He sells each slow ball for £3.00, each medium ball for £2.25 and each fast ball for £2.25. He wishes to maximise his profit. On Figure 1 on page 14, draw a diagram to enable this problem to be solved graphically, indicating the feasible region and the direction of an objective line. [7 marks]
    3. Find Phil's maximum possible profit and state the number of each type of ball that he must buy to obtain this maximum profit. [4 marks]
AQA D1 2010 June Q7
6 marks Easy -1.2
A student is testing a numerical method for finding an approximation for \(\pi\). The algorithm that the student is using is as follows. Line 10 \quad Input \(A\), \(B\), \(C\), \(D\), \(E\) Line 20 \quad Let \(A = A + 2\) Line 30 \quad Let \(B = -B\) Line 40 \quad Let \(C = \frac{B}{A}\) Line 50 \quad Let \(D = D + C\) Line 60 \quad Let \(E = (D - 3.14)^2\) Line 70 \quad If \(E < 0.05\) then go to Line 90 Line 80 \quad Go to Line 20 Line 90 \quad Print '\(\pi\) is approximately', \(D\) Line 100 \quad End Trace the algorithm in the case where the input values are $$A = 1, \quad B = 4, \quad C = 0, \quad D = 4, \quad E = 0$$ [6 marks]
AQA D1 2010 June Q8
4 marks Moderate -0.8
A simple connected graph has six vertices.
  1. One vertex has degree \(x\). State the greatest and least possible values of \(x\). [2 marks]
  2. The six vertices have degrees $$x - 2, \quad x - 2, \quad x, \quad 2x - 4, \quad 2x - 4, \quad 4x - 12$$ Find the value of \(x\), justifying your answer. [2 marks]
OCR D1 2008 January Q1
6 marks Easy -1.8
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]
OCR D1 2008 January Q2
5 marks Moderate -0.8
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]
OCR D1 2008 January Q3
11 marks Moderate -0.8
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]
OCR D1 2008 January Q4
12 marks Moderate -0.8
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]
OCR D1 2008 January Q5
12 marks Moderate -0.8
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]
OCR D1 2008 January Q6
13 marks Moderate -0.3
  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]
OCR D1 2008 January Q7
13 marks Moderate -0.8
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]
OCR D1 2012 January Q1
6 marks Easy -1.8
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. 3 \quad 6 \quad 2 \quad 6 \quad 5 \quad 7 \quad 1 \quad 4 \quad 9 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. [6]
OCR D1 2012 January Q2
8 marks Moderate -0.8
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]
  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. [2]
  3. What is the maximum number of arcs that a simply connected Eulerian graph with six vertices can have? Explain your reasoning. [2]
  4. State how you know that the graph below is semi-Eulerian and write down a semi-Eulerian trail for the graph. [2]
\includegraphics{figure_2}
OCR D1 2012 January Q3
13 marks Moderate -0.8
\includegraphics{figure_3}
  1. 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. [6]
In the remainder of this question, any least weight paths required may be found without using a formal algorithm.
  1. 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. [3]
  2. 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]
OCR D1 2012 January Q4
18 marks Moderate -0.8
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.
Colour of party bagBalloonsSweetsToys
Red535
Yellow472
Blue663
Lucy will raise £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. Maximise \quad \(P = x + y + z\), subject to \quad \(3x + 7y + 6z \leq 80\).
  1. What does the variable \(x\) represent in Lucy's formulation? [1]
  2. Explain why the constraint \(3x + 7y + 6z \leq 80\) must hold and write down another two similar constraints. [3]
  3. What other constraints and restrictions apply to the values of \(x\), \(y\) and \(z\)? [1]
  4. What assumption is needed for the objective to be valid? [1]
  5. Represent the problem as an initial Simplex tableau. Do not carry out any iterations yet. [3]
  6. Perform one iteration of the Simplex algorithm, choosing a pivot from the \(x\) column. Explain how the choice of pivot row was made and show how each row was calculated. [6]
  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. [2]
In the optimal solution Lucy makes 10 bags.
  1. Without carrying out further iterations of the Simplex algorithm, find a solution in which Lucy should make 10 bags. [1]
OCR D1 2012 January Q5
18 marks Moderate -0.8
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
250Birmingham
350103Cardiff
235104209Doncaster
446157121261Exeter
  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]
  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. [4]
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.
ABCDE
Distance from F2005015059250
  1. 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. [2]
  2. 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. [2]
  3. Use the two least weight arcs through A to form a least weight path of the form \(SAT\), 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 \(UEV\), 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. [8]