Slide 1: Probabilistic methods in operations research
GPEM - UPF José Niño Mora April 6, 2000
Slide 2: Outline
More about the course Elements of probabilistic models Idealized probability distributions Multivariate distributions Conditional probabilities The buildings of uncertainty: Functions of random variables Simulation / Optimization
Slide 3: Course objectives
Given a complex business decision making problem under uncertainty, learn how to: 1. Build a probabilistic model 2. Solve the model (analysis/simulation) 3. Interpret the solution in terms of original problem
Slide 4: Course features
Emphasis: NOT on abstract analysis But on: Modeling, Analysis/Simulation and Solution in the setting of CONCRETE planning problems YET: Need to learn fundamental methods and modeling techniques Also: Will solve/simulate models with computer (Excel)
Slide 5: Course overview (revised)
1. Review of probability 2. Decision trees 3. Dynamic programming 4. Queueing (Business process flows) systems 5. Simulation Methods illustrated through applications
Slide 6: Course web page
Look at: http://www.econ.upf.es/~ninomora/pmor.htm Contains:
class presentations, Excel spreadsheets Links to useful resources (probability, OR, …)
Slide 7: About grading ...
Final exam: 66% Problem sets (biweekly): 17% Course project: 17% Class participation: for boundary grades
Slide 8: Resources for probability review & for spreadsheet modeling
In course web page, look at:
Links: Probability Ex: The layman’s guide to probability theory
Look also at Bibliography:
Ex: Feller: An introduction to prob. Theory
For spreadsheet modeling: will use
Insight.xla (Business Analysis Software). Sam
L. Savage.
Slide 9: References
Course transparencies Copies from books/articles
Anupindi et al. (1999). Managing Business Process Flows. Prentice Hall. D.E. Bell et al. (1995). Decision making under uncertainty. Course Technology. ...
Slide 10: Ex: Uncertain benefits
Introducing new product in market ¿Benefit? Depends on:
Sales (in units) Price/unit Cost/unit (production, marketing, sales, ...) Fixed costs (overhead, publicidad) = E30.000
Benefit =
Sales * (Price- Cost_unit) - Fixed costs
Slide 11: Market scenarios
New market: Uncertainty Scenarios: high or low volume (50%)
Probability Units Price/unit(E) Market Scenarios Low volume High volume Mean volume 50% 50% 60000 100000 80000 10 8 9
Cost/unit Scenarios More likely High 25% 50% 6 7,5
Scenario: cost/unit
Low
Mean cost 25% 9 7,5
Probab. Cost/u.(E)
Slide 12: The building blocks of uncertainty
1. Uncertain numbers: Random numbers 2. Averages: Diversification 3. Important classes of random numbers: Idealized distributions 4. Functions of random numbers: uncertainty management
Slide 13: Exponential distribution
Models time between events, e.g., teleph. Calls, or product orders: X ≈ Exp (λ ) Density function: − λt f ( t ) = λe , t ≥ 0 Distribución: P{ X > t} = e −λt , t ≥ 0
1 E[ X ] = λ
1 Var[ X ] = 2 λ
Slide 14: Relation Exponential-Poisson
Suppose time between consecutive calls is X ≈ Exp (λ ) Then, number of calls ocurring in [0, t) es:
Y ≈ P ( λt )
− λt
Hence,
P{Y = j} = e ( λt ) / j!, j ≥ 0
Slide 15: Uniform distribution
Uniform distr. between a and b (a < b): X ≈ U ( a , b) 1 Density function: f ( x) = ,a ≤ x ≤ b b−a Distribution: x−a P{ X ≤ x} = ,a ≤ x ≤ b b−a E[ X ] = ( a + b) / 2
(b − a ) 2 Var[ X ] = 12
Slide 16: Uniform distribution (cont)
The RAND() Excel function:
RAND() ≈ U(0,1)
Usefulness of U ≈ U (0,1) in simulation:
Let F ( x ) = P{ X ≤ x}.
−1
Then, F (U ) ≈ X
Ex:
X ≈ Exp ( λ ); F ( x ) = 1 − e −λx Then, − log(1 − U ) F (U ) = ≈X λ
−1
Slide 17: Geometric distribution
Models no. of independent trials until first success, with success prob. p
X ≈ G( p) P{ X = j} = (1 − p ) E[ X ] = 1 / p Var[ X ] = (1 − p ) / p
2 j −1
p, j ≥ 1
Slide 18: Multivariate distributions
Main example: Multivariate Normal:
σ 11 σ 12 ( X 1 , X 2 ) ≈ N μ = ( µ1 , µ 2 ), Σ = σ 21 σ 22 µ j = E [ X j ] (marginal mean) Note :σ jj = σ j , σ ij = σ ji
2
σ ij = E [( X i − µ i )( X j − µ j )] (covariance bet. X i and X j )
Slide 19: Multivariate distr. (cont)
F ( x1 , x 2 ) = P{ X 1 ≤ x1 , X 2 ≤ x 2 }
Given by Joint Distribution:
or by Joint Density: Ex (Normal)
f ( x1 , x 2 ) = Ke
−Q ( x1 x 2 ) / 2
Slide 20: Covariance/correlation
Are measures of Linear Dependence between two r.v.:
Covariance : Cov( X 1 , X 2 ) = E [( X 1 − µ1 )( X 2 − µ 2 )] Correlation : Cov( X 1 , X 2 ) ρ( X1, X 2 ) = σ 1σ 2 Note : -1 ≤ ρ( X1, X 2 ) ≤ 1
Slide 21: Dependence/Independence of r.v.
If ρ ( X 1 , X 2 ) = 1 then X 2 = KX 1 , ( K > 0) If ρ ( X 1 , X 2 ) = −1, then X 2 = − KX 1 , ( K > 0) If ρ ( X , X ) = 0, then NO linear relation 1 2 Def: Two r.v. are INDEPENDENT if
P{ X 1 ≤ x1 , X 2 ≤ x 2 } = P{ X 1 ≤ x1 } P{ X 2 ≤ x 2 }
Ej: Two independent exponentials:
− λ1 x1
P{ X 1 ≤ x1 , X 2 ≤ x 2 } = (1 − e
)(1 − e
− λ2 x 2
)
Slide 22: Conditional expectation/probability
Conditional probabilitiy: probability of a success given another success occurs: P{ X 1 = x1 , X 2 ≤ x 2 } P{ X 2 ≤ x 2 | X 1 = x1 } ≡ P{ X 1 = x1 }
P{ X 1 > x1 , X 2 ≤ x2 } P{ X 2 ≤ x 2 | X 1 > x1 } ≡ P{ X 1 > x1 }
Conditional expectation:
E[ X 2 | X 1 = x1 ], E[ X 2 | X 1 > x1 ]
Slide 23: Conditional prob./exp. and Independence
Suppose X 1 , X 2 are independent r.v. Then,
P{ X 2 ≤ x 2 | X 1 = x1 } = P{ X 2 ≤ x 2 } E [ X 2 | X 1 = x1 ] = E [ X 2 ] E [ X 1 X 2 ] = E [ X 1 ]E [ X 2 ]
Var[ X 1 + X 2 ] = Var[ X 1 ] + Var[ X 2 ]
A useful identity:
E[ E[ X 2 | X 1 ]] = E[ X 2 ]
Slide 24: Application: Expected benefit
Have
E [ Benefit ] = E [ Sales( P − Cost ) − F ] = E[ Sales × P ] − E [ Sales × Cost ] − F = E [ Sales × P ] − E [ Sales ]E[Cost ] − F = 700.000 - 80.000 × 7,50 - 30.000 = 70.000 E
Slide 25: Ex: conditional prob./exp.
Cars enter a gas station with interarrival times ≈ Exp (λ ) Each car brings an independent number of people distributed as :
p( j ) = P{Z 1 = j}, j ≥ 1
¿Distribution/mean of the number Y of people arriving in time interval [0, t)?
Slide 26: Ex: conditional prob./exp.
Know: number X of cars arriving in [0, t) is X ≈ P ( λt ) Poisson: Z i = number of passengers in car i Let X Then, Y = ∑ Zi
i =1
E[Y ] = E[ E[Y | X ]] = E E ∑ Zi | X
i =1
[[
X
]
Slide 27: Ex: Conditional expectation
Have
E [Y | X = j ] = E
j i =1
[
i =1
∑ Zi
j
|X = j
]
= ∑ E[ Z i | X = j ] = jE[ Z ]
So, by previous slide,
E [Y ] = E [ E[Y | X ]] = E [ XE [ Z 1 ]] = E [ X ]E [ Z 1 ] = λtE[ Z 1 ]
Slide 28: The buildings of uncertainty: Functions of random variables
Managers routinely input uncertain numbers into spreadsheet models:
customer satisfaction future demand for a product future workload requirements, …
Outputs are: functions of random variables Tempting: plug in “best guesses” Does it work? NO!! Instead: plug in ALL uncertain inputs!
Slide 29: Functions of random variables
If X, Y, Z, … are random variables and f(x, y, z, …) is a function, f(X, Y, Z, …) is a function of r.v. Ex: linear functions of r.v.:
f(X, Y, Z) = 5 X + 4 Y - 2 Z
The output of a probabilistic model is of the form f(X, Y, Z, …) Ex: profit(revenues, cost) = revenues - cost
Slide 30: The average of a function of random variables
Wanted: average value of f(X), E[f(X)] Can just plug in average values? Is it true
E[f(X)]=f(E[X])? NO!! In general, E[f(X)] distinct from f(E[X]) !
When are they equal?
Slide 31: Averages of functions of r.v.
A sobering counterexample: Consider a drunk, wandering left and right from the middle of a highway in heavy traffic. Take: X = drunk’s left-right position; f(X) = drunk’s fate (A/D) What is f(E[X])? What is E[f(X)]?
Slide 32: Averages of functions of r.v.
We can relate E[f(X)] with f(E[X]) under certain conditions: Jensen’s inequality: if f(x) is convex, then E[f(X)] >= f(E[X])
So, then can calculate lower bound What is the intuition?
Slide 33: Simulation: estimating E[f(X)]
If cannot obtain µ = E[ f ( X )] analytically, estimate it with Monte Carlo simulation Generate sample X1, …, Xn Estimate is: 1n
µn = ˆ
n j =1
∑
f (X j)
How many trials are enough?
Slide 34: How many trials are enough?
Markov inequality: Let Y >= r.v., and a > 0. Then,
E[Y ] P{Y ≥ a} ≤ a
Useful consequence for simulation: 1 P{| X − µ |≥ kσ } ≤ 2 k 2 if µ = E [ X ], σ = Var[ X ]
Slide 35: Optimization under under uncertainty
Ex: Let f(X,a) be the benefit in an inventory system, under random demand X, with inventory level a Wanted: max E[f(X, a)] over feasible a How to do it? Analysis: Newsboy’s model Parameterized simulation: vary a Another view: Policy optimization
Slide 36: More references
Ross, S.M. Stochastic Processes. Wiley, 1983. Feller, W. An Introduction to Probability Theory and its Applications. Wiley, 1957. Savage, S. Insight.xla: Business Analysis Software, 1998. Bernstein, P. Against the Gods: The Remarkable Story of Risk. Wiley, 1996.
