Transcript S4P1 - Lyle School of Engineering

EMIS 7300
SYSTEMS ANALYSIS METHODS
FALL 2005
Dr. John Lipp
Copyright © 2005 Dr. John Lipp
Session 4 Outline
• Part 1: Monte Carlo Simulations.
• Part 2: Queuing Theory.
• Part 3: Linear Programming – Graphical Techniques.
• Part 4: Linear Programming – Computer Techniques.
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-2
Today’s Session Topics
• Part 1: Monte Carlo Simulations.
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-3
Monte Carlo Simulation
• The purpose of a Monte Carlo simulation is to generate
sample data for statistical analysis
– Carefully designed physical experiments.
– Table of random digits (Rand Corporation).
• Today, Monte Carlo simulation is often performed by
computers.
• Computers don’t really generate random numbers – they
generate pseudo random numbers using arithmetic algorithms.
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-4
Lehmer’s Algorithm – Minimum Standard Generator
• The core algorithm for random number generation produces
uniform random numbers on the interval 0 – 1, U(0,1).
• Lehmer developed the Multiplicative Congruential Generators
zn  a zn1  mod m
• The problem has been studied for a long time for good values
for a and m… the result is the following “good” algorithm:
zn
 75 zn1  mod 231  1
 16,807 zn1 mod 2,147,483,647
• The seed is turned into a uniform random number via
un  z n / m
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-5
Computer Code
double uniform(void)
{
static int z = 1; // Random seed
const int a = 16807;
const int m = 2147483647;
const int q = 1127773; // = m / a
const r = 2836; // = m mod a
temp1 = z / q;
temp2 = z % q; // = z mod q
z = a * temp1 – r * temp2;
z = (z > 0) ? z : z + m;
return z / m;
}
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-6
Non-Uniform Random Numbers
• Random numbers from other distributions are generated using
several methods.
– Method 1: Percentile Transformation.
– Method 2: Rejection Method.
– Method 3: Use known relationships between the variable
to be generated and either the standard normal N(0,1) or
uniform U(0,1) random variables.
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-7
Percentile Transformation
• Desire variable X to have a PDF fX(x) and CDF FX(x)
– Then X = F-1X(U) will have the desired distribution where
U is uniform random variable U(0,1).
• This works because U = FX(X) is uniformly distributed and all
CDFs are monotonic.
• Example: Generate an exponential random variable from a
uniform random variable:
FX ( X )  1  e X  U
 X 
EMIS 7300 Fall 2005
ln(1  U )

or 
Copyright  2005 Dr. John Lipp
ln(U )

S4P1-8
Table of Percentile Transforms
Distribution
CDF-1
Excel Built-in
Beta
BETAINV(RAND(), a, b)
Chi-square
CHIINV(RAND(), n)
Exponential
-LN(RAND()) / 
F
FINV(RAND(), n, m)
Gamma
GAMMAINV(RAND(), a, b)
Log-Normal
LOGINV(RAND(), m, s)
Normal
NORMINV(RAND(), m, s)
Rayleigh
SQRT(-a*LN(RAND()))
T
Weibull
EMIS 7300 Fall 2005
TINV(RAND(), n)
((-LN(RAND())) ^ (1/b)) / 
Copyright  2005 Dr. John Lipp
S4P1-9
Rejection Method
• The percentile transform requires a closed form (or closed
form numerical approximation) of the CDF.
• Start with two independent random variables
Y ~ FY(y)
U ~ U(0,1)
• To generate a random variable X with CDF FX(x)
– Find a,
 f X ( x) 
a  min 

x
 fY ( y ) 
– If
then assign X = Y.
EMIS 7300 Fall 2005
fY ( y )
U a
f X ( x)
Copyright  2005 Dr. John Lipp
S4P1-10
Box-Muller Transform
• Start with two independent uniform random variables
U ~ U(0,1)
V ~ U(0,1)
• Compute
X   2 ln U cos2V 
Y   2 ln U sin 2V 
• Then X and Y are mutually independent standard Normal
random variables N(0,1).
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-11
Monte Carlo Simulation Steps
• Determine the time characteristic to simulate
– Instantaneous (one shot)
– Fixed time increment
– Fixed event increment
• Determine important random variables and their distributions
– Plot sample data on probability paper.
– If no distribution fits, don’t hesitate to use a lookup table
based on the emperical CDF (discussed in text).
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-12
How many runs?
• The larger the number of trials in the simulation, the more
precise will be the final answer.
– Any estimate will have an associated error band.
– In practice, the allowable error is generally specified, and
this information is used to determine the required trials.
– The procedure is to use a priori knowledge and solve a
corresponding confidence interval for n, the number of
samples.
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-13
How many runs?
• Example: Monte Carlo simulation to determine the number of
successes.
– po is the initial gestimate of the population proportion
– Use po = 0.5 to obtain the most conservative number
– Pick a, the desired confidence level
 z1a 2 
n  po 1  po 

e


2
z-score
desired margin
of error
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-14
Simulation Pros
• Flexibility. Easy to ask “what-ifs?”
• Can find for the properties of very complex systems including
complicated details which do not yield well to quantitative,
closed-form solutions.
• No interference with the “real world.” Existing operations go
about their business while “what-ifs” are asked in the
computer lab.
• Time compression.
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-15
Simulation Cons
• Lack of interference from the “real world” can result in a
solution which has only academic value.
• A great deal of computer time may be needed to obtain the
desired accuracy.
• The entire simulation must be redone for a change in a single
variable or discovery of a programming error.
• Good simulations of complex problems require complex and
expensive computer programs.
• These complex and expensive computer problems are one
trick ponies and cannot solve any other problem.
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-16
Homework
•
Pick 1 of 3 computer simulation projects:
1. Good Experiment Gone Bad.
2. Verify Queuing Model Equations.
3. Reliable Design.
(I am open to other projects of similar complexity)
Notes:
•
You must use a computing language I have access to (C,
C++, MATLAB, FORTRAN).
•
If you aren’t much of a programmer, try a tool such as
Crystal Ball (http://www.decisioneering.com).
EMIS 7300 Fall 2005
Copyright  2005 Dr. John Lipp
S4P1-17