Questions D1 (932 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 2012 June Q4
8 marks Easy -1.2
4 The edges on the network below represent some major roads in a city. The number on each edge is the minimum time taken, in minutes, to drive along that road.
    1. Use Dijkstra's algorithm on the network to find the shortest possible driving time from \(A\) to \(J\).
    2. Write down the corresponding route.
  2. A new ring road is to be constructed connecting \(A\) to \(J\) directly. Find the maximum length of this new road from \(A\) to \(J\) if the time taken to drive along it, travelling at an average speed of \(90 \mathrm {~km} / \mathrm { h }\), is to be no more than the time found in part (a)(i). \section*{(a)(i)} \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-08_912_1276_1053_429}
AQA D1 2012 June Q5
8 marks Standard +0.3
5 The network below shows some streets in a town. The number on each edge shows the length of that street, in metres. Leaflets are to be distributed by a restaurant owner, Tony, from his restaurant located at vertex \(B\). Tony must start from his restaurant, walk along all the streets at least once, before returning to his restaurant. \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-10_643_1353_625_340} The total length of the streets is 2430 metres.
  1. Find the length of an optimal Chinese postman route for Tony.
  2. Colin also wishes to distribute some leaflets. He starts from his house at \(H\), walks along all the streets at least once, before finishing at the restaurant at \(B\). Colin wishes to walk the minimum distance. Find the length of an optimal route for Colin.
  3. David also walks along all the streets at least once. He can start at any vertex and finish at any vertex. David also wishes to walk the minimum distance.
    1. Find the length of an optimal route for David.
    2. State the vertices from which David could start in order to achieve this optimal route.
AQA D1 2012 June Q6
7 marks Moderate -0.8
6 The complete graph \(K _ { n } ( n > 1 )\) has every one of its \(n\) vertices connected to each of the other vertices by a single edge.
  1. Draw the complete graph \(K _ { 4 }\).
    1. Find the total number of edges for the graph \(K _ { 8 }\).
    2. Give a reason why \(K _ { 8 }\) is not Eulerian.
  3. For the graph \(K _ { n }\), state in terms of \(n\) :
    1. the total number of edges;
    2. the number of edges in a minimum spanning tree;
    3. the condition for \(K _ { n }\) to be Eulerian;
    4. the condition for the number of edges of a Hamiltonian cycle to be equal to the number of edges of an Eulerian cycle.
AQA D1 2012 June Q7
11 marks Moderate -0.8
7 Rupta, a sales representative, has to visit six shops, \(A , B , C , D , E\) and \(F\). Rupta starts at shop \(A\) and travels to each of the other shops once, before returning to shop \(A\). Rupta wishes to keep her travelling time to a minimum. The table shows the travelling times, in minutes, between the shops.
AQA D1 2012 June Q8
8 marks Easy -1.2
8 The following algorithm finds an estimate of the value of the number represented by the symbol e:
Line 10Let \(A = 1 , B = 1 , C = 1\)
Line 20Let \(D = A\)
Line 30Let \(C = C \times B\)
Line 40Let \(D = D + ( 1 / C )\)
Line 50If \(B = 4\) then go to Line 80
Line 60Let \(B = B + 1\)
Line 70Go to Line 30
Line 80Print 'An estimate of e is', \(D\)
Line 90End
  1. Trace the algorithm.
  2. A student miscopied Line 70 . His line was
    Line 70 Go to Line 10
    Explain what would happen if his algorithm were traced.
AQA D1 2012 June Q9
14 marks Moderate -0.3
9 Ollyin is buying new pillows for his hotel. He buys three types of pillow: soft, medium and firm. He must buy at least 100 soft pillows and at least 200 medium pillows.
He must buy at least 400 pillows in total.
Soft pillows cost \(\pounds 4\) each. Medium pillows cost \(\pounds 3\) each. Firm pillows cost \(\pounds 4\) each.
He wishes to spend no more than \(\pounds 1800\) on new pillows.
At least \(40 \%\) of the new pillows must be medium pillows.
Ollyin buys \(x\) soft pillows, \(y\) medium pillows and \(z\) firm pillows.
  1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), find five inequalities in \(x , y\) and \(z\) that model the above constraints.
  2. Ollyin decides to buy twice as many soft pillows as firm pillows.
    1. Show that three of your answers in part (a) become $$\begin{aligned} 3 x + 2 y & \geqslant 800 \\ 2 x + y & \leqslant 600 \\ y & \geqslant x \end{aligned}$$
    2. On the grid opposite, draw a suitable diagram to represent Ollyin's situation, indicating the feasible region.
    3. Use your diagram to find the maximum total number of pillows that Ollyin can buy.
    4. Find the number of each type of pillow that Ollyin can buy that corresponds to your answer to part (b)(iii).
      \includegraphics[max width=\textwidth, alt={}]{1258a6d3-558a-46dc-a916-d71f71b175ff-20_2256_1707_221_153}
