OR-Notes

J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.


Decision trees examples

Decision tree example 1995 UG exam

Your company is considering whether it should tender for two contracts (MS1 and MS2) on offer from a government department for the supply of certain components. The company has three options:

If tenders are to be submitted the company will incur additional costs. These costs will have to be entirely recouped from the contract price. The risk, of course, is that if a tender is unsuccessful the company will have made a loss.

The cost of tendering for contract MS1 only is £50,000. The component supply cost if the tender is successful would be £18,000.

The cost of tendering for contract MS2 only is £14,000. The component supply cost if the tender is successful would be £12,000.

The cost of tendering for both contract MS1 and contract MS2 is £55,000. The component supply cost if the tender is successful would be £24,000.

For each contract, possible tender prices have been determined. In addition, subjective assessments have been made of the probability of getting the contract with a particular tender price as shown below. Note here that the company can only submit one tender and cannot, for example, submit two tenders (at different prices) for the same contract.

Option        Possible     Probability
              tender       of getting
              prices (£)   contract
MS1 only      130,000      0.20
              115,000      0.85
MS2 only      70,000       0.15
              65,000       0.80
              60,000       0.95
MS1 and MS2   190,000      0.05
              140,000      0.65

In the event that the company tenders for both MS1 and MS2 it will either win both contracts (at the price shown above) or no contract at all.


Solution

The decision tree for the problem is shown below.

