What is computer
simulation?
Thie condition to be able to use a computer simulation model is that the
behavior of the individual parts of the system and the relationship between
these parts can be described logically. We must not confuse this with the
mathematical description of the system as a whole. In this case, we'd be
speaking of an analytical solution.
The most important part of a computer simulator is the "dice", i.e. the random
generator. The random generator is capable of generating chance numbers, thus
giving a realistic representation of the stochastic character of the system
(before the computer age, tables were often used in order to dispose of chance
numbers). However, a computer is absolutely predictable and it is thus
impossible to just generate chance numbers with a computer. So, we also speak of
a "pseudo random number" generator.
A good random generator, generates numbers within a certain interval (for
example 0 and 1), whereby each position within the interval has an equal chance
to be chosen (uniformly distributed) and whereby the result of each individual
draw is independent of the previous one.
Building a good random generator for a computer is a science in itsself. In
general you may assume that random generators in simulation packages and
simulation languages are suitable for their purpose. However, you can not always
say that random generators are good. There are differences in quality. That is
why we will now discuss the most important problems when generating a chance
number.
We have already mentioned that "draws" must be uniform and independent.
Besides this, we wish to be able to reproduce a batch of random numbers (a
random number stream). This can be useful in simulations where you want to
compare two alternatives whereby only one part of the system shows a different
behavior. This is solved by generating a batch of random numbers on the basis of
a starting value (random seed number).
The seed number is used in a formula. From this formula comes the first
draw. This number is again used in the formula and the second draw results,
etc.
The fact that a draw is based on a process of the previous draw, means, per
definition, that the numbers are independent. However, the challenge is that we
apply a process in such a way that it seems as if there is no statistical
dependence between the draws.
A second problem is that at a certain moment, each random generator starts
repeating the same batch of numbers. The trick is to make sure that the length
of this cycle is a long as possible.
Suppose we have the following generator to simulate a dice (numbers between
0 and 5 instead of 1 and 6):
Zn = (Zn-1+1) mod 6
With starting value Z0=3 we obtain the following batch (Z1, Z2,
Z3,...):
4,5,0,1,2,3,4,5,0,1,2,3,4,...
It is obvious that this batch is not independent and even repeats itself
after 6 draws.
We adapt the generator:
Zn = (A*Zn-1+B)
mod C
With starting value Z0=3, A=2, B=1 and C=6 we obtain (Z1, Z2,
Z3,...):
1,3,1,3,1,3,1,3,1,3,...
The draws may seem more independent but, the cycle length of 2 is rather
disappointing. It now appears that the choice of A and B and C can increase the
quality of the generator. There are criteria for the choice of these parameters
whereby prime numbers play a role. Most random generators in computers are based
on this type of process. We call them LCGs (linear congruential
generators).
Zn =
(515*Zn-1+1) mod 235 (Law and
Kelton)
Besides the random generators, the simulation algorithms used are also of
importance. Continuous simulations are mostly based on the solving of
differential equations of the first or higher order. Discrete simulations, the
subject of this book, either use the "time slicing" or the "next event"
technique.
Time slicing means that time passes in constant steps. At each point of
time, one checks if an event takes place. If this is the case, the state of the
system is adapted. A disadvantage of this method is that it is often slow,
because the times at which a systems doesn't change are also evaluated. The next
event technique does not have this disadvantage. The clock jumps from event to
event.
Next event versus time slicing
____________________________________________________________________________________________
The next event technique makes use of the fact that, in discrete processes,
the state of the system changes eratically. If a product is processed at time
10, and the process takes 7.3 seconds, then we know the process will be finished
at time 17.3. The next event simulator will determine at time 10 that the next
event will take place at time 17.3 and (assuming that no events occur before
that time) the clock will then jump from 10 to 17.3.
With the time slicing technique, time will pass according to fixed
intervals and the simulation algorithm will continually ask: process
ready?
For example: t=11: ready? No. t=12: ready? No. t=17: ready? No. t=18:
ready? Yes. We not only see that this takes more calculation, but we also see
that the size of the time steps determines the accuracy of the simulation. If we
had wanted to simulate the processing time more accurately, than we should have
taken steps of 0.1 seconds: i.e. even more calculating to cover the period of
7.3 seconds. The advantage of the time slicing technique is that it is easier to
program.
____________________________________________________________________________________________
Simulation algorithms in practice are a lot more complicated than the
example discussed above. Literature on simulation used to spend a lot of time on
the precise functioning of simulation algorithms, because it was assumed that
you had to program your own simulation models.
The current tools for computer simulation contain built-in simulation
algorithms, random generators, etc. so that the one who simulates (from now on
we will use the ugly word "simulater") can concentrate on the building of the
actual model. In the following paragraphs we will discuss the different tools
for computer simulation, differentiating between simulation languages and
simulation packages.
The random generator
____________________________________________________________________________________________
Q
Given 4 series of draws, each from a different random generator. Each
generator should produce numbers, uniform between 1 and 100.
Indicate for each series at which aspect the the generator seems to be
functioning badly.
1.
10,13,23,56,7,13,8,22,45,33,12,96,4,52,43,17
2.
3,7,23,48,63,93,14,32,52,78,83,2,27,31,67,98,4,17
3.
17,48,31,92,67,17,64,57,42,3,65,93,17,48,31,92,67,17,64,57
4.
12,44,96,72,48,88,32,36,84,64,8,56,28,76
A
1. Not uniform
(many low values, few high)
2. Not
independent (values keep mounting to 100)
3. Bad
reproducability (repeats itself)
4. Not aselect
(only draws multiples of 4)