A2 Module 4737 Decision Mathematics 2 Sample Pages

http://www.mppe.org.
uk
NOTICE TO CUSTOMER:
The sale of this product is intended for use of the original
purchaser only and for use only on a single computer system.
Duplicating, selling, or otherwise distributing this product is

a violation of the law ; your license of the product will be
terminated at any moment if you are selling or distributing
the products.
No parts of this book may be reproduced, stored in a retrieval

system, of transmitted, in any form or by any means, electronic,
mechanical, photocopying, recording, or otherwise, without the
prior written permission of the publisher.
Copyright © mppe.org.uk and its license. All Rights Reserved

http://www.mppe.org.uk
Practice 1
2
Answer all questions.
1 Five trainers, Ali, Bo, Chas, Dee and Eve, held an initial training session with each of four
teams over an assault course. The completion times in minutes are recorded below.
Ali Bo Chas Dee Eve

Team 1 16 19 18 25 24
Team 2 22 21 20 26 25
Team 3 21 22 23 21 24
Team 4 20 21 21 23 20
Each of the four teams is to be allocated a trainer and the overall time for the four teams is
to be minimised. No trainer can train more than one team.
(a) Modify the table of values by adding an extra row of values so that the Hungarian
algorithm can be applied. (1 mark)
(b) Use the Hungarian algorithm, reducing columns first then rows, to decide which four
trainers should be allocated to which team. State the minimum total training time for
the four teams using this matching. (8 marks)
2 A manufacturing company is planning to build three new machines, A, B and C, at the rate of
one per month. The order in which they are built is a matter of choice, but the profits will
vary according to the number of workers available and the suppliers' costs. The expected
profits in thousands of pounds are given in the table.
Profit (in units of £1000)

Month Already built A B C
1 Ð 52 47 48
2 A Ð 58 54
B 70 Ð 54
C 68 63 Ð
3 A and B Ð Ð 64
A and C Ð 67 Ð
B and C 69 Ð Ð
(a) Draw a labelled network such that the most profitable order of manufacture corresponds
to the longest path within that network. (2 marks)
(b) Use dynamic programming to determine the order of manufacture that maximises the
total profit, and state this maximum profit. (7 marks)
3
3 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
A building project is to be undertaken. The table shows the activities involved.
Number of
Immediate Workers
Activity Predecessors Duration (days) Required
A Ð 2 3
B A 4 2
C A 6 1
D B, C 8 3
E C 3 2
F D 2 2
G D, E 4 2
H D, E 6 1
I F, G, H 2 3
(a) Complete the activity network for the project on Figure 1. (3 marks)
(b) Find the earliest start time for each activity. (2 marks)
(c) Find the latest finish time for each activity. (2 marks)
(d) Find the critical path and state the minimum time for completion. (2 marks)
(e) State the float time for each non-critical activity. (2 marks)
(f) Given that each activity starts as early as possible, draw a resource histogram for the
project on Figure 2. (4 marks)
(g) There are only 3 workers available at any time. Use resource levelling to explain why
the project will overrun and state the minimum extra time required. (3 marks)
Turn over
s

4
4 [Figures 3, 4 and 5, printed on the insert, are provided for use in this question.]
The network shows a system of pipes, with the lower and upper capacities for each pipe in
litres per second.
M 5, 8 N
3, 9 1, 4
3, 6
S 2, 3 0, 4 T
6, 8 8, 12
P 5, 11 Q
(a) Figure 3, on the insert, shows a partially completed diagram for a feasible flow of
10 litres per second from S to T. Indicate, on Figure 3, the flows along the edges
MN , PQ, NP and NT. (4 marks)
(b) (i) Taking your answer from part (a) as an initial flow, use flow augmentation on
Figure 4 to find the maximum flow from S to T. (6 marks)
(ii) State the value of the maximum flow and illustrate this flow on Figure 5.
(2 marks)
(c) Find a cut with capacity equal to that of the maximum flow. (2 marks)

