Edexcel D1 (Decision Mathematics 1) 2003 January

\includegraphics{figure_1} Use the planarity algorithm to show that the graph in Fig. 1 is planar. [4]

At Tesafe supermarket there are 5 trainee staff, Homan \((H)\), Jenna \((J)\), Mary \((M)\), Tim \((T)\) and Yoshie \((Y)\). They each must spend one week in each of 5 departments, Delicatessen \((D)\), Frozen foods \((F)\), Groceries \((G)\), Pet foods \((P)\), Soft drinks \((S)\). Next week every department requires exactly one trainee. The table below shows the departments in which the trainees have yet to spend time. Initially \(H\), \(J\), \(M\) and \(T\) are allocated to the first department in their list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way. [2] Starting from this matching,
2. use the maximum matching algorithm to find a complete matching. You must make clear your alternating path and your complete matching. [4]

A manager wishes to purchase seats for a new cinema. He wishes to buy three types of seat; standard, deluxe and majestic. Let the number of standard, deluxe and majestic seats to be bought be \(x\), \(y\) and \(z\) respectively. He decides that the total number of deluxe and majestic seats should be at most half of the number of standard seats. The number of deluxe seats should be at least 10\% and at most 20\% of the total number of seats. The number of majestic seats should be at least half of the number of deluxe seats. The total number of seats should be at least 250. Standard, deluxe and majestic seats each cost £20, £26 and £36, respectively. The manager wishes to minimize the total cost, £\(C\), of the seats. Formulate this situation as a linear programming problem, simplifying your inequalities so that all the coefficients are integers. [9]

\includegraphics{figure_2} The arcs in Fig. 2 represent roads in a town. The weight on each arc gives the time, in minutes, taken to drive along that road. The times taken to drive along \(AB\) and \(DE\) vary depending upon the time of day. A police officer wishes to drive along each road at least once, starting and finishing at \(A\). The journey is to be completed in the least time.

1. Briefly explain how you know that a route between \(B\) and \(E\) will have to be repeated. [1]
2. List the possible routes between \(B\) and \(E\). State how long each would take, in terms of \(x\) where appropriate. [2]
3. Find the range of values that \(x\) must satisfy so that \(DE\) would be one of the repeated arcs. [3] Given that \(x = 7\),
4. find the total time needed for the police officer to carry out this journey. [3]

\includegraphics{figure_3} A project is modelled by the activity network in Fig. 3. The activities are represented by the arcs. One worker is required for each activity. The number in brackets on each arc gives the time, in hours, to complete the activity. The earliest event time and the latest event time are given by the numbers in the left box and right box respectively.

1. State the value of \(x\) and the value of \(y\). [2]
2. List the critical activities. [2]
3. Explain why at least 3 workers will be needed to complete this project in 38 hours. [2]
4. Schedule the activities so that the project is completed in 38 hours using just 3 workers. You must make clear the start time and finish time of each activity. [4]

25 22 30 18 29 21 27 21 The list of numbers above is to be sorted into descending order.

1. 1. Perform the first pass of a bubble sort, giving the state of the list after each exchange.
   2. Perform further passes, giving the state of the list after each pass, until the algorithm terminates.
   [5]

The numbers represent the lengths, in cm, of pieces to be cut from rods of length 50 cm.

1. 1. Show the result of applying the first fit decreasing bin packing algorithm to this situation.
   2. Determine whether your solution to \((b)\) \((i)\) has used the minimum number of 50 cm rods.
   [4]

\includegraphics{figure_4} Figure 4 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow from sources \(A\) and \(B\) to sinks \(I\), \(J\) and \(K\). Take this as the initial flow pattern.

1. On Diagram 1 in the answer booklet, add a supersource \(S\) and a supersink \(W\) to obtain a capacitated network with a single source and single sink. State the minimum capacities of the arcs you have added. [3]
2. 1. Use the given initial flow and the labelling procedure on Diagram 2 to find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
   2. Verify that your flow is maximal.
   [9]
3. Show your maximum flow pattern on Diagram 3. [2]

The tableau below is the initial tableau for a maximising linear programming problem.

1. For this problem \(x \geq 0\), \(y \geq 0\), \(z \geq 0\). Write down the other two inequalities and the objective function. [3]
2. Solve this linear programming problem. [8]
3. State the final value of \(P\), the objective function, and of each of the variables. [3]