AQA D1 2013 June Q1
7 marks Moderate -0.8
1 Six people, Andy, Bob, Colin, Dev, Eric and Faisal, are to be allocated to six tasks, \(1,2,3,4,5\) and 6 . The following table shows the tasks that each person is able to undertake.
PersonTask
Andy1,3
Bob1,4
Colin2,3
Dev\(4,5,6\)
Eric\(2,5,6\)
Faisal1,3
  1. Represent this information on a bipartite graph.
  2. Initially, Bob is allocated to task 1, Colin to task 3, Dev to task 5 and Eric to task 2. Demonstrate, by using an alternating path algorithm from this initial matching, how each person can be allocated to a different task.
AQA D1 2013 June Q2
5 marks Easy -1.8
2
  1. Use the quicksort algorithm to rearrange the following numbers into ascending order, showing the new arrangement after each pass. You must indicate the pivot(s) being used on each pass. $$2 , \quad 12 , \quad 17 , \quad 18 , \quad 5 , \quad 13$$
  2. For the first pass, write down the number of comparisons.
AQA D1 2013 June Q3
9 marks Moderate -0.5
3 The following network shows the lengths, in miles, of roads connecting ten villages, \(A , B , C , \ldots , J\). \includegraphics[max width=\textwidth, alt={}, center]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-06_899_1458_397_285}
    1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the network.
    2. Find the length of your minimum spanning tree.
    3. Draw your minimum spanning tree.
  2. Prim's algorithm from different starting points produces the same minimum spanning tree. State the final edge that would be added to complete the minimum spanning tree if the starting point were:
    1. \(A\);
    2. \(F\).
AQA D1 2013 June Q4
12 marks Moderate -0.8
4 Sarah is a mobile hairdresser based at \(A\). Her day's appointments are at five places: \(B , C , D , E\) and \(F\). She can arrange the appointments in any order. She intends to travel from one place to the next until she has visited all of the places, starting and finishing at \(A\). The following table shows the times, in minutes, that it takes to travel between the six places.
\cline { 2 - 7 } \multicolumn{1}{c|}{}\(\boldsymbol { A }\)\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)\(\boldsymbol { E }\)\(\boldsymbol { F }\)
\(\boldsymbol { A }\)-1511142712
\(\boldsymbol { B }\)15-13192415
\(\boldsymbol { C }\)1113-101912
\(\boldsymbol { D }\)141910-2615
\(\boldsymbol { E }\)27241926-27
\(\boldsymbol { F }\)1215121527-
  1. Sarah decides to visit the places in the order \(A B C D E F A\). Find the travelling time of this tour.
  2. Explain why this answer can be considered as being an upper bound for the minimum travelling time of Sarah's tour.
  3. Use the nearest neighbour algorithm, starting from \(A\), to find another upper bound for the minimum travelling time of Sarah's tour.
  4. By deleting \(A\), find a lower bound for the minimum travelling time of Sarah's tour.
  5. Sarah thinks that she can reduce her travelling time to 75 minutes. Explain why she is wrong.
AQA D1 2013 June Q5
17 marks Standard +0.3
5 The network on the page opposite shows the times, in minutes, taken by police cars to drive along roads connecting 12 places, \(A , B , \ldots , L\). On a particular day, there are three police cars in the area at \(A , E\) and \(J\). There is an emergency at \(G\) and all three police cars drive to \(G\).
    1. Use Dijkstra's algorithm on the network, starting from \(\boldsymbol { G }\), to find the minimum driving time for each of the police cars to arrive at \(G\).
    2. For each of the police cars, write down the route corresponding to the minimum driving time in your answer to part (a)(i).
  2. Each day, a police car has to drive along each road at least once, starting and finishing at \(A\). For an optimal Chinese postman route:
    1. find the driving time for the police car;
    2. state the number of times that the vertex \(B\) would appear.
      \includegraphics[max width=\textwidth, alt={}]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-13_2486_1709_221_153}
