IE 413 Midterm 2 Example Problems
• The interarrival time for entities entering a system follows an exponential distribution where the mean time between arrivals equals 15 minutes. A server with a capacity of 2 will take 10 minutes with probability 0.7 and 30 minutes with probability 0.3. The entity exits the system after being processed by the server.
Let Tn be the simulation time of the nth state transition. The system state X(Tn) is the number of entities at the server. The state includes entities who are being processed by the server.
The following uniform random numbers are generated for the interarrival times: 0.99, 0.25, 0.32, 0.55, 0.40
The following uniform random numbers are generated for the processing times: 0.95, 0.52, 0.29, 0.01
Assume the simulation starts at clock time = 0 with no entities in the system. What is the value of Tn, the time when the third entity leaves the system? What is the value of n for when the third entity leaves the system?
This solution assumes that if U < 0.7, then service time is 10 minutes. n Tn X(Tn) Cn,1 = arrival Cn,2 = server (1) Cn,3 = server (2) Next event 0 0 0 -ln(1-.99)/(1/15) = 69.1 e1 1 69.1 1 T2 = -ln(1-.25)/(1/15) = 4.3 0.95 > 0.7 30
e1
2
73.4
2
-ln(1-.32)/(1/15) = 5.8
25.7
0.52 < 0.7 10
e1
3
79.2
3
-ln(1-.55)/(1/15) = 10.4
19.9
4.2
e3
4
83.4
2
6.2
15.7
0.29 < 0.7 10
e1
5
89.6
3
-ln(1-.4)/(1/15) = 7.7
9.5
3.8
e3
6
93.4
2
3.9
5.7
0.01 < 0.7 10
e1
The third entity leaves at 93.4 minutes. This occurs at the 6th state transition. This solution assumes “third entity” means the third entity to enter the system.
• Consider the following pdf
and the corresponding cdf
for .
Assume you can generate a uniform random number between 0 and 1. Write down the equation that enables you to generate based on .
U = (x/5) ^ 3
U ^ (1/3) = x/5
x = 5*U ^ (1/3)
• What distributions would you choose to simulate the time it will take you to complete this exam if the maximum amount of time is 2 hours? Write down the names of two (2) distributions?
You need to choose a distribution with an upper and lower bound.
Beta or PERT (same distribution so listing both is not correct)
Triangle
Uniform
• After a ship arrives in a simulation model, you want to determine the type of ship based on a discrete probability distribution. The probability mass function is given in the table below.
x
p(x)
Panamax Max
0.180
PostPanamax I
0.247
Post Panamax II
0.573
To generate a random deviate from this distribution to determine which ship type arrived, you generate a random uniform number 0.191 from U(0,1). Which type of ship has arrived?
Look at cumulative probabilities.
If U < 0.180, choose Panamax Max
Else if U < 0.180+0.247 = 0.427 choose PostPanamax I
Else choose Post Panamax II
Since U = 0.191, choose PostPanamax I
• Two types of entities can arrive into a system. The arrival time in minutes of the first type of entity follows a triangular distribution with minimum , most likely , and maximum . The arrival time in minutes of the second type of entity follows a Weibull distribution with shape and scale . Two uniform random numbers are generated to simulate the arrival times of each type: for the first type and for the second type. Which entity will arrive first, and what is the time that the entity arrives?
Recall the pdf of the triangular distribution is:
and the cdf of a triangular distribution is:
Recall the pdf of the Weibull distribution is:
and the cdf of the Weibull distribution is:
Inverse of triangle distribution
X = sqrt[U*(b-a)*(m-a)] + a or b – sqrt[(1-U)*(b-a)*(m-a)]
If U = 0.3, X = sqrt[0.3*(15-2)*(10-2)] + 2 = 7.59 or 15-sqrt[(1-.3)*(15-2)*(10-2)] = 6.47
Since both values are less than m = 10, choose first expression and time of first type = 7.59
Inverse of Weibull distribution
X = beta* [-ln(1-U)]^(1/alpha)
If U = 0.4, X = 4*[-ln(1-.4)]^(1/2) = 2.86
The time of the first arrival is 2.86 minutes and it is entity of type 2.
Expect two problem where you have to model a scenario as a Markov chain and to the relevant calculation in R. In addition to answering the questions, make sure that you can characterize each Markov chain E.g., is it ergodic, absorbing, irreducible, periodic?
• You work for a sports drink company that currently has 70% market-share versus 30% share for your only competitor in the market. Customers of both companies sometime switch their preferred brand, and your marketing department believes that on a quarterly (three-month) basis, about 90% of your customers stay with your product whereas 10% switch their preferred brand. On the other hand, only about 5% of your competitor’s customers switch their preferred brand to yours every quarter (three months). Given the competitor’s better customer loyalty, the company is concerned about declining market share.
• Model this system as a discrete time Markov chain.
My product Competitor
My product 0.9 0.1
Competitor 0.05 0.95
Initial state = [.7 .3]
This Markov chain is aperiodic, positive recurrent, ergodic irreducible
• What will be your market share be in one year?
Initial state * P * P * P * P = [0.52 0.48]. The market share will be 52% after one year.
If your company improves customer loyalty so that only 5% of customers switch to the competitor each quarter, what will your market share be in 12 months?
0.63
Aperiodic, positive recurrent ergodic
Irreducible because it is possible to go from every state to another state
• On a highway three out of every four trucks are followed by a car, while only one out of every five cars is followed by a truck.
• Model the type of vehicle on the road as a Markov chain.
Truck car
Truck 0.25 0.75
Car 0.2 0.8
Aperiodic, positive recurrent ergodic
Irreducible because it is possible to go from every state to another state
• Using your Markov chain model, determine what fraction of vehicles on the road are trucks.
Calculating steady-state probabilities (either by multiplying the transition matrix many, many times or by using markovchain library in R)
0.21 truck and 0.79 car
• Consider a system with two identical machines. Each machine has an identical probability of failing in a particular day. There is no repair and the machines are independent of each other.
• Model the number of failures as a Markov chain
State = number of machines working
0 1 2
0 1 0 0
1 0.1 0.9 0
2 0.01 0.18 0.81
State 0 is absorbing and positive recurrent, States 1 and 2 are transient non-ergodic
All states are aperiodic
Absorbing and reducible Markov Chain (there is 0 probability of going from state 0 to state 1 or 2)
• Assume that both machines are working. Using your Markov chain model, determine the probability that one of the machines has failed and the other is operational on after two days.
Initial state = [0 0 1]
Initial state * P * P = [0.036, 0.31, 0.66]
There is a 0.31 probability that one machine is failed
• An automated guided vehicle (AGV) transports parts between four locations: a release station A, a machining station B, a machining station C, and an output buffer D. The movement of the AGV can be described as making trips from location to location on requests to move parts. More specifically,
• If the AGV is at the output buffer, it is equally likely to move next to any of the other locations: A,B or C.
• If the AGV is at the release station, it is equally likely to move next to machining station B or C.
• If the AGV is waiting at either of the machining stations, it is equally likely to move to any of the other three stations.
Model this system as a discrete time Markov chain to answer the following:
A B C D
A 0 1/2 1/2 0
B 1/3 0 1/3 1/3
C 1/3 1/3 0 1/3
D 1/3 1/3 1/3 0
Multiplying the transition matrices together once then twice then three times seems to indicate there is no period.
All states are aperiodic and positive recurrent ergodic
Irreduciblepi
• If the AGV is currently at machining station B, what is the probability that it will be at the output buffer after five trips?
Initial state = [0 1 0 0]
Initial state * P * P * P * P * P = [0.25 0.28 0.28 0.19]
Probability that output buffer is 0.19
• What is the long-run fraction of time the AGV spends traveling to the output buffer?
Steady-state probability = 0.19