Computer Simulation & Modeling
Monte Carlo Simulation
Dr. Hakeem–Ur–Rehman
IQTM-PU
1
Outlines
Introduction to Monte Carlo (MC) Simulation
Five Steps of MC Simulation
Examples of MC Simulation to solve the mathematical problems
MC Simulation: Random Number Mapping Method
MC Simulation of a Queuing System
MC Simulation of an Inventory System
MC Simulation of a Project
2
Different Kinds of Simulation
System Model
Deterministic Vs. Stochastic
Deterministic Is everything for sure or is there uncertainty? Stochastic
Static Vs. Dynamic
Static Dynamic Does time have a role in model? Static Dynamic
Monte Carlo
Simulation
Continuou Continuous Vs. Discrete Change
Discrete Can “state” change continuously, or only at Continuous Discrete
s
Continuous Discrete discrete points in time? Continuous Discrete
Simulation Event Simulation Event
Simulation Simulation
Most operational models: Stochastic, Dynamic, Discrete-change
3
Monte Carlo Simulation
John Von Neumann and Stanislav Ulam – Developed this method (1949).
The technique “Monte Carlo” derives its name from the city of Monte Carlo in the principality of
Monaco, France, famous for gambling and its casino.
Gambling is the game of probability and random sampling and so is the Monte Carlo Method.
Monte Carlo methods (or Monte Carlo experiments) are a broad class
of computational algorithms that rely on repeated random sampling to obtain numerical results.
(Based on random numbers)
To reflect the relative frequencies of the random variables, the random number mapping method is
used
“Monte Carlo is a method of approximating things using samples”
Simulation-Optimization: Run simulation many times, each time with different parameters, to find
the best (optimal) values of parameters. 4
Monte Carlo Simulation…
A Coin Tossing Game:
Charlize tosses a coin for her friends, Harry and Tom, exactly 100 times. Harry wins $1.00
when a head lands up, and Tom loses $1.00. Tom wins when the coin lands with tails up,
with Harry paying $1. Charlize tracks their respective wins and losses as they play the
game.
On any game (a game being exactly 100 tosses), is it more likely that both Harry and Tom
are each ahead on about ½ of the games, or is it more likely that one of the two is ahead
most of the time?
Analyze the coin tossing game after 400 trails (i.e. games).
5
Monte Carlo Simulation…
“Monte Carlo is a method of approximating things using samples”
Example–1: Using Monte Carlo Simulation to Estimate ‘’
Example–2: Integrate &
6
Monte Carlo Simulation…
Random Number Mapping Methods: Service Time
Probability
(Minutes)
Consider service time distribution shown here
1 0.4
2 0.35
3 0.2
To obtain a random service time, we need to map an 4 0.05
appropriate number of integers from 0 to 99 to each service
time, according to the probability
Service Time
Assume Probability Mapping
that we have random integers ‘Uniformly (Minutes)
distributed’ in range ‘0 – 99’ 1 0.4 0-39
2 0.35 40-74
o Obtained using Excel formula
3 0.2 75-94
• “TRUNC(100*RAND()) ” 4 0.05 95-99
• “RANDBETWEEN(0,99)”
7
Five Steps of Monte Carlo Simulation
The Monte Carlo method can be used with variables that are probabilistic.
1. Establishing probability distributions for important input variables
2. Building a cumulative probability distribution for each variable in step 1
3. Establishing an interval of random numbers for each variable
4. Generating random numbers
5. Simulating a series of trials
8
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of a Queuing System: A doctor’s office has one nurse and one doctor. Patients arrive randomly. Each patient first
goes through a check-up with the nurse and then proceeds for a full check-up by the doctor. Patients may have to wait before
being served by the nurse as well as before being served by the doctor. Service priority is first-in-first-out (FIFO). The service
time of the nurse is always 7 minutes, but the service time of the doctor is random. The distributions of the time between
arrivals and the service time of the doctor are given below:
Time between arrivals (Minutes) Probability Doctor’s Service time (Minutes) Probability
5 0.5 4 0.3
10 0.3 8 0.5
15 0.2 12 0.2
Constant Random
Random Service time Service time
(Inter-arrival time) Nurse Doctor
Patients (One) (One)
arrive Waiting Area Waiting Area
Determine the average time a patient spends in the doctor’s office from the arrival till leaving using
simulation. 9
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of a Queuing System:
1. What is the average inter-arrival time?
2. What is the arrival rate?
3. What is the average Doctor’s Service time?
4. What is the Doctor’s service rate?
5. What is the average time a patient spends in the doctor’s office from the arrival
till leaving?
6. How many number of patients in the doctor’s office at any given time?
10
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of a Queuing System…
Time between
arrivals [min] Probability
What is the average inter-arrival time?
Avg. inter-arrival time =
5 0.5 Arrival Rate = = 1 / (Avg. inter-arrival time)
10 0.3 = 0.1176 cust. /min.
15 0.2 = 7.059 cust. / hour
Doctor's service Doctor’s Service Time:
time [min] Probability What is the average Service time?
4 0.3 Avg. Service time =
8 0.5 Service Rate = = 1 / (Avg. service time)
12 0.2 = 0.1316 cust. /min.
= 7.895 cust. / hour
Nurse’s Service Time:
Avg. Service time =
Service Rate = = 1 / 7 = 0.1429 cust. /min. = 8.57 cust. / hour
11
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of a Queuing System…
Time between Mapping Doctor's service Mapping
arrivals [min] Probability 0-99 time [min] Probability 0-99
5 0.5 0-49 4 0.3 0-29
10 0.3 50-79 8 0.5 30-79
15 0.2 80-99 12 0.2 80-99
What is the average time a patient spends in the doctor’s office from the arrival till leaving?
Average time in the System = 12
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of a Queuing System…
How many number of patients in the doctor’s office at any given time?
LITTLE’S LAW Inventory (I) = Flow Rate (R) * Flow Time (T)
Average Number of customers in the system = Arrival Rate X Average time in the System
= 0.1176 cust. /min X 15.4 min. = 1.81 Cust.
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of a Queuing System…
Statistical Analysis of the Simulation Results:
Average time
Experiment in system n 10
(Min.) Mean 20.535
1 17.15 S.D. 6.652
2 37.25
3 17.1 R e ject H 00 R e ject H 00
4 18.7
5 17.65 .0 25 .0 25
6 16.8
7 21.25
8 15.15
-1.96 0 1.96 Z
9 17.95
10 26.35 Under 95% Confidence Interval (16.412 , 24.658 )
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of an Inventory System: Ali Appliance stocks and sells the KitchenChef electric mixer. Initially,
there are 25 units in the inventory. Each week a number of customers buy some units. The number of customers
and demand per customer have the following probability distributions:
Number of Customers Probability Demand per Customer Probability
0 0.10
1 0.10
1 0.30
2 0.15
2 0.25
3 0.20 3 0.40
4 0.15 4 0.35
Ali uses the following inventory policy: if at the end of the week inventory is R = 10 items or less and there is no
outstanding order, then order Q = 25 items. Holding cost $1 per unit per week. Order cost is $45 per order. Order
placed at the end of the week ‘n’ arrives at the beginning of a week ‘n+2’ (i.e. Lead time is 2 weeks). If Ali runs
out of units for which there is demand, they put them on backorder, i.e., the demand is satisfied once the next
order arrives. Backorder cost id $5 per unit per week.
Ali would like to determine the average weekly cost of inventory.
15
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of an Inventory System …
Number of Mapping
Probability Demand per Mapping Order 'Q' when inventory is less than or equal to R and there
Customers (0-99) Probability
Customers (0-99) is no outstanding order.
0 0.1 0-9
Q = 25, R =10
1 0.3 10-39 1 0.1 0-9
Ordering Cost = $45 per order
2 0.25 40-64 2 0.15 10-24
Holding Cost = $1 per unit per week
3 0.2 65-84 3 0.4 25-64 Backorder Cost = $5 per unit per week
4 0.15 85-99 4 0.35 65-99
15
Average Inventory Cost = 16
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of a Project:
Consider a project with activities shown in the first table and Activity Description Predecessors
activity time distributions shown in the second table. Activity F A Excavate -
always takes 5 days.
B Lay foundation A
What is the critical path and the expected project completion time if C Rough plumbing B, D
activity times are equal to expected (mean) activity times? D Frame A
Perform 10 simulation experiments and compute the following: E Finish exterior D
o Expected duration of the project. F Install HVAC C, E
o Probability that the project exceeds 27 days.
o Probability that a path is critical, for each path
A B C D E
Days Prob. Days Prob. Days Prob. Days Prob. Days Prob.
4 0.4 8 0.4 2 0.5 4 0.8 2 0.5
8 0.4 10 0.2 4 0.5 9 0.2 10 0.5
11 0.2 12 0.4
17
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of a Project…:
7
10
3
5
6
5 Mean duration of the Activity:
Critical Path: A B C F
Project Duration = 25 Days
All Paths:
A B C F (25 days)
A D C F (20 Days)
A D E F (23 Days)
18
Monte Carlo Simulation:
Random Number Mapping Method
Simulation of a Project…:
Average Duration = (27+29+23+23+35+30+25+28+19+27/10) = 26.6 Days
What is the Probability that project duration will exceed from 27 days? 4/10 = 40%
19
What is the Probability that path ‘ABCF’ is critical? ; ‘ADCF’ is critical? ; ‘ADEF’ is critical?
20
