Edexcel D2 (Decision Mathematics 2) 2017 June

1. The table above shows the least distances, in km , between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

1. Starting at A, and making your working clear, find an initial upper bound for the travelling salesperson problem for this network, using
   1. the minimum spanning tree method,
   2. the nearest neighbour algorithm.
      (5) By deleting A, and all of its arcs, a lower bound for the travelling salesperson problem for this network is found to be 500 km . By deleting B, and all of its arcs, the corresponding lower bound is found to be 474 km .
2. Using the results from (a) and the given lower bounds, write down the smallest interval that you can be confident contains the solution to the travelling salesperson problem for this network.
   (2)

2. The table shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { A } , \mathrm { B }\) and C , to each of four demand points, \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
   (1)
2. Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
   (2)
3. Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
4. Determine whether your current solution is optimal, giving a reason for your answer.

3. 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. State, giving a reason, whether there is a stable solution to this game.
3. Find the best strategy for player A.
4. Find the value of the game to player B.

4. Four workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , are to be assigned to four tasks, \(1,2,3\) and 4 . Each worker must be assigned to only one task and each task must be done by only one worker. Worker A cannot do task 3 and worker D cannot do task 2
The cost, in pounds, of assigning each worker to each task is shown in the table below. The total cost is to be minimised.
Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear. You do not need to solve this problem.

5. The tableau below is the initial tableau for a three-variable linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Using the information in the tableau, write down
   1. the objective function,
   2. the three constraints as inequalities.
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use.
3. State the final values of the objective function and each variable.

6. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of the corresponding arc. The numbers in circles represent an initial flow from S to T .

1. State the value of the initial flow.
2. State the capacity of cut \(C _ { 1 }\)
3. Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along \(\mathrm { AC } , \mathrm { SB } , \mathrm { BE } , \mathrm { DE }\) and FG .
   (2)
4. Hence use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
5. Draw a maximal flow pattern on Diagram 2 in the answer book.
6. Prove that your flow is maximal.

7. A clothing manufacturer can export a maximum of five batches of shirts each year. Each exported batch contains just one type of shirt, the types being T-shirts, Rugby shirts and Polo shirts. The table below shows the profit, in £ 1000 s, for the number of each exported batch type. 2.

1. 	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   3.

   	B plays 1	B plays 2	B plays 3
   A plays 1	0	- 2	6
   A plays 2	3	4	1
   A plays 3	- 1	1	- 3

   4.

   	1	2	3	4
   A	53	84	-	20
   B	87	72	41	38
   C	70	51	52	25
   D	45	-	81	70

   5. (a)
2. You may not need to use all of these tableaux

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	15	- 2	3	1	0	0	180
   \(s\)	10	1	1	0	1	0	80
   \(t\)	1	6	- 2	0	0	1	100
   \(P\)	- 1	- 2	- 5	0	0	0	0

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

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

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

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

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

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

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

3. 
   6. (a) Value of initial flow
4. Capacity of cut \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{d5798c81-290a-4e4b-aa46-497b62ca899b-20_1931_1099_507_408} \captionsetup{labelformat=empty} \caption{Diagram 1}
   \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{d5798c81-290a-4e4b-aa46-497b62ca899b-21_1874_953_653_589}
   7. You may not need to use all the rows of this table

   Stage	State	Action	Dest.	Value
   T-shirt

   Stage	State	Action	Dest.	Value

   Maximum annual profit £ \(\_\_\_\_\)