Edexcel D1 (Decision Mathematics 1)

1. (a) Make plane drawings of each of the graphs shown in Figure 1.

Graph 1 \begin{figure}[h] \end{figure} (b) State the name given to Graph 1 and write down the features that identify it.
(c) State, with a reason, whether it is possible to add further arcs to Graph 2 such that it remains a simple connected graph. No further vertices may be added.
(1 mark)

2. This question should be answered on the sheet provided. A builder is going to put up houses on a plot of land of area \(12000 \mathrm {~m} ^ { 2 }\).
There are 5 designs to choose from and no more than one of each design can be built. The builder needs to work out which houses he should build in order to maximise the total value of the site. He does this using a tree diagram and each "branch" on the tree is terminated when the total area of land on that branch exceeds \(12000 \mathrm {~m} ^ { 2 }\).

1. 1. Complete the tree diagram so that each branch is terminated or all choices have been considered.
   2. Hence, determine which designs the builder should use and the total value that the site will have when completed.
2. Explain how this method could be altered if more than one of each design is allowed.

3. (a) Draw a graph with 6 vertices, each of degree 1 .
(b) Draw two graphs with 6 vertices, each of degree 2 such that:

1. the graph is connected,
2. the graph is not connected. A simple connected graph has 5 vertices each of degree \(x\).
   (c) Find the possible values of \(x\) and explain your answer.
   (d) For each value of \(x\) you found in part (c) draw a possible graph.

4. A company produces \(x _ { 1 }\) finished articles at the end of January, \(x _ { 2 }\) finished articles at the end of February, \(x _ { 3 }\) finished articles at the end of March, \(x _ { 4 }\) finished articles at the end of April. Other details for each month are as follows: The cost of storing each finished but unsold article is \(\pounds 500\) per month. Thus, for example, any article unsold at the end of January would incur a \(\pounds 500\) charge if it is stored until the end of February or a \(\pounds 1000\) charge if it is stored until the end of March. There must be no unsold stock at the end of April.
The selling price of each article is \(\pounds 4000\) and the total profit ( \(\pounds P\) ) must be maximised.

1. Rewrite \(x _ { 4 }\) in terms of the other 3 variables.
2. Show that the total cost incurred \(( \pounds C )\) is given by: $$C = 600 x _ { 1 } + 900 x _ { 2 } + 200 x _ { 3 } + 1125000$$
3. Hence, show that \(P = { } ^ { - } 600 x _ { 1 } - 900 x _ { 2 } - 200 x _ { 3 } + 2875000\).
4. Three of the constraints operating can be expressed as \(x _ { 1 } \geq 200\), \(x _ { 2 } \geq 0\) and \(x _ { 3 } \geq 0\). Write down inequalities representing two further constraints.
   (2 marks)
5. Explain why it is not appropriate to use a graphical method to solve this problem.
6. An employee of the company wishes to use the Simplex algorithm to solve the problem. He tries to generate an initial tableau with \(x _ { 1 } , x _ { 2 }\) and \(x _ { 3 }\) as the non-basic variables. Explain why this is not appropriate and explain what he should do instead. You are not required to generate an initial tableau or to solve the problem.
   (2 marks)

5. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows a weighted network representing the paths in a certain part of St. Andrews. The numbers on the arcs represent the lengths of the paths in metres.

1. Use Dijkstra's algorithm to find a route of minimum length from \(P\) to \(F\). You do not need to consider routes via vertex \(Q\). You must show clearly:
   1. the order in which you labelled the vertices,
   2. how you found a route of minimum length from your labelling. Each night a security guard walks along each of the paths in Figure 2 at least once.
2. The security office is at vertex \(A\), so she must start and finish her inspection at \(A\). Find the minimum distance that she must walk each night.
   (4 marks)

6. This question should be answered on the sheet provided. A town has adopted a one-way system to cope with recent problems associated with congestion in one area. \begin{figure}[h] \end{figure} Figure 3 models the one-way system as a capacitated directed network. The numbers on the arcs are proportional to the number of vehicles that can pass along each road in a given period of time.

1. Find the capacity of the cut which passes through the \(\operatorname { arcs } A E , B F , B G\) and \(C D\).
   (2 marks) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-07_659_1278_196_335} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure} Figure 4 shows a feasible flow of 17 through the same network. For convenience, a supersource, \(S\), and a supersink, \(T\), have been used.
2. 1. Use the labelling procedure to find the maximum flow through this network. You must list each flow-augmenting route you use together with its flow.
   2. Show your maximum flow pattern and state its value.
3. Prove that your flow is the maximum possible through the network.
4. It is suggested that the maximum flow through the network could be increased by making road \(E F\) undirected, so that it has a capacity of 8 in either direction. Using the maximum flow-minimum cut theorem, find the increase in maximum flow this change would allow.
   (2 marks)
5. An alternative suggestion is to widen a single road in order to increase its capacity. Which road, on its own, could lead to the biggest improvement, and what would be the largest maximum flow this could achieve.
   (2 marks)

7. A project involves six tasks, some of which cannot be started until others have been completed. This is shown in the table below. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-09_2036_1555_349_248}

1. \(\_\_\_\_\)
2. \(\_\_\_\_\)
   \section*{Sheet for answering question 5} NAME \section*{Please hand this sheet in for marking} Sheet for answering question 6
   NAME \section*{Please hand this sheet in for marking}
4. 1. 
      \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-11_666_1280_461_374}
   2. 
      \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-11_657_1276_1356_376} Maximum Flow = \(\_\_\_\_\)
5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6. \(\_\_\_\_\)
7. \(\_\_\_\_\)