INDUSTRIAL AND MANUFACTURING ENGINEERING

OPERATIONS RESEARCH WRITE UP

Title; Decision trees

Name Registration number

Zviuya Samantha F H170134P
Kumirayi Owen H70120F
Mathende Munashe H170359Q
Nyamapfeni Tinotenda H170132E
Muzawazi Edward H170129Y
Shamboko Shelton H150611Z
Chimhini Anesu H170117Y
Mucheka Hamlet H170125T
Mukodi Tafadzwa H170127T

LECTURER P. MUPFUMIRA

Decision trees
Decision trees provide a useful way of visually displaying the problem and then organizing
the computational work. These trees are especially helpful when a sequence of decisions must
be made.

Decision trees consist of:

i. Decision nodes

Represented by a square, it indicates that a decision needs to be made at that point in the
process

ii. Event node (or chance node),

Represented by a big circle, indicates that a random event occurs at that point
iii. Terminal nodes
Represented by a small circle; it indicates the ends of paths from left to right through the
decision tree.
Uses of decision trees in operations research
 Decision analysis
 To help identify a strategy most likely to reach a goal

Advantages of Decision trees

 Are simple to understand and interpret. People are able to understand decision tree
models after a brief explanation.
 Have value even with little hard data. Important insights can be generated based on
experts describing a situation (its alternatives, probabilities, and costs) and their
preferences for outcomes.
 Help determine worst, best and expected values for different scenarios.
 Use a white box model. If a given result is provided by a model.
 Can be combined with other decision techniques.

Disadvantages of decision trees

 They are unstable, meaning that a small change in the data can lead to a large change
in the structure of the optimal decision tree.
  They are often relatively inaccurate. Many other predictors perform better with
similar data. This can be remedied by replacing a single decision tree with a random
forest of decision trees, but a random forest is not as easy to interpret as a single
decision tree.
 For data including categorical variables with different number of levels, information
gain in decision trees is biased in favor of those attributes with more levels.
 Calculations can get very complex, particularly if many values are uncertain and/or if
many outcomes are linked

Example

A company faces a decision with respect to a product (codenamed M997) developed by one
of its research laboratories. It has to decide whether to proceed to test market M997 or
whether to drop it completely. It is estimated that test marketing will cost £100K. Past
experience indicates that only 30% of products are successful in test market.

If M997 is successful at the test market stage then the company faces a further decision
relating to the size of plant to set up to produce M997. A small plant will cost £150K to build
and produce 2000 units a year whilst a large plant will cost £250K to build but produce 4000
units a year.

The marketing department have estimated that there is a 40% chance that the competition will
respond with a similar product and that the price per unit sold (in £) will be as follows
(assuming all production sold):

Large plant Small plant

Competition respond 20 35
Competition do not respond 50 65

Assuming that the life of the market for M997 is estimated to be 7 years and that the yearly
plant running costs are £50K (both sizes of plant - to make the numbers easier!) should the
company go ahead and test market M997?

Solution
Although the above example is somewhat simplified it plainly represents the type of decision
that often has to be made about new products.

N.B; In particular note how we cannot separate the test market decision from any decisions
about the future profitability (if any) of the product if test marketing is successful.

Figure 1 solution decision tree

Decision nodes represent points at which the company has to make a choice of one
alternative from a number of possible alternatives e.g. at the first decision node the company
has to choose one of the two alternatives "drop M997" or "test market M997".

Chance nodes represent points at which chance, or probability, plays a dominant role and
reflect alternatives over which the company has (effectively) no control.

Terminal nodes represent the ends of paths from left to right through the decision tree.
It is worth saying here that the difficult part of the decision tree technique is drawing
up a diagram such as the figure above from the written description of the problem.
Once that has been done the solution procedure is quite straightforward. Note here that
most, but not all, decision trees start with a decision node. One tip that may help you to
draw decision trees is to ask yourself the question "What happens next?" at each point
in the tree as you draw it.

Note here the inclusion of the "no plant" alternative at the plant size decision node. This is
necessary because it simply may not be profitable to build any plant (large or small) even if
the product is successful in test market. It is common in decision tree problems to find that at
decision nodes we need a "do nothing" alternative which is an implicit decision that can be
taken.

Note that it is important for the decision tree to be drawn so that there is a unique path in the
tree from the initial node to each of the terminal nodes.

To ease the discussion of the decision tree we have numbered the nodes
(decision/chance/terminal) 1, 2, 3... 12. At each decision node we have also numbered the
alternatives, at node 1 we have alternatives 1 and 2 and at node 5 alternatives 3, 4 and 5.

Although the decision tree diagram does help us to see more clearly the nature of the problem
it has not, so far, helped us to decide whether to drop M997 or whether to test market it (the
decision we are trying to make!). To do this we have two steps as illustrated below.

