Edexcel D2 (Decision Mathematics 2) 2003 June

1. A two person zero-sum game is represented by the following pay-off matrix for player \(A\).

1. Write down the pay off matrix for player \(B\).
2. Formulate the game as a linear programming problem for player \(B\), writing the constraints as equalities and stating your variables clearly.

2. (a) Explain the difference between the classical and practical travelling salesman problems.
\includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-1_691_1297_1014_383} The network in the diagram above shows the distances, in kilometres, between eight McBurger restaurants. An inspector from head office wishes to visit each restaurant. His route should start and finish at \(A\), visit each restaurant at least once and cover a minimum distance.
(b) Obtain a minimum spanning tree for the network using Kruskal's algorithm. You should draw your tree and state the order in which the arcs were added.
(c) Use your answer to part (b) to determine an initial upper bound for the length of the route.
(d) Starting from your initial upper bound and using an appropriate method, find an upper bound which is less than 135 km . State your tour.

3. Talkalot College holds an induction meeting for new students. The meeting consists of four talks: I (Welcome), II (Options and Facilities), III (Study Tips) and IV (Planning for Success). The four department heads, Clive, Julie, Nicky and Steve, deliver one of these talks each. The talks are delivered consecutively and there are no breaks between talks. The meeting starts at 10 a.m. and ends when all four talks have been delivered. The time, in minutes, each department head takes to deliver each talk is given in the table below.

1. Use the Hungarian algorithm to find the earliest time that the meeting could end. You must make your method clear and show
   1. the state of the table after each stage in the algorithm,
   2. the final allocation.
2. Modify the table so it could be used to find the latest time that the meeting could end.

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

1. Identify the play safe strategies for each player.
2. Verify that there is no stable solution to this game.
3. Explain why the pay-off matrix above may be reduced to

   \cline { 2 - 4 } \multicolumn{1}{c|}{}	\(B\) plays I	\(B\) plays II	\(B\) plays III
   \(A\) plays I	2	- 1	3
   \(A\) plays II	1	3	0

4. Find the best strategy for player \(A\), and the value of the game.

5. The manager of a car hire firm has to arrange to move cars from three garages \(A , B\) and \(C\) to three airports \(D , E\) and \(F\) so that customers can collect them. The table below shows the transportation cost of moving one car from each garage to each airport. It also shows the number of cars available in each garage and the number of cars required at each airport. The total number of cars available is equal to the total number required.

1. Use the North-West corner rule to obtain a possible pattern of distribution and find its cost.
   (3)
2. Calculate shadow costs for this pattern and hence obtain improvement indices for each route.
3. Use the stepping-stone method to obtain an optimal solution and state its cost.

6. Kris produces custom made racing cycles. She can produce up to four cycles each month, but if she wishes to produce more than three in any one month she has to hire additional help at a cost of \(\pounds 350\) for that month. In any month when cycles are produced, the overhead costs are \(\pounds 200\). A maximum of 3 cycles can be held in stock in any one month, at a cost of \(\pounds 40\) per cycle per month. Cycles must be delivered at the end of the month. The order book for cycles is Disregarding the cost of parts and Kris’ time,

1. determine the total cost of storing 2 cycles and producing 4 cycles in a given month, making your calculations clear. There is no stock at the beginning of August and Kris plans to have no stock after the November delivery.
2. Use dynamic programming to determine the production schedule which minimises the costs, showing your working in the table below.

   Stage	Demand	State	Action	Destination	Value
   \multirow[t]{3}{*}{1 (Nov)}	\multirow[t]{3}{*}{2}	0 (in stock)	(make) 2	0	200
   		1 (in stock)	(make) 1	0	240
   		2 (in stock)	(make) 0	0	80
   \multirow[t]{2}{*}{2 (Oct)}	\multirow[t]{2}{*}{5}	1	4	0	\(590 + 200 = 790\)
   		2	3	0

   The fixed cost of parts is \(\pounds 600\) per cycle and of Kris’ time is \(\pounds 500\) per month. She sells the cycles for \(\pounds 2000\) each.
3. Determine her total profit for the four month period.
   (3)
   (Total 18 marks)

7. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network.

1. Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 1 below. \section*{Diagram 1} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-4_684_1531_1816_267}
2. Find the values of \(x\) and \(y\), explaining your method briefly.
3. Find the value of cuts \(C _ { 1 }\) and \(C _ { 2 }\). Starting with the given feasible flow of 68,
4. use the labelling procedure on Diagram 2 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_647_1506_612_283}
5. Show your maximal flow on Diagram 3 and state its value. \section*{Diagram 3} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_654_1511_1567_278}
6. Prove that your flow is maximal.

8. The tableau below is the initial tableau for a maximising linear programming problem.

1. For this problem \(x \geq 0 , y \geq 0 , z \geq 0\). Write down the other two inequalities and the objective function.
2. Solve this linear programming problem. You may not need to use all of these tableaux.

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

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

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

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

3. State the final value of \(P\), the objective function, and of each of the variables.