Page 464 - Excel for Scientists and Engineers: Numerical Methods

APPENDIX 8 ANSWERS AND COMMENTS FOR PROBLEMS 44 1

Chapter 15 Random Numbers and Monte Carlo

1. The answer spreadsheet contains two examples. The first uses 32 points, and
is intended mainly to illustrate the method. Random number formulas are
used to generate a pair of x, y coordinates in columns A and B. The formula
in column C uses an IF statement to determine whether the point is inside the
circle; if inside, the formula returns the y coordinate, otherwise the cell is
blank.
The second example uses 4000 points and is used to create the chart. The
formula in column G returns the y coordinate if the point is inside the circle;
if not the cell returns #N/A. A cell containing #N/A is not plotted in a chart.
71; is the number of points within the circle divided by the total number of
points.

2. A random number is used to specify whether a child is male (>0.5) or female.
The simulation shown uses 100 mothers and a maximum of 10 children per
mother. The "series" is terminated when the first "F" is generated. (Very
occasionally 10 children is not sufficient to end the series.) It's fairly clear
from the results from 100 mothers that the proportion is 50:50, but a macro
button has been provided that sums the results of 100 recalculations.
When I first encountered this problem many years ago, I sat down and
derived an analytical expression for the result, but right now I can't reproduce
it.

3. Constructing a spreadsheet to simulate the traffic pattern is left to the reader.

4. The Traveling Salesman problem is usually formulated as follows: a
salesman must travel to a number of cities, visiting each one only once and
finally returning to the city of origin. The problem is to minimize the
distance traveled. It's obvious that this problem has many real-world
applications, so an algorithm for a general solution would be very useful.
But this seemingly simple problem is actually essentially impossible to solve
for all but the simplest of cases.
The straightforward approach would be to determine the distance between
each city and to calculate the total distance of all possible routes. Thus, for
example, if only five cities are to be considered, there are five cities at which
to begin; having chosen one of the five, there are four possible destinations,
etc. The total number of possible routes is 5! = 120. But as N, the number of
cities increases, N!, the number of possible routes, quickly increases to a
number so large as to be make the solution impossible even with today's
computers. Obviously, an approach that will simplify the problem is
required. One strategy is to always travel to the city that is closest (of the
ones not yet visited, of course). Strategies such as this may not provide the
perfect solution but may at least provide a useful one. This method is
illustrated on the sheet "Method 1 .It