AQA D1 2013 June Q6
9 marks Easy -1.2
6 A student is tracing the following algorithm. The function INT gives the integer part of any number, eg \(\operatorname { INT } ( 2.3 ) = 2\) and \(\operatorname { INT } ( 6.7 ) = 6\). Line 10 Input \(A , B\) Line \(20 \quad\) Let \(C = \operatorname { INT } ( A \div B )\) Line 30 Let \(D = B \times C\) Line \(40 \quad\) Let \(E = A - D\) Line 50 If \(E = 0\) then go to Line 90
Line 60 Let \(A = B\) Line \(70 \quad\) Let \(B = E\) Line 80 Go to Line 20
Line 90 Print \(B\) Line 100 Stop
  1. Trace the algorithm when the input values are:
    1. \(A = 36\) and \(B = 16\);
    2. \(A = 11\) and \(B = 7\).
  2. State the purpose of the algorithm.
AQA D1 2013 June Q7
16 marks Moderate -0.3
7 Paul is a florist. Every day, he makes three types of floral bouquet: gold, silver and bronze. Each gold bouquet has 6 roses, 6 carnations and 6 dahlias.
Each silver bouquet has 4 roses, 6 carnations and 4 dahlias.
Each bronze bouquet has 3 roses, 4 carnations and 4 dahlias.
Each day, Paul must use at least 420 roses and at least 480 carnations, but he can use at most 720 dahlias. Each day, Paul makes \(x\) gold bouquets, \(y\) silver bouquets and \(z\) bronze bouquets.
  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.
  2. On a particular day, Paul makes the same number of silver bouquets as bronze bouquets.
    1. Show that \(x\) and \(y\) must satisfy the following inequalities. $$\begin{aligned} & 6 x + 7 y \geqslant 420 \\ & 3 x + 5 y \geqslant 240 \\ & 3 x + 4 y \leqslant 360 \end{aligned}$$
    2. Paul makes a profit of \(\pounds 4\) on each gold bouquet sold, a profit of \(\pounds 2.50\) on each silver bouquet sold and a profit of \(\pounds 2.50\) on each bronze bouquet sold. Each day, Paul sells all the bouquets he makes. Paul wishes to maximise his daily profit, \(\pounds P\). Draw a suitable diagram, on the grid opposite, to enable this problem to be solved graphically, indicating the feasible region and the direction of the objective line.
      (6 marks)
    3. Use your diagram to find Paul's maximum daily profit and the number of each type of bouquet he must make to achieve this maximum.
  3. On another day, Paul again makes the same number of silver bouquets as bronze bouquets, but he makes a profit of \(\pounds 2\) on each gold bouquet sold, a profit of \(\pounds 6\) on each silver bouquet sold and a profit of \(\pounds 6\) on each bronze bouquet sold. Find Paul's maximum daily profit, and the number of each type of bouquet he must make to achieve this maximum.
    (3 marks) Turn over -
OCR D1 2005 January Q1
5 marks Easy -1.8
1 Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l l } 6 & 5 & 9 & 4 & 5 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.
OCR D1 2005 January Q2
5 marks Moderate -0.8
2
  1. A graph has six vertices; two are of order 3 and the rest are of order 4. Calculate the number of arcs in the graph, showing your working.
  2. Is the graph Eulerian, semi-Eulerian or neither? Give a reason to support your answer. 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 connected, directly or indirectly, to every other vertex.
  3. Explain why a simple graph with six vertices, two of order 3 and the rest of order 4, must also be a connected graph.
OCR D1 2005 January Q3
7 marks Standard +0.3
3 The diagram shows a network. The weights on the arcs represent distances in miles. The direct path between any two adjacent vertices is never longer than any indirect path. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-02_490_748_1372_699}
  1. By deleting vertex \(U\) and all arcs connected to \(U\), find a lower bound for the length of the shortest cycle that visits every vertex of this network.
  2. Find a vertex that can be used as the start vertex for the nearest neighbour method to give a cycle that passes through every vertex of this network. Give your cycle and its length.