Below we carry out step 1 of the decision tree solution procedure which (for this example) involves working out the total profit for each of the paths from the initial node to the terminal node (all figures in £'000).

Step 1

Hence we can arrive at the table below indicating for each branch the total profit involved in that branch from the initial node to the terminal node.

Terminal node    Total profit £'000
12               62
13               -50
14               47
15               -50
16               44
17               -14
18               39
19               -14
20               34
21               -14
22               111
23               -55
24               61
25               -55

We can now carry out the second step of the decision tree solution procedure where we work from the right-hand side of the diagram back to the left-hand side.

Step 2

Hence the best decision at decision node 2 is to tender at a price of 115 (EMV=32.45).

Hence the best decision at decision node 3 is to tender at a price of 60 (EMV=31.6).

Hence the best decision at decision node 4 is to tender at a price of 140 (EMV=20.4).

Hence at decision node 1 have three alternatives:

Hence the best decision is to tender for MS1 only (at a price of 115) as it has the highest expected monetary value of 32.45 (£'000).

The downside is a loss of 50 and the upside is a profit of 47.

With regard to the consultants offer then, ignoring ethical considerations, we could of course, tender 60 for MS2 only without her help and if we were to do that we would have a 0.95 probability of having our tender accepted. Hence there are essentially three options:

On an EMV basis we would still support our original decision. Looking at the risks (probabilities) of loosing money, and considering tendering for MS2 only at 60, we would essentially be paying the consultant 20 to avoid a 0.05 chance of loosing 14, the downside of tendering unaided.

Paying 20 to guarantee not incurring a loss of 14 which will occur with a probability of 0.05 (one in twenty) does not seem like an awfully good investment and so we should reject her offer (or offer her a smaller sum of money in return for her guarantee!).


Decision tree example 1994 UG exam

The Metal Discovery Group (MDG) is a company set up to conduct geological explorations of parcels of land in order to ascertain whether significant metal deposits (worthy of further commercial exploitation) are present or not. Current MDG has an option to purchase outright a parcel of land for £3m.

If MDG purchases this parcel of land then it will conduct a geological exploration of the land. Past experience indicates that for the type of parcel of land under consideration geological explorations cost approximately £1m and yield significant metal deposits as follows:

Only one of these three metals is ever found (if at all), i.e. there is no chance of finding two or more of these metals and no chance of finding any other metal.

If manganese is found then the parcel of land can be sold for £30m, if gold is found then the parcel of land can be sold for £250m and if silver is found the parcel of land can be sold for £150m.

MDG can, if they wish, pay £750,000 for the right to conduct a three-day test exploration before deciding whether to purchase the parcel of land or not. Such three-day test explorations can only give a preliminary indication of whether significant metal deposits are present or not and past experience indicates that three-day test explorations cost £250,000 and indicate that significant metal deposits are present 50% of the time.

If the three-day test exploration indicates significant metal deposits then the chances of finding manganese, gold and silver increase to 3%, 2% and 1% respectively. If the three-day test exploration fails to indicate significant metal deposits then the chances of finding manganese, gold and silver decrease to 0.75%, 0.04% and 0.175% respectively.


Solution

The decision tree for the problem is shown below.

Below we carry out step 1 of the decision tree solution procedure which (for this example) involves working out the total profit for each of the paths from the initial node to the terminal node (all figures in £'000000).

Step 1

Hence we can arrive at the table below indicating for each branch the total profit involved in that branch from the initial node to the terminal node.

Terminal node Total profit £ 
8             0
9             26
10            246
11            146
12            -4
13            25
14            245
15            145
16            -5
17            -1
18            25
19            245
20            145
21            -5
22            -1

We can now carry out the second step of the decision tree solution procedure where we work from the right-hand side of the diagram back to the left-hand side.

Step 2

Consider chance node 7 with branches to terminal nodes 15-21 emanating from it. The expected monetary value for this chance node is given by

0.0075(25) + 0.0004(245) + 0.00175(145) + 0.99035(-5) = -4.4125

Hence the best decision at decision node 5 is to abandon (EMV=-1).

The EMV for chance node 6 is given by 0.03(25) + 0.02(245) + 0.01(145) + 0.94(-5) = 2.4

Hence the best decision at decision node 4 is to purchase (EMV=2.4).

The EMV for chance node 3 is given by 0.5(2.4) + 0.5(-1) = 0.7

The EMV for chance node 2 is given by 0.01(26) + 0.0005(246) + 0.002(146) + 0.9875(-4) = -3.275

Hence at decision node 1 have three alternatives:

Hence the best decision is the 3-day test as it has the highest expected monetary value of 0.7 (£m).

Sharing the costs and revenues on a 50:50 basis merely halves all the monetary figures in the above calculations and so the optimal EMV decision is exactly as before. However in a wider context by accepting to share costs and revenues the company is spreading its risk and from that point of view may well be a wise offer to accept.


Decision tree example 1993 UG exam

A company is trying to decide whether to bid for a certain contract or not. They estimate that merely preparing the bid will cost £10,000. If their company bid then they estimate that there is a 50% chance that their bid will be put on the "short-list", otherwise their bid will be rejected.
Once "short-listed" the company will have to supply further detailed information (entailing costs estimated at £5,000). After this stage their bid will either be accepted or rejected.

The company estimate that the labour and material costs associated with the contract are £127,000. They are considering three possible bid prices, namely £155,000, £170,000 and £190,000. They estimate that the probability of these bids being accepted (once they have been short-listed) is 0.90, 0.75 and 0.35 respectively.

What should the company do and what is the expected monetary value of your suggested course of action?

Solution

The decision tree for the problem is shown below.

Below we carry out step 1 of the decision tree solution procedure which (for this example) involves working out the total profit for each of the paths from the initial node to the terminal node (all figures in £'000).

Step 1

Total profit = 0

Total cost = 10 Total profit = -10

Total cost = 10 + 5 + 127 Total revenue = 155 Total profit = 13

Total cost = 10 + 5 Total profit = -15

Total cost = 10 + 5 + 127 Total revenue = 170 Total profit = 28

Total cost = 10 + 5 Total profit = -15

Total cost = 10 + 5 + 127 Total revenue = 190 Total profit = 48

Total cost = 10 + 5 Total profit = -15

Total cost = 10 + 5 Total profit = -15

Hence we can arrive at the table below indicating for each branch the total profit involved in that branch from the initial node to the terminal node.

Terminal node   Total profit £
   7                0 
   8                -10
   9                13
   10               -15
   11               28
   11              -15
   13               48
   14              -15 
   15              -15

We can now carry out the second step of the decision tree solution procedure where we work from the right-hand side of the diagram back to the left-hand side.

Step 2

Consider chance node 4 with branches to terminal nodes 9 and 10 emanating from it. The expected monetary value for this chance node is given by 0.90(13) + 0.10(-15) = 10.2

Similarly the EMV for chance node 5 is given by 0.75(28) + 0.25(-15) = 17.25

The EMV for chance node 6 is given by 0.35(48) + 0.65(-15) = 7.05

Hence at the bid price decision node we have the four alternatives

(1) bid £155K EMV = 10.2

(2) bid £170K EMV = 17.25

(3) bid £190K EMV = 7.05

(4) abandon the bidding EMV = -15

Hence the best alternative is to bid £170K leading to an EMV of 17.25

Hence at chance node 2 the EMV is given by 0.50(17.25) + 0.50(-10) = 3.625

Hence at the initial decision node we have the two alternatives

(1) prepare bid EMV = 3.625

(2) do nothing EMV = 0

Hence the best alternative is to prepare the bid leading to an EMV of £3625. In the event that the company is short-listed then (as discussed above) it should bid £170,000.


Decision tree example 1989 UG exam

A householder is currently considering insuring the contents of his house against theft for one year. He estimates that the contents of his house would cost him £20,000 to replace.

Local crime statistics indicate that there is a probability of 0.03 that his house will be broken into in the coming year. In that event his losses would be 10%, 20%, or 40% of the contents with probabilities 0.5, 0.35 and 0.15 respectively.

An insurance policy from company A costs £150 a year but guarantees to replace any losses due to theft.

An insurance policy from company B is cheaper at £100 a year but the householder has to pay the first £x of any loss himself. An insurance policy from company C is even cheaper at £75 a year but only replaces a fraction (y%) of any loss suffered.

Assume that there can be at most one theft a year.

Solution

The decision tree for the problem is shown below.

Below we carry out step 1 of the decision tree solution procedure which (for this example) involves working out the total profit for each of the paths from the initial node to the terminal node.

Step 1

Total profit = 0

Total cost = 0.1(20000) = 2000 Total profit = - 2000

Similarly for terminal nodes 11 and 12 total profit = -4000 and -8000 respectively.

Total cost = 150 Total profit = -150

Total revenue = 2000 Total cost = 2000 + 150 Total profit = -150

It is clear from this calculation that when the reimbursement equals the amount lost the total profit will always be just the cost of the insurance.

This will be the case for terminal nodes 15 and 16 respectively.

Continuing in a similar manner we can arrive at the table below indicating for each branch the total profit involved in that branch from the initial node to the terminal node.

Terminal node   Total profit £
9               0
10              -2000
11              -4000
12              -8000 
13              -150 
14              -150
15              -150 
16              -150
17              -100 
18              -100-x (x <= 2000) 
19              -100-x
20              -100-x 
21              -75 
22              -75-2000(1-y/100) 
23              -75-4000(1-y/100) 
24              -75-8000(1-y/100)

We can now carry out the second step of the decision tree solution procedure where we work from the right-hand side of the diagram back to the left-hand side.

Step 2

Consider chance node 5 with branches to terminal nodes 10, 11 and 12 emanating from it. The expected monetary value for this chance node is given by
0.5(-2000) + 0.35(-4000) + 0.15(-8000) = -3600

Hence the EMV for chance node 1 is given by 0.97(0) + 0.03(-3600) = -108

Similarly the EMV for chance node 2 is -150.

The EMV for chance node 3 is 0.97(-100) + 0.03[0.5(-100-x) + 0.35(-100-x) + 0.15(-100-x)]

= -97 + 0.03(-100-x) = -100 - 0.03x (x <= 2000) = -101.5 since x = 50

The EMV for chance node 4 is

0.97(-75) + 0.03[0.5(-75-2000(1-y/100)) + 0.35(-75-4000(1-y/100)) + 0.15(-75- 8000(1-y/100))]

= 0.97(-75) + 0.03[-75-(1-y/100)(3600)] = -75 + 1.08y - 108 = -183 + 1.08y

= -139.8 since y = 40
Hence at the initial decision node we have the four alternatives

  1. no policy EMV = -108
  2. company A policy EMV = -150
  3. company B policy EMV = -101.5
  4. company C policy EMV = -139.8

Hence the best alternative is the policy from company B leading to an EMV of - £101.5

We know that for x = 50 policy B is best so we already have that the minimum value of x <= 2000
and so the LP for the minimum value of x is given by

minimise   x
s.t.       -100 - 0.03x >= -108         i.e. EMV B >= EMV no policy 
           -100 - 0.03x >= -150              EMV B >= EMV A 
           -100 - 0.03x >= -183 + 1.08y      EMV B >= EMV C

i.e.
minimise   x
s.t.
           x <= 266.67
           x <= 1666.67 
           1.08y + 0.03x <= 83 
           x >= 0
           y >= 0 and y <= 100

If x = 2000 then EMV B becomes -100-0.03(2000) = -160 so if x becomes that high we would prefer no policy (EMV for chance node 1 = -108). Hence the maximum value of x must be <= 2000 so that the LP for deciding the maximum value of x is

maximise x
s.t. the same constraints as above


Decision tree example 1986 UG exam

A government committee is considering the economic benefits of a program of preventative flu vaccinations. If vaccinations are not introduced then the estimated cost to the government if flu strikes in the next year is £7m with probability 0.1, £10m with probability 0.3 and £15m with probability 0.6. It is estimated that such a program will cost £7m and that the probability of flu striking in the next year is 0.75.

One alternative open to the committee is to institute an "early-warning" monitoring scheme (costing £3m) which will enable it to detect an outbreak of flu early and hence institute a rush vaccination program (costing £10m because of the need to vaccinate quickly before the outbreak spreads).

Solution

The decision tree for the problem is shown below.

Below we carry out step 1 of the decision tree solution procedure which (for this example) involves working out the total profit for each of the paths from the initial node to the terminal nodes.

Step 1

Total revenue = 0

Total cost = 0

Total profit = 0

Total revenue = 0

Total cost = 7

Total profit = -7 (all figures in £m)

Total revenue = 0

Total cost = 7

Total profit = -7

The key here is to regard the £7m paid for the program as "insurance" which reimburses the government for whatever losses are suffered as a result of flu striking. Hence we have

Total revenue = 7 (reimbursement)

Total cost = 7 (cost of program) + 7 (loss due to flu striking)

Total profit = -7

It is clear from the above calculation that since (in this case) the reimbursement always exactly equals the amount lost the total profit will just be the cost of the "insurance" (-£7m).

The situation with the vaccination program is very similar to household insurance where a single payment guarantees replacement of any losses suffered. Whatever happens the effect of the insurance will be "as if" nothing had occurred. Under these circumstances the only expense (in effect) is the cost of the insurance.

Total profit = -7 terminal node 15

Total profit = -7 terminal node 16

Total revenue = 0

Total cost = 3

Total profit = -3

Total profit = -13 terminal node 18

Total profit = -13 terminal node 19

Total profit = -13 terminal node 20

Total profit = -10 terminal node 21

Total profit = -13 terminal node 22

Total profit = -18 terminal node 23

Hence we can form the table below indicating for each branch the total profit involved in that branch from the initial node to the terminal node.

Terminal node   Total profit (£m)
9               0
10              -7
11              -10
12              -15
13              -7
14              -7
15              -7
16              -7
17              -3
18             -13
19             -13
20             -13
21             -10
22             -13
23             -18

We can now carry out the second step of the decision tree solution procedure where we work from the right-hand side of the diagram back to the left-hand side.

Step 2

Consider chance node 2 (with branches to terminal nodes 10, 11 and 12 emanating from it). The expected monetary value (EMV) for this chance node is given by 0.1 x (-7) + 0.3 x (-10) + 0.6 x (-15) = -12.7

Hence the EMV for chance node 1 is given by 0.25 x (0) + 0.75 x (-12.7) = -9.525

Similarly the EMV for chance node 7 is given by 0.1 x (-7) + 0.3 x (-7) + 0.6 x (-7) = -7

which leads to an EMV for chance node 3 of 0.25 x (-7) + 0.75 x (-7) = -7

The EMV for chance node 8 is 0.1 x (-13) + 0.3 x (-13) + 0.6 x (-13) = -13
and the EMV for chance node 6 is 0.1 x (-10) + 0.3 x (-13) + 0.6 x (-18) = -15.7

Hence for decision node 5 we have the two alternatives:

(4) vaccinate EMV = -13

(5) no vaccination EMV = -15.7

Hence the best alternative here is to vaccinate (alternative 4) with an EMV of -13.

The EMV for chance node 4 is therefore 0.25 x (-3) + 0.75 x (-13) = -10.5

and at the initial decision node (node 0) we have the three alternatives:

(1) no program EMV = -9.525

(2) program EMV = -7

(3) early warning EMV = -10.5

Hence the best alternative is alternative 2, institute a program costing £7m, leading to an EMV of -£7m.

Note here that it is clear that the concept of the vaccination program being an insurance against all possible losses could have enabled us to have drawn a much simpler decision tree (e.g. chance node 3 could be transformed into a "terminal" node of cost -£7m and nodes 7,13,14,15 dropped altogether (similarly for nodes 8,18,19,20)). However, for clarity, we have presented the decision tree as given above.

With respect to the last part of the question mention discounting, alternative value for a chance node (other than EMV), changing the decision node ("choose highest EMV alternative") rule and utility and briefly discuss whether appropriate/inappropriate.


Decision tree example 1985 UG exam

Your company is considering whether it should tender for two contracts (C1 and C2) on offer from a government department for the supply of certain components. If tenders are submitted, the company will have to provide extra facilities, the cost of which will have to be entirely recouped from the contract revenue. The risk, of course, is that if the tenders are unsuccessful then the company will have to write off the cost of these facilities.

The extra facilities necessary to meet the requirements of contract C1 would cost £50,000. These facilities would, however, provide sufficient capacity for the requirements of contract C2 to be met also. In addition the production costs would be £18,000. The corresponding production costs for contract C2 would be £10,000.

If a tender is made for contract C2 only, then the necessary extra facilities can be provided at a cost of only £24,000. The production costs in this case would be £12,000.

It is estimated that the tender preparation costs would be £2,000 if tenders are made for contracts C1 or C2 only and £3,000 if a tender is made for both contracts C1 and C2.

For each contract, possible tender prices have been determined. In addition, subjective assessments have been made of the probability of getting the contract with a particular tender price as shown below. Note here that the company can only submit one tender and cannot, for example, submit two tenders (at different prices) for the same contract.

                               Possible    Probability
                               tender      of getting
                               prices (£)  contract
Tendering for C1 only          120,000     0.30
                               110,000     0.85
Tendering for C2 only           70,000     0.10
                                65,000     0.60
                                60,000     0.90
Tendering for both C1 and C2   190,000     0.05
                               140,000     0.65
                               100,000     0.95

In the event that the company tenders for both C1 and C2 it will either win both contracts (at the price shown above) or no contract at all.

Solution

The decision tree for the problem is shown below.

Below we carry out step 1 of the decision tree solution procedure which (for this example) involves calculating the total profit for each of the paths from the initial node to the terminal nodes.

Step 1

Total revenue = 120

Total cost = 50 + 18 + 2 = 70

Total profit = 50 (all figures in £K)

Total revenue = 0

Total cost = 50 + 2 = 52

Total profit = -52

Total revenue = 110

Total cost = 50 + 18 + 2 = 70

Total profit = 40

Total revenue = 0

Total cost = 50 + 2 = 52

Total profit = -52

Total revenue = 70

Total cost = 24 + 12 + 2 = 38

Total profit = 32

Total revenue = 0

Total cost = 24 + 2 = 26

Total profit = -26

Total revenue = 65

Total cost = 24 + 12 + 2 = 38

Total profit = 27

Total revenue = 0

Total cost = 24 + 2 = 26

Total profit = -26

Total revenue = 60

Total cost = 24 + 12 + 2 = 38

Total profit = 22

Total revenue = 0

Total cost = 24 + 2 = 26

Total profit = -26

Total revenue = 190

Total cost = 50 + 18 + 10 + 3 = 81

Total profit = 109

Total revenue = 0

Total cost = 50 + 3 = 53

Total profit = -53

Total revenue = 140

Total cost = 50 + 18 + 10 + 3 = 81

Total profit = 59

Total revenue = 0

Total cost = 50 + 3 = 53

Total profit = -53

Total revenue = 100

Total cost = 50 + 18 + 10 + 3 = 81

Total profit = 19

Total revenue = 0

Total cost = 50 + 3 = 53

Total profit = -53

Total revenue = 0

Total cost = 0

Total profit = 0

Hence we can form the table below indicating for each branch the total profit involved in that branch from the initial node to the terminal node.

Terminal node     Total profit (£K)
12                50
13                -52
14                40
15                -52
16                32
17                -26
18                27
19                -26
20                22
21                -26
22                109
23                -53
24                59
25               -53
26               19
27               -53
28               0

We can now carry out the second step of the decision tree solution procedure where we work from the right-hand side of the diagram back to the left-hand side.

Step 2

Consider chance node 1 (with branches to terminal nodes 12 and 13 emanating from it). The expected monetary value (EMV) for this chance node is given by 0.3 x (50) + 0.7 x (-52) = -21.4

Consider chance node 2, the EMV for this chance node is given by 0.85 x (40) + 0.15 x (-52) = 26.2

Then for the decision node relating to the price for C1 we have the two alternatives:

(5) price 120K EMV = -21.4

(6) price 110K EMV = 26.2

It is clear that, in £ terms, alternative 6 is the most attractive alternative and so we can discard the other alternative.

Continuing the process the EMV for chance node 3 is given by 0.10 x (32) + 0.9 x (-26) = -20.2

The EMV for chance node 4 is given by 0.60 x (27) + 0.40 x (-26) = 5.8

The EMV for chance node 5 is given by 0.90 x (22) + 0.10 x (-26) = 17.2

Hence for the decision node relating to the price for C2 we have the three alternatives:

(7) price 70K EMV = -20.2

(8) price 65K EMV = 5.8

(9) price 60K EMV = 17.2

It is clear that, in £ terms, alternative 9 is the most attractive alternative and so we can discard the other two alternatives.

Continuing the process the EMV for chance node 6 is given by 0.05 x (109) + 0.95 x (-53) = -44.9

The EMV for chance node 7 is given by 0.65 x (59) + 0.35 x (-53) = 19.8

The EMV for chance node 8 is given by 0.95 x (19) + 0.05 x (-53) = 15.4

Hence for the decision node relating to the price to charge for C1 and C2 we have the three alternatives:

(10) price 190K EMV = -44.9

(11) price 140K EMV = 19.8

(12) price 100K EMV = 15.4

It is clear that, in £ terms, alternative 11 is the most attractive alternative and so we can discard the other two alternatives.

Hence for the decision node relating to the tender decision we have the four alternatives:

(1) C1 only EMV = 26.2

(2) C2 only EMV = 17.2

(3) C1 and C2 EMV = 19.8

(4) no tender EMV = 0

It is clear that, in £ terms, alternative 1 is the most attractive alternative and so we can discard the other three alternatives.

Hence we recommend that the company tenders for contract C1 only, with a tender price of £110K because this alternative has the highest EMV of £26.2K.

If the company follows this recommendation the actual outcome will be one of the terminal nodes 14 or 15 (depending upon chance events) i.e. the outcome will be one of [40, -52]. Hence the downside is that the company may lose £52K (if their tender is unsuccessful).