Edexcel D2 (Decision Mathematics 2) 2007 June

1. The network above shows the distances, in miles, between seven gift shops, \(A , B\), \(C , D , E , F\) and \(G\).

The area manager needs to visit each shop. She will start and finish at shop A and wishes to minimise the total distance travelled.

1. By inspection, complete the two copies of the table of least distances below.
   \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-1_666_1136_141_863}

   	A	\(B\)	C	\(D\)	\(E\)	\(F\)	\(G\)
   A	-		15	36		53	23
   B		-	17	38	49	80	49
   C	15	17	-	21		62	32
   D	36	38	21	-	11	42
   E		49		11	-	31	61
   \(F\)	53	80	62	42	31	-	30
   \(G\)	23	49	32		61	30	-

   (4)

   	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
   \(A\)	-		15	36		53	23
   \(B\)		-	17	38	49	80	49
   \(C\)	15	17	-	21		62	32
   \(D\)	36	38	21	-	11	42
   \(E\)		49		11	-	31	61
   \(F\)	53	80	62	42	31	-	30
   \(G\)	23	49	32		61	30	-

2. Starting at A, and making your method clear, find an upper bound for the route length, using the nearest neighbour algorithm.
   (3)
3. By deleting A, and all of its arcs, find a lower bound for the route length.
   (4) (Total 11 marks)

2. Denis (D) and Hilary (H) play a two-person zero-sum game represented by the following pay-off matrix for Denis.

1. Show that there is no stable solution to this game.
2. Find the best strategy for Denis and the value of the game to him.
   (10) (Total 13 marks)

3. To raise money for charity it is decided to hold a Teddy Bear making competition. Teams of four compete against each other to make 20 Teddy Bears as quickly as possible. There are four stages: first cutting, then stitching, then filling and finally dressing.
Each team member can only work on one stage during the competition. As soon as a stage is completed on each Teddy Bear the work is passed immediately to the next team member. The table shows the time, in seconds, taken to complete each stage of the work on one Teddy Bear by the members \(A , B , C\) and \(D\) of one of the teams.

1. Use the Hungarian algorithm, reducing rows first, to obtain an allocation that minimises the time taken by this team to produce one Teddy Bear. You must make your method clear and show the table after each iteration.
2. State the minimum time it will take this team to produce one Teddy Bear. Using the allocation found in (a),
3. calculate the minimum total time this team will take to complete 20 Teddy Bears. You should make your reasoning clear and state your answer in minutes and seconds.
   (Total 13 marks)

4. A group of students and teachers from a performing arts college are attending the Glasenburgh drama festival. All of the group want to see an innovative modern production of the play 'The Decision is Final'. Unfortunately there are not enough seats left for them all to see the same performance. There are three performances of the play, 1,2 , and 3 . There are two types of ticket, Adult and Student. Student tickets will be purchased for the students and Adult tickets for the teachers. The table below shows the price of tickets for each performance of the play. There are 18 teachers and 200 students requiring tickets. There are 94,65 and 80 seats available for performances 1,2 , and 3 espectively.

1. Complete the table below.

   	Adult	Student	Dummy	Seats available
   Performance 1	£5.00	£4.50
   Performance 2	£4.20	£3.80
   Performance 3	£4.60	£4.00
   Tickets needed

2. Explain why a dummy column was added to the table above.
3. Use the north-west corner method to obtain a possible solution.
4. Taking the most negative improvement index to indicate the entering square, use the stepping stone method once to obtain an improved solution. You must make your shadow costs and improvement indices clear. After a further iteration the table becomes:

   	Adult	Student	Dummy
   Performance 1		73	21
   Performance 2	18	47
   Performance 3		80

5. Demonstrate that this solution gives the minimum cost, and find its value.
   (Total 16 marks)

5. \begin{figure}[h] \end{figure} In solving a network flow problem using the labelling procedure, the diagram in Figure 1 was created.
The arrow on each arc indicates the direction of the flow along that arc.
The arrows above and below each arc show the direction and value of the flow as indicated by the labelling procedure.

1. Add a supersource S , a supersink T and appropriate arcs to the diagram above, and complete the labelling procedure for these arcs.
2. Write down the value of the initial flow shown in Figure 1.
3. Use Figure 2 below, the initial flow and the labelling procedure to find the maximal flow of 124 through this network. List each flow-augmenting path you use, together with its flow.
4. Show your flow on the diagram below and state its value.
   \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-4_967_1520_114_214}
5. Prove that your flow is maximal.
   (2)
   (Total 14 marks)

6. Anna (A) and Roland (R) play a two-person zero-sum game which is represented by the following pay-off matrix for Anna. Formulate the game as a linear programming problem for player \(\mathbf { R }\). Write the constraints as inequalities. Define your variables clearly.
(Total 8 marks)

7.
\includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-5_965_1657_210_121} Agent Goodie has successfully recovered the stolen plans from Evil Doctor Fiendish and needs to take them from Evil Doctor Fiendish's secret headquarters at X to safety at Y . To do this he must swim through a network of underwater tunnels. Agent Goodie has no breathing apparatus, but knows that there are twelve points, \(A , B , C , D , E , F , G , H , I , J , K\) and \(L\), at which there are air pockets where he can take a breath. The network is modelled above, and the number on each arc gives the time, in seconds, it takes Agent Goodie to swim from one air pocket to the next. Agent Goodie needs to find a route through this network that minimises the longest time between successive air pockets.

1. Use dynamic programming to complete the table below and hence find a suitable route for Agent Goodie. Unfortunately, just as Agent Goodie is about to start his journey, tunnel XA becomes blocked.
2. Find an optimal route for Agent Goodie avoiding tunnel XA.

8. The tableau below is the initial tableau for a linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\). Using the information in the tableau, write down

1. the objective function,
2. the three constraints as inequalities with integer coefficients. Taking the most negative number in the profit row to indicate the pivot column at each stage,
3. solve this linear programming problem. Make your method clear by stating the row operations you use.

   b.v.	x	y	z	r	s	t	Value	Row operations

   b.v.	x	y	z	r	s	t	Value	Row operations

   b.v.	x	y	z	r	s	t	Value	Row operations

   b.v.	x	y	z	r	s	t	Value	Row operations

4. State the final values of the objective function and each variable.
5. One of the constraints is not at capacity. Explain how it can be identified.

9. \begin{figure}[h] \end{figure}

1. State the value of the initial flow.
2. State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\). Figure 2 shows the labelling procedure applied to the above network.
3. Using Figure 2, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow.
4. Prove that the flow is now maximal. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-8_2146_1038_127_422} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure}