Simulation o For a maximization (minimization) problem, move the arbitrary

 Monte Carlo Simulation Process: Monte Carlo technique is a objective function away from (towards) (0,0) until further
movement would take the line completely out of the feasible region
mathematical process for selecting numbers randomly from a
probability distribution for use in a trial run of a simulation model
 Random Numbers: Uniformly distributed – Usually between 0 and
1. Generated in such a way that every possible number within the
interval has an equal chance of occurring. No discernible pattern,
appears fully random. In Excel, the function = RAND().
 Random Variates
o Definition: Particular outcomes of a random variable that are
generated from a probability distribution. Random variates are
assigned proportional to relative frequency of random variables we
 Binding constraint gets satisfied as an equality at optimality
wish to generate. Correspondence between random variates and
 Non-binding constraint gets satisfied as an inequality at
actual outcomes is key to valid, credible simulation models!
optimality
 DISCRETE Distributions: General Approach
o Random variates for DISCRETE distributions can be obtained  Advertising Mix - Example
using LOOKUP TABLES
o Example: Demand = {0,1,2,3,4} with probabilities:
 P(0) = 0.2, P(1) = 0.4, P(2) = 0.2, P(3) = 0.1, P(4) = 0.1
Lower Bound Upper Bound Random Variate
0 0.2 0
0.2 0.6 1
0.6 0.8 2
0.8 0.9 3
0.9 1 4
o Generate random number r, and find the corresponding random
variate up in the lookup table
 Ex: r = 0.2630 generates the random variate of 1 Linear Programming – Math Required for Solving Graphically
 CONTINUOUS Distributions: UNIFORM  Determining point of intersection of two straight lines
o Cumulative distribution, F(x) = (x – a) / (b – a) o EQN 1: 5x + 4y = 20, EQN 2: 3x + 5y = 15
 Where a < b  Multiply both sides of EQN by 3 and EQN 2 by 5
o F(x) lies between 0 and 1. Let F(x) take a random value between – o EQN 3: 15x + 12y = 60, EQN 4: 15x + 25y = 75
and 1 which is generated using the function rand().  Subtract EQN 3 from EQN 4 to eliminate x variable
 Thus, rand() = (x-a)/(b-a) or x = a + (b-a) * rand() o 13y = 15 or y = 15/13 = 1.115
o To generate a random observation from the uniform distribution,  Substitute y = 15/13 back into EQN 1
with values between a and b equally likely: o 5x + 60/13 = 20 or x = 40/13 or 3.09
 x = a + (b - a) * RAND()  Thus, Point of Intersection is:
 Ex: For a uniform distribution between 15 and 25 minutes o (1.115, 3.08)
o x = 15 + (25 – 15) * RAND() Linear Programming – Types of Solutions
 CONTINOUS Distributions: EXPONENTIAL
o Probability density function  1. Unique Optimal
 𝒇(𝒙) = 𝝀𝒆 𝒙𝝀
o Cumulative distribution function
 𝑭(𝒙) = 𝟏 − 𝒆 𝒙𝝀
o To generate a random observation from the exponential
distribution:
 𝑿 = −(𝒎𝒆𝒂𝒏) ∗ 𝒍𝒏(𝑹𝑨𝑵𝑫())
o 𝒙 = −(𝟏/𝝀)𝒍𝒏(𝒓𝒂𝒏𝒅())  Budgeting – Example
 Statistical Analysis for Simulation Results
o Outcomes of simulation modelling are statistical measures such as
averages (expected values), standard deviations, ranges, etc.
o Statistical results are typically subjected to additional statistical
analysis to determine their degree of accuracy
o Confidence intervals can be developed for the analysis of the
statistical validity of simulation results
 Confidence Interval for Mean
o If number of replications is less than 200:  2. Alternate Optimal
𝒔
 𝒙 ± 𝒕𝒏 𝟏,𝟏 𝒂/𝟐
√𝒏
 x = Mean (obtained from the simulation model)
 s = Standard deviation (obtained from the simulation model)
 a = Significance level
 n = Number of replications
 When the number of replication is 200 or greater, the t distribution
can be approximated from the Normal distribution:  Product Mixing – Example
𝒔
 𝒙 ± 𝒁𝒂/𝟐
√𝒏
o Ex: 95% Confidence Interval = Sample Mean +/- (1.96)(St. Dev
of the sample (s) / Square root of sample size (n))
 We can be 95% confidence that the true population mean will
be between the upper confidence limit and the lower
confidence limit
o Common Confidence Level  Z-Score  3. Unbounded Problem
 90%  1.645, 95%  1.96, 98%  2.33, 99%  2.575
 Area = (1 + CL) / 2 = Z Score
 Determining Number of Replications (n)
o Recall from statistics that the sample size, n, needed to have a
confidence interval with a desired margin of error is:
 𝑛 = (2𝑍 / 𝑠/𝑀𝐸)
o Hence, the number of replications needed to have a confidence
interval of width W is:
 𝒏 = (𝟐 ∗ 𝒁𝒂/𝟐 ∗ 𝒔/𝑾) 𝟐  Staff Scheduling – Example
 Note: For the purposes of this course, we will always use Z (not t
distribution) to determine number of replications
Linear Programming - Graphical Solution
 1. Determine the feasible region
o Plot a constraint line for each constraint  4. Infeasible Problem
o For each constraint line, determine the feasible side
o Identify the set of solutions that satisfy all the constraints
 2. Corner Points
o Determine the corner points of the feasible region
o Evaluate the objective function at each corner point and choose
the corner point that maximizes (minimizes) the objective
function
 Investment Allocation – Example

Linear Programming – Formulation

 Types of Functional Constraints

 2. Arbitrary Objective Function (Alternate Approach)

o Identify an arbitrary objective function
 Blending – Example  All variables are restricted to be integer values, X >= 0 and integer
o Mixed Integer problems
 Some variables are restricted to be integer values
o Binary Variable problems
 All variables are restricted to be either 0 or 1; 0 =< X =< 1 and
integer
 Possible Integer Programming Outcomes
o Unique Optimal solutions
o Alternate Optimal solutions
 Although does not imply infinite # of solutions
o Unbounded problem
o Infeasible problem
 Solving Integer Programming Problems
o Difficult to solve relative to Linear programs
o If LP solution is an integer value:
 Limiting the decision variables to integer numbers will not change
o Assignment Problems the optimal solution (optimal solution is same if formatted as IP)
 Multi-Period Scheduling - Example o Solution Methods:
 LP Relaxation Method
 Complete Enumeration
 Computer Solution
 LP Relaxation
o Relationship between LP and IP:
 The optimal solution is only as good as, or worse (never better)
than the LP optimal solution
 Max Problems: OFV(LP) >= OFV(IP)
 Min Problems: OFV(LP) <= OFV(IP)
 Fewer feasible solutions for an IP than there are for LP models,
the solutions will be very sensitive to changes in input parameters
o Process:
 Find regular LP solution and simply round to nearest integer value
(could also truncate, or always round up/down depending on
nature of the problem)
 Solution may be far from optimal; works best for large decision
Linear Programming – Network Flow Problems variable values
 Caution: Rounding can lead to poor or even infeasible solutions!

 Minimum Cost Flow Problems

o Transportation Problems
 Maximum Flow Problems
o Assumptions  Complete Enumeration
 All flow through the network originates at source nodes and o Exhaustive check of all possible solutions
terminates at destination (sink) nodes o Not feasible for large problems
 All the remaining nodes are transshipment nodes
 Flow through an arc is only allowed in the direction indicated by
the arrowhead, where the maximum amount of flow is given by
the capacity of that arc
 At the source, all arcs point away from the node. At the
destination (sink), all arcs point into the node
 The objective is to maximize the total amount of flow from the
source to the destination (sink). This amount is measured in either
of two equivalent ways: either the amount leaving the source or
the amount entering the destination.

 Common Logical Constraints

o Binary: Xi = 1 if project i is selected, 0 otherwise; i = 1,…,n
 At most k out of n projects will be selected:
o Si=1,…,n Xi ≤ k
 Exactly k out of n projects will be selected:
o Si=1,…,n Xi = k
 Projects i & k are mutually exclusive (if you select i, you cannot
select k):
o Xi + X k ≤ 1
 Must select at least one of projects i or k (if you do not select
 Shortest Path Problems project i, then you must select project k)
o Assumptions o Xi + X k ≥ 1
You need to choose a path through the network that starts at a
certain node, called the origin, and ends at another certain node,
called the destination.
 The lines connecting certain pairs of nodes are links (which allow
travel in either direction), or arcs (which only permit travel in one
direction).
 Associated with each link (or arc) is a nonnegative number called
its length.
 The objective is to find the shortest path (the path with the
minimum total length) from the origin to the destination.

o Transshipment Problems

Integer Programming – Formulation

 Decision Variables
o Integer Variable: A decision variable that can only be integer
values (whole numbers)
o Binary Variable: A decision variable that is restricted to be either 0
or 1
 Well suited for modelling yes-or-no decisions and representing
logical constraints
 Types of Integer Programming Problems
o Pure Integer problems