14
Simulation
14.1 INTRODUCTION
There are many problems of real life which cannot be represented mathematically due to the stochastic nature of the problem, the complexity in problem formulation, or the conflicting ideas needed to properly describe the problem under study. In such situations simulations can be used.
Simulation analysis is a natural and logical extension of the analytical and mathematical techniques used for solving problems in Operations Research. Simulation, which can be called management laboratory, determines the effect of alternate policies without disturbing the real system. Recent advances in simulation methodologies, software availability, and technical developments have made this technique one of the most widely used and popularly accepted tools in Operations research and System Analysis. Simulation helps us in deciding the best policy with the prior assurance that its implementation will certainly prove to be beneficial to the organisation.
The technique of simulation has long been used by designers and analysis in physical sciences and it promises to become an important tool for tackling the complicated problems of managerial decision making. Scale modes of machine have been tested in wind tunnels to determine their aerodynamic characteristics. The first important application of simulation was made by Jon Von Neumann and Stanni-slaw Ulam for studying the tedious behavior of neutrons in a nuclear shielding problem which was too complex for mathematical analysis. With the remarkable success of the technique on the neutron problem, simulation become popular and found many applications in business and industry, Development of the digital computer in the 1950s is further responsible for the rapid progress made by simulation techniques.
Simulation is one of the easiest tools of management science to use, but one the hardest to apply properly and perhaps the most difficult from which to draw accurate conclusions, Due to widespread applications of digital computers, simulation becomes readily available to most engineers and managers engaged in Operations Research projects. Regardless of these drawbacks, simulation is a useful technique and one which is specially suitable for complicated Operations Research and System Analysis problems.
The purpose of this chapter is to examine the process of simulations and the necessary tools to perform such analysis, Special emphasis is given to the Monte-Carlo method of simulation. Some simplex examples are discussed to explain the Monte-Carlo technique. To obtain reliable results, the use of computer is very essential in all simulation technique; the numerical examples have solved by hand computation only.
14.1.1 What is Simulation
Simulation is an imitation of reality.
Some Examples of Simulation:
- Children’s cycling park with various crossings and signals is a simulated model of the city traffic system.
- Testing an aircraft model in a wind tunnel.
- Planetarium: To determine the behavior of a real system in true environments a number of experiments are performed on simulated models either in the laboratories or in the computer itself.
- Training of pilots: A computer directs a student’s handling of the controls in a simulated flight deck. The instruments are then operated by the computer to give the same readings as in a real flight. An instructor can intervene with ‘catastrophes’ like an engine failure or a storm and a television camera is moved over a model of some countryside to give the trainee visual feedback of how the aircraft is behaving.
- TV games: The combination of computing and simulation has resulted in the production of TV games. Players interrupt the way a computer program moves various images around the screen with a keyboard or hand-held controller. The computer incorporates their responses into these movements in accordance with the rules of the particular game. Incidentally, such programs make extensive use of random numbers to find the deflection of tennis balls, the positioning of hostile space ships, and others.
- Chess: Chess is a non-probabilistic simulation of a fight between black and white armies.
- Snakes and ladders game: The game of snakes and ladders was initially proposed to simulate the moral progress of the players who moved up ladders when they were ‘good’ and fell down snakes, indicating temptation, when they were bad. Like in many other board games, dice are used as random generators.
In all these examples, reality is imitated to see what might happen under real operating conditions. This imitation of reality, which may be in the physical form or in the form of mathematical equations may be called simulation.
The simple examples cited above are of simulating the reality in physical form, and are referred to as analogue simulation.
14.1.2 Definitions of Simulation
Following are a few definitions of simulation.
- Simulation is a representation of reality through the use of a model or other device which will react in the same manner as reality under a given set of conditions.
- Simulation is the use of a system model that has the designed characteristics of reality in order to produce the essence of actual operation.
- According to Donald G. Malcolm, a simulated model may be defined as one which depicts the working of a large-scale system of men, machines, materials and information operating over a period of time in a simulated environment of the actual real world conditions.
- According to Naylor et al. (1966), simulation is a numerical technique for conducting experiments on a digital computer, which involves certain types of mathematical and logical relationships necessary to describe the behavior and structure of a complex real world system over extended periods of time.
- Churchman has defined simulation as follows:
“X simulates Y ” is true if and only if:
- X and Y are formal systems;
- Y is taken to be the real system;
- X is taken to be a approximation to the real system; and
- The rules of validity in X are non-error-free, otherwise X will become the real system.
14.1.3 Types of Simulation
Simulation is mainly of two types.
- Analogue (environmental) simulations: The simple examples cited in 14.1.1 are of simulating the reality in physical form, which we refer as analogue (or environmental) simulation.
- Computer, system or digital simulation: For complex and intricate problems of managerial decision-making, analogue simulations may not be applicable; moreover, actual experimentation with the system may also be uneconomical. In such situations, the complex system is formulated into a mathematical model for which a computer program is developed and then the problem is solved using a high-speed electronic computer. Such type of simulation is called computer simulation, system simulation or digital simulation. In other words, it is the representation of a system in a form acceptable to a digital computer as opposed to an analogue computer. Electronic circuit simulation uses mathematical models to replicate the behaviour of an electronic device or circuit. Simulation software allows for modelling of circuit operation and is an invaluable analysis tool. Simulating a circuit’s behaviour before actually building it can greatly improve design efficiency by making fault designs and providing insight into the behaviour of the electronic circuit designs.
Simulation models can be classified into following four categories: Deterministic models: In these models input and output variables are not permitted to be random and models are described by exact functional relationship.
Stochastic models: In these models at least one of the variables or functional relationship is given by probability functions.
Static models: These models do not take variable time into consideration.
Dynamic models: These models deal with time varying interaction.
14.1.4 Why to Use Simulation
For solving various types of managerial decision-making problems in operations research, the following techniques are adopted:
- Scientific method,
- Analytical method, and
- Interactive method.
But each method has its own drawbacks and limitations.
- Drawbacks of Scientific Method: The scientific method has the following limitations and difficulties:
- It may be either impossible or extremely costly to observe certain processes in real-life situations.
- The observed system may be so complex that it may be impossible to describe it in terms of a set of mathematical equations.
- Event though a mathematical model can be formulated to describe the system under study, a straightforward analytical solution may not be available. Such situations may arise in complex queueing problems, job-shop problems, high order difference equations, complicated stochastic models, multi-integral problems, and so on.
- It may be either impossible or very costly to perform validating experiments on mathematical models describing the system.
On account of these drawbacks, the scientific method cannot be used to solve complex managerial decision-making processes.
- Drawbacks of Analytical Method: Analytical techniques used in dynamic programming, queueing theory, network models, and hence forth, are not sufficient to tackle problems requiring data analysis due to the following limitations:
- Dynamic programming models can be used to determine optimal strategies taking into account the uncertainties and can analyse multi-period planning problems. But, it has its own shortcomings. Dynamic programming models can only be used to tackle very simple situations involving very few variables. If the number of static variables becomes larger, the computation becomes complex and difficult.
- Similar limitations also hold good for other mathematical models such as inventory and waiting lines. Only small-scale systems are amenable to these models. But by making a number of assumptions the systems are simplified to such an extent that in many cases the results thus obtained are only rough approximations.
- Drawbacks of Iterative method
- In linear programming models, we assume that the data does not change over the entire planning horizon. This is a one–time decision process and assumes average values for the decision variables. If the planning horizon is long, say 15 years, the multi-period linear programming model may deal with the yearly averaged data, but will not take into account the variables over the months and weeks. Consequently, months to month and week to week operations are left implicit.
- Linear programming assumes that the data should be known with certainly. In many real-life situations, the uncertainties about the data are such that they cannot be ignored. In case the uncertainty relates to only a few variables, sensitivity analysis can be used to determine its effect on the decision. But in situations where uncertainty pervades the entire model, the sensitivity analysis may become too cumbersome and computationally difficult to determine the impact of uncertainty on the recommended plan.
From above mentioned drawbacks, we conclude that whenever characteristics like uncertainty, complexity, dynamic interaction between the decision and subsequent event, and the need to develop detailed procedures and finely divided time intervals are combined together in one situation, then the model becomes too complex to be solved by any of the techniques of mathematical programming and probabilistic models. Such complex models must be analysed by some other kind of quantitative technique which may give accurate and reliable results. Many new techniques have been tested but among all, the best available is simulation. In general, the simulation technique is a dependable tool in situations where mathematical analysis is either too complex or too expensive.
14.1.5 Limitations of Simulation
- Quantification of the variables may be difficult.
- Large number of variables makes simulation unwieldy and difficult.
- Simulation may not yield optimum results.
- It may not be economic.
- It may not always be less time consuming.
- One cannot rely too much on the results obtained from simulation models.
14.1.6 Advantages of Simulation
- It is less complicated mathematically.
- It is flexible.
- It can be modified to suit the changing environments of the situation.
- It can be used for training purposes.
- It may be less expensive in several real-world situations.
- It may be less time consuming.
14.1.7 Phases of Simulation Model
A simulation model consists of two basic phases:
Phase I: Data Generation Data generation involves the sample observation of variables and can be carried out with the help of any of the following methods:
- Using random numbers,
- resorting to mechanical devices, and
- Using electronic computers.
Phase II: Book Keeping The book-keeping phase of a simulation model deals with updating the system when new events occur, monitoring and recording the system states as and when they change, and keeping track of qualities of our interest (such as, idle time and waiting time) to compute the measures of effectiveness.
Steps in Simulation Process:
Step 1: Identify the measure of effectiveness.
Step 2: Decide the variables which influence the measure of effectiveness, choose those variables which affect the measure of effectiveness significantly.
Step 3: Determine the probability distribution for each variable in step 2 and construct the cumulative probability distribution.
Step 4: Choose an appropriate set of random numbers.
Step 5: Consider each random number as a decimal value of the game cumulative probability distribution.
Step 6: Use the simulated values so generated into the formula derived from the measure of effectiveness.
Step 7: Repeat (5) and (6) until the sample is large enough to arrive at a satisfactory and reliable decision.
14.2 EVENT TYPE SIMULATION
The event-type simulation can be understood with the following two examples:
Consider a situation where customers arrive at a one-man barber shop for cutting their hair. The problem is to analyse the system in order to evaluate the quality of service and the economic feasibility of offering the service. To measure the quality of service, assess the average waiting time per customer and the percentage of time the barber remains idle. Construct the simulation model.
Formulation of the model: To formulate the model of this system we observe that the changes involved in the analysis of the system can occur only when a customer arrives for service or departs after completion of service. When a customer reaches the barber’s shop, he will have to wait if the server (barber) is busy. On the other hand, departure of a customer after the completion of his service (hair cut) indicates that the server is available to serve waiting customers, if present. From this, we conclude that only two types of events can occur, that is, an arrival event and a departure event. It shows that as the simulator progresses on the time scale, we must pay due attention to one system whenever an event occurs.
FIGURE 14.1
Let us denote the arrival event by E_{a}, the departure event by E_{d}, and the simulated period (time span) by T. The simulator starts at time 0 and first progresses up to t = t_{1} then t = t_{2}, and so on until the entire simulated period T is covered. Fig 14.1 shows the occurrences of events E_{a} and E_{d} over the time period T, where the simulation starts by generating E_{a} to t_{1}. In the beginning, when the service facility is free, the service of the customer will begin immediately. Then, the following two new events must be generated:
- the next arrival may occur
- the service of the customer may be completed.
The next arrival can be determined from the inter-arrival time. Thus, E_{a} is determined at time t_{2}. The departure time of the customer in service is obtained from service time and from this event E_{d} is generated at time t_{3}. Now, both the events E_{a} (at t_{1}) and E_{d} (at t_{3}) are listed in chronological order, so that the simulator may recognise that the event E_{a} occur before E_{d}. The next event under consideration is E_{a} at t_{2} and at this moment E_{a} at t is deleted from the stored list (because of past event). The event E_{a} at t_{2} now generates E_{a} at t_{4}. Since the service facility is busy, the new arriving customer E_{a} (at t_{2}) joins a waiting line. Now, E_{a} at t_{2} is deleted from the list and E_{d} at t_{3} is considered next. At this time a customer is taken from the waiting line and departure event E_{d} at t_{5} is generated. This process is repeated until the entire simulated period T is covered.
Example 2
Customers arrive at a milk booth for the required service. Assume that inter-arrival and service time are constants and given by 1.5 and 4 minutes, respectively. Simulate the system by hand computation for 14 minutes. (i) What is the waiting time per customer? (ii) What is the percentage idle time for the facility? (Assume that the system starts at t = 0).
Solution: First customer starts getting the service. So, its departure time becomes t = 0 + 4 = minutes. ext event (arrival) occurs at t = 0 +15 = 15 minutes, which is listed before d1 at t = 4. The facility is still busy; the 2^{nd} customer stands in the queue and the 1st one is to be considered in this queue. The 3^{rd} arrival event a_{4} (customer) at t = 3.0 + 1.5 = 4.5. this event succeeds d_{1} at t = 4.
At this moment, the first customer departs leaving the servicing facility free. The 2^{nd} customer who was the first to join the queue now gets service. The waiting time is the time period from the moment he joined the queue until his service is started.
The process is repeated until the simulated period is completed. The results of the simulation are given in Table 14.1
TABLE 14.1
For customers who are yet to get service after 14 minutes the waiting times are given in Table 14.2
TABLE 14.2
Customer no. | Waiting time in minutes |
---|---|
5 | 14 − 6 = 8 |
6 | 14 − 7.5 = 6.5 |
7 | 14 − 9.0 = 5.0 |
8 | 14 − 10.5 = 3.5 |
9 | 14 − 12.0 = 2.0 |
10 | 14 − 13.5 = 0.5 |
From this simulation table it is clear that
- Average waiting time for customer
- Average waiting time per customer for those who must wait = 45 minutes.
- Percentage idle time of the facility = 0%.
(since service facility is always busy)
14.3 GENERATION OF RANDOM NUMBERS (OR) DIGITS
Random numbers play a vital role in simulation models. In computer simulation, random numbers can be obtained by the following methods:
- Random numbers may be drawn from the random number table stored in the memory of the computer. This process, however, is neither practicable nor economical. It is a very slow process and the numbers occupy a large portion of the computer memory. Even on methodological grounds it is objectionable to use the same set of random numbers again and again. Therefore, several methods of generating random numbers internally by the computer have been evolved. The necessary formulae occupy relatively little space.
- An electronic device may be constructed as part of the digital computer to generate true random numbers. The method, however, is expensive.
- In the mid-square method of generating pseudo-random numbers, a four-digit number is taken. By squaring it a high digit figure is obtained from which the middle four digits are picked. This yields the second random number and the process is repeated and a sequence of pseudo-random numbers is obtained. For instance, if
x_{1} = 2421
then,
∴
x_{2} = 8612
∴
x_{3} = 1665
∴
x_{4} = 7722 and so on.
However, one may come across the following situations:
- The series may vanish because a random number obtained is 0000.
- A random number reproduces itself. For example, x_{7} = 8625, x_{8} = 8625, x_{9} = 8625.
- A loop occurs, for example, x_{11} = 6100, x_{12} = 2100, x_{13} = 4100, x_{14} = 8100, x_{15} = 6100 and the process continues in a circle.
- Pseudo-random numbers may also be generated by arithmetic operations. A frequently used method is the congruence method or the residue method, which is described by the expression
where, a, b and m are constants and r_{i}, r_{i + 1} are the i^{th} and (i + 1)^{th} random numbers. The expression implies multiplying of a by r_{i}, addition of b and then dividing by m. Then, r_{i} + 1 is the remainder or residue. To begin the process of random number generation, in addition to a, b and m, the value of r_{o} is also required. It may be any random number and is called seed.
The congruence random number generator may be of the additive, multiplicative or mixed type. Equation (14.3.1) gives the mixed type.
If a = 1, the equation (14.3.1) reduces to the additive type
If b = 0, the congruence method is called the multiplicative type
The multiplicative methods are considered better than the additive methods and as good as the mixed methods.
The selection of the values for the constants a, b and m is very important, because the length of the sequence of random numbers depends on it. It is not possible to generate a non-repeating sequence of numbers with these methods. However, a sufficiently long string of random numbers can be obtained by making a suitable selection of constants. Since the number r_{i + 1} can be predicted from r_{1} and the whole string of random numbers is reproducible, the numbers obtained are not truly random. They are called pseudo-random numbers and the method is termed as the pseudo-random number generator.
The validation of a pseudo-random number generator is very essential. A sequence of random numbers is considered to be adequately random if its uniformity is assured, and the successive numbers in the sequence are independent.
Generation of Random Numbers or Digits from Probability Distributions
There are a couple of methods to generate a random number based on a probability density function. These methods involve transforming a uniform random number in some way. Because of this, the methods work equally well in generating both pseudo-random and true random numbers. The first method, called the inversion method, involves integrating up to an area greater than or equal to the random number (which should be generated between 0 and 1 for proper distributions). The second method, called the acceptance–rejection method, involves choosing the x and y values and testing whether the function of x is greater than the y value. If it is so, the x value is accepted. Otherwise, the x value is rejected and the algorithm tries again.
The Chi-square test of goodness of fit is employed to check if the sequence of numbers is generated from a(0, 1) uniform distribution. The randomness or independence test is used to check that the successive numbers are not correlated. One of the most effective methods for this purpose is the poker test. Most computer systems have a sub-routine available for generating random numbers.
In inventory models, the variables include customer’s demand and delivery times, which may also be probabilistic. In this type of situations, for generating random numbers the manual method consisting of the following steps can be used.
- Collect the data related to the current problem.
- Construct a frequency distribution with this data.
- Construct the relative frequency distribution.
- Assign a coding system that relates the identified events to generate random numbers.
- Select a suitable method for obtaining the required random numbers.
- Match the random numbers to the assigned events and tabulate the results.
- Repeat step (vi) until the desired number of simulation runs has been generated.
MR Colour Lab uses an expensive grade of developing fluid when printing special colour portraits. Since the developing fluid cannot be stored for long periods, it is important to keep on hand only as much as is needed to fill anticipated demand. In the past few months, however, demand for the product has been fluctuating.
The owner has decided to simulate the demand for this service.
A study of MR Colour Lab appointment book resulted in the following frequency distribution:
The data was taken for a 100-day period, during which no more than five special prints were requested on any given day. Using the data given above, generate a 10-day sequence of demand values.
Step 1: Collect the data relevant to the current problem.
Step 2: Using the data of step 1, construct the frequency distribution.
Step 3: Construct the corresponding relative frequency distribution.
Daily demand Relative frequency Probability 0 10/100 0.10 1 20/100 0.20 2 40/100 0.40 3 20/100 0.20 4 6/100 0.06 5 4/100 0.04 Step 4: Given the relative frequency distribution of step 3, assign a coding system that relates the identified events to generated random numbers. This coding system is the device whereby, given a random number, a particular event will be specified.
The most practical coding system is one which assigns random numbers in proportion to the probability value. In this case, 10% of the random numbers will be assigned to a daily demand of zero, 20% to a daily demand of one, and 40% to a daily demand of two. In a similar manner, random numbers will be assigned to the remaining daily demand figures.
TABLE 14.3
Step 5: Select an appropriate method for generating the required random numbers. For the limited purpose of this example it is feasible to use a manual method such as the spinning arrow. To use the approach, we divide the face of a clock into 100 equal parts and number the parts from 00 to 99, inclusive, centre an arrow on the clock in such a way that it can spin freely. At each spin of the arrow, record the number to which it points when it stops. This is the generated random number. Each spin thus corresponds to the simulation run.
Step 6: Using the model selected I step 5, generate the random numbers to be used in the simulation, match these to the assigned events, and summarise the results in an appropriate table. Since the owner wants a 10-day simulation, it is necessary to spin the arrow 10 times and record the random number generated each time. Once the random numbers have been generated, then with reference to the coded assignment, Table 14.4 gives the value of the generated demand. For example, if 35 is the first number generated, it falls in the range 30-69 and thus corresponds to the event of a daily demand for two portraits. Result for the full 10-day simulation are summarised in Table 14.4
TABLE 14.4
Day number Generated random demand Generated demand 1 35 2 2 92 4 3 68 2 4 03 0 5 51 2 6 05 0 7 72 3 8 84 3 9 98 5 10 34 2 Step 7: Repeat step 6 until required number of simulation runs have been generated. Since the owner was only interested in one simulation run, this step is not required. However, if there were to be more than 10-day simulations, it would be necessary to repeat step 6 as needed.
Remark: The numbers generated by the computer are always predictable and reproducible and hence cannot be treated as random. For this reason they are called as pseudo-random numbers.
Example 2 Congruence Methods
- Mixed congruence method
r_{i + 1} = (ar_{i} + b)(module m)
Take
r_{0} = 1
r_{1} = (16 × 1 + 18) (modulo 23) = 11
r_{2} = (16 × 11 + 18) (modulo 23) = 10
r_{3} = (16 × 10 + 18) (modulo 23) = 17
r_{4} = (16 × 17 + 18) (modulo 23) = 14
r_{5} = (16 × 14 + 18) (modulo 23) = 12
r_{6} = (16 × 12 + 18) (modulo 23) = 3
r_{7} = (16 × 3 + 18) (modulo 23) = 20
r_{8} = (16 × 20 + 18) (modulo 23) = 16
r_{9} = (16 × 16 + 18) (modulo 23) = 21
r_{10} = (16 × 21 + 18) (modulo 23) = 9
r_{11} = (16 × 9 + 18) (modulo 23) = 1
The string of random numbers obtained is 1, 11, 10, 17, 14, 12, 3, 20, 16, 21, 9 after which the sequence starts repeating.
- Multiplicative congruential method
r_{i + 1} = 16r_{i} (module 23)
Put
r_{0} = 1
r_{1} = 16 × 1 (modulo 23) = 16
r_{2} = 16 × 16 (modulo 23) = 3
r_{3} = 16 × 3 (modulo 23) = 2
r_{4} = 16 × 2 (modulo 23) = 9
r_{5} = 16 × 9 (modulo 23) = 6
r_{6} = 16 × 6 (modulo 23) = 4
r_{7} = 16 × 4 (modulo 23) = 18
r_{8} = 16 × 18 (modulo 23) = 12
r_{9} = 16 × 12 (modulo 23) = 8
r_{10} = 16 × 8 (modulo 23) = 13
r_{11} = 16 × 13 (modulo 23) = 2
- Additive congruential method
r_{i + 1} = (r_{i} + 18) (module 23)
Put
r_{0} = 1
r_{1} = (1 + 18) (modulo 23) = 19
r_{2} = (19 + 18) (modulo 23) = 14
r_{3} = (14 + 18) (modulo 23) = 9
r_{4} = (9 + 18) (modulo 23) = 4
r_{5} = (4 + 18) (modulo 23) = 22
r_{6} = (22 + 18) (modulo 23) = 17
r_{7} = (17 + 18) (modulo 23) = 12
r_{8} = (12 + 18) (modulo 23) = 7
r_{9} = (7 + 18) (modulo 23) = 2
r_{10} = (2 + 18) (modulo 23) = 10
14.4 MONTE-CARLO METHOD OF SIMULATION
The Monte-Carlo method is a simulation technique in which statistical distribution functions are created by using a series of random numbers. This approach has the ability to develop many months or years of data in a matter of a few minutes on a digital computer. The method is generally used to solve problems which cannot be adequately represented by mathematical model, or where the solution of the model is not possible by analytical method.
Monte-Carlo simulation yields a solution which should be very close to the optimal, but not necessarily the exact solution. However, it should be not noted that this technique yields a solution that converges to the optimal or correct solution as the number of simulated trials lead to infinity.
Steps in Monte-Carlo simulation:
Step 1: Clearly define the problem
- Identify the objectives of the problem.
- Identify the main factors which have the greatest effect on the objectives of the problem.
Step 2: Construct an appropriate model
- Specify the variables and parameters of the model.
- Formulate the appropriate decision rules, that is, state the conditions under which the experiments is to be performed.
- Identify the type of distribution that will be used-models use either theoretical distributions or empirical distributions to state the patterns and the occurrence associated with the variables.
- Specify the manner in which time will change.
- Define the relationship between the variables and parameters.
Step 3: Prepare the model for experimentation
- Define the starting conditions for the simulation.
- Specify the number of runs of simulation to be made.
Step 4: Using step 1 to 3, experiment with the model
- Define a coding system that will correlate the factors defined in step 1 with the random numbers to be generated for the simulation.
- Select a random number generator and create the random numbers to be used in the simulation.
- Associate the generated random numbers with the factors identified in step 1 and coded in step 4(i).
Step 5: Summarise and examine the results obtained in step 4.
Step 6: Evaluate the results of the simulation.
Select the best course of action.
Example 1
Using simulation, find the value of π
Solution: Taking the origin O as the centre, draw an arc AB of unit random cutting the coordinate axes OX, OY at A and B and complete the square OACB as shown in the Fig. 14.2
FIGURE 14.2
Equation of arc AB is x^{2} + y^{2} = 1, 0 ≤ x ≤ 1, 0 ≤ y ≤ 1 and 0 ≤ x ≤ 1, 0 ≤ y ≤ 1 is nothing but all the points are inside and on the square OACB.
Using the random number table, select any two random numbers, say 0.8262 and 0.9586 and let x = 0.8262 and y = 0.9586. The point (0.8262, 0.9586) will lie inside or on the arc AB if x_{2} + y_{2} ≤ 1 or will be outside the arc and within the square if x_{2} + y_{2} > 1.
In this manner, a large number of pairs of random numbers are selected and whether the points representing the pairs lie in, on the arc or beyond the arc but inside is determined.
Let p be the total number of points considered (p pairs of random numbers are selected) and let q be the points which lie inside or on the arc.
Then, obviously,
Hence,
Larger the value of p, closer will be the value obtained to p.
Example 2
A tourist car operator finds that during the past few months the car’s use have varied so much that the cost of maintaining the car has varied considerably. During the past 200 days the demand for the car fluctuated as below:
Trips per week | Frequency |
0 | 16 |
1 | 24 |
2 | 30 |
3 | 60 |
4 | 40 |
5 | 30 |
Using random numbers simulate the demand for a 10-week period.
Solution: The tag-number allotted for various demand levels is shown in the Table 14.5.
TABLE 14.5
The simulated demand for the cars for the next 10 weeks is given in Table 14.6
TABLE 14.6
Week | Random number | Demand |
---|---|---|
1 | 82 | 4 |
2 | 95 | 5 |
3 | 18 | 1 |
4 | 96 | 5 |
5 | 20 | 2 |
6 | 84 | 4 |
7 | 56 | 3 |
8 | 11 | 1 |
9 | 52 | 3 |
10 | 03 | 0 |
Total demand = 28 cars.
Average demand = = 2.8 cars per week.
Example 3
Suppose that the sales of a particular item per day is Poisson with mean 5. Generate 20 days of sales by the Monte-Carlo method.
Solution: The cumulative distribution of sales is calculated on the basis of the information that sales have Poisson distribution with mean λ = 5.
The probability sales is given by
TABLE 14.7
r | Cumulative probability | Tag numbers |
---|---|---|
0 | 0.01 | 00–00 |
1 | 0.04 | 01–03 |
2 | 0.13 | 04–12 |
3 | 0.13 | 13–26 |
4 | 0.27 | 27–43 |
5 | 0.44 | 43–61 |
6 | 0.62 | 62–75 |
7 | 0.76 | 76–86 |
8 | 0.87 | 87–92 |
9 | 0.93 | 93–96 |
10 | 0.97 | 97–97 |
11 | 0.99 | 98–98 |
12 | 1.00 | 99–99 |
The simulated sales for the next 20 days is given in Table 14.8.
TABLE 14.8
14.5 APPLICATIONS TO QUEUEING PROBLEMS
Queueing theory provides techniques for determining measure of effectiveness, such as queue length, average waiting time, and so on, when the distribution of inter-arrival times and services times are known. If costs be assigned to waiting time of customers and idle time service facility, the problem of establishing a proper balance between these costs can be determined.
However, many queueing problems cannot be solved explicitly by analytical methods. In such cases, the only possible method of solution is to simulate the experiment. We illustrate the use of simulation in the study of queues by the following example.
Example 1
Records of 100 truck-loads of finished jobs arriving in a department’s check-out area show the following: checking out takes 5 minutes and checker takes care of only one truck at a time. The data is summarised in the following table.
As soon as the trucks are checked out, the truck drivers take them to the next department. Using Monte-Carlo simulation, determine:
- What is the average waiting time before service?
- What is likely to be the longest wait?
Solution: From the given distribution of truck arriving times, we construct a cumulative probability distribution, as shown in Table 14.9. The Table enable us to select the range of random numbers for which we shall choose a prescribed value of time.
A simulation work-sheet can be prepared as in Table 14.10.
TABLE 14.10
First, we select 20 two-digit random numbers from the random table. The first random number for the arrival time is 12. This number lies in the range (12–28). Therefore, this random number indicates the arrival time at 10.04 a.m., assuming that the checking starts at 10.00 a.m. Similarly, we can work out all the simulated arrivals and service times. Since the first truck arrives at 10.04 a.m, the checker waits for 4 minutes. This is indicated in the last column, as checker’s waiting time in Table 14.10. The checker takes 5 minutes and thus the service for first truck will end at 10.09 a.m, which indicates that the checker waits for 1 minute. Whenever a truck has to wait because of the checker begins busy in dealing with a previous truck, the waiting time is listed in the last column of Table 14.10. The similar procedure can be adopted to prepare the entire work sheet.
After completing the simulation, the following information can be obtained which describes the behaviour of a single server counter:
- Average waiting time of trucks before service
- Excepted longest period of waiting = 3 minutes.
14.6 APPLICATIONS TO INVENTORY PROBLEMS
Many of the inventory problems, especially storage problems, cannot be solved analytically because of the complex nature of the distribution followed by demand or supply. It is, however, possible to get the solution by using simulation techniques. The basic approach would be to determine the probability distribution of the input and output functions from the past data, and run the inventory system artificially by generating the future observations on the assumption of the same distributions. Subsequently, the decision-making regarding the optimisation problems would be made by the trial and error method.
The artificial samples for future can be generated with the help of random numbers.
In inventory control, the recoding point is to be chosen with consideration for the demand during lead time to provide adequate service to customers. If both the lead time and demand of inventory per unit of time are random variables, then simulation technique can be used to investigate the effect of different inventory policies.
Example 1
A wholesaler dealing in stationery items wants to determine the order of size for desk calendars.
The demand and lead time are probabilistic and their distribution are given below.
The cost of placing an order is 50 per order and the holding cost of 1,000 calendars is 2 per week. The shortage cost 10 per thousand. The inventory manager is considering a policy whereby whenever the inventory level is equal to or below 2,000, an order is placed equal to the difference between the current inventory balance and specified maximum replenishment level of 4,000.
Simulate the policy of the 20 week period assuming that (a) the beginning inventory is 3,000 units, (b) no back orders are permitted, (c) each order is placed at the beginning of the week following the drop in inventory level to (or below) the reorder point, and (d) the replenishment orders are received at the beginning of the week.
Solution: Using the weekly demand and lead time distributions, assign an appropriates set of random numbers to represent value or range of values of variables (Tables 14.11 and 14.12).
TABLE 14.11
TABLE 14.12
The simulation for a period of 20 weeks concerning the inventory system and the related costs with a replenishment level of 4,000 units and recorder level of 2,000 units is given in Table 14.13. At the start of the a simulation, the first random number 31 generates a demand of 1,000 units, as determined from the cumulative probability values of calendar demand in Table 14.11, leaving 2,000 units on hand at the end of the first week. Since it is equal to the recorder level, an order for 4,000 − 2,000 = 2,000 units is placed. With a random number 29, the lead time is 2 weeks; refer to the lead time cumulative probability values in Table 14.12.
TABLE 14.13
With 2,000 units to be held, the holding cost is 4 and there is no shortage cost. In the next week, the random number 70 results in a demand of 2,000 units from Table 14.11, and 2000 units available in inventory at the beginning of the second week are reduced to zero units, by the end of the week. In the third week, demand is for 1,000 units but as the available inventory is zero, this results in the shortage cost of 10. The 2,000 units ordered in the first week are received in the beginning of the fourth week. The demand in the fourth week is also for 2,000 units, and hence ending inventory is zero. The second shortage thus occurs in the fifth week and continues till the end of the eighth week. The units ordered at the end of fourth week are received only in the beginning of the nineth week. In this way, the simulation is continued for a period of 20 weeks.
To evaluate the performance of the policy simulated, we need to know the number of orders placed, the average inventory, and the number of units short. Form Table 14.13, we note that orders were placed 5 times during the course of simulation.
The average inventory can be calculated by adding the weekly ending inventory balances (ignoring negative balances) and dividing by the number of weeks. Thus,
Average inventory = = 750 units per week.
The total average weekly cost can be calculated as follows:
Weekly average cost = Ordering cost + Inventory holding cost + Shortage cost.
In this case the average shortage cost is high as compared to the holding cost. This shortage cost can be reduced by increasing the recorder level.
The two decision variables, replenishment level and recorder level interact with each other and influence the three cost elements. Since replenishment level and recorder level depend on each other, experiments conducted with the simulation model should be so designed as to list the various combinations of both variables. In the present problem, the average lead time is 2.8 weeks and the average demand per week is 14,000 units. Hence, average demand during lead time is 3,920 units. On the other hand, maximum lead time is 4 weeks and maximum weekly demand is 3,000 units. Thus, maximum demand during lead time is 12,000 units. It follows that the best recorder point, irrespective of the replenishment level, should be somewhere in the range 3,920 and 12,000 units.
14.7 APPLICATIONS TO CAPITAL BUDGETING PROBLEM
An important decision of financial analysis is to select the optimum alternative among various capital investment policies and evaluation of risk involved with the specific decision. The main purpose of evaluating the risk is to determine the effect of various factors (e.g selling price, market growth rate, market size, etc.) on financial parameters. The samples from the probability distributions of the factors involved can be drawn and analysed to determine the rate of return on investment.
Step 1: To develop the probability distribution of uncertain factor.
The probability distributions are developed on the basis of assessment of the probable outcomes. The following factors are taken into consideration for evaluating an investment proposal:
- Market size
- Selling price
- Market growth rate
- Share of market
- Investment required
- Residual value of investment
- Operating costs
- Fixed costs
- Useful life of facilities
Step 2: To generate a set of random numbers
A set of random numbers is generated and respective probability distribution is assigned to each factor in system for calculating the expected values of these factors. Then, the values of all the factors are combined to determine the rate of return for the combination.
Step 3: To simulate the process
The above process is repeated several times to simulate a clear portrayal of investment risk.
An investment corporation wants to study the investment projects based on three factors; market demand in units, price per unit minus cost per unit, and the investment required. These factors are felt to be independent of each other. In analyzing a new consumer product, the corporation estimates the following probability distributions:
TABLE 14.14
Using simulation process, repeat the trial 10 times, compute the return on investment for each trial taking these three factors into accounts. What is the most likely return (appx)?
Solution: The yearly return can be determined by the formula
To determine a cumulative probability distribution corresponding to each of the three factors, we assign an appropriate set of random numbers representing each of the three factors as shown in Tables 14.15, 14.16 and 14.17.
TABLE 14.15
TABLE 14.17
The simulation worksheet for 10 trials is given in Table 14.18.
TABLE 14.18
Table 14.19 shows that the highest likely return is 20%, which is corresponding to the annual demand of 35,000 units resulting in a profit of 10per unit. The required investment will 17,50,000.
14.8 APPLICATIONS TO PERT PROBLEMS
Simulation can be applied to PERT problems. This is illustrated with the following examples.
A project consists of activities A to H. The completion time for each activity is a random variable. The data concerning probability distribution along with completion times for each activity is as follows:
- Draw the network diagram and identify the critical path using the expected activity times.
- Simulate the project to determine the activity times. Determine the critical path and the expected. project completion time.
- Repeat the simulation four times and state the estimated duration of the project in each of the trials.
Solution: (a) The network diagram based on the precedence relationship is shown in Fig 14.3. The expected completion time of each activity is obtained by using the formula.
Excepted time = Σ (Activity × Probability)
= 4 × 0.2 + 6 × 0.4 + 7 × 0.4 = 6 days (Activity A)
The critical path of the project is 1–2–3–4–5–6–7, with expected time of 23.6 days. The random coding for each activity’s expected time is shown in Table 14.19.
FIGURE 14.3
TABLE 14.19 Simulation Worksheet
TABLE 14.20 Random Number Coding: Activity times
The simulation worksheet for four simulation runs is shown in Table 14.21. For each run the project time is obtained as follows:
Total time = Larger of times for activities A, B and C+ Larger of times for activities
D and F + Larger of times for activities F and G + Time for activity H.
Using the data given in Table 14.20, we have the simulation results shown in Table 14.22.
TABLE 14.21 Simulation Worksheet
TABLE 14.22 Simulation Results
Here, it may be noted that simulated mean project completion time 25.4 days is almost of two days longer than the 23.6 days completion time indicated using expected values alone.
14.9 HOSPITAL SIMULATION
Hospital simulation is an example of a manual simulation.
Example 1
Wednesday’s schedule for operating room number 3 at a famous hospital is shown in Table 14.23. From looking at this schedule, the operating room head nurse concludes that it may not be possible to finish with the operating and clean-up schedule by 5 pm, the time at which this operating room must be available for emergency night service.
TABLE 14.23
Time | Activity | Expected time |
---|---|---|
8:00 am | Appendectomy | 40 min |
8:40 | Clean-up | 20 min |
9:00 am | Laminetormy | 90 min |
10:30 | Clean-up | 20 min |
10:50 | Kidney removal | 120 min |
12:50 pm | Clean up | 20 min |
1:10 | Hysterectomy | 60 min |
2:10 | Clean-up | 20 min |
2:30 | Colostomy | 100 min |
4:10 | Clean-up | 20 min |
4:30 | Lesion removal | 10 min |
4:40 | Clean-up | 20 min |
The hospital management analyst suggests that simulation might indicate whether the schedule for Wednesday is workable and if not, what change could be made. The analyst reviews the operating records for the past few months and finds that patients do not always arrive at the operating room at the schedule time. They often have to wait for per-op medication to be administered; sometimes operating room transportation personnel are late, and from time to time physicians forget to order the patient moved from the floor to the operating room. Investigation of the operating room log indicates that arrival expectations are as shown in Table 14.24. The management analyst finds that’s operating times also vary according to surgical difficulties encountered, differences in surgical skills, and the effectiveness of the surgical team in general. An analysis of operations scheduled over the past few months produces the results shown in Table 14.25, which gives a good indication of this variation. He also recognises that any variation in the expected clean-up time will affect the schedule and checks the records once again. Here, he finds that about half the time, the clean-up crew finishes in 10 minutes. The rest of the time, it takes them 30 minutes.
TABLE 14.24 Arrival Expectation
Patient arrives on time | 0.50 probability |
Patient arrives 5 minutes early | 0.10 probability |
Patient arrives 10 minutes early | 0.05 probability |
Patient arrives 5 minutes late | 0.20 probability |
Patient arrives 10 minutes late | 0.15 probability |
TABLE 14.25 Operation Time Exceptions
Operation is completed in the expected time | 0.45 probability |
Operation is completed in 90 % of the expected time | 0.15 probability |
Operation is completed in 80 % of the expected time | 0.05 probability |
Operation is completed in 110 % of the expected time | 0.25 probability |
Operation is completed in 120 % of the expected time | 0.10 probability |
Generating the variables in the system (Process Generators)
The analyst needs a way to generate arrival times, operating times, and clean-up times. The methods he uses to do this are called process generators. He decides to use a random number table. A random number table is the output we would expect to get from sampling a uniformly distributed random variable where all of its values (digital 0 through 9 in this case) are alike.
Generating arrival times
The analyst decides to use the first two digits of each 10-digit number in a random number table as his process generator for arrival times. Since there are 100 possible two-digit number from 00 through 99, he relates these two-digit number to arrival variation as shown in Table 14.26
TABLE 14.26
Random number | Arrivals | |
---|---|---|
00 through 49 | on time | (0.50 probability) |
50 through 59 | 5 minutes early | (0.10 probability) |
60 through 64 | 10 minutes early | (0.05 probability) |
65 through 84 | 5 minutes late | (0.20 probability) |
85 through 99 | 10 minutes late | (0.15 probability) |
Generating operating times
The analyst now decides to use the last two digits of each 10-digit number in a random number table. He relates these two-digit numbers to operating times as shown in Table 14.27.
TABLE 14.27
Random | Number | |
---|---|---|
00–44 | On-time completion | (0.45 probability) |
45–59 | Completion in 90% of expected time | (0.15 probability) |
60–64 | Completion in 80% of expected time | (0.05 probability) |
65–89 | Completion in 110% of expected time | (0.25 probability) |
90–99 | Completion in 120% of expected time | (0.10 probability) |
Generating clean-up times
Since there are only two values the random variable takes on here, the analyst decides to use the fourth digit of each 10-digit number in a random table as his process generator. If it’s an odd number, he will let that represent a 10-minute clean-up an, even number would represent a 30-minute clean-up.
The simulation
The analyst now proceeds with the simulation. First, he generates an arrival-time deviation for the first patient; then he generates an operating time deviation for the first operation; finally, he generates a clean-up time for that operation. He continues with this process until the last operation has been performed and the operating room cleaned up for the final time that day. The results of the simulation are shown in Table 14.28.
TABLE 14.28 Results of Simulation of Activity in Operating Room No. 3
From the analyst’s simulation, it appears that the scheduled operations can be completed and the room vacated by 5 pm. In fact, his simulation indicates that the day’s schedule ends at 4:45 pm, a few minutes early.
Assumptions
The analyst simulated the day’s operation only once, and it may be dangerous for us to draw conclusions from such a short simulation. If he had repeated the day’s simulation several times using different random numbers, then we could feel better about generalising from his results. He also assumed that the variables in this simulation (arrival deviation, operating time deviation, and clean-up deviation) were independent of each other. If this is not the case, his simulation is not a valid one. Finally, he used discrete distributions of the three variables. In actual practice, were computation time not such a problem, continuously distributed random variables would be more appropriate.
14.10 COMPUTER SIMULATION
The role of computers in simulation is vital. They are used to generate random numbers, simulate the given problem with varying values of variables in a few minutes and help the decision-maker to prepare reports which enable making quick decision as well as drawing valid conclusions.
For the complex and intricate problems of managerial decision-making, the analogue simulation may not be practicable, and actual experimentation with the system may be uneconomical. Under such circumstances, the complex system is formulated into a mathematical model for which a computer program is developed, and the problem is solved by using high-speed electronic computer, and hence it is a named as computer simulation or system simulation.
Simulation languages
The efficiency of programming and execution of a simulation project depends upon the programming language used. Computer language available to help the simulation process can be divided into two categories:
- General Purpose Programming Languages
The general purpose programming languages includes FORTRAN, BASIC, COBAL, PL/I, PASCAL, C, C++, Java, and so on. To use these languages for simulation process, an extensive programming experience is required as even a simple queueing problem involves many tedious details.
Being well known and commonly available on computer system, FORTRAN is often used to write simulation programmes. It is efficient in computer time and storage requirements. However, programming in FORTRAN is more difficult and time consuming as compared to the special simulation languages. When the complexities of the simulation project increase, the book-keeping of the intricate details of simulation becomes difficult and this makes the programming in FORTRAN harder. Thus, for realistic situations, simulation programs should be written in specialised simulation languages which are designed to meet the following objectives:
- Conveniently describe the elements which commonly appear in simulation, such as the generation of random variates for most of the statistical distributions.
- Flexibility of changing the design configuration of the system so as to consider alternate configurations.
- Internal timing and control mechanism for book keeping of vital information during the simulation run.
- Obtain conveniently the data and statistics about the behavior of the system.
- Provide simple operational procedures, such as altering the initial state of the system and kind of output data to be generated, and so on.
- Special Purpose Simulation Languages
Special purpose simulation languages have several advantages. (i) They reduce programming Preparation time and cost with features specially designed for simulation models. Such features generally include a master sequencing routine to automatically maintain event sequence and to keep track of simulated time sub-routines to handle arrivals and departures in a queuing system, (ii) they have the capability to readly generate different types of random and certain types of statistical table, (iii) they require little or no prior programming knowledge for use. The main special purpose simulation languages are:
- GPSS (General Purpose System Simulation): Usually, it does not require programme writing. The system model is constructed via block diagrams using block commands. The third version of this language, GPSS III consists of two parts. The first part is an assembly programme which converts the system descriptors into input for the second part that performs the simulation. This language was developed by IBM in early 1960s.
- SIMSCRIPT: This language neither depends on any predefined coding forms nor on any intermediate language such as FORTRAN for its implementation. This language was developed by RAND Corporation in the early 1960s.
- DYNAMO: It is a computer program which is capable of taking input in the form of a set of equations describing the system. These equations are evaluated continuously for each time interval to understand the behaviour of the system. This language was developed at MIT in 1959 and is best suited for econometric modelling of industrial complexes and urban, social and world systems planning.
The choice of a simulation package depends on the specific purpose, the availability of simulation languages on a particular computer, the training and experience in simulation modelling programming and the availability of experienced programmers.
14.11 SIMULATION OF JOB SEQUENCING
In this section, we shall illustrate the use of simulation in sequencing problems.
Example 1
A job has to be processed over two machines M_{1} and M_{2} in that order. This distribution of inter-arrival time of the jobs at the first machine is as follows:
Time (minutes) | Probability |
---|---|
1 | 0.2 |
2 | 0.2 |
3 | 0.2 |
4 | 0.4 |
The processing time at the two machines is as follows:
On the basis of 10 simulation runs find out the average queue length before machine M_{1} and the average queue length before machine M_{2}.
Solution: The various steps for simulation are explained below:
- Simulate the inter-arrival time of the ith job on machine M_{1} with the help of random numbers (i = 1, 2, …)
- Arrival time of i^{th} job.
= arrival time of (i − 1)^{th} job (i = 1, 2, …) + inter-arrival of i^{th} job.
Arrival time of the first job = inter-arrival time of the first job.
- Simulate the processing time on machine M_{1} by random numbers.
- Departure time on machine M_{1}.
= Arrival time for processing on Machine M_{2}.
= Max (Arrival time of i^{th} job process completion time of (i − 1)^{th} job on machine M_{1}) + processing time of i^{th} job on Machine M_{1}.
- If arrival time of ith < process completion time of (i − 1)^{th}, i^{th} arrival waits. If arrival time of i^{th} < process completion time of (i − 2)^{th}, both i^{th} and (i − 1)^{th} arrival wait.
- Simulate the processing time of M_{2} with the help of random numbers.
- Process completion by machine M_{2} of ith arrival.
= Max (Arrival time of ith, process completion time of (i − 1)^{th}.
+ process time by machine M_{2}.
TABLE 14.29 Simulation Worksheet
- If arrival time of i^{th} < process completion time of (i − 1)^{th}, i^{th} arrival waits. If arrival time of i^{th} < process completion time of (i − 2)^{th}, both i^{th} and (i − 1)^{th} arrival wait and so on.
Using the procedure, the simulated processing data of 10 arrivals are displayed in the simulation worksheet in Table 14.27.
On the basis of simulation study, the average queue length before machine M_{1} is 0.5, and the average queue length before machine M_{2} is 1.2.
14.12 APPICATION OF SIMULATION
There is a wide range of applications of computer-based simulation models because it is an approach rather than an application of specific techniques. The major use of computer-based Monte-Carlo simulation models has been in the solution of complex problems. Some of the major applications of simulation are:
- Queuing problems
- Inventory problem
- Training programmes
- Network problems (PERT)
- Job sequencing
- Capital budgeting and investment problems
- Military studies of logistics, support planning and weapon system and effectiveness
- Studies of individual and group behavior
- Financial studies involving risks investments
- Testing of decision rules for hospital admission and operating policies
- Carpet cutting application
- Public school planning application.
EXERCISES
Section 14.1
1. What is simulation?
2. Explain simulation.
3. Explain the Monte-Carlo method.
4. What are the advantages of simulation?
5. What are the limitations of simulation?
6. Mention the uses of simulation.
7. When is simulation preferable?
8. What are the different steps involved in solving a problem by simulation?
9. Distinguish between solutions derived from simulation model and from analytical models.
10. “When it becomes difficult to use an optimization technique for solving a problem, one has to resort to simulation technique.” Discuss.
11. Can you in all situations use simulation exercise without a computer? Discuss.
12. Do you think that the application of simulation will increase in the next 10 years? Why?
13. What types of problems can be solved more easily by quantitative technique other than simulation?
14. Explain the various types of simulation.
15. Why should one use simulation?
16. Explain the phases of simulation model.
Section 14.2
17. With the help of a single server queueing model having inter-arrival and services times constant 1.4 and 3 minutes, respectively, explain the discrete simulation technique taking 10 minutes as the simulation period. Find from this the average waiting time for a customer (assume that initially the system is empty and the first customer arrives at time t = 0). [Answer: Average time = 2.35 minutes per customer.]
18. At a telephone booth, customers arrive with an average time of 1.2 time units between two arrivals. Service times are assumed to be 2.8 time units. Simulate the system for 12 time units by assuming that the system starts at t = 0. What is the average waiting time per customer? [Answer: Average time = 3.36 time units per customer.]
Section 14.3
19. Write short notes on generation of random numbers.
20. What do you mean by the mid-square method of generating pseudo-random numbers? What are the disadvantages of this method?
21. What do you mean by the congruence method of generating random numbers? Explain with an example.
22. What are random numbers? Why are random numbers useful in simulation models and solutions derived from analytical models?
23. Use the mixed congruential method to generate the following sequences of random numbers:
- A sequence of five two-digit numbers, such that r_{i + 1} = (21r_{i} + 53) (modulo 100), take r_{0} = 46.
- A sequence of five random numbers between 0 and 31, such that r_{n + 1} = (9r_{n} + 15) (modulo 32), take r_{0} = 12. 24. Solve problem 24 when mixed congruential method is reduced to multiplicative method.
Section 14.4
25. Explain Monte-Carlo method of simulation with a suitable example.
26. (The chef example) The number of customers at a restaurant each evening is distributed as shown below:
The chef refuses to work on an evening when there are very few customers and walks out. He will not return to work until at evening when there are lots of customers, although he always comes in on Friday because he gets paid then. We are interested in the fraction of evening that the chef is at the restaurant.
[Answer: Chef is in for 49% of all days.]
27. A tourist car operator has 25 taxis in operation. He keeps three drivers as reserve to attend to calls, in case the scheduled drives report sick. The probability distribution of sick drivers is as follows:
Use the Monte-Carlo method to estimate the utilization of reserve drivers and the probability that at least one taxi will be off the road due to non-availability of a drivers. Compare with the correct answers.
Section 14.5
28. A company has a single service station which has the following characteristic: the mean arrival rate of customers and the mean service time are 6.2 minutes and 5.5 minutes, respectively. The time between an arrival and its service varies from 1 minute to 7 minutes. The arrival and services time distributions are given below:
Time (Minutes) | Arrival (Probability) | Service (Probability) |
---|---|---|
1–2 | 0.05 | 0.10 |
2–3 | 0.20 | 0.20 |
3–4 | 0.35 | 0.40 |
4–5 | 0.25 | 0.20 |
5–6 | 0.10 | 0.10 |
6–7 | 0.15 | – |
The queueing process starts at 11 am and closes at 12 pm. An arrival moves immediately into the service facility if it is empty. One the other hand, if the service station is busy, the arrival will wait in the queue. Customers are served on the first come, first served basis.
If the clerk changes 6 per hour and the customer’s waiting line costs 5 per hour, would it be economical for the manger to engage a second clerk?
[Answer: Average queue length = 0.85]
Average waiting time of customer before starting service = 2.80 minutes
Average service time = 2.70 minutes.
Time a customer spends in the system = 5.5 minutes.]
29. Dr Anish is a dentist who schedules all his patients for 30-minute appointments. Some of the patients take more or less than 30 minutes depending on the type of dental work to be done. The following summary shows the various categories of work, their probabilities and the time actually taken to complete the work.
Category | Time required (minutes) | Probability Category |
---|---|---|
Filling | 45 | 0.40 |
Crown | 60 | 0.15 |
Cleaning | 15 | 0.15 |
Extraction | 45 | 0.10 |
Check-up | 15 | 0.20 |
Simulate the dentist’s clinic for four hours and determine the average waiting time for the patients as well as the idle time of the doctor. Assume that all the patients show up at the clinic at exactly their scheduled arrival time starting at 8 am. Use the following random numbers handling the above. Problem: 40, 82, 11, 34, 25, 66, 17, 79.
[Answer: The average waiting time = 35.625 minutes.]
30. A company manufactures 2,000 mopeds. Depending upon the availability of raw materials and other conditions, the daily production has been varying from 196 mopeds to 204 mopeds, whose probability distribution is as given below:
The finished mopeds are transported in a specially designed three-storeyed lorry that can accommodate only 200 mopeds. Using the given 15 random numbers, viz, 82, 89, 78, 24, 53, 61, 18, 45, 04, 23, 50, 77, 27, 54, 10 simulate the process to find out.
- What will be the average number of mopeds waiting in the factory?
- What will be the average number of empty spaces in the lorry?
[Answer: (i) 0.67 per day (ii) 0.93 per day.]
31. An owner of a petrol pump with signal attendant wishes to perform a simulation of operations to see whether any improvement is possible. He studied the system and found that an average of 6 customers arrive for service with random arrival times and from a queue, and the attendant provides a service for exactly 9 minutes. For simulating the arrival times of customers, he has selected 10 random numbers with expected length of interval equal to one as
- The total idle time for the attendant,
- Total waiting time for the customers, and
- Maximum queue length during this period.
If the service time is reduced to 6 minutes what is the quality of service?
32. An automobile production line turns out about 100 cars a day, but deviations occur owing to many causes. The production is more accurately described by the probability distribution given below:
Finished cars are transferred across the bay, at the end of each day, by ferry. If the ferry has space for only 101 cars, what will be the average number of cars waiting to be shipped, and what will be the average number of empty space on the boat?
33. An airline has 15 flights leaving a base per day, each with a hostess. The airline keeps three hostesses in reserve so that they may be called in case the scheduled hostess for a flight reports sick. The probability distribution for daily number of sick hostesses is as follows:
Use the Mote-Carlo method to estimate the utilization of reserve hostesses and also the probability that at least one flight will be cancelled in a day because of non-availability of a hostess.
34. A firm has a single-channel service station with the following arrival and service time probability distributions:
The customer’s arrival at the service station is a random phenomenon and the time between the arrival varies from one minute to five minutes. The service time from one minute to three minutes. The queueing process begins at 10.00 am and proceeds for nearly 2 hours. An arrival goes to the service facility immediately, if it is free. Otherwise, it will wait in a queue. The queue discipline is FIFO. If the attendant’s wages arè8 per hour and the customer’s waiting time costs 9 per hour, would it be an economical proposition to engage a second attendant? Answer on the basis of the Monte-Carlo simulation technique.
Section 14.6
35. Consider an inventory in a manufacturing concern. If the number of sales per day is Poisson with mean 5, then generate 30 days of sales by the Monte-Carlo method.
36. After studying the weekly receipts and payments over the past 200 weeks a retailer has developed the following information:
Using the following set of random numbers, simulate the weekly pattern of receipts and payments for the 12 weeks of the next quarter, assuming further that the beginning bank balance is 8,000. What is estimated balance at the end of the 12-week period? What is the highest weekly balance during the quarter? What is the average weekly balance for the quarter?
[Answer: The balance at the end of the 12-week period is a deficit of 3,000. The highest weekly balance during the quarter is 7,000 while the average balance works out to bè3,750.]
37. Iyengar Bakery keeps stock of a popular brand of cake. Previous experience indicates the daily demand as given here:
Consider the following sequence of random numbers:
48, 78, 19, 51, 56, 77, 15, 14, 68, 09
Using this sequence, simulate the demand for the next 10 days. Find out the stock situation if the owner of the bakery decides to make 30 cakes every day. Also, estimate the daily average demand for this cake on the basis of simulated data.
[Answer: Stock situation: 0, 00, 20, 20, 20, 20, 40, 80, 80 and 80, respectively. Average demand = 22 units per day.]
38. A confectioner’s past data of demand per week (in hundred Kg) with frequency is given below;
Using the following sequence of random numbers, generate the demand for the next 10 weeks. Also, find the average demand per week.
35, 52, 90, 13, 23, 73, 34, 57, 35, 83, 94, 56, 67, 66, 60
[Answer: Demand level: 10, 15, 20, 05, 05, 15, 10, 15, 10, 15, respectively. Average demand = 1,200 kg per week.]
39. A gas transport company controls pipe lines between several natural gas fields and out of state distributors. The company has a 1,00,000 unit storage capacity. Because of federal regulations, the company receives either 40,000 or 60,000 units per day. There is no equal probability of either quality being stripped on a given day. The actual demand for natural gas is given by the following table of relative frequencies:
Daily demand | Probability |
25,001–45,000 | 0.3 |
45,000–55,000 | 0.3 |
55,000–65,000 | 0.4 |
- What is the expected daily demand?
- Construct a model that can be used to simulate the company’s daily receiving, storage and shipping activities.
40. The manager of a book store has to decide the number of copies of a particular tax law book to order. The book costs 60 and is sold for 80. Since some of the tax laws change year after year, any copies unsold while the edition is current must be sold for 30. From past records, the distribution of demand for this book has been obtained as follows:
Using the following sequence of random numbers, generate data on demand for 20 time periods (years). Calculate the average profit obtainable under each of the courses of action open to the manager. What is the optimal policy?
41. A retail store distributes catalogues and takes orders on the telephone. Distribution of intervals between incoming calls and the length of time required to complete each call is given below. The store management has determined that they want a probability of no more than 5% that a caller will have to wait longer than 10 seconds for the telephone to be answered. Use simulation to determine how many sales representatives should be available to answer incoming calls.
42. ABC Company stocks certain products. The following data is available:
- Weekly demand of the production has the following distribution:
- The variation of the lead has the following distribution:
The company wants to know (1) how much to order and (2) when to order.
Assume, that the inventory on hand at the start of the experiment is 20 units, and 15 units are ordered as soon as the inventory level falls to 10 units. No back orders are allowed. Simulate the situation for 25 weeks.
[Answer: Average inventory = 17.92 units, total lost sales is zero units.]
43. A book store wishes to carry Ramayana in stock. Demand is probabilistic and replenishment of stock takes 2 days (i.e if an order is placed on 1 March, it will be delivered at the end of the day on 3 March). The probability of demand are given below:
Each time an order is placed, the store incurs an ordering cost of 10 per order. The store also incurs a carrying cost of 0.50 per book per day. The inventory carrying cost is calculated on the basis of stock at the end of each day.
The manager of the book store wishes to compare two options for his inventory decision:
- Order 5 books when the inventory at the beginning of the day plus orders outstanding is less than 8 books.
- Order 8 books when the inventory at the beginning of the day plus orders outstanding is less than 8.
Currently, (beginning 1^{st} day) the store has a stock of 8 books plus 6 books ordered two days ago and expected to arrive next day.
Using Monte-Carlo simulation for 10 cycles, recommend which option the manager should choose. The two-digit random numbers are given below:
89, 34, 70, 63, 61, 81, 39, 16, 13, 73.
[Answer: Total cost of option A = 59.50
Total cost of option B = 52.50, option B should be chosen.]
Section 14.7
44. The director of finance of a farm cooperative is concerned about the yields per acre she can expect from this year’s corn crop. The probability distribution of the yields for the current weather conditions is given below:
Yield in kg per acre | Probability |
120 | 0.18 |
140 | 0.26 |
160 | 0.44 |
180 | 0.12 |
She would like to see a simulation of the yields she might expect over the next 10 years for weather conditions similar to those she is now experiencing.
- Simulate the average yield she might expect per acre using the following random numbers: 20, 72, 34, 54, 30, 22, 48, 74, 76, 02
She is also interested in the effect of market price fluctuations on the cooperative’s farm revenue,. She makes this estimate of per kg price of corn.
Price per kg () Probability 2.00 0.05 2.10 0.15 2.20 0.30 2.30 0.25 2.40 0.15 2.50 0.10 - Simulate the price she might expect to observe over the next 10 years using the following random numbers:
82, 95, 18, 96, 20, 84, 56, 11, 52, 03 - Assuming that prices are independent of yields, combine these two into revenue per acre and also find out the average revenue per acre she might except every year.
[Answer: Average revenue per acre is 3,386/10 = 338.60.]
45. (a) A businessman is considering taking over a new business. Based on past information and his own knowledge of the business, he works out the probability distribution of the monthly costs and sales revenues, as given here:
Cost (in ) Probability Sales Revenue () Probability
Use the following sequence of random numbers to be used for estimating costs and revenues. Obtain the probability distribution of the monthly net revenue.
(b) Repeat the analysis in (a) by using the following random number streams:
46. The investment required for introducing a new product is 10,000. The probability estimates for variables cost, selling price and annual sales volume are given below:
Simulate the situation by generating random numbers to find out the selling price, variable cost, and annual sales volume. The random numbers for the three factors are:
Determine the average profit for 20 simulations (observations).
[Answer: Average profit = 2,600.]
Section 14.8
47. Consider the network of a project given in the following figure:
FIGURE 14.1
Suppose, the duration of the activities is non-deterministic with the following probability distribution:
Activity | Days | Probability |
---|---|---|
1 | 0.2 | |
1−2 | 4 | 0.5 |
8 | 0.3 | |
2 | 0.3 | |
1−3 | 4 | 0.5 |
7 | 0.2 | |
2 | 0.3 | |
2−4 | 4 | 0.3 |
6 | 0.4 | |
3 | 0.3 | |
3−4 | 6 | 0.4 |
8 | 0.3 | |
2 | 0.2 | |
4−5 | 3 | 0.2 |
4 | 0.6 |
Simulate the duration of the project 10 times and estimate the chances of various paths to be critical. What is the average duration of the project?
48. For a project comprising activities A, B,…, H, the following information is available: Precedence relationships:
A and B are the first activities of the project. C succeeds A while B precedes D. Both C and D precede E and F activity follows activity F. While H is the last activity of the project and succeeds E and G.
Time estimates and probabilities:
Simulate the project and determine, using random numbers, the activity times. Find the critical path and the project duration. Repeat five times. Does the critical path change? State the estimated duration of the project in each of the trials.
Section 14.10
49. Why do need a computer to do simulation? Explain.
50. An assembly line has three work stations. The time required for each station to complete its operations is as follows:
The times given are the only values the operation times take on. Simulate the flow of 20 items through the assembly line. What is the average time that an item takes to go through all the operations?