Edexcel FD1 AS (Further Decision 1 AS) Specimen

1. \begin{figure}[h] \end{figure} [The total weight of the network is 189]
Figure 1 represents a network of pipes in a building. The number on each arc is the length, in metres, of the corresponding pipe.

1. Use Dijkstra's algorithm to find the shortest path from A to F . State the path and its length. On a particular day, Gabriel needs to check each pipe. A route of minimum length, which traverses each pipe at least once and which starts and finishes at A, needs to be found.
2. Use an appropriate algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
3. State the minimum length of Gabriel's route. A new pipe, BG, is added to the network. A route of minimum length that traverses each pipe, including BG, needs to be found. The route must start and finish at A. Gabriel works out that the addition of the new pipe increases the length of the route by twice the length of BG .
4. Calculate the length of BG. You must show your working.

2. \begin{figure}[h] \end{figure} A teacher buys pens and pencils. The number of pens, \(x\), and the number of pencils, \(y\), that he buys can be represented by a linear programming problem as shown in Figure 2, which models the following constraints: $$\begin{aligned} 8 x + 3 y & \leqslant 480
8 x + 7 y & \geqslant 560
y & \geqslant 4 x
x , y & \geqslant 0 \end{aligned}$$ The total cost, in pence, of buying the pens and pencils is given by $$C = 12 x + 15 y$$ Determine the number of pens and the number of pencils which should be bought in order to minimise the total cost. You should make your method and working clear.

3. The table above shows the activities required for the completion of a building project. For each activity, the table shows the time taken in days to complete the activity and the immediately preceding activities. Each activity requires one worker. The project is to be completed in the shortest possible time.

1. Draw the activity network described in the table, using activity on arc. Your activity network must contain the minimum number of dummies only.
2. 1. Show that the project can be completed in 21 days, showing your working.
   2. Identify the critical activities.

4. (a) Explain why it is not possible to draw a graph with exactly 5 nodes with orders \(1,3,4,4\) and 5 A connected graph has exactly 5 nodes and contains 18 arcs. The orders of the 5 nodes are \(2 ^ { 2 x } - 1,2 ^ { x } , x + 1,2 ^ { x + 1 } - 3\) and \(11 - x\).
(b) (i) Calculate X .
(ii) State whether the graph is Eulerian, semi-Eulerian or neither. You must justify your answer.
(c) Draw a graph which satisfies all of the following conditions:

• The graph has exactly 5 nodes.
• The nodes have orders 2, 2, 4, 4 and 4
• The graph is not Eulerian.

1. Jonathan makes two types of information pack for an event, Standard and Value.

Each Standard pack contains 25 posters and 500 flyers.
Each Value pack contains 15 posters and 800 flyers.
He must use at least 150000 flyers.
Between \(35 \%\) and \(65 \%\) of the packs must be Standard packs.
Posters cost 20p each and flyers cost 4p each.
Jonathan wishes to minimise his costs.
Let x and y represent the number of Standard packs and Value packs produced respectively.
Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem. \section*{(Total for Question 5 is 5 marks)} TOTAL IS 40 MARKS