5
5 (a) Display the following linear programming problem in a Simplex tableau.
Maximise P 3x 2y 4z
subject to x 4y 2z 4 8
2x 7y 3z 4 21
x 5 0, y 5 0, z 5 0 (3 marks)
(b) Use the Simplex method to perform one iteration of your tableau for part (a), choosing
a value in the z-column as pivot. (3 marks)
(c) (i) Perform one further iteration. (5 marks)
(ii) State whether or not this is the optimal solution, and give a reason for your
answer. (2 marks)
6 Sam is playing a computer game in which he is trying to drive a car in different road
conditions. He chooses a car and the computer decides the road conditions. The points
scored by Sam are shown in the table.
Road Conditions
C1 C2 C3
S1 2 2 4
Sam's Car S2 2 4 5
S3 5 1 2
Sam is trying to maximise his total points and the computer is trying to stop him.
(a) Explain why Sam should never choose S1 and why the computer should not choose C3 .
(2 marks)
(b) Find the play-safe strategies for the reduced 2 by 2 game for Sam and the computer,
and hence show that this game does not have a stable solution. (4 marks)
(c) Sam uses random numbers to choose S2 with probability p and S3 with probability 1 p.
(i) Find expressions for the expected gain for Sam when the computer chooses each
of its two remaining strategies. (3 marks)
(ii) Calculate the value of p for Sam to maximise his total points. (2 marks)
(iii) Hence find the expected points gain for Sam. (1 mark)
END OF QUESTIONS

Figure 1 (for use in part (a))
B D
4 8
Insert for Practice 1
Duration C E
6 3
2
Earliest start Latest finish

time time
For use in Question 3
Figure 2 (for use in part (f))

Number of workers
6 ±
5 ±
4 ±
3 ±

2 ±
1 ±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
±
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Time (days)
3
For use in Question 4
Figure 3 (for use in part (a))
M N
S 2 1 T
6 8
P Q
Figure 4 (for use in part (b)(i))
M N
Route Extra
flow
S T
P Q
Figure 5 (for use in part (b)(ii))
M N
S T
P Q

Practice 2
1. Explain what is meant, in a network, by
(a) a walk
(2)
(b) a tour
(2)
(Total 4 marks)
2. Jameson cars are made in two factories A and B. Sales have been made at the two main showrooms
in London and Edinburgh. Cars are to be transported from the factories to the showrooms. The
table below shows the cost, in pounds, of transporting one car from each factory to each showroom.
It also shows the number of cars available at each factory and the number required at each
showroom.
London (L) Edinburgh (E) Supply

A 80 70 55
B 60 50 45
Demand 35 60
It is decided to use the transportation algorithm to obtain a minimal cost solution.
(a) Explain why it is necessary to add a dummy demand point.

(2)
(b) Complete table 1 in the answer booklet.

(2)
(c) Use the north-west corner rule to obtain a possible pattern of distribution.
(1)
(d) Taking the most negative improvement index to indicate the entering square, use the
stepping-stone method to obtain an optimal solution. You must make your shadow costs and
improvement indices clear and demonstrate that your solution is optimal.
(7)
(e) State the cost of your optimal solution.

(1)
(Total 13 marks)

3. (a) Explain the difference between a maximin route and a minimax route in dynamic
programming.
(2)
A 185 D 175 G
279 160
155 132
119 162
190 B 250 E 144 H 175
L R
123 102
148 145 139
240
C 170 F 210 I
Figure 1
A Maximin route from L to R is to be found through the staged network shown in Figure 1.
(b) Use dynamic programming to complete the table in the answer book and hence find a maximin
route.
(10)
(Total 12 marks)
Copyright © mppe.org.uk and its license. All Rights Reserved Turn over
4. (a) In game theory, explain the circumstances under which column (x) dominates column (y) in a
two-person zero-sum game.
(2)
Liz and Mark play a zero-sum game. This game is represented by the following pay-off matrix for Liz.
Mark plays 1 Mark plays 2 Mark plays 3
Liz plays 1 5 3 2
Liz plays 2 4 5 6
Liz plays 3 6 4 3
(b) Verify that there is no stable solution to this game.

(3)
(c) Find the best strategy for Liz and the value of the game to her.
(9)
The game now changes so that when Liz plays 1 and Mark plays 3 the pay-off to Liz changes from
2 to 4. All other pay-offs for this zero-sum game remain the same.
(d) Explain why a graphical approach is no longer possible and briefly describe the method Liz
should use to determine her best strategy.
(2)
(Total 16 marks)

