Transcript Notes on Monte Carlo Simulation - The University of Chicago GSB

University of Chicago
Graduate School of Business
Introduction to Computer Based Models
Mr. Schrage
Bus-36102-81
Spring 2003
Notes on Monte Carlo Simulation
(Monte Carlo) Simulation
Basic Idea:
Operation of a system, including random elements,
can be described/modeled by a computer program.
Advantages:
Can experiment with the simulator much cheaper
than with the real system(usually).
Can represent arbitrary detail.
Disadvantages:
Usually too complex to apply optimization
such as LP.
Can ask only “What If”, rather than “What’s Best”.
Example Applications
Boulder 10K Race
Telephone call centers
Coal loading facility
Asian financial options
Exxon tanker fleet: Scheduling, sizing,
NYFD: Response policies, location, redeployment, staffing
Burger King restaurants: Multiple drive-up windows, no. of cashiers
IBM inventory simulator
GM Production lines
American Airlines Reservation System
Proposed computer design
Military
Useful Ideas/Avoiding Pitfalls
a) How to compare two policies the good way.
b) How to generate random variables the good way
c) When can a random variable be replaced by its
expectation.
Types of Simulators
Transaction processing/trackers
e.g., Extend, Witness
Replicators,
e.g., @Risk, Crystal Ball
System Dynamics/Differential Equation
e.g., Extend
Animation
Can work with output log from any of above.
Quick Introduction to the Extend Simulation Program
The Extend simulation program allows you to:
run one replication of a many period Extend(nonspreadsheet) model.
This is in contrast to the @RISK spreadsheet program that allows:
run many replications of a single period spreadsheet model.
Extend is a very powerful and general purpose simulation program.
A slightly simplified description of its capabilities is that it allows to
simulate a system in which various entities move through a series of
processing steps or blocks, subject to various kinds of random
influences. You build an Extend simulation by 1) selecting blocks or
processes from a library of blocks, 2) specifying parameters for each
block, e.g. the distribution and its mean and standard deviation, and 3)
hooking up the blocks to specify how entities flow among blocks.
Bank Teller Simulation in Extend
Te l l e r s
T
Hel
Hel pp
U
count
D
Tel l er 1
Cus t ome r s c ome
i n f r ont door
V
1 2
Cust omer s
T
F
L W
Wai t i ng Li ne
U
D
Tel l er 2
T
U
D
Tel l er 3
Le a v e ba nk
Pl ot t e r
#
Exi t
( 4)
Pl ot t er
Extend cont.
The first/customer block generates an arrival stream of
customers according to some arrival process that you specify.
The "waiting line" block simply records how long each
customer is in the waiting queue.
The teller blocks delay each customer for some random
length of time. As with the first block, you can specify the
distribution of this delay.
The final block simply
removes completed customers from the system.
What kind of questions can you answer with a simulation such as this?
Some examples are:
What's the benefit of adding more tellers? Is it worth the cost?
What's the effect of offering specialized service,
for example, a "deposits only" teller?
What is the effect of reducing the service time,
e.g., by increasing the wage rate so that the bank keeps
more experienced tellers?
Examining and Controlling an Extend Model
You can examine and the parameters that control a block by double
clicking on the block. This opens up a dialog box in which you can
change parameters, e.g., the mean of a distribution, or the type of the
distribution, and see statistics from the most recent run.
Under the "Run" menu you can turn on "Show Animation" if you wish
to see statistics reported at each block for the current state of the system,
e.g., number in queue, etc.
More Information
More information on Extend can be found at
http://www.imaginethatinc.com/.
Another simulation software vendor is Pritsker and Associates,
with information at: http://www.pritsker.com/.
Generating Random Numbers, Some Pointers
Prob{ Demand = 1] = .21
Prob{ Demand = 2} = .47
Prob{ Demand = 3} = .16
Prob{ Demand = 3} = .16
4
1
3
2
Generating Random Numbers, Graphically
Cumulative
Probability
1.0
.84
.68
.21
0
1
2
Random outcome
3
4
Generating Continuous Random Variables
Cumulative
Probability
1.0
0
0
1
2
Random outcome
3
4
Generating a
Normal deviate!?
Excel 97 uses inverse transform method for Normal,but...
Using the Tools|Data Analysis|Random Number Generator
In Excel/Office 2002
Each column used a starting seed = 55.
Unif(10,20)
10.06653
12.764061
16.325571
14.638508
15.829035
19.509262
14.794458
10.719321
10.330515
16.148869
19.303873
19.315165
11.942198
17.810602
18.75576
Norm(15,3) Poisson(15) Binom(.75,20) Bernoulli(.5)
7.573612
14
14
1
13.219347
15
17
1
16.015903
13
17
0
14.727789
12
13
1
15.627981
8
13
0
19.961707
12
15
0
14.845367
16
14
1
10.61534
9
14
1
9.486825
18
13
1
15.876239
18
16
0
19.436051
16
15
0
19.461549
13
16
0
12.412647
13
16
1
17.327336
14
12
0
18.459459
19
16
0
Quasi-Random Numbers
An important variance reduction method in Monte Carlo.
Available in @Risk and other simulators as an option.
Suppose I want to run 9 replications,
one random variable per replication.
How should I generate the 9 uniforms?
(Make sure you get one in each interval, make “super-uniform”)
0
1
Quasi-Random Numbers, continued
Suppose I want to run 9 replications,
Need two random variables per replication.
How should I generate the 9 pairs of uniforms?
1
0
0
1
Numerical Examples
Applichem Case:
How to best serve six international markets in the face of
random demand, and random foreign exchange rates.
Design of experiment: 4096 scenarios(12 random variables each),
100 replications.
Method: Random Antithetic Stratified Weyl
LH
SLH
Mean:
1145.739 1145.427 1145.549 1145.274 1145.217 1145.288
Std Error: 2.834
1.348
1.717
2.609
0.815
0.663
Because we are maximizing profit, an optimizing
simulation will have a slight optimistic bias. Why?
Numerical Examples, cont.
Pricing a EurAsian option,
i.e., Value =
max(0, average_price_til_maturity – strike_price).
Design of experiment: 1024 scenarios(10 periods to maturity),
200 replications.
Method: Random Antithetic Stratified Weyl
LH
SLH
Mean: 1.8972 1.8946
1.8896 1.8807 1.8902 1.8897
Std Error: 0.0811 0.0578
0.0554 0.1133 0.0373 0.0302