Edexcel D2 (Decision Mathematics 2)

This question should be answered on the sheet provided. The table below shows the distances in miles between five villages. Jane lives in village A and is about to take her daughter's friends home to villages B, C, D and E. She will begin and end her journey at A and wishes to travel the minimum distance possible.

	A	B	C	D	E
A	\(-\)	4	7	8	2
B	4	\(-\)	1	5	6
C	7	1	\(-\)	2	7
D	8	5	2	\(-\)	3
E	2	6	7	3	\(-\)

1. Obtain a minimum spanning tree for the network and hence find an upper bound for the length of Jane's journey. [4 marks]
2. Using a shortcut, improve this upper bound to find an upper bound of less than 15 miles. [2 marks]

The payoff matrix for player A in a two-person zero-sum game with value V is shown below.

	B
	I	II	III
\multirow{3}{*}{A}	I	6	\(-4\)	\(-1\)
	II	\(-2\)	5	3
	III	5	1	\(-3\)

Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player B.

1. Rewrite the matrix as necessary and state the new value of the game, v, in terms of V. [2 marks]
2. Define your decision variables. [2 marks]
3. Write down the objective function in terms of your decision variables. [2 marks]
4. Write down the constraints. [2 marks]

This question should be answered on the sheet provided. The table below gives distances, in miles, for a network relating to a travelling salesman problem.

	A	B	C	D	E	F	G
A	\(-\)	83	57	68	103	91	120
B	83	\(-\)	78	63	41	82	52
C	57	78	\(-\)	37	59	63	74
D	68	63	37	\(-\)	60	52	62
E	103	41	59	60	\(-\)	48	51
F	91	82	63	52	48	\(-\)	77
G	120	52	74	62	51	77	\(-\)

1. Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of a tour beginning and ending at A and state the tour. [4 marks]
2. By deleting A, obtain a lower bound for the length of a tour. [4 marks]
3. Hence, write down an inequality which must by satisfied by d, the minimum distance travelled in miles. [1 mark]

This question should be answered on the sheet provided. A rally consisting of four stages is being planned. The first stage will begin at A and the last stage will end at L. Various routes are being considered, with the end of one stage being the start of the next. The organisers want the shortest stage to be as long as possible. The table below shows the length, in miles, of each of the possible stages.

			Finishing point
		C	D	E	F	G	H	I
\multirow{3}{*}{Starting point}	A	1	4.5	13	10	8	11	4
	B					5	10.5
	C					9	6
	D					12	7	15
	E
	F							5
	G							8
	H							10
	I
	J
	K

Finishing point
J	K	L
		2
9	2	3
2	9
		5
		6
		10

Use dynamic programming to find the route which satisfies the wish of the organisers. State the length of the shortest stage on this route. [10 marks]

Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances.

	Stage
	1	2	3
Alex	19	69	168
Darren	22	64	157
Leroy	20	72	166
Suraj	23	66	171

Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm. [11 marks]

The payoff matrix for player X in a two-person zero-sum game is shown below.

	Y
	\(Y_1\)	\(Y_2\)
\multirow{2}{*}{X}	\(X_1\)	\(-2\)	4
	\(X_2\)	6	\(-1\)

1. Explain why the game does not have a saddle point. [3 marks]
2. Find the optimal strategy for
   1. player X, [8 marks]
   2. player Y.
3. Find the value of the game. [2 marks]

A transportation problem has costs, in pounds, and supply and demand, in appropriate units, as given in the transportation tableau below.

	D	E	F	Supply
A	13	11	14	20
B	10	9	12	15
C	15	6	8	25
Demand	30	5	25

1. Find the initial solution given by the north-west corner rule and state why it is degenerate. [3 marks]
2. Use the stepping-stone method to obtain an optimal solution minimising total cost. State the resulting transportation pattern and its total cost. [15 marks]