MSBA7003 Quantitative Analysis Methods
ZHANG, Wei Assistant Professor HKU Business School
03 Basics of Monte Carlo Simulation
1
• Monte Carlo Simulation • Risk Assessment
• Inventory Management • Service Management
Agenda
2
Monte Carlo Simulation
• In practice, we often make decisions under risk for very complicated problems.
• Too many random variables involved
• Too many or even infinitely many possible states • Objective functions are highly nonlinear
• Cannot be explicitly solved
• Use computer to duplicate the features, appearance, and characteristics of a real system, and learn the outcome of a decision.
3
Monte Carlo Simulation
• Monte Carlo methods rely on repeated random sampling to obtain numerical results.
What is the probability of hitting the shaded area?
4
Monte Carlo Simulation
• Mathematically, if the objective function 𝑉 𝑋, 𝐷 depends on the
value of a (vector of) random variable(s) 𝑋 and a decision 𝐷, then the
expected objective value given 𝐷 can be approximated by randomly
sample 𝑋 independently 𝑁 times and computing the average: 1𝑁
𝑁 𝑉𝑋𝑖,𝐷
𝑖=1
• Then we can try different 𝐷 to maximize or minimize the objective.
5
Sampling State of the World via Simulation
Average Objective Value
Options Sample (1) Sample (2) Sample (3) …
Sample (N)
Option (A) Option (B) Option (C)
VA1 VA2 VB1 VB2 VC1 VC2
VA3 … VAN VB3 … VBN VC3 … VCN
(VA1+VA2+VA3+ … +VAN)/N (VB1+VB2+VB3+ … +VBN)/N (VC1+VC2+VC3+ … +VCN)/N
Generating a Random Number
• Random sampling is a critical step. Suppose the model is ready (i.e., the distribution of X is known), how to sample the value of 𝑋?
The cumulative probability distribution of X 1
0.075 0.26
0.35
0.19 0.125
1. Calculate the cumulative probability for each possible value of X and divide the [0,1] interval into segments corresponding to each possible value of X.
6
2. Generate a random number (uniformly) from [0,1].
0.8 0.6 0.4 0.2
0
X<=1 X<=2 X<=3 X<=4
X<=5
3.Return the value of X corresponding to the segment that contains the random number.
Probability
Generating a Random Number
• For discrete random variables
• Step 1: Build a cumulative distribution table with 𝑋𝑖 < 𝑋𝑖+1.
• Step 2: Assign the interval (0, 𝐹 𝑋 ] to 𝑋 and (𝐹 𝑋 , 𝐹 𝑋 ] to 𝑋 from
7
1 1 𝑖−1 𝑖 𝑖
• Step 3: generate a random probability and find the corresponding 𝑋 value.
𝑖 = 2.
• Generating a discrete random number in Excel:
• Binomial distribution: BINOM.INV(n, p_s, probability)
• An arbitrary distribution: VLOOKUP(probability, distribution table, column index for the return value)
Harry’s Auto Tire
• Harry’s Auto Tire sells a popular radial tire and replenish its inventory every 10 days. If the daily demand independently follows the distribution shown in the table below and the initial inventory level is 40 units, what is the expected sales in a 10-day period?
8
Daily Demand
0
1
2
3
4
5
Probability
0.05
0.10
0.20
0.30
0.20
0.15
• Note that 10-day sales = min(10-day demand, total inventory).
First, build a cumulative distribution table.
Next, suppose we decompose the simulation of daily demand into two steps: random number & vlookup
Harry’s Auto Tire
9
=vlookup(B13,$D$4:$E$9,2)
The VLOOKUP function looks up the random number in the leftmost column of the defined lookup table. It moves downward through this column until it finds a cell that is equal to or bigger than the random number. It then goes to the previous row and gets the value from the specified column.
A more compact & comprehensive spreadsheet model:
Harry’s Auto Tire
10
Use data table to try different inventory levels and plot the relationship between sales and inventory.
=VLOOKUP(RAND(),$D$4:$E$9,2,1)
Generating a Random Number
• For continuous random variables, the idea is the same
• Step 1: derive the inverse function of 𝑌 = 𝐹 𝑋
• E.g., for exponential distribution with parameter 𝜆, the cumulative distribution function (CDF) is 𝑌 = 𝐹 𝑋 = 1 − 𝑒−𝜆𝑋 and the inverse CDF is 𝑋 = 𝐹−1 𝑌 = −𝜆−1 ∙ ln 1 − 𝑌 .
• Step 2: generate a random probability (i.e., a random number uniformly from [0,1]) and assign it to 𝑌 to get 𝑋.
Probability Cumulative Density Probability
• Generating a continuous random number in Excel:
• Normal distribution: NORM.INV(probability, mean, st_dev) • Standard Normal distribution: NORM.S.INV(probability)
• Uniform distribution on [0, 1]: RAND()
11
Risk Assessment
• Monte Carlo method not only can assess the average performance of a decision, but can also assess the probability of some events.
• For Harry’s Auto Tire, what is the probability of running out of stock?
12
13
Inventory Management
• The goal of inventory management is to achieve an optimal balance between inventory holding cost, ordering cost, and stock-out cost.
• The biggest challenges are posed by uncertainties • Demand uncertainty
• Lead time uncertainty
• There are two types of commonly used policies:
• For continuous inventory monitoring, set up an order-triggering level (r) and
decide the order quantity (Q)
• For periodic inventory monitoring, set up an order-triggering level (s) and an order-up-to level (S)
• Continuous inventory monitoring: (r,Q) policy
Inventory Management
14
𝐷 1
𝐷2
𝐷4
Order Quantity (Q)
Order- Triggering Level (r)
Time(Day)
𝐷3
Order Quantity (Q)
0
𝐷5 𝐷6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Lead Time Lead Time
Inventory Level
Inventory Management
• Periodic inventory monitoring: (s,S) policy
15
Order Quantity =
S-I6
Order Quantity =
S-I12
Order-up-to Level (S)
Order- Triggering Level (s)
Time (Day)
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Lead Time Lead Time
Inventory Level
Simkin’s Hardware Store
• The owner of Simkin’s hardware store wants to find a good, low cost inventory policy for an electric drill (Ace Model). Because all the sales and inventory are recorded in the computer and the supplier accepts orders at any time, so continuous inventory monitoring is adopted.
• How to optimize the order quantity (Q) and reorder point (r), given the distributions of daily demand and reorder lead time below?
16
Daily Demand
Frequency (Days) Prob. Cumu. Prob.
0 15 1 30 2 60 3 120 4 45 5 30
0.05 0.05 0.10 0.15 0.20 0.35 0.40 0.75 0.15 0.90 0.10 1.00
Lead Time (Days)
1 2 3
Frequency (Orders)
Prob. Cumu. Prob.
10
25
15
50 1.00
0.20 0.20 0.50 0.70 0.30 1.00
300 1.00
Simkin’s Hardware Store
• Suppose Simkin’s wants to test the policy of Q=10 and r=5. The process is simulated manually for a 10-day period.
17
UNITS BEGINNING RANDOM
DAY RECEIVED INVENTORY NUMBER DEMAND
ENDING LOST RANDOM LEAD INVENTORY SALES ORDER NUMBER TIME
1 0 10 0.06 1 9 0 No 2 0 9 0.63 3 6 0 No 3 0 6 0.57 3 3 0 Yes 4 0 3 0.94 5 0 2 No 5 10 10 0.52 3 7 0 No
0.02 1
0.33 2
0.14 1
6 0 7 0.69 3 4 7 0 4 0.32 2 2 8 0 2 0.30 2 0 9 10 10 0.48 3 7
0 Yes 0 No 0 No 0 No 0 Yes
10 0 7 0.88 4 3
Total 41 2
Simkin’s Hardware Store
• The objective is to find a low-cost solution so Simkin’s must determine the costs associated with carrying inventory, lost sales, and ordering cost.
• Simkin’s store is open 200 days a year, and the holding cost is $12 per drill per year. The estimated ordering cost is $10 per order. Lost sales cost $8 per unit.
• The average (ending) inventory level = 41/10 = 4.1 units per day
• The rate of lost sales = 2/10 = 0.2 units per day
• The rate of orders = 3/10 = 0.3 times per day
• The average daily cost = 4.1*12/200 + 0.2*8 + 0.3*10 = 4.85
18
Simkin’s Hardware Store
Search for night of arrival Compare previous total order from previous rows placements and order arrivals
19
Use 2D data table to try different(r,Q)combination and find the optimal policy.
• Company Overview:
Kroger
20
• 1,950 in-store pharmacies
• Each stock about 2 to 3 thousand drugs • Periodic inventory review: (s,S) policy
• Each pharmacy faces unique demand
• The Challenge of Inventory Management:
• The demand distribution is highly irregular and cannot be captured by standard distributions; complicated models are not acceptable
Kroger
• The historical sales data of a particular drug sold at a particular store. • The basic dose is one pill per day and the prescriptions are often
written for 30 days (or 60 or 90 days).
Date
21
Demand
Kroger
• The historical sales data of a particular drug sold at a particular store. • The basic dose is one pill per day and the prescriptions are often
written for 30 days (or 60 or 90 days).
Demand
22
Empirical Probability
Frequency
Kroger
23
• Important notes in practice:
• Check whether lost sales (or the true demand) were recorded.
• Historical sales were affected by various factors, which may be under different conditions currently.
• If we delegate the optimization to a software, the starting point for the search algorithm should be carefully set.
• Possible Solutions:
• Check whether stock-outs were solely caused by low inventory levels; if so,
data points with stock-outs can be dropped.
• Use multiple linear regression to model the demand and perform simulation.
• Use data table to manually search for the optimal solution.
Kroger
24
Service Management
• When customers obtain utility by occupying and using firm resources, services take place.
• A critical decision in service management is to optimize the service capacity, which determines the cost and the level of congestion.
25
Pinevalley Bank
• The X branch of Pinevalley Bank has four service counters, but sometimes it is not necessary to open all four counters. Historical data shows that customers arrive every 10 minutes on average between 2 to 3 p.m. on a Thursday afternoon. The inter-arrival time follows exponential distribution. The service time for each customer also follows exponential distribution with a mean of 5 minutes. The question is, in order to make sure the average waiting time for each customer is less than 3 minutes, what is the minimum number of counters needed during this period of time?
26
Pinevalley Bank
• We first manually simulate the process of customer arrival and service (assuming that two counters are open):
27
Arrival Customer Interval No. (Minute)
Arrival Time (Minute)
Counter 1 Available From (Minute)
Counter 2 Available
From Assigned (Minute) Counter
Service Time (Minute)
Service Complete (Minute)
Waiting Time (Minute)
16
6001
8 14 0
29
15 14 0 2
3 18 0
31
16 14 18 1
7 23 0
41
17 23 18 2
4 22 1
57
24 23 22 2
3 27 0
6 12
36 23 27 1
4 40 0
Counters not available will be available at an infinitely far time point.
Pinevalley Bank
28
Average waiting time 0.45 minutes, but the longest waiting time exceeds 17 minutes.
29
Port of New Orleans
• Fully loaded barges arrive at night for unloading
• The number of barges each night varies from 0 - 5
• The number of barges vary from day to day
• Barges are unloaded first-in, first-out
• The unloading rate also varies from day to day
• Barges must wait for unloading, which is expensive
• The dock manager wants to do a simulation study to enable him to make better staffing decisions
Port of New Orleans
• Historical data suggests the following distributions:
30
NUMBER OF ARRIVALS
CUMULATIVE PROBABILITY PROBABILITY
0 0.13 0.13
1 0.17 0.30
2 0.15 0.45
3 0.25 0.70
4 0.20 0.90
5 0.10 1.00
1 0.05 0.05
2 0.15 0.20
3 0.50 0.70
4 0.20 0.90
5 0.10 1.00
DAILY
UNLOADING CUMULATIVE
RATE PROBABILITY PROBABILITY
Port of New Orleans
1 — 0.52 3 3 0.37 3 2 0 0.06 0 0 0.63 0 3 0 0.50 3 3 0.28 3 4 0 0.88 4 4 0.02 1 5 3 0.53 3 6 0.74 4 6 2 0.30 1 3 0.35 3 7 0 0.10 0 0 0.24 0 8 0 0.47 3 3 0.03 1 9 2 0.99 5 7 0.29 3
10 4 0.37 2 6 0.60 3 11 3 0.66 3 6 0.74 4 12 2 0.91 5 7 0.85 4 13 3 0.35 2 5 0.90 4 14 1 0.32 2 3 0.73 3 15 0 0.00 5 5 0.59 3
20 41 39
Total delays Total arrivals Total unloadings
31
NUMBER DELAYED RANDOM NUMBER OF TOTAL TO BE RANDOM NUMBER DAY FROM PREVIOUS DAY NUMBER NIGHTLY ARRIVALS UNLOADED NUMBER UNLOADED
Port of New Orleans
• What if there are another unloading team working in parallel?
32
NUMBER OF NUMBER DELAYED FROM RANDOM NIGHTLY DAY PREVIOUS DAY NUMBER ARRIVALS
TOTAL TO BE UNLOADED
RANDOM NUMBER FOR TEAM 1
RANDOM
NUMBER FOR TOTAL CAN BE NUMBER
TEAM 2 UNLOADED UNLOADED 1—.....................
Port of New Orleans
• What if all the barges have to be loaded again by a loading team before leaving the port?
33
NUMBER DELAYED FROM DAY PREVIOUS DAY
NUMBER OF NIGHTLY ARRIVALS
RANDOM
NUMBER FOR TEAM 2
RANDOM NUMBER
TOTAL TO BE UNLOADED
NUMBER FOR TEAM 1
NUMBER UNLOADED
NUMBER RELOADED
DAY RELOADED 1—............... .........
NUMBER DELAYED
FROM TOTAL TO PREVIOUS BE
RANDOM
• Simulation and Financial Planning • Cash flows, stock prices, etc.
• Simulation and Marketing
• Customer retention, market share evolution, etc.
• Simulation and Sports
• Basketball, baseball, etc.
• Simulation and Artificial Intelligence • AlphaGo (Monte Carlo Tree Search)
More Applications ...
34
Verification and Validation
• It is important that a simulation model be checked to see that it is working properly and providing good representation of the real- world situation
• Verification process involves determining that the computer model is internally consistent and following the logic of the conceptual model
• Verification answers the question “Did we build the model right?”
• Validation is the process of comparing a simulation model to the real system it represents to make sure it is accurate
• Validation answers the question “Did we build the right model?”
35
• True or False?
• Ken is good at shooting three-pointers. For each shot, the chance of success is 0.92. To simulate the total score after 10 shots, in total 10 random numbers should be generated.
• If the cumulative probability distribution of random variable X is given by the Python dictionary of {1:0.15, 2:0.35, 4:0.6, 5:0.82, 8:1}. Then the probability of generating “4” from this distribution is 0.25.
• We want to simulate the operations of a restaurant during a particular time period. We have the distributions of the number of customer arrivals within 15 minutes in this period and we know each customer’s meal-preparing time and dining time both follow exponential distribution with separate means. Then we need to build a simulation model for the operations of the restaurant associated with each customer.
In-Class Exercises
36