5. Four salespersons, Joe, Min-Seong, Olivia and Robert, are to attend four business fairs, A, B, C and
D. Each salesperson must attend just one fair and each fair must be attended by just one salesperson.
The expected sales, in thousands of pounds, that each salesperson would make at each fair is shown
in the table below.
A B C D
Joe 48 49 42 42
Min-Seong 53 49 51 50
Olivia 51 53 48 48
Robert 47 50 46 43
(a) Use the Hungarian algorithm, reducing rows first, to obtain an allocation that maximises the
total expected sales from the four salespersons. You must make your method clear and show
the table after each stage.
(10)
(b) State all possible optimal allocations and the optimal total value.
(4)
(Total 14 marks)
6. A
98
E
87
G 59
61 57
56
C
38 F 75
102
75
89 68
64
H
111 B
108
D
Figure 2
The network in figure 2 shows the distances, in km, between eight weather data collection points.
Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum
distance.
(a) Obtain a minimum spanning tree for the network using Kruskal’s algorithm, stating the order
in which you select the arcs.
(2)
(b) Use your answer to part (a) to determine an initial upper bound for the length of the route.
(1)
(c) Starting from your initial upper bound use short cuts to find an upper bound, which is below
630km. State the corresponding route.
(4)
(d) Use the nearest neighbour algorithm starting at B to find a second upper bound for the length
of the route.
(3)
(e) By deleting C, and all of its arcs, find a lower bound for the length of the route.
(4)
(f) Use your results to write down the smallest interval which you are confident contains the
optimal length of the route.
(2)
(Total 16 marks)
TOTAL FOR PAPER: 75 MARKS
END

Answer book for Practice 2
Leave
blank
1. _______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q1
(Total 4 marks)
Turn over

Leave
blank
2. (a) ___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
(b) Table 1
L E Dummy Supply
A 80 70 55
B 60 50 45
Demand 35 60 100
(c)
L E D
A
B
(d) You may not need to use all of these tables
L E D
A
B
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
L E D
A
B
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________

Leave
blank
L E D
A
B
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
L E D
A
B
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
L E D
A
B
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
L E D
A
B
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
Turn over

Leave
blank
L E D
A
B
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
L E D
A
B
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________ Q2
(Total 13 marks)

BLANK PAGE
Turn over

Leave
blank
3. (a) ___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
(b)
Stage State Action Destination Value

________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________

Leave
blank
Stage State Action Destination Value
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
Q3
___________________________________________________________________
(Total 12 marks)
Turn over

Leave
blank
4. _______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
10

Leave
blank
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q4
(Total 16 marks)
11
Turn over

Leave
blank
5.
A B C D __________________________________________
__________________________________________
J
__________________________________________
M __________________________________________
O __________________________________________
__________________________________________
R
__________________________________________
__________________________________________
A B C D
__________________________________________
J
__________________________________________
M __________________________________________
O __________________________________________
__________________________________________
R
__________________________________________
__________________________________________
A B C D
__________________________________________
J __________________________________________
M __________________________________________
__________________________________________
O
__________________________________________
R
__________________________________________
__________________________________________
A B C D
__________________________________________
J __________________________________________
M __________________________________________
__________________________________________
O
__________________________________________
R __________________________________________
__________________________________________
A B C D __________________________________________
J __________________________________________
M __________________________________________
__________________________________________
O
__________________________________________
R __________________________________________
12

Leave
blank
__________________________________________
A B C D
__________________________________________
J
__________________________________________
M __________________________________________
O __________________________________________
__________________________________________
R
__________________________________________
__________________________________________
A B C D
__________________________________________
J __________________________________________
M __________________________________________
O __________________________________________
__________________________________________
R
__________________________________________
__________________________________________
A B C D
__________________________________________
J __________________________________________
M __________________________________________
__________________________________________
O
__________________________________________
R
__________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q5
(Total 14 marks)
13
Turn over

Leave
blank
6. _______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
14

Leave
blank
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
15
Turn over

Leave
blank
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
Q6
_______________________________________________________________________
(Total 16 marks)
END
16

Practice 3
2
1 [Figure 1, printed on the insert, is provided for use in this question.]
A building project is to be undertaken. The table shows the activities involved.
Activity Immediate Duration

Predecessors (weeks)
A – 2
B – 1
C A 3
D A, B 2
E B 4
F C 1
G C, D, E 3
H E 5
I F, G 2
J H, I 3
(a) Complete an activity network for the project on Figure 1. (3 marks)
(b) Find the earliest start time for each activity. (2 marks)
(c) Find the latest finish time for each activity. (2 marks)
(d) State the minimum completion time for the building project and identify the critical
paths. (4 marks)

3
2 Five successful applicants received the following scores when matched against suitability
criteria for five jobs in a company.
Job 1 Job 2 Job 3 Job 4 Job 5