OCR D1 2005 January Q4
12 marks Moderate -0.3
4 [Answer this question on the insert provided.]
A competition challenges teams to hike across a moor, visiting each of eight peaks, in the quickest possible time. The teams all start at peak \(A\) and finish at peak \(H\), but other than this the peaks may be visited in any order. The estimated journey times, in hours, between peaks are shown in the table. A dash in the table means that there is no direct route between two peaks.
\(A\)\(B\)CD\(E\)\(F\)G\(H\)
A-423----
\(B\)4-1-3---
C21-2-65-
\(D\)3-2---4-
\(E\)-3---8-7
\(F\)--6-8--8
\(G\)--54---9
\(H\)----789-
  1. Use Prim's algorithm on the table in the insert to find a minimum spanning tree. Start by crossing out row \(A\). Show which entries in the table are chosen and indicate the order in which the rows are deleted. What can you deduce from this answer about the quickest possible time needed to complete the challenge?
  2. On the insert, draw a network to represent the information given in the table above. A team decides to visit each peak exactly once on the hike from peak \(A\) to peak \(H\).
  3. Explain why the team cannot use the arc \(A C\).
  4. Explain why the team must use the arc \(E F\).
  5. There are only two possible routes that the team can use. Find both routes and determine which is the quicker route.
OCR D1 2005 January Q5
13 marks Standard +0.8
5 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]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-04_1118_816_404_662}
  1. Write down four inequalities that define the feasible region. The objective is to maximise \(P = 5 x + 3 y\).
  2. Using the graph or otherwise, obtain the coordinates of the vertices of the feasible region and hence find the values of \(x\) and \(y\) that maximise \(P\), and the corresponding maximum value of \(P\). The objective is changed to maximise \(Q = a x + 3 y\).
  3. For what set of values of \(a\) is the maximum value of \(Q\) equal to 3?
OCR D1 2005 January Q6
13 marks Standard +0.8
6 Consider the linear programming problem:
maximise\(P = 2 x - 5 y - z\),
subject to\(5 x + 3 y - 5 z \leqslant 15\),
\(2 x + 6 y + 8 z \leqslant 24\),
and\(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).
  1. Using slack variables, \(s\) and \(t\), express the non-trivial constraints as two equations.
  2. Represent the problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm.
  3. Use the Simplex algorithm to find the values of \(x , y\) and \(z\) for which \(P\) is maximised, subject to the constraints above.
  4. The value 15 in the first constraint is increased to a new value \(k\). As a result the pivot for the first iteration changes. Show what effect this has on the final value of \(y\).
OCR D1 2005 January Q7
17 marks Moderate -0.8
7 [Answer this question on the insert provided.]
The network below represents a simplified map of the centre of a small town. The arcs represent roads and the weights on the arcs represent distances, in units of 100 metres. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-06_725_1259_495_443}
    1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest route from \(A\) to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. State the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(J\), and give their lengths. [7]
    2. The shortest route from \(E\) to \(J\) that passes through every vertex can be treated as being made up of two parts, one from \(E\) to \(A\) and the other from \(A\) to \(J\). Use your answers to part (i) to write down the length of the shortest such route. List the vertices in the order that they are visited in travelling from \(E\) to \(J\) using this route.
    3. Explain why a similar approach to that used in parts (a)(i) and (a)(ii) would not give the shortest route between \(G\) and \(H\) that passes through every vertex.
  2. By considering pairings of odd nodes, find the length of the shortest route that starts at \(A\) and ends at \(E\) and uses every arc at least once. \section*{OXFORD CAMBRIDGE AND RSA EXAMINATIONS} Advanced Subsidiary General Certificate of Education Advanced General Certificate of Education MATHEMATICS
    4736
    Decision Mathematics 1
    INSERT for Questions 4 and 7
    Wednesday
OCR D1 2005 January Q12
Moderate -1.0
12 JANUARY 2005
Afternoon
1 hour 30 minutes
  • This insert should be used to answer Questions 4 and 7.
  • Write your name, centre number and candidate number in the spaces provided at the top of this page.
  • Write your answers to Questions 4 and 7 in the spaces provided in this insert, and attach it to your answer booklet.
