OCR MEI D1 (Decision Mathematics 1) 2011 June

1 Two students draw graphs to represent the numbers of pairs of shoes owned by members of their class. Andrew produces a bipartite graph, but gets it wrong. Barbara produces a completely correct frequency graph. Their graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Draw a correct bipartite graph.
2. How many people are in the class?
3. How many pairs of shoes in total are owned by members of the class?
4. Which points on Barbara's graph may be deleted without losing any information? Charles produces the same frequency graph as Barbara, but joins consecutive points with straight lines.
5. Criticise Charles's graph.

2 The algorithm gives a method for drawing two straight lines, if certain conditions are met. Start with the equations of the two straight lines
Line 1 is \(a x + b y = c , \quad a , b , c > 0\)
Line 2 is \(d x + e y = f , \quad d , e , f > 0\)
Let \(X =\) minimum of \(\frac { c } { a }\) and \(\frac { f } { d }\)
Let \(Y =\) minimum of \(\frac { c } { b }\) and \(\frac { f } { e }\) If \(X = \frac { c } { a }\) then \(X ^ { * } = \frac { c - b Y } { a }\) and \(Y ^ { * } = \frac { f - d X } { e }\) If \(X = \frac { f } { d }\) then \(X ^ { * } = \frac { f - e Y } { d }\) and \(Y ^ { * } = \frac { c - a X } { b }\)
Draw an \(x\)-axis labelled from 0 to \(X\), and a \(y\)-axis labelled from 0 to \(Y\)
Join ( \(0 , Y\) ) to ( \(X , Y ^ { * }\) ) with a straight line
Join ( \(X ^ { * } , Y\) ) to ( \(X , 0\) ) with a straight line

1. Apply the algorithm with \(a = 1 , b = 5 , c = 25 , d = 10 , e = 2 , f = 85\).
2. Why might this algorithm be useful in an LP question?

3 John has a standard die in his pocket (ie a cube with its six faces labelled from 1 to 6).

1. Describe how John can use the die to obtain realisations of the random variable \(X\), defined below.

   \(x\)	1	2	3
   \(\operatorname { Probability } ( X = x )\)	\(\frac { 1 } { 2 }\)	\(\frac { 1 } { 6 }\)	\(\frac { 1 } { 3 }\)

2. Describe how John can use the die to obtain realisations of the random variable \(Y\), defined below.

   \(y\)	1	2	3
   \(\operatorname { Probability } ( Y = y )\)	\(\frac { 1 } { 2 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 1 } { 4 }\)

3. John attempts to use the die to obtain a realisation of a uniformly distributed 2-digit random number. He throws the die 20 times. Each time he records one less than the number showing. He then adds together his 20 recorded numbers. Criticise John's methodology.

4 An eco-village is to be constructed consisting of large houses and standard houses.
Each large house has 4 bedrooms, needs a plot size of \(200 \mathrm {~m} ^ { 2 }\) and costs \(\pounds 60000\) to build.
Each standard house has 3 bedrooms, needs a plot size of \(120 \mathrm {~m} ^ { 2 }\) and costs \(\pounds 50000\) to build.
The area of land available for houses is \(120000 \mathrm {~m} ^ { 2 }\). The project has been allocated a construction budget of \(\pounds 42.4\) million. The market will not sustain more than half as many large houses as standard houses. So, for instance, if there are 500 standard houses then there must be no more than 250 large houses.

1. Define two variables so that the three constraints can be formulated in terms of your variables. Formulate the three constraints in terms of your variables.
2. Graph your three inequalities from part (i), indicating the feasible region.
3. Find the maximum number of bedrooms which can be provided, and the corresponding numbers of each type of house.
4. Modify your solution if the construction budget is increased to \(\pounds 45\) million.

5 The activity network and table together show the tasks involved in constructing a house extension, their durations and precedences.
\includegraphics[max width=\textwidth, alt={}, center]{2e03f6fb-69db-438a-a79e-3e04fab0d08a-5_231_985_338_539}

1. Show the immediate predecessors for each activity.
2. Perform a forward pass and a backward pass to find the early time and the late time for each event.
3. Give the critical activities, the project duration, and the total float for each activity.
4. The activity network includes one dummy activity. Explain why this dummy activity is needed. Whilst the foundations are being dug the customer negotiates the installation of a decorative corbel. This will take one day. It must be done after the walls have been built, and before the roof is constructed. The windows and doors cannot be installed until it is completed. It will not have any effect on the construction of the floor.
5. Redraw the activity network incorporating this extra activity.
6. Find the revised critical activities and the revised project duration.

6 The table shows the distances in miles, where direct rail connections are possible, between 11 cities in a country. The government is proposing to construct a high-speed rail network to connect the cities.

1. Use the tabular form of Prim's algorithm, starting at vertex P , to find a minimum connector for the network. Draw your minimum connector and give its total length.
2. Give one advantage and two disadvantages of constructing a rail network using only the arcs of a minimum connector.
3. Use Dijkstra's algorithm on the diagram in the Printed Answer Book, to find the shortest route and distance from P to Nr in the original network.
4. Give the shortest distance from P to Nr using only arcs in your minimum connector.