Alex 13 11 9 10 13
Bill 15 12 12 11 12
Cath 12 10 8 14 14
Don 11 12 13 14 10
Ed 12 14 14 13 14
It is intended to allocate each applicant to a different job so as to maximise the total score of
the five applicants.
(a) Explain why the Hungarian algorithm may be used if each number, x, in the table is
replaced by 15 x . (2 marks)
(b) Form a new table by subtracting each number in the table from 15. Use the Hungarian
algorithm to allocate the jobs to the applicants so that the total score is maximised.
(8 marks)
(c) It is later discovered that Bill has already been allocated to Job 4. Decide how to alter
the allocation of the other jobs so as to maximise the score now possible. (3 marks)
3 (a) Display the following linear programming problem in a Simplex tableau.
Maximise P ¼ 5x þ 8y þ 7z
subject to 3x þ 2y þ z 4 12
2x þ 4y þ 5z 4 16
x 5 0, y 5 0, z 5 0 (3 marks)
(b) The Simplex method is to be used by initially choosing a value in the y-column as a
pivot.
(i) Explain why the initial pivot is 4. (1 mark)
(ii) Perform two iterations of your tableau from part (a) using the Simplex method.
(6 marks)
(iii) State the values of P, x, y and z after your second iteration. (2 marks)
(iv) State, giving a reason, whether the maximum value of P has been achieved.
(1 mark)
s
Turn over
4
4 (a) Two people, Ros and Col, play a zero-sum game. The game is represented by the
following pay-off matrix for Ros.
Col
Strategy X Y Z
I 4 3 0
Ros II 5 2 2
III 1 1 3
(i) Show that this game has a stable solution. (3 marks)
(ii) Find the play-safe strategy for each player and state the value of the game.
(2 marks)
(b) Ros and Col play a different zero-sum game for which there is no stable solution.
The game is represented by the following pay-off matrix for Ros.
Col
Strategy C1 C2 C3
R1 3 2 1
Ros
R2 2 1 2
(i) Find the optimal mixed strategy for Ros. (7 marks)
(ii) Calculate the value of the game. (1 mark)

5
5 A three-day journey is to be made from S to T, with overnight stops at the end of the first
day at either A or B and at the end of the second day at one of the locations C, D or E. The
network shows the number of hours of sunshine forecast for each day of the journey.
C
4
A
7
4
9
6 9
S T
5 D
8
5
5
B
7
E
The optimal route, known as the maximin route, is that for which the least number of hours
of sunshine during a day’s journey is as large as possible.
(a) Explain why the three-day route SAET is better than SACT. (2 marks)
(b) Use dynamic programming to find the optimal (maximin) three-day route from S to T.
(8 marks)
Turn over for the next question

s
Turn over
6
The diagram shows a network of pipelines through which oil can travel. The oil field is at S,
the refinery is at T and the other vertices are intermediate stations. The weights on the edges
show the capacities in millions of barrels per hour that can flow through each pipeline.
C
10 B
A
4
20 15
12 6
16 D 14
S E 17
T
9
7 15
8
(a) (i) Find the value of the cut marked C on the diagram. (1 mark)
(ii) Hence make a deduction about the maximum flow of oil through the network.
(2 marks)
(b) State the maximum possible flows along the routes SABT, SDET and SFT. (2 marks)
(c) (i) Taking your answer to part (b) as the initial flow, use a labelling procedure on
Figure 2 to find the maximum flow from S to T. Record your routes and flows in the
table provided and show the augmented flows on the network diagram. (6 marks)
(ii) State the value of the maximum flow, and, on Figure 3, illustrate a possible flow
along each edge corresponding to this maximum flow. (2 marks)
(iii) Prove that your flow in part (c)(ii) is a maximum. (2 marks)
END OF QUESTIONS

Figure 1 (for use in Question 1) 2
Latest finish
time
Duration
D
C
Earliest start
time
B
1
A
2
0

3
Figure 2 (for use in Question 6(c)(i))
A B
D
S E
T
Route Flow
SABT
SDET
F SFT
Figure 3 (for use in Question 6(c)(ii))
B
A
D
S E
T

Practice 4
1. A company, Kleenitquick, has developed a new stain remover. To promote sales, three salespersons,
Jess, Matt and Rachel, will be assigned to three of four department stores 1, 2, 3 and 4, to demonstrate
the stain remover. Each salesperson can only be assigned to one department store.
The table below shows the cost, in pounds, of assigning each salesperson to each department
store.
1 2 3 4
Jess 15 11 14 12
Matt 13 8 17 13
Rachel 14 9 13 15
(a) Explain why a dummy row needs to be added to the table.

(1)
(b) Complete Table 1 in the answer book.

(1)
(c) Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the
cost of assigning salespersons to department stores. You must make your method clear and
show the table after each iteration.
(6)
(d) Find the minimum cost.

(1)
(Total 9 marks)

