Transcript Chapter 11 - Monté Carlo Simulation

(Monté Carlo) Simulation
MGS 3100 – Chapter 4
What is Simulation?
A definition of simulation from Dictionary.com
– Imitation or representation, as of a potential
situation or in experimental testing.
– The basic idea is to build an experimental device, or
simulator, that will “act like” the system of interest …
in a quick, cost-effective manner.
– Representation of the operation or features of one
process or system through the use of another:
computer simulation of an in-flight emergency.
Simulation in Business Analysis
• Uses mathematical models
• Probabilistic (as opposed to deterministic)
• Uses the entire range of possible values of
a variable in the model
• Imitates a system or situation (like a coinflip, or how long a person might have to
wait in a line at a restaurant)
Why Simulate?
• Safety – flight simulator
• Cost – easier to simulate adding a new
runway and find out effects than to
implement in reality and then find out
• Time – Boeing uses simulated
manufacturing before the real thing, with
tremendous savings in time and money –
can discover parts that do not fit and fix
them before actual production
How does it work?
• Simulation requires you to know
– What variable is to be simulated
– Is the variable discrete or continuous?
– The distribution of the variable – values it can take on
and the probabilities of those values occurring.
• Step 1: Generate a variable containing uniformly
distributed random variables between 0 and 1
(the rand() function in Excel).
• Step 2: Create a rule to map the random
numbers to values of the variable desired in the
right proportion, and apply the rule.
Types of Variables in Simulation
Models
• Discrete
– Used for simulating specific values or specific
points.
– Example: Number of people in a waiting line
(queue).
• Continuous
– Used for simulating any value (between
specific points)
– Example: The amount of time a person
spends in a queue.
Discrete Example 1– coin toss
• Variable to be simulated is “Outcome of a
coin toss”. It takes on values “Heads” and
“Tails”, each with 0.5 probability.
• Generate 100 random numbers (100
tosses of coin).
• Make a rule like – if random number >
0.5, then “Heads”, else “Tails”. This will
create the right distribution of outcomes.
Discrete Example 2:
Machine Failures
• Simulate machine
failures based on this
historical data
Number of
Failures per
month
Frequency
(# of months
this
occurred)
0
1
2
3
36
20
3
1
Total
60
Discrete Example 2: Machine Failures
Create the following cumulative probability table.
Number of
Failures per
month
Frequency
(# of
months this
occurred)
Probability
0
1
2
3
36
20
3
1
0.600
0.333
0.050
0.016
Total
60
1.00
Cumulative
Probability
0.600
0.933
0.983
1.000
Discrete Example 2: Machine Failures
• Now map the random numbers between 0
and 1 using the cumulative prob. Column
as the cutoffs.
0 failures
0
1 failure
0.60
0.93
2
3 failures
0.98
• Random numbers between 0 and 0.6
represent 0 failures, between 0.6 and
0.933 represent 1 failure, and so on.
Discrete Example 2 Solution –
Random Number Mapping
The random numbers are now mapped to number of failures as follows.
Random Number
#
of
Failures
0.345
0.008
0.985
0.878
0
0
3
1
Continuous Example – arrival time
• Variable to be simulated is arrival time at
a restaurant which can literally take on
infinite individual values
• For example someone could arrive at:
• 12:09:37
• 12:09:37:52
• 12:09:37:52:14, etc.
Continuous Example – arrival time
con’t
To simulate this situation, we must specify intervals
At the restaurant the intervals could be all people arriving
between 11am and 12pm, 12pm and 1pm, or 1pm and
2pm.
As with the coin toss, generate random numbers in Excel (
=RAND() )
• Make a rule – if random number:
• <=.333, then =11am-12pm
• >.333 up to =.666, then 12pm-1pm
• >.666 up to 1, then 1pm to 2pm
each category is equally likely
Continuous Example – arrival time
con’t
If the random number is.47, then this would fall in
the 12pm to 1pm category,
If the random number is .88, then this would fall in
the 1pm to 2pm category, etc.
Because each category is equally likely, if we run
enough trials, each category will contain about
the same number of random numbers, which will
tell the restaurant owner that it is equally likely
that a person will arrive at any of the three times.
Continuous Example – arrival time
con’t
• The owner looks at historical information
and says that on an average day, 225
people eat lunch at his restaurant , and
that typically
• 47 people arrive between 11am and 12pm
• 112 people arrive between 12pm and 1pm
• 66 people arrive between 1pm and 2pm
How do we map these numbers?
Continuous Example – arrival time
count
11am to 12pm
12pm to 1pm
1pm to 2pm
total
47
112
66
225
con’t
percent
0.21
0.50
0.29
1.00
To complete the mapping, we need to make a
cumulative distribution function (CDF)
Continuous Example – arrival time
count
11am to 12pm
12pm to 1pm
1pm to 2pm
total
47
112
66
225
con’t
percent
CDF
0.21
0.21
0.50
0.71
0.29
1.00
1.00
Make a new rule – if random number:
<=.21, then =11am-12pm
>.21 up to =.71, then 12pm-1pm
>.71 up to 1, then 1pm to 2pm
Note on Random Numbers in Excel
Spreadsheets
• Once entered in a spreadsheet, a random
number function remains “live.” A new random
number is created whenever the spreadsheet is
re-calculated. To re-calculate the spreadsheet,
use the F9 key. Note, almost any change in the
spreadsheet causes the spreadsheet to be
recalculated!
• If you do not want the random number to
change, you can freeze it by selecting: tools,
options, calculations, and checking “manual.”
Evaluating Results
• Simulation measures the quality of a
solution because it gives the probability of
a certain event occurring
• Simulation also shows the variability
• Simulation does not necessarily give the
best possible answer. It gives the most
likely answer.
Appendix
• Some useful information on very popular
probability distribution function
Probability Distributions
A probability distribution defines the behavior of a
variable by defining its limits, central tendency
and nature
–
–
–
–
Mean
Standard Deviation
Upper and Lower Limits
Continuous or Discrete
Examples are:
–
–
–
–
–
Normal Distribution (continuous)
Binomial (discrete)
Poisson (discrete)
Uniform (continuous or discrete)
Custom (created to suit a specific purpose)
Uniform Distribution
• All values between minimum and maximum
occur with equal likelihood
• Conditions
–
–
–
Minimum Value is Fixed
Maximum Value is Fixed
All values occur with equal likelihood
• Excel function: RAND() – returns a uniformly
distributed random number in the range (0,1)
Normal Distribution
• Conditions:
–
–
Uncertain variable is symmetric about the mean
Uncertain variable is more likely to be in vicinity of the
mean than far away
• Use when:
Distribution of x is normal (for any sample size)
– Distribution of x is not normal, but the distribution of
sample means (x-bar) will be normally distributed with
samples of size 30 or more (Central Limit Theorem)
• Excel function: NORMSDIST() – returns a random
number from the cumulative standard normal distribution
with a mean of zero and a standard deviation of one [e.g.,
NORMSDIST(1) = .84]
–
Simulation
Continuous Variables
Distributions
• Variables to be simulated may be normal
(e.g. height) or exponential (e.g. service
time) or various other distributions.
• Task is to convert uniform distribution to
the required distribution.
Freq
Freq
0
1
0
infinity
Application - Queuing Systems
• A queuing system is any system where
entities (people, trucks, jobs, etc.) wait in
line for service (processing of some sort) –
– retail checkout lines, jobs on a network server,
phone switchboard, airport runways, etc.
Queuing System Inputs
• Queuing (waiting line) systems are
characterized by:
– Number of servers / number of queues
•
•
•
•
SSSQ – Single Server Single Queue
SSMQ – Single Server Multiple Queue
MSSQ – Multiple Server Single Queue
MSMQ - Multiple Server Multiple Queue
– Arrival Rate (Arrival Intervals)
– Service Rate (Service Times)
Performance Variables (outcome)
• Performance of a queuing system is
measured by
– Average time waiting in queue/system
– Average number of entities in queue/system
Time in Queue
Arrival time
Service Time
Service Begins
Time in System
Service Ends
Distributions in Queuing
• Arrival Intervals (time between two
consecutive arrivals) and Service Time
(time to serve one customer) are
exponentially distributed.
• Confirm it yourself by watching cars on a
street!
Sample Problem
• A loading dock (SSSQ) has trucks arriving
every 36 minutes (0.6 hrs) on average,
and the average service (loading /
unloading) time is 30 minutes (0.5 hrs). A
new conveyer belt system can reduce that
to 15 minutes (0.25 hours). Simulate the
arrival of 200 trucks to see how
performance would be affected by the new
system.
Simulating Exponential
Distributions
• To convert the uniform distribution of the random
numbers to an exponential distribution, take the
negative natural log of the random numbers.
– This creates an exponential distribution with an
average of 1.00.
– To get an average of 0.6 (to represent average arrival
interval in hours), simply multiply result by 0.6.
– Thus, the conversion formula is:
–ln(rand())*µ
where µ is the mean of the exponential distribution desired.
Sample Conversion
Average:
0
1
0.500645
1.040982
Random
-ln(rand())
0.449796
0.798962
0.858464
0.15261
0.828061
0.188668
0.938751
0.063206
0.84637
0.166798
0.428408
0.847678
0.357574
1.028412
0.63932
0.447351
…..
…..
0
infinity