Session 3
Simulation Basics
Learning Objectives
At the and of the session, the students are
expected to
1. Understand simulation basics
2. Conduct a simple simulation using
spreadsheet
Topics
Types of simulation
• Random behavior
• Simulating random behavior
• Generating random numbers
• Generating random variates
• Simple spreadsheet simulation
1. Introduction
concept
system
model
• Simulation is much more meaningful when we
understand what it is actually doing
• Understanding how simulation works help us
to know whether we are applying it correctly
and what the output results mean
2. Types of Simulation
• Static or dynamic
• Stochastic or deterministic
• Discrete or continuous
Static vs. Dynamic Simulation
Static Simulation: Dynamic simulation:
• A simulation that is • Includes the passage
NOT based on time of time
• involves drawing • A clock mechanism
random samples to moves forward in
generate a statistical time and state
outcome Monte variables are
Carlo simulation updated as time
• i.e.: select portfolio advances
of stocks and bonds • i.e. manufacturing
and service systems
Stochastic/Probabilistic vs.
Deterministic Simulation
Stochastic Deterministic
simulation:
simulation:
• Has no input
• One or more input
components that are
variables are
random
random
• Has no randomness
• Produces output
• All future states are
that is it self
determined once the
random
input data and initial
• Gives only one
state have been
data point on how defined
the system behave
Stochastic/Probabilistic vs. Deterministic
Simulation (cont.)
Constant Random Random
Constant
outputs inputs outputs
inputs
12.3
3.4 Simulation Simulation
106
5
(a) (b)
Examples of (a) a deterministic simulation and (b) a stochastic simulation
3. Random Behavior
• Stochastic system frequently have time or
quantity values that vary within a given
range and according to special density, as
defined by a probability distribution.
• Probability distributions are useful for
predicting the next time, distance,
quantity, and so forth when these values
are random variables.
• Probability distributions from which we
obtain random variates may be either
discrete or continuous. A discrete
distribution represents a finite or countable
number of possible values. A continuous
distribution represents a continuum of
Discrete vs. Continuous Distribution
Discrete vs. Continuous Distribution
Discrete Continuous
• A finite or countable • A continuum of values
number of possible • i.e. a machine with a
values cycle time that is
• i.e. number of items uniformly distributed
in a lot, individuals between 1.2 – 1.8
in a group of people minutes
4. Simulating Random Behavior
How to Generate Random Numbers
• Random behavior is imitated in simulation by
using a random number generator
• the numbers produced by a random number
generator are not “random” in the “truest”
sense. i.e. pseudo random number
generator, which can produce the same
sequence of numbers again and again.
How to Generate Random Numbers
The uniform(0,1) distribution of a random number generator
Linear Congruential Generators
(LCG)
Methods:
A sequence of integers Z1, Z2, Z3, … is defined
by the recursive formula:
Zi = (aZi-1 + c) mod (m)
a : multiplier
c : increment
m: modulus
LCG: Example
a=21, c=3, m=16 to generate pseudo-random
numbers
Zi= (aZi-1 + c) mod(m) Zi= (21Zi-1 + 3) mod (16)
Z0 = 13 (arbitrarily selected between 0 and 15 (m-
1)) seed value, starting value
Z1 = (21Z0 + 3) mod (16) = (21(13)+3) mod (16)
= 276 mod (16) = 4
Ui = Zi/16 = 4/16 = 0.2500
Table 1 Example LCG
Zi = (21Zi-1 + 3) mod(16)
i 21Zi-1+3 Zi Ui=Zi/16
0 13
1 276 4 0,25
2 87 7 0,4375
3 150 6 0,375
4 129 1 0,0625
5 24 8 0,5
6 171 11 0,6875
7 234 10 0,625
8 213 5 0,3125
9 108 12 0,75
10 255 15 0,9375
11 318 14 0,875
12 297 9 0,5625
13 192 0 0
14 3 3 0,1875
15 66 2 0,125
16 45 13 0,8125
17 276 4 0,25
18 87 7 0,4375
19 150 6 0,375
20 129 1 0,0625
LCG: example (cont)
We will execute five replications of a simulation.
To run that simulation model for one replication
requires that the random number generator be
called 1,000 times during the simulation.
We would need a random number generator
with a cycle length of at least 5,000
LCG (cont)
A guideline to select a, c and m to
realize the maximum cycle length :
• m = 2b, where b is determined based
on the number of bits per word on the
computer being used. Many
computers use 32 bits per word,
making 31 a good choice for b
• c and m such that the greatest
common factor is 1 (the only positive
integer that exactly divides both m
and c is 1)
• a = 1 + 4k, where k is an integer
LCG (cont.)
• The maximum cycle length that an LCG
can achieve is m
• LCG can achieve a full cycle length of
over 2.1 billion (231) random numbers
• ProModel uses the following
multiplicative generator
Zi = (630,360,012 Zi-1 ) mod (231 – 1)
Here : a = 630,360,012
c=0
m = 231 – 1 = 2,147,483,647
Example
Simulating “random” events in a drive-
through restaurant
• the arrival time of cars to a
restaurant’s drive-through window
• The time takes the driver to place an
order
• The number of hamburgers, drinks,
and fries ordered
• The time it takes the restaurant to
prepare the order
Testing Random Number Generators
The numbers produced by the random
number generators must be
(1) independent and
(2) uniformly distributed between zero
and one (uniform (0,1)).
Stream
• The long sequence of random
numbers is subdivided into
smaller segments, as
streams.
• i.e.: stream 1: arrival pattern
of cars to a restaurant’s
drive-through window, stream
2: time required for the driver
of the car to place and order
LCG: how to implement
• Decide how many random number
to place in each stream
• Subdivide the generator’s sequence
of random number into streams
• Generate the entire sequence of
random numbers (cycle length)
• Recording the Zi values that mark
the beginning of each stream
• Each stream has its own starting
value or seed value
LCG (cont)
Two types of LCG:
• Mixed congruential generators: c>0
• Multiplicative congruential generators c=0
• More efficient than the mixed generator no
require the addition of c
Promodel uses the multiplicative generator
Zi= (630,360,016Zi-1) mod(231-1)
How to generate random variates
How to generate observations (random
variates) from probability distribution other
than the uniform (0,1) distribution?
Transforming the observations generated by
the random number generator to the desired
distribution
Transformed value variates from the
specified distribution
How to generate random variates
(cont.)
Types of method for generating random
variates from a desired distribution:
• Inverse transformation method
• The acceptance/rejection method
• The composition method
• The convolution method
• Methods employing special properties
Generating Random Variates
(Using inverse transformation)
1. Given a probability density
function f(x).
2. Find the cumulative distribution
function of X, that is F(x) = P(X
≤ x).
3. Set U = F(x), where U is
uniform(0,1).
4. Solving for x = F-1(U)
Continuous Distributions (an example:
exponential distribution with mean )
F(x)
1.00 U=1 - exp(-x/beta)
1 x/
e for x 0
f ( x) U2
0 elsewhere
1 e x / for x 0
F ( x)
0 elsewhere 0.50
U 1 e x / U1
x ln(1 U )
x1 x2
Graphical explanation of inverse transformation method for continuous variates
How to generate random variates
(cont.)
Discrete distribution:
• Basically the same as for the continuous
case
• Example : a simulation to represent the
number of defective components on a
circuit board, number of drinks ordered
from a drive-through window
How to generate random variates (cont.)
Discrete distribution:
5. Simple Spreadsheet
Simulation
An example: Dynamic, stochastic simulation
model arrive to use an automatic teller machine (ATM)
Customers
at a mean inter-arrival time of 3.0 minutes exponentially
distributed. When customers arrive to the system they join
a queue to wait for their turn on the ATM. The queue has
the capacity to hold an infinity number of customers.
Customers spend an average of 2.4 minutes exponentially
distributed at the ATM to complete their transactions,
which is called the service time at the ATM.
• Simulate the system for the arrival and processing of 25
customers and
• estimate the expected waiting time for customers in the
queue (the average time customers wait in line for the
ATM) and
• the expected time in the system (the average time
customers wait in the queue plus the average time it
takes them to complete their transaction at the ATM).
An example:
Dynamic, stochastic simulation
model
• System: ATM
• Entities: customers that arrive to the
ATM for processing
• Resource: ATM that serves the
customers with the capacity to serve
one customer at a time
• The system controls that dictate how,
when and were activities are
performed for this ATM system
Arriving customers ATM queue ATM server Departing
(entities) (FIFO) (resource) customers
(entities)
8 7 6 5 4 3 2 1
Interarrival
time 4.8
minutes
7th customer 6th customer
arrives at arrives at
21.0 min. 16.2 min.
Figure: Descriptive drawing of the ATM system
Simulating Random Variates
The transformation equation is:
Where
X ln(1 U )
i i
Xi = the i th value from the exponential
distribution with mean ,
Ui = the ith random drawn from a
uniform(0,1) distribution
i = 1,2,…,25
Ui will be produced by the equation:
Z1i (21Z1i 1 3) mod(128)
U 1i Z12 / 128 i 1,2,...,25
Z10 3
X 1i 3.0 ln(1 U 1i )
Z 2 i (21Z 2 i 1 3) mod(128)
U 2 i Z 2 2 / 128 i 1,2,...,25
Z 2 0 122
X 2 i 2.4 ln(1 U 2 i )
Tabel. Summary of ATM System Simulation
Output Average Time in Queu Average Time in System
Replication
1 1.94 minutes 4.26 minutes
2 0.84 minutes 2.36 minutes
Average 1.39 minutes 3.31 minutes
Replication Z10 Z20
1 3 122
2 29 92
• Changing the seed values Z10 and Z20
causes the spreadsheet program to
recompute all values in the spreadsheet.
• When we change the seed values Z10
and Z20 appropriately, we produce
another replication of the simulation.
• The heart of simulation is the generation
of the random variates that drive the
stochastic events in the simulation.
Summary
Modeling random behavior:
• Transforming the output produced by a
random number generator into observation
(random variates) from an appropriate
statistical distribution
• Combining with logical operators in a
computer program to compute output that
mimics the performance behavior of
stochastic system
• Performance estimates for stochastic
simulations are obtained by calculating the
average value of the performance metric
across several replications of the simulation
• Models can realistically simulate a variety of
Review Questions
1. What is the difference between a stochastic
and a deterministic model in terms of the
input variables and the way results are
interpreted?
2. Give a statistical description of the
numbers produced by a random number
generator.
3. What are the two statistical properties that
random numbers must satisfy?
4. Given two LCG:
Zi = (9Zi-1 + 3) mod(32)
Zi = (12Zi-1 + 5) mod(32)
a. Which LCG will achieve its maximum
length? Answers the question without
computing.
b. Compute Z1 through Z5 from a seed of 29
(Z0 = 29).
5. What is a random variate, and how are
7. Apply the inverse transformation method to
generate three variates from the following
distributions using U1 = 0.10, U2 = 0.53, and U3 =
0.15. 1
for x x
for x 1,2,3,4,5
(a ) f ( x) (b) p ( x) P ( X x) 5
0 elsewhere 0 elsewhere
where 7 and 4.
8. Reproduce the spreadsheet simulation
of the ATM system presented in this
week lecture. Set the random numbers
seeds Z10=29 and Z20=92 to compute
the average time customers spend in
the queue and in the system.
a. verify that the average time
customers waiting in the queue and in
the system match the values given for
the second replication in Table 3.3.
b. Verify that resulting random number
stream 1 and stream 2 are completely
different than the corresponding stream
in table 3.2. Is this a requirement for a
new replication of the simulation?
9. Refer to problem 8 above, replace the
interarrival time with mean 3.0 minutes
uniformly distributed by setting uniform
distribution’s minimum value to 1.0
minute and the maximum value to 5.0
minutes. How did the change influence the
average time in queue and the average
time in system compared to the second
replication results shown in Table 3.3 (3rd
edition), which are based on the
exponentially distributed interarrival time
with mean 3.0 minutes