2. (a) Explain the difference between the classical and the practical travelling salesperson
problems.
(2)
The table below shows the distances, in km, between six data collection points, A, B, C, D, E, and F.
A B C D E F
A - 77 34 56 67 21
B 77 - 58 58 36 74
C 34 58 - 73 70 42
D 56 58 73 - 68 38
E 67 36 70 68 - 71
F 21 74 42 38 71 -
Rachel must visit each collection point. She will start and finish at A and wishes to minimise the
total distance travelled.
(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. Make your
method clear.
(3)
Starting at B, a second upper bound of 293 km was found.
(c) State the better upper bound of these two, giving a reason for your answer.
(1)
By deleting A, a lower bound was found to be 245 km.
(d) By deleting B, find a second lower bound. Make your method clear.
(4)
(e) State the better lower bound of these two, giving a reason for your answer.
(1)
(f) Taking your answers to (c) and (e), use inequalities to write down an interval that must contain
the length of Rachel’s optimal route.
(1)
(Total 12 marks)
3. A two-person zero-sum game is represented by the following pay-off matrix for player A.
B plays 1 B plays 2 B plays 3

A plays 1 –5 6 –3
A plays 2 1 –4 13
A plays 3 –2 3 –1
(a) Verify that there is no stable solution to this game.

(3)
(b) Reduce the game so that player B has a choice of only two actions.
(1)
(c) Write down the reduced pay-off matrix for player B.

(2)
(d) Find the best strategy for player B and the value of the game to player B.
(7)
(Total 13 marks)

4.
C2
E
C1 4 4
D
6 10 2
A 2 7
5 0 4
7 6 8 F
1
7 2 B 8 T
5 5 14
S 8 10 25
3 22
2 G
11
11 9 9
C2
C
C1
Figure 1
Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. The numbers
in circles represent an initial flow from S to T.
Two cuts C1 and C2 are shown in Figure 1.
(a) Find the capacity of each of the two cuts.

(2)
(b) Find the maximum flow through the network. You must list each flow-augmenting route you
use together with its flow.
(3)
(Total 5 marks)
5. While solving a maximising linear programming problem, the following tableau was obtained.
Basic Variable x y z r s t value
z 1
4 – 14 1 1
4 0 0 2
5 7 – 34
s 4 4 0 1 0 4
5 – 12
t 3 2 0 0 1 2
5
P –2 –4 0 4 0 0 10
(a) Write down the values of x, y and z as indicated by this tableau.

(2)
(b) Write down the profit equation from the tableau.

(2)
(Total 4 marks)

6. The table below shows the cost, in pounds, of transporting one unit of stock from each of three
supply points, X, Y and Z to three demand points, A, B and C. It also shows the stock held at each
supply point and the stock required at each demand point.
A B C Supply
X 17 8 7 22
Y 16 12 15 17
Z 6 10 9 15
Demand 16 15 23
(a) This is a balanced problem. Explain what this means.

(1)
(b) Use the north west corner method to obtain a possible solution.
(1)
(c) Taking ZA as the entering cell, use the stepping-stone method to find an improved solution.
Make your route clear and state your exiting cell.
(3)
(d) Perform one more iteration of the stepping-stone method to find a further improved solution.
You must make your shadow costs, improvement indices, entering cell, exiting cell and route
clear.
(6)
(e) State the cost of the solution you found in part (d).
(1)
(Total 12 marks)
7. Minty has £250 000 to allocate to three investment schemes. She will allocate the money to these
schemes in units of £50 000. The net income generated by each scheme, in £1000s, is given in the
table below.
£0 £50 000 £100 000 £150 000 £200 000 £250 000
Scheme 1 0 60 120 180 240 300
Scheme 2 0 65 125 190 235 280
Scheme 3 0 55 110 170 230 300
Minty wishes to maximise the net income. She decides to use dynamic programming to determine
the optimal allocation, and starts the table shown in your answer book.
(a) Complete the table in the answer book to determine the amount Minty should allocate to each
scheme in order to maximise the income. State the maximum income and the amount that
should be allocated to each scheme.
(10)
(b) For this problem give the meaning of the table headings
(i) Stage,
(ii) State,
(iii) Action.
(3)
(Total 13 marks)
8. Laura (L) and Sam (S) play a two-person zero-sum game which is represented by the following
pay-off matrix for Laura.
S plays 1 S plays 2 S plays 3

L plays 1 –2 8 –1
L plays 2 7 4 –3
L plays 3 1 –5 4
Formulate the game as a linear programming problem for Laura, writing the constraints as
inequalities. Define your variables clearly.
(Total 7 marks)
END

Answer book for Practice 4
Leave
blank
1. (a) ___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
(b)
1 2 3 4
Jess 15 11 14 12
Matt 13 8 17 13
Rachel 14 9 13 15
Dummy
Table 1
(c) You may not need to use all of these tables
_____________________________________
1 2 3 4
_____________________________________
J _____________________________________
M _____________________________________
R _____________________________________
D _____________________________________
_____________________________________
1 2 3 4 _____________________________________
_____________________________________
J
_____________________________________
M
_____________________________________
R
_____________________________________
D _____________________________________
_____________________________________
1 2 3 4 _____________________________________
J _____________________________________
M _____________________________________
R _____________________________________
_____________________________________
D
_____________________________________
_____________________________________
_____________________________________
_____________________________________
2
Leave
blank
(Question 1 continued)
1 2 3 4
_____________________________________
J
_____________________________________
M _____________________________________
R _____________________________________
D _____________________________________
_____________________________________
1 2 3 4 _____________________________________
J _____________________________________
_____________________________________
M
_____________________________________
R
_____________________________________
D
_____________________________________
_____________________________________
1 2 3 4 _____________________________________
J _____________________________________
M _____________________________________
R _____________________________________
D _____________________________________
_____________________________________
_____________________________________
1 2 3 4
_____________________________________
J
_____________________________________
M
_____________________________________
R _____________________________________
D _____________________________________
Allocation Jess does __________________

Matt does __________________
Rachel does __________________
(d) Minimum cost: ____________________________________ Q1
(Total 9 marks)
3
Turn over
Leave
blank
2. (a) ___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
A B C D E F
A - 77 34 56 67 21
B 77 - 58 58 36 74
C 34 58 - 73 70 42
D 56 58 73 - 68 38
E 67 36 70 68 - 71
F 21 74 42 38 71 -
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
4
Leave
blank
A B C D E F
A - 77 34 56 67 21
B 77 - 58 58 36 74
C 34 58 - 73 70 42
D 56 58 73 - 68 38
E 67 36 70 68 - 71
F 21 74 42 38 71 -
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
Q2
_______________________________________________________________________
(Total 12 marks)
5
Turn over
Leave
blank
3.
B plays 1 B plays 2 B plays 3
A plays 1 –5 6 –3
A plays 2 1 –4 13
A plays 3 –2 3 –1
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
6
Leave
blank
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q3
(Total 13 marks)
7
Turn over
Leave
blank
4. (a) ___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
Value of cut C1: ______________________________________

Value of cut C2: ______________________________________
(b) ___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________ Q4
(Total 5 marks)
8
Leave
blank
5. (a) x = _____________________________
y = _____________________________
z = _____________________________
(b) ___________________________________________________________________
___________________________________________________________________
___________________________________________________________________ Q5
(Total 4 marks)
9
Turn over
Leave
blank
6. (a) ___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
(b)
A B C
X
Y
Z
You may not need to use all of these tables
_____________________________________
A B C
_____________________________________
X
_____________________________________
Y
_____________________________________
Z _____________________________________
_____________________________________
A B C _____________________________________
X _____________________________________
Y _____________________________________
Z _____________________________________
_____________________________________
A B C _____________________________________
_____________________________________
X
_____________________________________
Y
_____________________________________
Z
_____________________________________
_____________________________________
A B C _____________________________________
X _____________________________________
Y _____________________________________
Z _____________________________________
_____________________________________
_____________________________________
_____________________________________
_____________________________________
10
Leave
blank
A B C _____________________________________
X _____________________________________
_____________________________________
Y
_____________________________________
Z
_____________________________________
_____________________________________
A B C
_____________________________________
X _____________________________________
Y _____________________________________
Z _____________________________________
_____________________________________
A B C _____________________________________
X _____________________________________
_____________________________________
Y
_____________________________________
Z
_____________________________________
_____________________________________
A B C
_____________________________________
X
_____________________________________
Y _____________________________________
Z _____________________________________
_____________________________________
A B C _____________________________________
X _____________________________________
Y _____________________________________
_____________________________________
Z
_____________________________________
_____________________________________
A B C
_____________________________________
X
_____________________________________
Y _____________________________________
Z _____________________________________ Q6
(Total 12 marks)
11
Turn over
Leave
blank
7. (a)
Stage State Action Destination Value (in £1000s)

(in £1000s) (in £1000s) (in £1000s)
1 250 250 0 300 *
200 200 0 240 *
150 150 0 180 *
100 100 0 120 *
50 50 0 60 *
0 0 0 0*
2 250 250 0 280 + 0 = 280
200 50 235 + 60 = 295
150 100
100 150
50 200
0 250
200 200 0
150 50
100
50
0
150 150
100
50
0
100
12
Leave
blank
Stage State Action Destination Value (in £1000s)

(in £1000s) (in £1000s) (in £1000s)
Maximum income: ____________________________________________________
Scheme 1 2 3
Amount to be invested (in £1000s)
(b) ___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________ Q7
(Total 13 marks)
13
Turn over
Leave
blank
8. _______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
14
Leave
blank
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q8
(Total 7 marks)
END
15
Practice 5 2
A group of workers is involved in a building project. The table shows the activities involved.
Each worker can perform any of the given activities.
Activity Immediate Duration (days) Number of

predecessors workers required
A – 3 5
B A 8 2
C A 7 3
D B, C 8 4
E C 10 2
F C 3 3
G D, E 3 4
H F 6 1
I G, H 2 3
(a) Complete the activity network for the project on Figure 1. (2 marks)
(b) Find the earliest start time and the latest finish time for each activity, inserting their
values on Figure 1. (4 marks)
(c) Find the critical path and state the minimum time for completion. (2 marks)
(d) The number of workers required for each activity is given in the table above. Given
that each activity starts as early as possible and assuming there is no limit to the
number of workers available, draw a resource histogram for the project on Figure 2,
indicating clearly which activities take place at any given time. (4 marks)
(e) It is later discovered that there are only 7 workers available at any time. Use resource
levelling to explain why the project will overrun and indicate which activities need to
be delayed so that the project can be completed with the minimum extra time. State the
minimum extra time required. (3 marks)

3
2 The following table shows the times taken, in minutes, by five people, Ash, Bob, Col, Dan
and Emma, to carry out the tasks 1, 2, 3 and 4. Dan cannot do task 3.
Ash Bob Col Dan Emma

Task 1 14 10 12 12 14
Task 2 11 13 10 12 12
Task 3 13 11 12 ** 12
Task 4 13 10 12 13 15
Each of the four tasks is to be given to a different one of the five people so that the overall
time for the four tasks is minimised.
(a) Modify the table of values by adding an extra row of non-zero values so that the
Hungarian algorithm can be applied. (1 mark)
(b) Use the Hungarian algorithm, reducing columns first then rows, to decide which four
people should be allocated to which task. State the minimum total time for the
four tasks using this matching. (8 marks)
(c) After special training, Dan is able to complete task 3 in 12 minutes. Determine, giving
a reason, whether the minimum total time found in part (b) could be improved.
(2 marks)
3 Two people, Rob and Con, play a zero-sum game.
The game is represented by the following pay-off matrix for Rob.
Con
Strategy C1 C2 C3
R1 2 5 3
Rob R2 3 3 1
R3 3 3 2
(a) Explain what is meant by the term ‘zero-sum game’. (1 mark)
(b) Show that this game has no stable solution. (3 marks)
(c) Explain why Rob should never play strategy R3. (1 mark)
(d) (i) Find the optimal mixed strategy for Rob. (7 marks)
(ii) Find the value of the game. (1 mark)

s
Turn over
4
4 A linear programming problem involving the variables x, y and z is to be solved. The

objective function to be maximised is P ¼ 2x þ 3y þ 5z . The initial Simplex tableau is
given below.
P x y z s t u value
1 2 3 5 0 0 0 0
0 1 0 1 1 0 0 9
0 2 1 4 0 1 0 40
0 4 2 3 0 0 1 33
(a) In addition to x 5 0 , y 5 0 , z 5 0 , write down three inequalities involving x, y and z

for this problem. (2 marks)
(b) (i) By choosing the first pivot from the z-column, perform one iteration of the
Simplex method. (4 marks)
(ii) Explain how you know that the optimal value has not been reached. (1 mark)
(c) (i) Perform one further iteration. (4 marks)
(ii) Interpret the final tableau and state the values of the slack variables. (3 marks)

5
5 [Figure 3, printed on the insert, is provided for use in this question.]
The following network shows 11 vertices. The number on each edge is the cost of travelling
between the corresponding vertices. A negative number indicates a reduction by the amount
shown.
C 4 H
2 2
A 5 F 5
2 4
1 1 2
D T
S 1 6
5 2
5
5 I
B 3 G
3
Stage 5 Stage 4 Stage 3 Stage 2 Stage 1 Stage 0
(a) Working backwards from T, use dynamic programming to find the minimum cost of
travelling from S to T. You may wish to complete the table on Figure 3 as your
solution. (6 marks)
(b) State the minimum cost and the routes corresponding to this minimum cost. (3 marks)
Turn over for the next question

s
Turn over
6
6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]
Water has to be transferred from two mountain lakes P and Q to three urban reservoirs U,
V and W . There are pumping stations at X , Y and Z.
The possible routes with the capacities along each edge, in millions of litres per hour, are
shown in the following diagram.
Cut C
U
5
P 15 Y
7 7
4
V
X
7 17 12
Q 8 Z
14
W
(a) On Figure 4, add a super-source, S, and a super-sink, T, and appropriate edges so as to

