Chapter 20 - Simulation Flashcards
Define simulation
Simulations is about imitating some operation of an entire system or process.
Name an example of simulation
Wind tunnel.
It is important to understand that things we can simulate is possible to do mathematically, but it quickly becomes so difficult and challenging that it is automatically dropped. For instance, we could use the laws of physics to calculate the wind effects, but it is so much easier to simulate it.
What is OR concerned about regarding simulation?
They are not building physical models of cars etc.
Rather, they are focused on developing procedures/operating procedures for some stochastic system. I.e. OR tries to find out how systems operate.
Rather than using wind tunnels to measure perofrmance, we typically run simulations from random events from probability distributions
What do we need to do simulation in OR?
This checklist:
1) A definition of the state of the system. In queueing, this state is the number of customers currently in the system.
2) Identify the possible states in the system. For instance, in queueing theory, this could be how many states we are allowed to have (max capacity queue).
3) identify the possible events that impact the system. This is, in queueing, the arrivals and completions.
4) A provision for the simulation clock. Recall that time can have fixed increments or time-by-event.
5) A method for randomly generating the events so that it mimics the actual operations of the system we are modelling.
6) A formula for identifying state transitions that are generated by the various events.
Elaborate on the difference between continuous events and discrete events
Discrete events happen all at once. For instance, a new arrival in our store. we dont say that the arrival is gradually arriving. We say that the person has either arrived, or he has not arrived.
Continuous events happen conttnuously. This means that the events are sort of transitional.
An example of continuous event, is airplane positioning during a flight. The position of the plane is in constant motion, and will therefore always change position.
What is a random number generator?
A random number generator is an algorithm that produce sequences of numbers that follow a specified probability distribution and have the appearence of being random.
We typically just draw “random numbers” from a uniform distribution. This just means that each number of equally likely.
Briefly, how do we generate random numbers+
We generate random integer, and then convert this into a real number by following this transformation:
if we want to have the interval [0,1], we take the random integer, and divide the number by the maximum size /length of the integer value domain. If we draw random integers from [0, 100], and we get 33, we get 33/100 as the random number.
If we want to convert to some arbitrary interval, we use the following formula:
y = x(b-a) + a
NB: Note that the formula above accepts CONTINUOUS values on the interval [0,1], and then maps these values to [a, b].
What are the most common random number generator “methods” classifeid as?
Congruential methods
What is the congruential method we care about?
Mixed congruential method. It is mixed because it incorporates both mutliplication and addition.
Elaborate on the mixed congruential method
The method generates a sequence of pseudo-random integer numbers over some specified range. This range is from 0 to m-1. We dont get “m”, because this would not give any “rest” in the expression.
The mixed congruential method always calculate the next random integer in the sequence by using the previous one. it is therefore recursive.
The first number used to initialize the process, is called the “seed”. This seed is important to us, because it allows us to reproduce the exact same sequence of random numbers.
We need to be careful when choosing values for a and c. First of all, they must be non-negative and smaller than “m”. However, they also need to satisfy other requirements if they are to be as good as we want them to be. In particular, we WANT the sequence of m random integers (from 0 to m-1) to be a sequence where each random integer appear only ONCE during the m values. This is because, if we find repeated values, the algorithm will “restart” the cycle, and deliver results that we have already used. We dont want this. Recall that the previous value is the input for the next iteration. Therefore, if we ever find a value that we have previously used as input, we are fucked.
What is “cycle length”?
Cycle length refers to the sequence of different random integers generated by some random integer number generator.
Ideally, we want the cycle length to be equal to m.
How do we convert from discrete integer to continuous nubmer?
Number = [randomInteger + 1/2] / [m]
the “1/2” is because discrete values are not centered correctly. This is important if m is small. If m is very large, this centering is not that important. However, I dont think it hurts to add it.
Given a random sequence of numbers, how can we generate a random sequence of events from a probability distribution?
3 methods:
1) Direkte oppslag
2) Inverse transformation method
3) Acceptance/rejection method
Elaborate on “direkte oppslag”
This is a thing that can work for simple cases.
it also only works well for discrete distributions.
We use a series of random numbers, and allocate them to the different outcomes from the probability distribution that we are looking at.
We would allocate random numbers so that the number of random numbers together create the relative weighting of the actual outcome.
Elaborate on inverse transformation method
Works on both discrete and continuous probability distributions.
Procedure is simple:
We first need the cumulative distribution, F(x) = P(X<x)
Then we set it equal to “r”, which represent our random number between 0 and 1.
We solve for x.
x = F^(-1)(r)
