Edexcel D2 (Decision Mathematics 2) 2008 June

1. The diagram above shows a capacitated, directed network of pipes. The number on each arc represents the capacity of that pipe. The numbers in circles represent a feasible flow.

1. State the values of \(x\) and \(y\).
2. List the saturated arcs.
3. State the value of the feasible flow.
4. State the capacities of the cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\), and \(\mathrm { C } _ { 3 }\).
5. By inspection, find a flow-augmenting route to increase the flow by one unit. You must state your route.
6. Prove that the new flow is maximal.

2. Explain what is meant, in a network, by (a) a walk, (b) a tour.
(2) (2) (Total 4 marks)

3. 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.

1. Explain why it is necessary to add a dummy demand point.
2. Complete the table below.

   	L	E	Dummy	Supply
   A	80	70		55
   B	60	50		45
   Demand	35	60		100

3. Use the north-west corner rule to obtain a possible pattern of distribution.
   (1)
4. 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.
   (7)
5. State the cost of your optimal solution.
   (1) (Total 13 marks)

4. (a) Explain the difference between a maximin route and a minimax route in dynamic programming.
(2)
\includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-2_533_1356_667_376} A maximin route from L to R is to be found through the staged network shown above.
(b) Use dynamic programming to complete a table below and hence find a maximin route.
(10) (Total 12 marks)

5. (a) 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. (b) Verify that there is no stable solution to this game.
(c) 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.
(d) Explain why a graphical approach is no longer possible and briefly describe the method Liz should use to determine her best strategy.
(2) (Total 16 marks)

6. 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.

1. 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.
2. State all possible optimal allocations and the optimal total value.
   (4)(Total 14 marks)

7.
\includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-3_738_1052_466_516} The network in the diagram above 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.

1. Obtain a minimum spanning tree for the network using Kruskal's algorithm, stating the order in which you select the arcs.
2. Use your answer to part (a) to determine an initial upper bound for the length of the route.
3. Starting from your initial upper bound use short cuts to find an upper bound, which is below 630 km . State the corresponding route.
4. Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.
5. By deleting C, and all of its arcs, find a lower bound for the length of the route.
6. Use your results to write down the smallest interval which you are confident contains the optimal length of the route.
   (2) (Total 16 marks)

8. The tableau below is the initial tableau for a maximising linear programming problem in \(x , y\) and \(z\).

1. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use. You may not need to use all of these tableaux.

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	S	\(t\)	Value	Row operations
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations
   \includegraphics[max width=\textwidth, alt={}]{151644c7-edef-448e-ac2a-b374d79f264c-4_86_102_967_374}
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(S\)	\(t\)	Value	Row operations
   \(P\)