produce a directed network with a single source and a single sink. Indicate the capacity
of each of the edges you have added. (2 marks)
(b) (i) Find the value of the cut C. (1 mark)
(ii) State what can be deduced about the maximum flow from S to T. (1 mark)
(c) On Figure 5, write down the maximum flows along the routes SQZWT and SPYXZVT.
(2 marks)
(d) (i) On Figure 6, add the vertices S and T and the edges connecting S and T to the
network. Using the maximum flows along the routes SQZWT and SPYXZVT
found in part (c) as the initial flow, indicate the potential increases and decreases
of flow on each edge. (2 marks)
(ii) Use flow augmentation to find the maximum flow from S to T. You should
indicate any flow augmenting paths on Figure 5 and modify the potential
increases and decreases of the flow on Figure 6. (4 marks)
(e) State the value of the flow from Y to X in millions of litres per hour when the
maximum flow is achieved. (1 mark)
END OF QUESTIONS

Figure 1 (for use in Question 1)
B D
8 8
A E
3 10
Duration C F
7 3
2
Earliest start Latest finish

time time

~
10 –
9 –
8 –
7 –
6 –
Number
5 –
of
workers 4 –
3 –

2 –
1 –
~
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Time (days)
3
Stage State From Value

1 H T 5
I T 6
2 F H 2 þ 5 ¼ 3
T 4
I
G I
3 C H
F
G
Turn over
4

