Edexcel D2 (Decision Mathematics 2) 2006 January

1. A theme park has four sites, A, B, C and D, on which to put kiosks. Each kiosk will sell a different type of refreshment. The income from each kiosk depends upon what it sells and where it is located. The table below shows the expected daily income, in pounds, from each kiosk at each site.

Reducing rows first, use the Hungarian algorithm to determine a site for each kiosk in order to maximise the total income. State the site for each kiosk and the total expected income. You must make your method clear and show the table after each stage.
(Total 13 marks)

2. An engineering firm makes motors. They can make up to five in any one month, but if they make more than four they have to hire additional premises at a cost of \(\pounds 500\) per month. They can store up to two motors for \(\pounds 100\) per motor per month. The overhead costs are \(\pounds 200\) in any month in which work is done.
Motors are delivered to buyers at the end of each month. There are no motors in stock at the beginning of May and there should be none in stock after the September delivery. The order book for motors is: Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided below. \section*{Production schedule} Total cost: \(\_\_\_\_\)

3. Three depots, F, G and H, supply petrol to three service stations, S, T and U. The table gives the cost, in pounds, of transporting 1000 litres of petrol from each depot to each service station. F, G and H have stocks of 540000,789000 and 673000 litres respectively.
S, T and U require 257000,348000 and 412000 litres respectively. The total cost of transporting the petrol is to be minimised. Formulate this problem as a linear programming problem. Make clear your decision variables, objective function and constraints.

4. The following minimising transportation problem is to be solved.

1. Complete the table below.

   	J	K	L	Supply
   A	12	15		9
   B	8	17		13
   C	4	9		12
   Demand	9	11		34

2. Explain why an extra demand column was added to the table above. A possible north-west corner solution is:

   	J	K	L
   A	9	0
   B		11	2
   C			12

3. Explain why it was necessary to place a zero in the first row of the second column. After three iterations of the stepping-stone method the table becomes:

   	J	K	L
   A		8	1
   B			13
   C	9	3

4. Taking the most negative improvement index as the entering square for the stepping stone method, solve the transportation problem. You must make your shadow costs and improvement indices clear and demonstrate that your solution is optimal.

5. 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. Explain why the \(4 \times 4\) game above may be reduced to the following \(3 \times 3\) game.
3. Formulate the \(3 \times 3\) game as a linear programming problem for player A. Write the

   - 2	1	3
   - 1	3	2
   1	- 2	- 1

   constraints as inequalities. Define your variables clearly.

6. The network in the figure above, shows the distances in km , along the roads between eight towns, A, B, C, D, E, F, G and H. Keith has a shop in each town and needs to visit each one. He wishes to travel a minimum distance and his route should start and finish at A . By deleting D, a lower bound for the length of the route was found to be 586 km .
By deleting F, a lower bound for the length of the route was found to be 590 km .

1. By deleting C, find another lower bound for the length of the route. State which is the best lower bound of the three, giving a reason for your answer.
2. By inspection complete the table of least distances. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(8)
   (8)
   (Total 13 marks)} \includegraphics[alt={},max width=\textwidth]{a5d69a77-c196-483c-a550-1a55363555af-3_780_889_1069_1078}
   \end{figure} (4) The table can now be taken to represent a complete network. The nearest neighbour algorithm was used to obtain upper bounds for the length of the route: Starting at D, an upper bound for the length of the route was found to be 838 km .
   Starting at F, an upper bound for the length of the route was found to be 707 km .
3. Starting at C , use the nearest neighbour algorithm to obtain another upper bound for the length of the route. State which is the best upper bound of the

   	A	B	C	D	E	F	G	H
   A	-	84	85	138	173		149	52
   B	84	-	130	77	126	213	222	136
   C	85	130	-	53	88	83	92
   D	138	77	53	-	49			190
   E	173	126	88	49	-	100	180	215
   F		213	83		100	-	163	115
   G	149	222	92		180	163	-	97
   H	52	136		190	215	115	97	-

   three, giving a reason for your answer.
   (4) (Total 13 marks)

7.

1. Define the terms
   1. cut,
   2. minimum cut, as applied to a directed network flow.
      \includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_844_1465_338_299} The figure above shows a capacitated directed network and two cuts \(C _ { 1 }\) and \(C _ { 2 }\). The number on each arc is its capacity.
2. State the values of the cuts \(C _ { 1 }\) and \(C _ { 2 }\). Given that one of these two cuts is a minimum cut,
3. find a maximum flow pattern by inspection, and show it on the diagram below.
   \includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_597_1470_1656_296}
4. Find a second minimum cut for this network. In order to increase the flow through the network it is decided to add an arc of capacity 100 joining \(D\) either to \(E\) or to \(G\).
5. State, with a reason, which of these arcs should be added, and the value of the increased flow.