In these steps we will need to use information (numbers) relating to future sales, prices,
costs, etc. Whilst we may not be able to give accurate figures for these we need to factor
such figures into our calculations if we are to proceed. Investigating how our decision to
test market or not might change as these figures change (i.e. sensitivity analysis) can be
done once we have carried out the basic calculations using our assumed figures.

Step 1
In this step we, for each path through the decision tree from the initial node to a terminal
node of a branch, work out the profit (in £) involved in that path. Essentially in this step we
work from the left-hand side of the diagram to the right-hand side.

 path to terminal node 2 - we drop M997

Total revenue = 0

Total cost = 0

Total profit = 0

Note that we ignore here (and below) any money already spent on developing M997
(that being a sunk cost, i.e. a cost that cannot be altered no matter what our future
decisions are, so logically has no part to play in deciding future decisions).

 path to terminal node 4 - we test market M997 (cost £100K) but then find it is not
successful so we drop it

Total revenue = 0

Total cost = 100

Total profit = -100 (all figures in £K)

 path to terminal node 7 - we test market M997 (cost £100K), find it is successful,
build a small plant (cost £150K) and find we are without competition (revenue for 7
years at 2000 units a year at £65 per unit = £910K)

Total revenue = 910

Total cost = 250 + 7x50 (running cost)

Total profit = 310

 path to terminal node 8 - we test market M997 (cost £100K), find it is successful,
build a small plant (cost £150K) and find we have competition (revenue for 7 years at
2000 units a year at £35 per unit = £490K)
Total revenue = 490

Total cost = 250 + 7x50

Total profit = -110

 path to terminal node 10 - we test market M997 (cost £100K), find it is successful,
build a large plant (cost £250K) and find we are without competition (revenue for 7
years at 4000 units a year at £50 per unit = £1400K)

Total revenue = 1400

Total cost = 350 + 7x50

Total profit = 700

 path to terminal node 11 - we test market M997 (cost £100K), find it is successful,
build a large plant (cost £250K) and find we have competition (revenue for 7 years at
4000 units a year at £20 per unit = £560K)

Total revenue = 560

Total cost = 350 + 7x50

Total profit = -140

 path to terminal node 12 - we test market M997 (cost £100K), find it is successful, but
decide not to build a plant

Total revenue = 0

Total cost = 100

Total profit = -100

Note that, as mentioned previously, we include this option because, even if the product is
successful in test market, we may not be able to make sufficient revenue from it to cover any
plant construction and running costs.
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)

2 0
4 -100
7 310
8 -110
10 700
11 -140
12 -100

So far we have not made use of the probabilities in the problem - this we do in the second
step where we work from the right-hand side of the diagram back to the left-hand side.

Step 2

Consider chance node 6 with branches to terminal nodes 7 and 8 emanating from it. The
branch to terminal node 7 occurs with probability 0.6 and total profit 310K whilst the branch
to terminal node 8 occurs with probability 0.4 and total profit -110K. Hence the expected
monetary value (EMV) of this chance node is given by

0.6 x (310) + 0.4 x (-110) = 142 (£K)

Essentially this figure represents the expected (or average) profit from this chance node (60%
of the time we get £310K and 40% of the time we get -£110K so on average we get (0.6 x
(310) + 0.4 x (-110)) = 142 (£K)).

The EMV for any chance node is defined by "sum over all branches, the probability of the
branch multiplied by the monetary (£) value of the branch". Hence the EMV for chance node
9 with branches to terminal nodes 10 and 11 emanating from it is given by

0.6 x (700) + 0.4 x (-140) = 364 (£K)

We can now picture the decision node relating to the size of plant to build as below where the
chance nodes have been replaced by their corresponding EMV's.

Hence at the plant decision node we have the three alternatives:

Alternative 3: build small plant EMV = 142K

Alternative 4: build large plant EMV = 364K

Alternative 5: build no plant EMV = -100K

It is clear that, in £ terms, alternative number 4 is the most attractive alternative and so we
can discard the other two alternatives, giving the revised decision tree shown below.
We can now repeat the process we carried out above.

The EMV for chance node 3 representing whether M997 is a success in test market or not is
given by

0.3 x (364) + 0.7 x (-100) = 39.2 (£K)

Plant decision node 4

Hence at the decision node representing whether to test market M997 or not we have the two
alternatives:

Alternative 1: drop M997 EMV = 0

Alternative 2: test market M997 EMV = 39.2K

It is clear that, in £ terms, alternative number 2 is preferable and so we should decide to test
market M997.

Summary

 Decision trees can be used to help predict the future

 The trees are easy to understand

  Decision trees work more efficiently with discrete attributes

 The trees may suffer from error propagation

References

http://people.brunel.ac.uk/~mastjjb/jeb/or/dectree.html

Hillier Frederik S, (2015), Introduction to Operations Research Tenth Edition, McGraw-Hill

Education, ISBN 978-0-07 35 23 45-3