U
5
P 15 Y
7 7
4
V
X
7 17 12
Q 8 Z
14
W
Route Flow
SQZWT
SPYXZVT

U
P Y
V
X
Q Z
W

A2 Module 4737 Decision Mathematics 2 Sample Pages

Uploaded by

Copyright:

Available Formats

A2 Module 4737 Decision Mathematics 2 Sample Pages

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

A2 Module 4737 Decision Mathematics 2 Sample Pages

Uploaded by

Copyright:

Available Formats

http://www.mppe.org.

Duplicating, selling, or otherwise distributing this product is

No parts of this book may be reproduced, stored in a retrieval

Copyright © mppe.org.uk and its license. All Rights Reserved

Answer all questions.

Ali Bo Chas Dee Eve

Profit (in units of £1000)

A building project is to be undertaken. The table shows the activities involved.

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

5 (a) Display the following linear programming problem in a Simplex tableau.

(c) (i) Perform one further iteration. (5 marks)

Copyright © mppe.org.uk and its license. All Rights Reserved

Earliest start Latest finish

Figure 2 (for use in part (f))

Copyright © mppe.org.uk and its license. All Rights Reserved

For use in Question 4

Figure 3 (for use in part (a))

Figure 4 (for use in part (b)(i))

Figure 5 (for use in part (b)(ii))

