Edexcel D2 (Decision Mathematics 2) 2014 June

1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.

Worker A cannot do task 4 and worker B cannot do task 2. The amount, in pounds, that each worker would earn if assigned to the tasks, is shown in the table below. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You must make your method clear and show the table after each stage.

2. The table shows the least times, in seconds, that it takes a robot to travel between six points in an automated warehouse. These six points are an entrance, A , and five storage bins, \(\mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F . The robot will start at A , visit each bin, and return to A . The total time taken for the robot's route is to be minimised.

1. Show that there are two nearest neighbour routes that start from A . You must make the routes and their lengths clear.
2. Starting by deleting F , and all of its arcs, find a lower bound for the time taken for the robot's route.
3. Use your results to write down the smallest interval which you are confident contains the optimal time for the robot's route.

3. The tableau below is the initial tableau for a three-variable linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use.
2. State the final values of the objective function and each variable.

4. A two-person zero-sum game is represented by the following pay-off matrix for player A.

1. Verify that there is no stable solution to this game.
2. Find the best strategy for player A.

5. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
   (1)
2. Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along \(\mathrm { SC } , \mathrm { AB } , \mathrm { CE } , \mathrm { DE }\) and DT .
   (2)
3. Hence use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
   (4)
4. Draw a maximal flow pattern on Diagram 2 in the answer book.
   (2)
5. Prove that your flow is maximal.
   (2)

6. Three warehouses, \(\mathrm { P } , \mathrm { Q }\) and R , supply washing machines to four retailers, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . The table gives the cost, in pounds, of transporting a washing machine from each warehouse to each retailer. It also shows the number of washing machines held at each warehouse and the number of washing machines required by each retailer. The total cost of transportation is to be minimised. Formulate this transportation problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.
You do not need to solve this problem.
(Total 7 marks)

7. A company assembles microlight aircraft. They can assemble up to four aircraft in any one month, but if they assemble more than three they will have to hire additional space at a cost of \(\pounds 1000\) per month.
They can store up to two aircraft at a cost of \(\pounds 500\) each per month.
The overhead costs are \(\pounds 2000\) in any month in which work is done. Aircraft are delivered at the end of each month. There are no aircraft in stock at the beginning of March and there should be none in stock at the end of July.
The order book for aircraft is Use dynamic programming to determine the production schedule which minimises the costs. Show your working in the table provided in the answer book and state the minimum production cost.
(Total 14 marks)