Edexcel D2 (Decision Mathematics 2)

1. A glazing company runs a promotion for a special type of window. As a result of this the company receives orders for 30 of these windows from business \(B _ { 1 } , 18\) from business \(B _ { 2 }\) and 22 from business \(B _ { 3 }\). The company has stocks of 20 of these windows at factory \(F _ { 1 } , 35\) at factory \(F _ { 2 }\) and 15 at factory \(F _ { 3 }\). The table below shows the profit, in pounds, that the company will make for each window it sells according to which factory supplies each business.

The glazing company wishes to supply the windows so that the total profit is a maximum.
Formulate this information as a linear programming problem.

1. State your decision variables.
2. Write down the objective function in terms of your decision variables.
3. Write down the constraints and state what each one represents.

2. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 1 shows a network in which the nodes represent five major rides in a theme park and the arcs represent paths between these rides. The numbers on the arcs give the length, in metres, of the paths.

1. By inspection, add additional arcs to make a complete network showing the shortest distances between the rides.
   (2 marks)
2. Use the nearest neighbour algorithm, starting at \(A\), and your complete network to find an upper bound to the length of a tour visiting each ride exactly once.
3. Interpret the tour found in part (b) in terms of the original network.

3. Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:

• strip the wallpaper,
• paint the woodwork and ceiling,
• hang the new wallpaper,
• replace the fittings and tidy up.

The table below shows the time, in hours, that each of the friends is likely to take to complete each job. As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.

1. Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
   (6 marks)
2. Hence, find the minimum time in which the friends can redecorate the lounge.
   (1 mark)

4. This question should be answered on the sheet provided. The owner of a small plane is planning a journey from her local airport, \(A\) to the airport nearest her parents, \(K\). On the journey she will make three refuelling stops, the first at \(B , C\) or \(D\), the second at \(E , F\) or \(G\) and the third at \(H , I\) or \(J\). \begin{figure}[h] \end{figure} Figure 2 shows all the possible flights that can be made on the journey with the number by each arc indicating the distance of each flight in hundreds of miles. As her plane does not have a large fuel tank, the owner wishes to choose a route that minimises the maximum distance of any one flight. Find the route that she should use and state the maximum distance of any one stage on this route.

5. A car-hire firm has six branches in a region. Three of the branches, \(A , B\) and \(C\), have spare cars, whereas the other three, \(D , E\) and \(F\), require cars. The total number of cars required is equal to the number of cars available. The table below shows the cost in pounds of sending one car from each branch with spares to each branch needing more cars and the number of cars available or required by each branch.

1. Use the north-west corner method to obtain a possible pattern of moving cars and find its cost. The firm wishes to minimise the cost of redistributing the cars.
2. Calculate shadow costs for the pattern found in part (a) and improvement indices for each unoccupied cell.
3. State, with a reason, whether or not the pattern found in part (a) is optimal.

6. This question should be answered on the sheet provided. A furniture company in Leeds is considering opening outlets in six other cities.
The table below shows the distances, in miles, between all seven cities.

1. Starting with Leeds, obtain and draw a minimum spanning tree for this network of cities showing your method clearly.
   (4 marks)
   A representative of the company is to visit each of the areas being considered. He wishes to plan a journey of minimum length starting and ending in Leeds and visiting each of the other cities in the table once. Assuming that the network satisfies the triangle inequality,
2. find an initial upper bound for the length of his journey,
3. improve this upper bound to find an upper bound of less than 575 miles.
4. By deleting Leeds, find a lower bound for his journey. Turn over

7. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.