Copyright © mppe.org.uk and its license. All Rights Reserved

1. Explain what is meant, in a network, by

London (L) Edinburgh (E) Supply

It is decided to use the transportation algorithm to obtain a minimal cost solution.

(a) Explain why it is necessary to add a dummy demand point.

(b) Complete table 1 in the answer booklet.

(e) State the cost of your optimal solution.

Copyright © mppe.org.uk and its license. All Rights Reserved

Mark plays 1 Mark plays 2 Mark plays 3

(b) Verify that there is no stable solution to this game.

Copyright © mppe.org.uk and its license. All Rights Reserved

TOTAL FOR PAPER: 75 MARKS

Copyright © mppe.org.uk and its license. All Rights Reserved

Answer book for Practice 2

Copyright © mppe.org.uk and its license. All Rights Reserved

(d) You may not need to use all of these tables

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Stage State Action Destination Value

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Copyright © mppe.org.uk and its license. All Rights Reserved

Answer all questions.

1 [Figure 1, printed on the insert, is provided for use in this question.]

A building project is to be undertaken. The table shows the activities involved.

Activity Immediate Duration

(a) Complete an activity network for the project on Figure 1. (3 marks)

Copyright © mppe.org.uk and its license. All Rights Reserved

Job 1 Job 2 Job 3 Job 4 Job 5

3 (a) Display the following linear programming problem in a Simplex tableau.

(i) Explain why the initial pivot is 4. (1 mark)

(i) Show that this game has a stable solution. (3 marks)