4
  1. \(A\)\(B\)CD\(E\)\(F\)G\(H\)
    A-423----
    \(B\)4-1-3---
    C21-2-65-
    \(D\)3-2---4-
    E-3---8-7
    \(F\)--6-8--8
    \(G\)--54---9
    \(H\)----789-
  2. B \(E\) \(C\) F
    • \(H\) \(A\) •
    • \({ } ^ { \text {F } }\)
    H D
    G
  3. \(\_\_\_\_\)
  4. \(\_\_\_\_\)
  5. \(\_\_\_\_\) 7
      1. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_191_1179_269_482} Do not cross out your working values (temporary labels) \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_871_1557_612_335} Shortest route from \(A\) to \(E =\) \(\_\_\_\_\) Length = \(\_\_\_\_\) Shortest route from \(A\) to \(J =\) \(\_\_\_\_\) Length = \(\_\_\_\_\)
      2. Length of route \(=\) \(\_\_\_\_\) Vertices visited in order \(\_\_\_\_\)
      3. Explanation \(\_\_\_\_\)
    2. \(\_\_\_\_\) Length = \(\_\_\_\_\)
OCR D1 2006 January Q3
6 marks Moderate -0.8
3 Consider the following algorithm.
Step 1: Input a positive integer \(n\).
Step 2 : Draw a graph consisting of \(n\) vertices and no arcs.
Step 3 : Create a new vertex and join it directly to every vertex of order 0.
Step 4: Create a new vertex and join it directly to every vertex of odd order.
Step 5 : Stop.
  1. Draw separate diagrams to show the result of applying this algorithm in the following cases.
    1. \(n = 1\)
    2. \(n = 2\)
    3. \(n = 3\)
    4. \(n = 4\)
    5. State how many arcs are in the graph that results when the algorithm is applied to a set of \(n\) vertices.
OCR D1 2006 January Q4
8 marks Moderate -0.5
4
  1. Represent the linear programming problem below by an initial Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 5 x - 4 y - 3 z , \\ \text { subject to } & 2 x - 3 y + 4 z \leqslant 10 , \\ & 6 x + 5 y + 4 z \leqslant 60 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
  2. Perform one iteration of the Simplex algorithm and write down the values of \(x , y , z\) and \(P\) that result from this iteration.
OCR D1 2006 January Q5
13 marks Moderate -0.8
5 Findlay is trying to get into his local swimming team. The coach will watch him swim and will then make his decision. Findlay must swim at least two lengths using each stroke and must swim at least 8 lengths in total, taking at most 10 minutes. Findlay needs to put together a routine that includes breaststroke, backstroke and butterfly. The table shows how Findlay expects to perform with each stroke.
StrokeStyle marksTime taken
Breaststroke2 marks per length2 minutes per length
Backstroke1 mark per length0.5 minutes per length
Butterfly5 marks per length1 minute per length
Findlay needs to work out how many lengths to swim using each stroke to maximise his expected total number of style marks.
  1. Identify appropriate variables for Findlay's problem and write down the objective function, to be maximised, in terms of these variables.
  2. Formulate a constraint for the total number of lengths swum, a constraint for the time spent swimming and constraints on the number of lengths swum using each stroke. Findlay decides that he will swim two lengths using butterfly. This reduces his problem to the following LP formulation: $$\begin{array} { l c } \text { maximise } & P = 2 x + y , \\ \text { subject to } & x + y \geqslant 6 , \\ & 4 x + y \leqslant 16 , \\ & x \geqslant 2 , y \geqslant 2 , \end{array}$$ with \(x\) and \(y\) both integers.
  3. Use a graphical method to identify the feasible region for this problem. Write down the coordinates of the vertices of the feasible region and hence find the integer values of \(x\) and \(y\) that maximise \(P\).
  4. Interpret your solution for Findlay.
OCR D1 2006 January Q6
16 marks Standard +0.3
6 The network represents a railway system. The vertices represent the stations and the arcs represent the tracks. The weights on the arcs represent journey times between stations, in minutes. The sum of all the weights is 105 minutes. \includegraphics[max width=\textwidth, alt={}, center]{8f17020a-14bf-4459-9241-1807b954a629-5_981_1215_468_477} Norah wants to travel around the system visiting every station. She wants to start and end at \(A\) and she wants to complete her journey in the shortest possible time.
  1. Apply the nearest neighbour method starting at \(A\) to find two suitable tours and calculate the journey time for each of these tours. Which of these answers gives the better upper bound for Norah's journey time?
  2. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex \(G\) and all the arcs that are directly joined to \(G\). Draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Norah's journey time. Norah now decides that she wants to use every section of track in her journey. She still wants to start and end at \(A\) and to complete her journey in the shortest possible time.
  3. Calculate the journey time for Norah's new problem. Show your working; quickest times between stations may be found by inspection. State which arcs Norah will have to travel twice and how many times she will pass through station \(D\).