Transcript No Slide Title

Simulation
Simulation involves using a computer to imitate
(simulate) the operation of an entire process or
system.
For example, simulation is frequently used to
perform risk analysis on financial processes.
Simulation also is widely used to analyze
stochastic systems that will continue operating
indefinitely.
Simulation model
To prepare for simulating a complex system, a
detailed simulation model needs to be formulated
to describe the operation of the system and how it
is to be simulated.
A simulation model has several basic building
blocks:
1. A definition of the state of the system (e.g., the
number of customers in a queueing system).
2. Identify the possible states of the system that
can occur.
3. Identify the possible events (e.g., arrivals and
service completions in a queueing system) that
would change the state of the system.
4. A provision for a simulation clock, located at
some address in the simulation program, that will
record the passage of (simulated) time.
5. A method for randomly generating the
events of the various kinds.
6. A formula for identifying state transitions that
are generated by the various kinds of events.
Discrete – Event versus Continuous Simulation
A discrete-event simulation is one where changes
in the state of the system occur instantaneously at
random points in time as a result of the occurrence
of discrete events.
A continuous simulation is one where changes in
the state of the system occur continuously over
time.
Generation of Random Numbers
Implementing simulation sometimes requires
random numbers to obtain random observations
from probability distributions.
The procedure used by a computer to obtain random
numbers is called a random number generator.
A random number generator is an algorithm that
produces of numbers that follow a specified
probability distribution and possess the appearance
of randomness.
Random numbers can be divided into two main
categories.
(1) random integer number:
A random observation from a discretized uniform
distribution over some range n, n  1,, n.
The probabilities for this distribution are
1
P(n)  P(n  1)    P(n ) 
.
n  n 1
Usually, n  0 or 1 .
(2) uniform random number:
A random observation from a (continuous) uniform
distribution over some interval [a, b].
The probability density function of this uniform
distribution is
 1

f ( x)   b  a

0
if a  x  b
otherwise.
When a and b are not specified, they are assumed
to be a = 0 and b = 1.
For a given random integer number in the
range 0 to n , dividing this number by
yields (approximately) a uniform random
number.
(If n is small, this approximation should be
1
improved by adding to the random integer
2
number and then dividing by n  1 instead.)
Strictly speaking, the numbers generated by the
computer should not be called random numbers
because they are predictable and reproducible,
given the random number generator being used.
Therefore, they are sometimes given the name
pseudo - random numbers.
However, the important point is that they
satisfactory play the role of random numbers in
the simulation if the method used to generate
them is valid.
Congruential Method for Random Number
Generation
Mixed congruential method:
The mixed congruential method generates a
sequence of random integer numbers over the range
from 0 to m-1.
The method always calculates the next random
number from the last one obtained, given an initial
random number x0 .
xn1  (axn  c)(modulo m),
where a, c, and m are positive integers(a  m, c  m).
Illustration of the mixed congruential method
where m  8, a  5, c  7, x0  4.
N
0
1
2
3
4
5
6
7
xn
4
3
6
5
0
7
2
1
5 xn  7 (5xn  7) / 8
27
3  38
22
2  68
37
4  58
32
4  08
7
0  78
42
5  28
17
2  18
12
1  48
The cycle length is 8.
xn 1
3
6
5
0
7
2
1
4
Outline of a Major Simulation Study
Step 1: Formulate the Problem and Plan the Study
Step 2: Collect the Data and
Formulate the Simulation Model
Step 3: Check the Accuracy of the Simulation Model
Step 4: Select the Software and
Construct a Computer Program
Step 5: Test the Validity of the Simulation Model
Step 6: Plan the Simulations to Be Performed
Step 7: Conduct the Simulation Runs and
Analyze the Results
Step 8: Present Recommendations to Management
Step 1: Formulate the Problem & Plan the Study
1. What is the problem that management wants
studied?
2. What are the overall objectives for the study?
3. What specific issues should be addressed?
4. What kinds of alternative system configurations
should be considered?
5. What measures of performance of the system are
of interest to management?
6. What are the time constraints for performing
the study?
Step 2: Collect the Data and
Formulate the Simulation Model
The types of data needed depend on the nature of
the system to be simulated.
In each cases, the probability distributions of the
relevant quantities are needed.
In order to generate representative scenarios of how
a system would perform, it is essential that a
simulation generate random observations from
these distributions rather than simply using
averages.
Step 3: Check the Accuracy of the Simulation
Model
Before constructing a computer program, the OR
team should engage the people most intimately
familiar with how the system will operate in
checking the accuracy of the simulation model.
Then several erroneous model assumptions will be
discovered and corrected, a few new assumptions
will be added.
Step 4: Select the Software and
Construct a Computer Program
There are four major classes of software used for
computer simulations.
(1) spreadsheet software, e.g., Excel
for more extensive applications
(2) general-purpose programming languages,
e.g. C, FORTRAN, PASCAL, BASIC
(3) general-purpose simulation languages
(4) applications-oriented simulators
Another key development in recent years
the development of animation capabilities for
displaying computer simulations in action,
including three-dimensional capabilities.
Key elements of a system are represented in a
computer display by icons that change shape,
color, or position when there is a change in the
state of the simulation capabilities.
Step 5: Test the Validity of the Simulation Model
The next step is to test whether the simulation
model incorporated into the program is providing
valid results for the system it is representing.
Typically, the purpose of simulation is to
investigate and compare various proposed system
configurations to help choose the best one.
Step 6: Plan the Simulations to Be Performed
At this point, you need to begin making
decisions on which system configurations to
simulate.
This often is an evolutionary process, where the
initial results for a range of configurations help
you to hone in on which specific configurations
warrant detailed investigation.
Step 7: Conduct the Simulation Runs and
Analyze the Results
The output from the simulation runs now provides
statistical estimates of the desired measures of
performance for each system configuration of
interest.
In addition to a point estimate of each measure, a
confidence interval normally should be obtained
to indicate the range of likely values of the
measure.
Step 8: Present Recommendations
to Management
After completing its analysis, the OR team
needs to present its recommendations to
management.
This usually would be done through both a
written report and a formal oral presentation to
the managers responsible for making the
decisions regarding the system under study.