Simulation and modeling 2069

Simulation is the imitation of the operation of a real-world process or system over time. Simulation involves the generation of an artificial history of the system, and the observation of that artificial history to draw inferences concerning the operating characteristics of the real system that is represented.

Steps in simulation study

1.Problem formulation

     Clearly state the problem.

2. Setting of objectives and overall project plan

     How we should approach the problem.

3. Model conceptualization

     Establish a reasonable model.

4. Data collection

    Collect the data necessary to run the simulation (such as arrival rate, arrival process, service discipline, service rate etc.).

5. Model translation

     Convert the model into a programming language.

6. Verification

     Verify the model by checking if the program works properly. Use common sense.

7. Validation

     Check if the system accurately represent the real system.

8. Experimental design

     How many runs? For how long? What kind of input variations?

9. Production runs and analysis

     Actual running the simulation, collect and analize the output.

10. Repeatition

     Repeat the experiments if necessary.

11. Document and report

     Document and report the results.

12. Implementation: Implement the simulated system in the real world if the simulation results show that it is advantageous to implement the new system or policy.

If the future states of a process are independent of the past and depend only on the present , the process is called a Markov process. A discrete state Markov process is called a Markov chain. A Markov Chain is a random process with the property that the next state depends only on the current state.

Markov chains are used to analyze trends and predict the future. (Weather, stock market, genetics, product success, etc.

Formally,

A Markov chain is a sequence of random variables X₁, X₂, X₃, ... with the Markov property, namely that, given the present state, the future and past states are independent.

The conditional probability above gives us the probability that a process in state i_n at time n moves to i_n+1 at time n + 1. We call this the transition probability for the Markov chain. If the transition probability does not depend on the time n, we have a stationary Markov chain, with transition probabilities

Now we can write down the whole Markov chain as a matrix P:

Example:

Weather Problem:

• raining today  ⇒ 40 % rain tomorrow

                                ⇒ 60 % no rain tomorrow

• not raining today  ⇒ 20 % rain tomorrow

                                      ⇒ 80 % no rain tomorrow

What will be probability if todays is not raining then not rain the day after tomorrow?

Markov chain diagram:

Transition matrix:

Thus, the probability of not rainy the day after tomorrow is 0.76.

Random numbers are samples drawn from a uniformly distributed random variable between some satisfied intervals, they have equal probability of occurrence.

Properties of Random Numbers

1. Uniformity:

• The random numbers generated should be uniform. That means a sequence of random numbers should be equally probable every where.
• If we divide all the set of random numbers into several numbers of class interval then number of samples in each class should be same.
• If ‘N’ number of random numbers are divided into ‘K’ class interval, then expected number of samples in each class should be equal to e_i = N / K.

2. Independent:

• Each random number should be independent samples drawn from a continuous uniform distribution between 0 and 1.
• The probability density function is given by:
  f(x) = 1, 0 <= x <= 1
        = 0, otherwise

3. Maximum Density:

• The large samples of random number should be generated in a given range.

4. Maximum Cycle:

•  It states that the repetition of numbers should be allowed only after a large interval of time.

Now,

Given sequence of number,

    0.54, 0.73, 0.98, 0.11 and 0.68

Arranging the given number in ascending order:

    0.11, 0.54, 0.68, 0.73, 0.98

Here, N = 5

Calculation table for Kolmogorov-Smirnov test :

i
1	0.11	0.2	0.09	0.11
2	0.54	0.4	-	0.34
3	0.68	0.6	-	0.28
4	0.73	0.8	0.07	0.13
5	0.98	1	0.02	0.18

Now, calculating

 = 0.09

 = 0.35

 = 0.35

Given, Critical value  = 0.565

Since the computed value, D = 0.35, is less than the tabulated critical value,  = 0.565, the hypothesis of no difference between the distribution of the generated numbers and the uniform distribution is not rejected.

Simulation is the imitation of the operation of a real-world process or system over time. Simulation involves the generation of an artificial history of the system, and the observation of that artificial history to draw inferences concerning the operating characteristics of the real system that is represented.

The following lists when simulation is useful:

• Simulation enables the study of, and experimentation with, the internal interactions of a complex system, or a subsystem within a complex system.
• Informational, organizational, and environmental changes can be simulated, and the effects of these alterations on the model’s behavior can be observed.
• Simulation can be used as a pedagogical device to reinforce analytic solution methodologies.
  
• Simulation can be used to experiment with new designs or policies prior to implementation
• Simulation can be used to verify analytic solutions.
• By simulating different capabilities for a machine, requirements can be determined.
• Animation shows a system in simulated operations so that the plan can be visualized.
• The modern system is so complex that the interactions can be treated only through simulation.

The following lists when simulation is not useful:

• Simulation is not appropriate when the problem can be solved by common sense.
• Simulation should not be used if the problem can be solved analytically.
• Simulation should not be used if it is easier to perform direct implementations.
• Simulation should not be used if the cost exceeds the savings.
• Simulation should not be done if the resources and time are not available.
• Simulation can not be done if no data is available.
• Simulation is not preferred if the system behavior is too complex to be defined.

Server/System utilization is the percentage of the time that all servers are busy. System utilization factor (ρ ) is the ratio of average arrival rate (λ) to the average service rate (μ).

ρ = λ/μ in the case of a single server model

ρ = λ/μn in the case of a “n” server model

The system utilization can be increased by increasing the arrival rate which amounts to increasing the average queue length as well as the average waiting time, as shown in fig below. Under the normal circumstances 100% system utilization is not a realistic goal.

Non-uniform random variate generation is concerned with the generation of random variables with certain distributions. Such random variables are often discrete, taking values in a countable set, or absolutely continuous, and thus described by a density. The methods used for generating non-uniform random variate are inverse transformation technique and acceptance/rejection technique.

Acceptance/Rejection Method

The rejection method for obtaining samples of random numbers forms a given non-uniform distribution works by generating uniform random numbers repeatedly and accepting only those numbers that meet certain conditions.

The rejection method is applied when the probability density function, f(x), has a lower and upper limit to its range, 'a' and 'b', respectively, and an upper bound 'c'. The method can be specified as follows:

1. Find the maximum value c of f(x) on a ≤ x ≤ b.

        f(X)  ≤ c ∀ x ∈ [a, b]

2. Compute two values μ₁, μ₂ of the uniformity distributed variables, both defined on [a, b] = [0, 1].

3. Compute x₀ = a + μ₁(b - a)

4. Compute y₀ = c μ₂

5. If y₀ ≤ f(x₀), accept x₀ as desired output; otherwise reject x₀ and repeat the process with two next values μ₁ &  μ_2.

Autocorrelation Test is needed to determines whether a random number generator is producing independent random number in a sequence. The test for the auto correlation is concerned with the dependence between numbers in a sequence.

The test computes the autocorrelation between every m numbers (m is also known as lag) starting with i^th index. Thus the autocorrelation  between the following numbers would be of interest.

The value M is the largest integer such that  where N is the total number of values in the sequence.

For large values of M, the distribution of the estimator , denoted as , is approximately normal if the values  are uncorrelated.

Form the test statistic:

The actual formula for  and the standard deviation is

and  

After computing , do not reject the null hypothesis of independence if  where  is the level of significance.

Validation is concerned with building the right model. It is utilized to determine that a model is an accurate representation of the real system. It is usually achieved through the calibration of the model.

Calibration means to validate the model with the real system, look out for the places for betterment of the models and revising the model to form next better model repeatedly until a satisfiable model is not achieved. The initial model is developed and is calibrated using Naylor-Finger calibration steps with the real system. It is then revised and a first revision model is generated. The first revision model is then calibrated with the real system. It is revised to form a second revision model. This process is continued until the model becomes acceptable.

Naylor and Finger formulated a three step approach:-

1. Build a model that has high face validity.

2. Validate model assumptions.

3. Compare the model input-output transformations to corresponding input-output transformations for the real system.

The following figure shows the relationship of the model calibration to the overall validation process.

The comparison of the model to reality is carried out by verity of test. Some test are subjective and other are objective.

• Subjective test usually involve people, who are knowledgeable about one or more aspects of the system, making judgments about the model and its output.
• Objective test always require data on the system's behavior plus the corresponding data produced by the model.

In reality, the system is of neither a pure continuous nor a pure discrete nature. For simulating such system, the combination of analog and digital computers are used. Such setup is known as hybrid computers. The simulation provided by the hybrid computers is known as hybrid simulation.

The form taken by hybrid simulation depends upon the application. One computer may be simulating the system being studied while other is providing a simulation of the environment in to which the system is to operate. It is also possible that the system being simulated is an interconnection of continuous and discrete subsystem, which can best be modeled by an analog and digital computer being linked together.. 

The major difficulty in use of hybrid simulation is that it requires high speed converters to transform signals from analog to digital form and vice versa.

Given,

    X₀ = 118, 

    α = 4,

    m=1000

We have,

For multiplicative congruential method:

        X_i+1 = (α X_i ) mod m

        & R_i =X_i/m,

The sequence of random numbers are calculated as follows:

X₀ = 118

R₀ = 118/1000 = 0.118

X₁ = (α X₀) mod m = (4*118) mod 1000 = 472 mod 1000 = 472

R₁ = 472/1000 = 0.472

X₂ = (α X₁) mod m = (4*472) mod 1000 = 1888 mod 1000 = 888

R₂ = 888/1000 = 0.888

X₃ = (α X₂) mod m = (4*888) mod 1000 = 3552 mod 1000 = 552

R₃ = 552/1000 = 0.552

X₄= (α X₃ ) mod m = (4*552) mod 1000 = 2208 mod 1000 = 208

R₄ = 208/1000 = 0.208

Models that have the property of changing only at fixed interval of time is called distributed lag model. It is used to predict current values of a dependent variable based on both the current values of an explanatory variable (independent variable) and the lagged (past period) values of this explanatory variable.

This model consists of linear algebraic equations that represent continuous system but data are available at fixed points in time.

For example: Mathematical model of national economy

Let

C = consumption

I = investment

T = Taxes

G = government expenditures

Y = national income

Then

C=20+0.7(Y-T)

I=2+0.1Y

T=0.2Y

Y=C+I+G

All the equation are expressed in billions of rupees. This is static model and can be made dynamic by lagging all the variables as follows

C=20+0.7(Y_-1-T_-1)

I=2+0.1Y_-1

T=0.2Y_-1

Y=C_-1+I_-1+G_-1

Any variable that can be expressed in the form of its current value and one or more previous value is called lagging variable. And hence this model is given the name distributed lag model. The variable in a previous interval is denoted by attaching –n suffix to the variable. Where –n indicate the nth interval.

a. Queueing Discipline

Queue discipline refers to the rule that a server uses to choose the next customer from the queue when the server completes the service of the current customer. Common queue disciplines include first-in-first-out (FIFO); last-in-first-out (LIFO); service in random order (SIRO); shortest processing time first (SPT); and service according to priority (PR).

• First in first out :This principle states that customers are served one at a time and that the customer that has been waiting the longest is served first.
• Last in first out : This principle also serves customers one at a time, however the customer with the shortest waiting time will be served first. 
• Service in random order: A customer is picked up randomly from the waiting queue for service.
• Shortest job first: The next job to be served is the one with the smallest size (shortest service time).
• Priority: Customers with high priority are served first.

b. CSMP

CSMP or Continuous System Modelling Program is an early scientific computer software designed for modelling and solving differential equations numerically. This enables real-world systems to be simulated and tested with a computer.

Types of statements in CSMP:

1. Structural statements which defines the model. They consist of FORTARN like statement and functional block designed for operations that frequently occur in a model definition. Structural statement can make use of the operation of addition, subtraction, multiplication, division and exponentiation, using the same notation and rule as are used in FORTRAN. If the model include the equation .Then the following statement would be used

         X=6.0*Y/W+(Z-2)**2.0

2. Data statements which assign numerical value to parameters, constant and initial conditions. For example one data statement called INCON can be used to set the initial value of integration function block.

3. Control statements which specify options in the assembly and execution of program and choice of inputs. For e.g. If printed output is required, control statements with PRINT and PRDEL are used followed by the names of variables to form the outputs.