Edexcel FD1 AS (Further Decision 1 AS) 2018 June

1. \begin{figure}[h] \end{figure} Figure 1 represents a network of roads.
The number on each arc represents the time taken, in minutes, to drive along the corresponding road.

1. 1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to H .
   2. State the quickest route. For a network with \(n\) vertices, Dijkstra's algorithm has order \(n ^ { 2 }\)
2. If it takes 1.5 seconds to run the algorithm when \(n = 250\), calculate approximately how long it will take, in seconds, to run the algorithm when \(n = 9500\). You should make your method and working clear.
3. Explain why your answer to part (b) is only an approximation.

2. A simply connected graph is a connected graph in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself.

1. Given that a simply connected graph has exactly four vertices,
   1. write down the minimum number of arcs it can have,
   2. write down the maximum number of arcs it can have.
2. 1. Draw a simply connected graph that has exactly four vertices and exactly five arcs.
   2. State, with justification, whether your graph is Eulerian, semi-Eulerian or neither.
3. By considering the orders of the vertices, explain why there is only one simply connected graph with exactly four vertices and exactly five arcs.

3. The table above shows the activities required for the completion of a building project. For each activity, the table shows the time it takes, in days, and the immediately preceding activities. Each activity requires one worker. The project is to be completed in the shortest possible time. \begin{figure}[h] \end{figure} Figure 2 shows a partially completed activity network used to model the project. The activities are represented by the arcs and the number in brackets on each arc is the time taken, in days, to complete the corresponding activity.

1. Add the missing activities and necessary dummies to Diagram 1 in the answer book.
2. Complete Diagram 1 in the answer book to show the early event times and the late event times.
3. State the critical activities. At the beginning of the project it is decided that activity G is no longer required.
4. Explain what effect, if any, this will have on
   1. the shortest completion time of the project if activity G is no longer required,
   2. the timing of the remaining activities.

4. The manager of a factory is planning the production schedule for the next three weeks for a range of cabinets. The following constraints apply to the production schedule.

• The total number of cabinets produced in week 3 cannot be fewer than the total number produced in weeks 1 and 2
• At most twice as many cabinets must be produced in week 3 as in week 2
• The number of cabinets produced in weeks 2 and 3 must, in total, be at most 125

The production cost for each cabinet produced in weeks 1,2 and 3 is \(\pounds 250 , \pounds 275\) and \(\pounds 200\) respectively.
The factory manager decides to formulate a linear programming problem to find a production schedule that minimises the total cost of production. The objective is to minimise \(250 x + 275 y + 200 z\)

1. Explain what the variables \(x , y\) and \(z\) represent.
2. Write down the constraints of the linear programming problem in terms of \(x , y\) and \(z\). Due to demand, exactly 150 cabinets must be produced during these three weeks. This reduces the constraints to $$\begin{gathered} x + y \leqslant 75
   x + 3 y \geqslant 150
   x \geqslant 25
   y \geqslant 0 \end{gathered}$$ which are shown in Diagram 1 in the answer book.
   Given that the manager does not want any cabinets left unfinished at the end of a week,
3. 1. use a graphical approach to solve the linear programming problem and hence determine the production schedule which minimises the cost of production. You should make your method and working clear.
   2. Find the minimum total cost of the production schedule.