Edexcel A Level Maths D2 · Decision Mathematics 2 June 2008 question paper 6690

Explain what is meant, in a network, by

a walk

a tour

Jameson cars are made in two factories A and B. Sales have been made at the two main showrooms in London and Edinburgh. Cars are to be transported from the factories to the showrooms. The table below shows the cost, in pounds, of transporting one car from each factory to each showroom. It also shows the number of cars available at each factory and the number required at each showroom.

It is decided to use the transportation algorithm to obtain a minimal cost solution.

Explain why it is necessary to add a dummy demand point.

Complete table 1 in the answer booklet.

Use the north-west corner rule to obtain a possible pattern of distribution.

Taking the most negative improvement index to indicate the entering square, use the stepping-stone method to obtain an optimal solution. You must make your shadow costs and improvement indices clear and demonstrate that your solution is optimal.

State the cost of your optimal solution.

Explain the difference between a maximin route and a minimax route in dynamic programming.

A Maximin route from L to R is to be found through the staged network shown in Figure 1.

Use dynamic programming to complete the table in the answer book and hence find a maximin route.

In game theory, explain the circumstances under which column (x) dominates column (y) in a two-person zero-sum game.

Liz and Mark play a zero-sum game. This game is represented by the following pay-off matrix for Liz.

Verify that there is no stable solution to this game.

Find the best strategy for Liz and the value of the game to her.

The game now changes so that when Liz plays 1 and Mark plays 3 the pay-off to Liz changes from 2 to 4. All other pay-offs for this zero-sum game remain the same.

Explain why a graphical approach is no longer possible and briefly describe the method Liz should use to determine her best strategy.

Four salespersons, Joe, Min-Seong, Olivia and Robert, are to attend four business fairs, A, B, C and D. Each salesperson must attend just one fair and each fair must be attended by just one salesperson. The expected sales, in thousands of pounds, that each salesperson would make at each fair is shown in the table below.

Use the Hungarian algorithm, reducing rows first, to obtain an allocation that maximises the total expected sales from the four salespersons. You must make your method clear and show the table after each stage.

State all possible optimal allocations and the optimal total value.

The network in figure 2 shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.

Obtain a minimum spanning tree for the network using Kruskal’s algorithm, stating the order in which you select the arcs.

Use your answer to part (a) to determine an initial upper bound for the length of the route.

Starting from your initial upper bound use short cuts to find an upper bound, which is below 630km. State the corresponding route.

Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.

By deleting C, and all of its arcs, find a lower bound for the length of the route.

Use your results to write down the smallest interval which you are confident contains the optimal length of the route.