Simulation Modeling is the study of the real system (original), by replacing it with a new object its model having a certain object compliance with it and allows you to predict its functional features, i.e. When modeling, it is not experimenting with an object itself, but an object called the substitute.
The simulation process includes several stages:
1. Setting the problem and determination of the properties of the real object to be studied.
2. The statement of the difficult task or the impossibility of studying the real object.
3. Select a model that function well functioning the basic properties of an object on one side and easy-to-study on the other. The model should reflect the basic properties of the object and should not be a guide.
4. Study of the model in accordance with the goal.
5. Check the adequacy of the object and model. If there is no match, then you need to repeat the first four points.
There is a classic and systematic approach to solving modeling tasks. The essence of the method is as follows: the real object to be studied is divided into separate components D. and selected certain goals C. formation of individual components of the model TO. Then, based on the source data, the components of the model are created, which are bonded by which, taking into account their relations, are combined into the model. This method is inductive, i.e. The construction of the model comes from the private to the total.
The classic method is used to simulate relatively simple systems, for example, sau. Systems approach The essence of the method is to be based on the source data. D.which are known from the analysis of the external environment, taking into account the restrictions that are superimposed on the system and in accordance with the goal C.Requirements are formed T. and object model. On the basis of these requirements is built subsystem P and elements of subsystems E. And with the help of the KV selection criterion, the best model is selected, i.e. The construction of the model comes from the common to the private.
The system approach is used to simulate complex systems.
Classification of modeling types 1. According to the method of constructing the model. And theoretical (analytical) is based on data on the internal structure based on relations arising from physical data. b) Formal - depending between the output and the input to the system. It is based on the principle of the black box. In) Combined.2. By changing variables in time. And Static.B) Dynamic. Static model describes the state of the object and does not contain derivatives h. and w. (input and output) time signals. Mathematical model B) describes volume statics with coordinates distributed by length. Dynamic model describes transient processes over time and contains derivatives w. I.dt.Dynamic model, depending on the method of obtaining, is represented as a differential transitional pulse or frequency response equation in the form of a gear ratio. Dynamics of objects with concentrated parameters is described by ordinary differential equations, and objects with distributed parameters are described by differential equations in frequency derivatives. According to the dependence of the variable modules from spatial coordinate. And with distributed parameters. B) with concentrated parameters. According to the principle of construction. And stochastic. B) deterministic. If h. and w. (input and output) permanent or known values \u200b\u200b(deterministic), then the model is called stochastic. If h. and w. Random (probable) values, the model is called stochastic.
Stochastic models contain probable elements and are a system of dependence obtained as a result of a static study of the existing object.
Determined is a system of functional dependencies, built using the theoretical approach.
Deterministic models have a number of advantages. They can be developed even in the absence of a valid object, as often happens when designing. They qualitatively, more correctly characterize the processes occurring in the object, even if there is not enough accurate in quantitatively, the model parameters quantitatively.
If information about the modeling object does not have a sufficiently high completeness or due to its considerable complexity, it is impossible to describe all input effects in the form of a model, and the effect of unobservable variables on the output coordinates is essential, the static model is used.
5. According to the parameters of the model from variables.
a) dependent (nonlinear).
b) independent (linear).
If the parameters (coefficients) of the model depend on the variables or the last multiplicative, then the model is non-linear.
The model is considered linear with continuous response to the input effect and with addendativeness from the model parameters.
The ademitivity of quantities is a property that enters the value of the value of an entire object equal to the sum of the values \u200b\u200bof the corresponding frequencies of the whole in any partition of the object on the part.
The multiplication of values \u200b\u200bis a property that consists in the fact that the value of the magnitude of the whole object is equal to the product of the value of the corresponding parts of the whole in any partitioning of the object on the part.
6. At adaptability of the model.
a) Adaptive.
b) Naadaptive.
Adaptive is a model, the structure and parameters of which are changed so that some measure of the error between the output variables of the model and the object has been minimal.
They are divided into search and intelligent.
In search models, the automatic optimizer varies the parameters of the model so that the minimal error measure between the output models of the object is obtained.
Lecture number 2.
Mathematical modeling schemes
Main approaches to the construction of a mathematical model of the system
Initial information in constructing a mathematical model, the process of functioning of systems is data on the purpose and condition of the system under study. This information determines the main purpose of modeling systems. S. and allows you to formulate the requirements and the developed mathematical model M..
The mathematical scheme is a link, when moving from the process of functioning of the process substantial to the formal description, taking into account the effects of the external environment, i.e. There is a chain: Descriptive model → Mathematical circuit → Mathematical model.
Each system S. It is characterized by a set of properties reflecting the behavior of the system and the conditions for its functioning in interaction with the external environment ε .
The fullness of the model is regulated mainly by the selection of the boundary system. S. and external environment E..
The task of simplifying the model helps to allocate the main properties of the system, rejecting the minor.
We introduce the following designation:
1) A combination of input influences on the system
.
2) a set of impact of the external environment
.
3) A combination of internal or own system parameters
.
4) a set of output characteristics of the system
16 Mathematical schemes modeling systems.
The main approaches to the construction of mathematical models of the system. Continuous-deterministic models. Discrete-deterministic models. Discrete-stochastic models. Continuous-stochastic models. Network models. Combined models.
The main approaches to the construction of mathematical models of the system.
The initial information in constructing mathematical models of system operation processes is data on the purpose and conditions of the work of the study (designed) system S.
Mathematical schemes
Real processes are displayed as specific schemes. Mat. Schemes - the transition from a meaningful description to a formal description of the system, taking into account environmental impact.
Formal object model
Model model model
i.e. systems S,can be represented as a variety of values,
describing the process of functioning of the real system and forming
in the general case, the following subsets:
· COLUMPLEMENT input influenceson the system
h.i., EX, (e.-Simal belongs)i.=1; nX.
· COLUMPLEMENT exterior environmental impacts
v.l E.V. L \u003d 1; NV
· COLUMPLEMENT internal (own) parameterssystems
hkeh. k \u003d 1; nh
· COLUMPLEMENT output characteristicssystems
yjey. J \u003d 1; NY
You can select managed and unmanaged variables.
When modeling systems, the input effects, exposure to the external environment and internal parameters contain both deterministic and stochastic components.
input effects, exposure to the external environment E.and the internal parameters of the system are independent (exogenous) variables.
System functioning process S.describes in time by the operator FS,which in general converts exogenous variables to endogenous in accordance with the ratios of the form:
y.(t) \u003d Fs (x., v, h, t) - all with vek.torus.
The law of functioning of the FS system can be specified as a function, functional, logical conditions, in algorithmic and tabular forms or in the form of a verbal rule of conformity.
The concept of an AS functioning algorithm -the method of obtaining output characteristics, taking into account the input effects, the effects of the external environment and its own system parameters.
The state states are also introduced - system properties at specific points in time.
The combination of all possible state values \u200b\u200bmake up the space state space.
Thus, the chain of the "input - state-output object" of the equation allows you to determine the characteristics of the system:
Thus, under mathematical model of the object(real system) understand the final subset of variables (X (T), V (T), H(t)) together with mathematical connections between them and characteristics y (t).
Typical schemes
In the initial stages of the study, typical schemes are used. : differential equations, finite and probability automata, mass maintenance systems, petri network, etc.
As deterministic models, when the random factors are not taken into account, differential, integrated, integrodifferential and other equations are used to represent systems operating in continuous time, and for presentation of systems operating in discrete time - finite machines and finite-difference schemes .
As stochastic models (when registering random factors), probabilistic machines are used to represent systems with discrete time, and to represent a system with continuous time - mass maintenance systems, etc.
Thus, when constructing mathematical models of operation processes, the following main approaches can be distinguished: continuously deterministic (for example, differential equations); discrete-deterministic (finite automata); discrete-stochastic (probabilistic automata); continuous-stochastic (mass maintenance systems); Generalized, or universal (aggregative systems).
Continuously deterministic models
Consider the features of a continuously deterministic approach on the example using as mat. Models differential equations.
Differential equations are called such equations in which the functions of one variable or several variables will be unknown, and the equation includes not only their functions but their derivatives of various orders.
If unknown - the functions of many variables, then the equations are called - equations in private derivatives.If unknown functions of one independent variable, then take place ordinary differential equations.
Mathematical ratio for deterministic systems in general form:
Discrete-deterministic models.
DDM are subject to consideration automatic theory (TA). The section of the theoretical cybernetics, which studies the device, processing discrete information and changes its internal states only at permissible moments of time.
Eltimate machine gun A vehicle is called a set of internal states and input signals (and, consequently, a plurality of output signals) are finite sets.
Finite automatic It has many internal states and input signals that are finite sets. Machine set Fraame: F \u003d
where Z, X, Y is respectively the final sets of input, output signals (alphabets) and a finite set of internal states (alphabet). Z0îZ - initial state; j (z, x) - function of transitions; y (z, x) - the function of the output.
The machine operates in a discrete automatic time, the moments of which are the tacts, i.e., adjacent to each other equal time intervals, each of which corresponds to the constant values \u200b\u200bof the input, output signal and an internal state. The abstract automatic has one input and one output channels.
To specify the F - machine, you must describe all the elements of the set F \u003d
In the table way of task, the transitions and output table are used, the strings of which correspond to the input signals of the machine, and the columns are its states.
Work description F.- Mili machine Tables j and outputs Y are illustrated in table (1), and the description F - Moore machine - transitions table (2).
Table 1
Transitions |
||||
………………………………………………………… |
||||
………………………………………………………… |
||||
table 2
………………………………………………………… |
||||
Examples of a tabular method of setting the F - mile F1 mile with three states, two input and two output signals are shown in Table 3, and for F - Moore Moore F2 - in Table 4.
Table 3.
Transitions |
|||
Table 4.
With a different method of setting a finite automaton, the concept of directed graph is used. The graph of the automaton is a set of vertices corresponding to different states of the machine and connecting the vertices of the graph of the graph corresponding to those or another transitions of the machine. If the input signal XK calls the transition from the zi state to the zj state, then on the arc automaton graph connecting the vertex Zi with the vertex zj is indicated by XK. In order to set the transition function, the arc of the graph must be noted by the corresponding output signals.
Fig. 1. Count graphs mile (a) and mura (b).
When solving modeling tasks, a often more convenient form is the matrix job of the final automaton. In this case, the matrix of the compounds of the machine is a square matrix C \u003d || Cij ||, whose strings correspond to the initial states, and columns - transition states.
Example. For the previously considered Moore Moore F2, write the state matrix and the output vector:
;
Discrete-stochastic models
Let F be a set of all kinds of pairs of the form (ZK, Yi), where Ui is an element of the output
subsets Y. We will require any element of the set G induced
on the set f, some law of the distribution of the following form:
Elements from F (Z1, Y2) (Z1, Y2ZK, YJ-1) (ZK, YJ)
(XI, ZS) B11 B1BK (J-1) BKJ
Information Networks "HREF \u003d" / TEXT / CATEGORY / INFORMATCIONNIE_SETI / "REL \u003d" BOOKMARK "\u003e Processing ECM information from remote terminals, etc.
At the same time characteristic for
the work of such objects is the random appearance of applications (requirements) on
service and completion of maintenance at random moments of time,
i.e. the stochastic nature of the process of their functioning.
Under the SMO, they understand the dynamic system designed to effectively maintain the random flow of applications with limited system resources. The generalized structure of the SMO is shown in Figure 3.1.
Fig. 3.1. SCO scheme.
The homogeneous applications entering the SMO, depending on the generating cause, are divided into types, the intensity of the flow of type I (i \u003d 1 ... M) flows is indicated by Li. The set of applications of all types is the incoming SMO stream.
Application service is executed m. channels.
Distinguish universal and specialized service channels. For a universal type J channel, the functions of the distribution function FJI (T) of the duration of service of arbitrary type applications are considered known. For specialized channels, the distribution function of the duration of servicing channels of applications of some types is uncertain, the appointment of these applications for this channel.
Q - Schemes can be explored by analytically and simulation models. The latter provides greater versatility.
Consider the concept of mass service.
In any elementary service, you can allocate two main components: expectation of servicing the application and the actual application of the application. This can be displayed as a certain I-th device of the PI service consisting of an application drive in which Li \u003d 0 ... Lih applications can be located simultaneously, where Lih is the Capacity of the I-Wow Drive, and the order service channel, Ki.
Fig. 3.2. Scheme of the device SMO
On each element of the service device, the PI service flows are received: in the Hi drive, the Wi application stream, on the Ki channel - the UI service flow.
Stream of events (Ps) is a sequence of events that occur one after another at some random moments of time. There are threads of homogeneous and inhomogeneous events. HomogeneousThe PS is characterized only by the moments of receipt of these events (causing moments) and is set by a sequence (TN) \u003d (0 £ T1 £ T2 ... £ Tn £ ...), where Tn is the moment of receipt of the N-ego event - a non-negative real number. OPS can also be specified as a sequence of time intervals between N-th and N-1-th events (TN).
Inhomogeneous PS is called a sequence (TN, Fn), where TN is causing moments; Fn is a set of signs of an event. For example, it can be asked to an affiliation to a particular source of applications, the presence of a priority, the possibility of maintenance by one or another type of channel, etc.
Applications served by the Ki channel and the applications that left the PI device for various reasons are not served, form the output stream Yiîy.
The process of functioning of the PI service device can be represented as the process of changing the states of its elements in time Zi (T). The transition to a new state for PI means changing the number of applications that are located in it (in the Ki channel and Hi drive). T. about. The status vector for PI has the form: where - the states of the drive, (https://pandia.ru/text/78/362/images/image010_20.gif "width \u003d" 24 height \u003d 28 "height \u003d" 28 "\u003e \u003d 1 - In the drive one application ..., \u003d - The drive is complete; - Channel condition Ki (\u003d 0 - channel is free, \u003d 1 channel is busy).
Q-schemes of real objects are formed by the composition of many elementary maintenance devices of PI. If ki different service devices are connected in parallel, then there is a multichannel maintenance (multichannel Q-diagram), and if the instruments of PI and their parallel compositions are connected in series, then multiphase maintenance (multiphase Q scheme) takes place.
To specify the Q-scheme, it is also necessary to describe the algorithms of its functioning, which determine the rules for the behavior of applications in various ambiguous situations.
Depending on the occurrence of such situations, algorithms (disciplines) of expectations of applications in the HI drive and servicing the Ki canal are distinguished. The inhomogeneity of the flow of applications is taken into account by introducing the class of priorities - relative and absolute priorities.
T. about. Q-scheme describing the process of operation of the SMO of any complexity is uniquely set as a set of sets: Q \u003d
Network models.
For a formal description of the structure and interaction of parallel systems and processes, and the analysis of causal relations in complex systems uses Petri nets (English. Petri Nets), called N-schemes.
Formally, the N-scheme is set by the top one
N \u003d
where B is a finite set of characters, called positions, B ≠ O;
D - finite set of characters, called transitions D ≠ O,
B ∩ D ≠ O; I - input function (direct incidence function)
I: b × D → (0, 1); O - output function (inverse incident function),
A: B × D → (0, 1). Thus, the input function I displays the transition DJ in
many input positions BJ i (DJ), and the output function o displays
transition DJ in many output positions BJ O (DJ). For each transition
dJ https://pandia.ru/text/78/362/images/image013_14.gif "width \u003d" 13 "height \u003d" 13 "\u003e b | i (bi, dj) \u003d 1),
O (dj) \u003d (Bi b | o (dj, bi) \u003d 1),
i \u003d 1, n; j \u003d 1, m; n \u003d | B |, m \u003d | D |.
Similarly, for each position Bi b is introduced
many input positions of position I (BI) and output transitions
positions O (BI):
I (Bi) \u003d (DJ D | I (DJ, Bi,) \u003d 1),
O (Bi) \u003d (dj d | o (bi, dj) \u003d 1).
Petri net is a dvostot-oriented graph consisting of tops of two types - positions and transitions connected by arcs, the vertices of the same type cannot be connected directly.
An example of a Petri net. White circles indicate positions, strips - transitions, black circles - labels.
Approximate arcs connect positions and transitions, and each arc is directed from the element of one set (position or transition) to the element of another set
(transition or position). Count of N-schemes is a multigraph since he
allows the existence of multiple arcs from one vertex to another.
Decomposition "href \u003d" / text / category / dekompozitciya / "REL \u003d" BOOKMARK "\u003e Decomposition The complex system is represented as a multi-level construction from interconnected elements combined into subsystems of various levels.
As an element of the A-scheme, an aggregate acts, and the relationship between aggregates (inside the S system and with the external environment E) is carried out using the conjugation operator R.
Any unit is characterized by the following sets: time points T, input x and output y signals, states z at each time T. The state of the unit at the time of TT is denoted as z (t) z,
a input and output signals as x (t) x and y (t) y, respectively.
We assume that the transition of the unit from the state Z (T1) into the state Z (T2) ≠ Z (T1) occurs over a small time interval, i.e., the jump Δz takes place.
The transitions of the unit from the state Z (T1) in Z (T2) are determined by their own (internal) parameters of the H (T) H aggregate itself and the input signals X (T) X.
In the initial moment of time T0, the state z have values \u200b\u200bequal to z0, i.e. z0 \u003d z (t0), set by the law of the distribution of the process Z (T) at time t0, namely J. Suppose that the process of functioning the unit in case of influence XN input signal is described by a random operator V. Then at the time of receipt of the input signal TNT
xN can determine the state
z (tn + 0) \u003d V.
Denote half interval T1< t ≤ t2 как (t1, t2], а полуинтервал
t1 ≤ T.< t2 как .
A combination of random operators V and U are considered as an operator of the aggregate transitions to new states. In this case, the process of operation of the unit consists of jumps of states Δz in moments of receipt of input signals (operator V) and changes of states between these points Tn and Tn + 1 (Operator U). No restrictions are superimposed on the U statement U, therefore the jumps of states Δz are allowed at times that are not the moments of receipt of input signals x. In the future, the moments of the jumps of Δz will be called by special points of time Tδ, and the states z (tδ) - by the special states of the A-scheme. To describe the jumps of states Δz in singular time Tδ, we will use a random operator W, which is a special case of the operator U, i.e.
z (tΔ + 0) \u003d W.
In a set of states z, such a subset z (y) is distinguished, which if Z (Tδ) reaches z (y), then this state is the moment of issuing an output signal defined by the output operator
y \u003d g.
Thus, under the unit, we will understand any object, determined by an ordered set of considered sets T, X, Y, Z, Z (Y), H and random operators V, U, W, G.
The sequence of input signals located in the order of their arrival in the A-scheme will be called input message or x-message. The sequence of output signals, ordered relative to the issuance time, call the output message or Y-message.
If brief
Continuous and deterministic models (D-schemes)
Used to study systems operating in continuous time. To describe such systems, differential, integral, integra-differential equations are mainly used. In ordinary differential equations, the function of only one independent variable is considered, and in partial derivative equations - the functions of several variables.
As an example of the use of D-models, it is possible to investigate the operation of a mechanical pendulum or an electrical oscillatory circuit. The technical basis of D-models is analog computing machines (AVM) or rapidly developing hybrid computing machines (GMM). As is known, the main principle of studies on the computer is that according to the specified equations, the researcher (AVM) collects a diagram from individual standard nodes - operating amplifiers with the inclusion of zoom chains, damping, approximation, etc.
The AVM structure varies in accordance with the type of reproducible equations.
In digital computer, the structure remains unchanged, and the sequence of operation of its nodes changes in accordance with the program laid into it. A comparison of AVM and TSM clearly shows the difference between simulation and statistical modeling.
AVM implements a simulation model, but, as a rule, does not use the principles of statistical modeling. Most imitation models are based on the study of random numbers, processes, i.e. on statistical modeling. Continuous-deterministic models are widely used in mechanical engineering in the study of automatic control systems, the choice of depreciation systems, detecting resonant phenomena and oscillations in the technique
etc.
Discrete-deterministic models (F-schemes)
Operate with discrete time. These models are the basis for the work of the work of an extremely important and common class of systems of discrete automata. In order to study their research, an independent mathematical apparatus of automata theory has been developed. Based on this theory, the system is considered as a machine, processing discrete information and changing, depending on the results of its processing, its internal states.
The principles of minimizing the number of elements and nodes in the diagram, device, the optimization of the device as a whole and the sequence of its nodes are based on this model. Along with the electronic circuits, a bright representative of the automata described by this model is a robot that controls (according to a given program) technological processes in a given deterministic sequence.
The machine with numeric software control is also described by this model. The selection of the details processing sequence on this machine is carried out by setting the control node (controller) generating control signals at certain points in time / 4 /.
The theory of automata uses the mathematical apparatus of Boolean functions that operate with two possible values \u200b\u200bof the signals 0 and 1.
The machines are divided into machines without memory, machine guns. The description of their work is made using tables, matrices, graphs displaying the automaton transitions from one state to another. Analytical estimates for any form of a description of the operation of the automaton are very cumbersome and already with a relatively small number of elements, nodes that form the device, practically impossible. Therefore, the study of complex automata schemes, which undoubtedly include robotic devices, is made using imitation modeling.
Discrete-stochastic models (p-schemes)
Applied in the study of the work of probabilistic machines. In the automata of this type, transitions from one state to another are carried out under the influence of external signals and taking into account the internal state of the machine. However, in contrast to Mc machines, these transitions are not strictly determined, but can be carried out with certain probabilities.
An example of such a model represents a discrete Markov chain with a finite set of states. Analysis of F-schemes is based on the processing and transformation of transition probability matrices and the analysis of probabilistic graphs. Already for the analysis of relatively simple devices, the behavior of which is described by F-schemes, it is advisable to use simulation simulation. An example of such a modeling is given in paragraph 2.4.
Continuous-stochastic models (Q schemes)
Used when analyzing a wide class of systems considered as mass maintenance systems. Different processes in their physical nature can be presented as the maintenance process: product supply flows by enterprise, streams of components of custom parts and products, parts of parts on the assembly conveyor, streams of control influences from the ACS management center on workplaces and back requests for information processing in computer etc.
As a rule, these streams depend on many factors and specific situations. Therefore, in most cases, these streams are random in time with the possibility of change in any moments. Analysis of such schemes is made on the basis of the mathematical apparatus of mass maintenance theory. These include a continuous Markov chain. Despite significant successes achieved in the development of analytical methods, mass maintenance theory, the analysis of Q-schemes by analytical methods can be carried out only with significant simplifying assumptions and assumptions. A detailed study of the majority of these schemes, especially such complex, as an automated control system, robotics systems, can only be carried out using imitation modeling.
Generalized models (A-schemes)
Based on the description of the processes of operation of any systems based on the aggregative method. In an aggregative description, the system is divided into separate subsystems that can be considered convenient for the mathematical description. As a result of such a partition (decomposition), the complex system is represented as a multi-level system, separate levels (aggregates) of which are analyzed. Based on the analysis of individual aggregates and, taking into account the laws of the relationships of these aggregates, it is possible to carry out a comprehensive study of the entire system.
, Yakovlev systems. 4th ed. - M.: Higher School, 2005. - P. 45-82.
A model of a complex system, discussed earlier, is a mathematical scheme for modeling a common type. In practice, to formalize conceptual models of a number of systems, it is more profitable to apply typical modeling schemes that take into account the method of presenting time in the model (continuous variable or discrete), and on the other hand, the degree of randomness of the simulated processes. According to these features, the following mathematical modeling schemes (MM classes) are distinguished.
Continuously - deterministic models (D - diagrams).
Discrete - deterministic models (F - schemes).
Discreteren - probabilistic models (P - schemes).
Continuous - probabilistic models (Q - Schemes).
Network models (n - circuits).
Aggregate models (A - Schemes).
Continuously deterministic models. In these models time t. Remies continuous variable, and random factors in the system neglected. The mathematical apparatus of models is the theory of differential and integral equations, with which an adequate description of the dynamic systems is achieved. The main method of describing and researching the processes of the functioning of dynamic systems and their structures was most developed.
An example of a continuously deterministic model of a single-channel automatic control system is an inhomogeneous differential equation with constant coefficients.
In this equation x (t) - entrance effect; y (t) - the output value characterizing the position of the control object; - Internal system parameters.
If the dynamic system is described by a nonlinear differential equation, then it is linearized and solved as linear.
The use of continuously deterministic models allows you to quantify not only the analysis of dynamic systems, but also the optimal synthesis of them.
Discrete-deterministic models. In discrete-deterministic (DD) models time t. It is a discrete variable, where - the sampling step, and the discrete moments of time.
The main mathematical apparatus used in the construction of DD models is the theory of difference equations and the apparatus of discrete mathematics, in particular, the theory of finite automata.
The difference equation is an equation containing final differences in the desired function
where - according to the state of the system and the external influence in the discrete moments of time.
In the applied tasks of DD - models in form (2.6), they often occur as intermediates in the study of ND models on a computer when the analytical solution of the differential equation cannot be obtained and the difference schemes have to be applied.
Briefly consider the theory of finite automata, which is used to build DD - models.
The final automaton is a mathematical model of a discrete system, which under the action of input signals generates output signals, and which can have some variable internal states; Here are the final sets.
The final automatic is characterized by: input alphabet; output alphabet; internal alphabet of states; initial state; transition function; function outputs.
The process of functioning of a finite automaton is as follows. In -M, the input signal is in the input of the automaton, which is in the input signal, to which the machine responds to the transition to-with the state to the state and issuing the output signal, for example, the mile finite automaton is described by the following recurrent ratios:
Discrete-probabilistic models. In the discrete-probabilistic model, random items of the studied complex system are taken into account. The main mathematical apparatus used in the construction and study of DV - models is the theory of difference stochastic equations and the theory of probabilistic machines.
The difference stochastic equation is such an equation that contains random parameters or random input effects.
Let a random - vector of parameters and a random sequence of input influences are defined on probabilistic space. 
The nonlinear difference stochastic equation of the order has the form (2.8)
where the specified initial states of the system; The specified function of variables.
By the solution of this equation, a random consistency of the states of the simulated system is defined on the set:
If the function is linear software, then (2.8) will take the form:
(2.9)
where vector parameters.
Another mathematical apparatus of constructing DV - models of complex systems represents the theory of probabilistic machines.
A probabilistic machine defined on the set is a finite machine in which the function of transitions 
And the function of the outputs are random functions that have some probabilistic distributions.
We will take the designation for probabilistic distributions - the initial distribution of probabilities, 
- the likelihood of an event consisting in the fact that in -M clock in a state of automatic under the influence of the input signal will give output signal and goes on-it
The mathematical model of a probabilistic machine is fully determined by five elements :.
Continuous - probabilistic models. When constructing and studying HV-models, the theory of stochastic differential equations and the theory of mass maintenance is used.
Stochastic differential equation (in the form of ito) has the form:
where is a random process that determines the state of the system at the time of time; - Standard Wiener Random Process; - Diffusion and transfer coefficients. NB - model is often used in modeling stochastic control systems, exchange processes.
The theory of mass service develops and explores mathematical models of different processes of operations of systems, for example: supplies of raw materials and components to some enterprise; tasks coming on a computer from remote terminals; Call at telephone stations, etc. For the functioning of such systems, stochasticity is characterized: the random of the time of the appearance of applications for maintenance, etc.
The system described as a mass maintenance system (SMO) consists of service devices. The service device consists of a drive of applications, in which applications can be simultaneously located, and application service channels; - Capacity of the drive, that is, the number of places in the queue for servicing applications in the channel.
On each element of the device comes flow streams; In the drive - the flow of applications, on the channel - the flow of "maintenance". The application stream represents a sequence of time intervals between the moments of appearing applications at the entrance of the SMO and forms a subset of unmanaged SMO variables. A stream is a sequence of time intervals between the moments of the beginning and end of servicing applications and forms a subset of controlled variables.
Applications served by the SMO form the output stream - the sequence of time intervals between the moments of requests for applications. Not served applications, but who left the SMO for various reasons, form a weekend of lost applications.
Network models Used to formalize causal relationships in complex systems with parallel processes. The basis of these models is a network of Petri. With a graphical interpretation, Petri network is a graph of a special type consisting of peaks of two types - Positionsand transitionsconnected by oriented arcs, and each arc can only associate the variety of vertices (position with the transition or transition with a position). The vertices position are marked with mugs, tops-transitions - invasses. From a meaningful point of view, the transitions correspond to the events inherent in the system under study, and the positions are the conditions for their occurrence.
Thus, the combination of transitions, positions and arc allows you to describe causal relationships inherent in the system, but in statics. So that the network of Petri "came to life," one more type of network objects is introduced - the so-called chips or Tagspositions that move on network transitions provided the label in the input position and the absence of a label at the output position. The location of the chips in the network positions is called network markup.
Aggregate models. An analysis of existing tasks leads to the conclusion that the comprehensive solution of problems is possible only if the modeling systems are based on a single mathematical modeling scheme. Such an approach to the formalization of the process of functioning of a complex system is proposed Buslenko N.P. and based on the concept of "aggregate".
In the aggregate description, the complex system is divided by the subsystem, while maintaining the connection to ensure their interaction. If the subsystem turns out to be difficult, the process of dismissal continues until subsystems are formed, which in the conditions of the problem under consideration can be considered comfortable for the mathematical description.
As a result, a multi-level design is obtained from interconnected elements of the combined in the subsystems of various levels. Elements of the aggregate model are aggregates. Communications between aggregates and external environments are carried out using interface operators. The unit itself can also be considered as an aggregate model, that is, to be divided into elements of the next level.
Any unit is characterized by sets: time moments T.Entrance X. and weekends Y. Signals, aggregate states Z. at every moment of time t.. The process of functioning the unit consists of irregular states in the moments of input signals x. and changes of states between these moments and.
The moments of jumps that are not the moments of receipt of input signals are called special points of time, and the states by the special states of the aggregate scheme. In a variety of states Z. Select a subset that if reaches, this state is the moment of issuing an output signal. y..
The initial information in constructing the MM process functioning processes is data on the appointment and working conditions of the under study (designed) system. This information determines the main purpose of modeling, the requirements for mm, the level of abstraction, the choice of the mathematical modeling scheme.
The concept of a mathematical scheme allows us to consider mathematics not as a method of calculation, but as a method of thinking, means of forming concepts, which is the most important in transition from a verbal description to a formalized representation of the process of its functioning in the form of some MM.
When using the mathematical scheme, first of all, the system researcher should be interested in the issue of adequacy. Displaying in the form of specific schemes of real processes in the system under study, and not the possibility of obtaining an answer (solution result) on a specific issue of research.
For example, the presentation of the process of functioning of the IVC of collective use in the form of a network of mass maintenance schemes makes it possible to describe the processes occurring in the system, but in case of complex laws, incoming streams and service streams do not give the possibility of obtaining results explicitly.
Mathematical scheme It can be defined as a link when switching to a formalized description of the process of operation of the system, taking into account the effects of the external environment. Those. There is a chain: a descriptive model - a mathematical scheme-imitation model.
Each specific system is characterized by a set of properties under which the values \u200b\u200breflecting the behavior of the simulated object (real system) and take into account the conditions for its operation in cooperation with the external environment (system) E.
When building a MM system, it is necessary to resolve the question of its completeness. The fullness of the simulation is regulated mainly by the choice of the "System-E E" boundaries. The task of simplifying MM, which helps to allocate the basic properties of the system, rejecting secondary, in terms of purpose, modeling is also solved.
MM modeling object, i.e. Systems can be represented as a set of values \u200b\u200bdescribing the process of functioning the real system and forming the following under the set:
Aggregate - which influences on
A combination of environmental impacts
A combination of internal (own) system parameters
A combination of the output characteristics of the system
In the listed sets, managed and unmanaged values \u200b\u200bcan be distinguished. In the general case, X, V, H, Y, non-stopped sets, contain both deterministic and stochastic components.
Thus, under the MM object, we understand the final set of variables together with mathematical connections between them and characteristics.
Modeling is called deterministic if operators F, F deterministic, i.e. For a specific entry, the input is deterministic. Determined modeling is a special case of stochastic modeling. In practice, modeling objects in the field of system analysis at the primary stages of the study is rational to use typical mathematical schemes: differential equations, finite and probability machines, SMO, etc.
As deterministic models, when a random fact is not taken into account in the study, differential, integral and other equations are used to represent systems that are functioning in continuous time, and for presentation of systems operating in discrete time - finite machines and difference schemes.
General guidelines
The purpose of the discipline "Methods of optimal solutions" is to master the methodology for modeling trade and economic processes to analyze and optimal management them.
The purpose of these methodological instructions is to assist students in studying the foundations of economic and mathematical modeling, show the necessary practical skills on the use of mathematical methods in building models of communication indicators of trade practices and based on their scientific substantiation of the choice of management decisions.
The object of studying the course is the economic mechanisms of management of trade organizations and enterprises.
The subject of studying the course is the information and functional bonds of trade and economic systems.
The result of admission to the test on the discipline "Methods of optimal solutions" is solvable testing with all the tasks with the mark of the teacher "Changed". The studied test work remains among the teacher, a review of the educational and methodological department. In case of ambiguity of the conditions of tasks and with the emergence of difficulties in solving problems, it is necessary to consult a student from the lead teacher. If solved work is not credited, the student needs to eliminate the comments and pass the test on re-review.
Rules of paperwork
On the title page, the name of the discipline, the name of the faculty, course, surname, name, patronymic should be written.
At the beginning of work or on the title page, the tasks performed in the control task should be specified.
Before the solution of each task, you must completely record its condition. The task solution should include detailed calculations and brief explanations, economic analysis of the results obtained. At the end of the test work, lead a list of used literature and put your signature.
Task number 1
Build an economic and mathematical model for determining the structure of dishes at a catering plant that provides maximum profits based on specified product cost standards for the first and second dishes presented in the following table 1.
Data for tasks should be selected from Table 2 according to the first letters of the name, name and patronymic of the student. For example, the student Kornienko Nikolai Sergeevich must solve the problem with the data A 11 \u003d 2, a 12 \u003d 3, a 21 \u003d 2, a 23 \u003d 13, a 31 \u003d 6, a 32 \u003d 7, a 33 \u003d 8, a 41 \u003d 9 , a 42 \u003d 6, a 44 \u003d 4, a 54 \u003d 19, b 1 \u003d 450, b 2 \u003d 310, b 3 \u003d 410, b 4 \u003d 315, b 5 \u003d 400, C 1 \u003d 89, C 2 \u003d 41 , C 3 \u003d 50.
Mathematical System Modeling Schemes
Advantages and disadvantages of imitation modeling
Maintenance dignity Simulation in the study of complex systems:
· The ability to explore the features of the process of functioning S system in any conditions;
· Due to the use of computers, the duration of the tests is significantly reduced compared with the field experiment;
· The results of the inventory tests of the real system or its parts can be used to carry out imitation modeling;
· The flexibility of variation of the structure, algorithms and parameters of the simulated system when searching for the optimal version of the system;
· For complex systems is the only practically implemented method for studying the process of operation of systems.
Maintenance limitations Simulation:
· For complete analysis of the characteristics of the process of operation and the search for the optimal option, it is necessary to repeatedly reproduce the simulation experiment by varying the source data of the task;
· Great machine time costs.
Machine modeling efficiency.When modeling, it is necessary to ensure maximum efficiency of the system model. Efficiency It is usually defined as some difference between any indicators of the value of the results obtained during the operation of the model, and the costs that were invested in its development and creation.
The effectiveness of simulation can be assessed by a number of criteria:
· Accuracy and accuracy of modeling results,
· Time for building and working with the model M.,
· The cost of machine resources (time and memory),
· The cost of developing and operating the model.
The best evaluation of efficiency is the comparison of the results obtained with real studies. Using a statistical approach with a certain degree of accuracy (depending on the number of implementations of the machine experiment), the averaged characteristics of the system behavior are obtained.
The total amount of machine time consists of time to enter and output for each modeling algorithm, time to carry out computing operations, taking into account access to RAM and external devices, as well as the complexity of each modeling algorithm and experiment planning.
Mathematical schemes.Mathematical model- This is a combination of mathematical objects (numbers, variables, sets, vectors, matrices, etc.) and relations between them, adequately reflecting the physical properties of the technical object being created. The process of forming a mathematical model and use of it for analysis and synthesis is called mathematical modeling.
When building a mathematical model of the system, it is necessary to solve the issue of its completeness. The fullness of the model is adjustable, mainly by the choice of the border "System S. - Wednesday E." The task of simplifying a model should also be solved, which helps to allocate depending on the purpose of modeling the main properties of the system, rejecting the minor.
When moving from the process of functioning of the system to a formal description of the system, taking into account the impact of the external environment, use mathematical scheme As the link in the chain "Descriptive model - a mathematical scheme - a mathematical (analytical or (and) imitation) model."
Formal object model. Object model (system S.) It can be represented as a set of values \u200b\u200bdescribing the process of functioning of the real system:
· Aggregate of input influences on the system
x i \u003d x, I \u003d.;
· A combination of environmental impacts
v. J. = V., j.= ;
· A combination of internal (own) system parameters
h k \u003d h, k \u003d;
· A combination of the output characteristics of the system
y j \u003d y, j \u003d.
In general x i, v j, h k, y j They are elements of non-passing subsets and contain both deterministic and stochastic components.
Input effects, exposure to the external environment E. and the internal parameters of the system are independent (exogenous) variables that in vector form have a view respectively ( t.) = (x. 1 (t.), x. 2 (t.), …, x Nx.(t.)); (t.) = (v. 1 (t.), v. 2 (t.), …, v NV.(t.)); (t.) = (h. 1 (t.), h. 2 (t.), …, h NN(t.)), and the output characteristics are dependent (endogenic) variables and in vector form have the form: ( t.) = (w. 1 (t.), w. 2 (t.), …, nY.(t.)). You can select managed and unmanaged variables.
System functioning process S. Describes in time by the operator F S.which converts exogenous variables to endogenous in accordance with the ratio of the form
(t.) = F S.(,,, t.). (2.1)
A combination of the dependencies of the output characteristics of the system of time y J.(t.) for all species j \u003d.called output trajectory (t.). Dependence (2.1) is called the law of functioning system F swhich is specified in the form of function, functional, logical conditions, in algorithmic, tabular forms, or as a verbal rule of conformity. A S functioning algorithm is called the method of obtaining output characteristics, taking into account the input effects ( t.), environmental impacts ( t.) and own system parameters ( t.). The same law of functioning F S. Systems S. can be implemented in various ways, i.e. With the help of many different functioning algorithms A S..
Mathematical models are called dynamic(2.1), if mathematical ratios describe the behavior of the object (system) of modeling in time t.. reflect dynamic properties.
For staticmodels The mathematical model is a mapping between two subsets of the properties of the simulated object Y. and ( X, V, H) at a certain point, that in vector form can be recorded as
= f.(, , ). (2.2)
Relations (2.1) and (2.2) can be given in various ways: analytically (using formulas), graphically, table, etc. These relations can be obtained through system properties. S. At specific points in time, called states. State of the system S.characterized by vectors
" = (z " 1, z. " 2, ..., z "k) I. "" = (z "" 1 , z "" 2 , ..., z "" k),
where z " 1 = z. 1 (t "), z " 2 = z. 2 (t "), …, z "K.= z K.(t ") in the moment t "Î ( t. 0 , T.); z "" 1 = z. 1 (t ""), z "" 2 = z. 2 (t ""), …, z "" k = z K.(t "") in the moment t ""Î ( t. 0 , T.) etc. k \u003d.
If we consider the process of functioning system S. as a consistent state change z. 1 (t.), z. 2 (t.), …, z K.(t.), then they can be interpreted as the coordinates of the point in k.-Herm phase space. Moreover, each implementation of the process will correspond to some phase trajectory. The set of all possible state values \u200b\u200b() is called space of states Object modeling Z., and
z K.Î Z..
System status S. At the time of time t. 0 < t * £ T. fully determined by the initial conditions 0 \u003d ( z. 0 1 , z. 0 2 , …, z. 0 K.) [where z. 0 1 = z. 1 (t. 0),
z. 0 2 = z. 2 (t. 0), …, z. 0 K. = z K.(t. 0)], entrance effects ( t.), internal parameters ( t.) and exposure to the external environment ( t.) who took place in the time t * – t. 0, with the help of two vector equations
(t.) \u003d F (0 ,,,, t.); (2.3)
(t.) \u003d F (, t.). (2.4)
The first equation for the initial state 0 and exogenous variables, determines the vector function ( t.), and the second of the value obtained ( t.) - endogenous variables at the system output ( t.). Thus, the chain of the "Input - Status" object equations allows you to determine the characteristics of the system
(t.) \u003d F [f (0 ,,,, t.)]. (2.5)
In general, time in the system model S. can be considered on the modeling interval (0, T.) both continuous and discrete, i.e. quantized on segments long D t. temporary units each when T. = m.D. t.where m. = - The number of sampling intervals.
Thus, under mathematical modelthe object (real system) understand the final subset of variables (( t.), (t.), (t.)) Together with mathematical connections between them and characteristics ( t.).
If the mathematical description of the modeling object does not contain randomness elements or they are not taken into account, i.e. If we assume that in this case the stochastic effects of the external environment ( t.) and stochastic internal parameters ( t.) missing, then the model is called deterministic In the sense that the characteristics are uniquely determined by deterministic input influences
(t.) = f.(, t.). (2.6)
Obviously, the deterministic model is a private case of a stochastic model.
Typical mathematical schemes.In the practice of modeling objects in the field of system engineering and system analysis at the initial stages of the study of the system more efficiently use typical mathematical schemes: Differential equations, finite and probability automata, mass maintenance systems, Petri nets, aggregative systems, etc.
Typical mathematical schemes have the advantages of simplicity and visibility. As deterministic models, when the study random factors are not taken into account, differential, integrated, integrodifferential and other equations are used to represent systems operating in continuous time, and for presentation of systems operating in discrete time, finite machines and finite-difference schemes. As stochastic models (when taking into account random factors), probabilistic machines are used to represent systems with discrete time, and for presentation of systems with continuous time - mass maintenance systems. For the analysis of causal relationships in complex systems, where several processes are simultaneously flowing in parallel, Petri nets are used. To describe the behavior of continuous and discrete, deterministic and stochastic systems (for example asoi), it is possible to apply a generalized (universal) approach based on an aggregative system. With an aggregative description, the complex object (system) is dissected to a finite number of parts (subsystems), while maintaining bonds that ensure the interaction of parts.
Thus, when constructing mathematical models of operation processes, the following main approaches can be distinguished: continuously deterministic ( D.-schemes); Discrete-deterministic ( F.-schemes); discrete-stochastic ( R-schemes); continuous-stochastic ( Q.-schemes); Network ( N.-schemes); generalized or universal ( but-schemes).
2.2. Continuous-deterministic models ( D.-schemes)
Basic relations. Consider the features of the continuous-deterministic approach on the example of use as mathematical models of differential equations. Differential equations These equations in which the unknown functions of one or several variables will be unknown, and the equation includes not only functions, but also their derivatives of various orders. If unknown functions of many variables, the equations are called equations of private derivativesOtherwise, when considering the function of one independent variable equation is called ordinary differential equations.
Mathematical ratio for deterministic systems (2.6) in general will be
" (t.) = (, t.); (t. 0) = 0 , (2.7)
where " = d./dt., = (y. 1 , y. 2 , …, y N.) and \u003d ( f. 1 , f. 2 , …, f N.) – n.- dimensional vectors; (, t.) - a vector function that is defined by some ( n.+1) -Mim (, t.) Set and is continuous.
Mathematical schemes of this species are called D-schemes (eng. dynamic), they reflect the dynamics of the system being studied, and as an independent variable, on which unknown desired functions depend on, usually serves t..
In the simplest case, the ordinary differential equation has the form:
y "(t.) = f.(y., t.). (2.8)
Consider the simplest example of formalizing the process of functioning of two elementary schemes of various nature: mechanical S. M (pendulum oscillation, Fig.2.1, but) and electrical S. K (oscillatory contour, Fig.2.1, b.).
Fig. 2.1. Elementary systems
The process of small oscillations of the pendulum is described by an ordinary differential equation.
m. M. l. M 2 ( d. 2 F.(t.)/ dt. 2) + M. M. gL M. F.(t.) = 0,
where m. M, l. M - the mass and length of the pendulum suspension; g. - acceleration of gravity; F.(t.) - the angle of deviation of the pendulum at the time of time t..
From this free fluctuation equation of the pendulum, you can find estimates of the characteristics of interest. For example, the period of pendulum oscillation
T. M \u003d 2p.
Similarly, the processes in the electrical oscillatory circuit are described by an ordinary differential equation
L. K ( d. 2 q.(t.)/dt. 2) + (q.(t.)/C. K) \u003d 0,
where L. K, C. K - inductance and capacitance of the capacitor; q.(t.) - Capacitor charge at time t..
From this equation, you can get different estimates of the characteristics of the process in the oscillatory circuit. For example, the period of electrical oscillations
T. M \u003d 2p.
Obviously, introducing notation h. 2 = m. M. l. M 2 \u003d. L. K, h. 1 = 0,
h. 0 = m. M. gL M \u003d 1 / C. K, F.(t.) = q.(t.) = z.(t.), we obtain the ordinary differential equation of the second order, describing the behavior of this closed system:
h. 2 (d. 2 z.(t.)/dt. 2) + h. 1 (dZ.(t.)/dt.) + h. 0 z.(t.) = 0, (2.9)
where h. 0 , h. 1 , h. 2 - system parameters; z.(t.) - system status at time
of time t..
Thus, the behavior of these two objects can be studied on the basis of a common mathematical model (2.9). In addition, it should be noted that the behavior of the pendulum (systems S. M) can be studied using an electrical oscillatory circuit (systems S. TO).
If the system is studied S. (pendulum or contour) interacts with the external environment E.then there is an input effect x.(t.) (The external force for the pendulum and the energy source for the contour), and the continuous-deterministic model of such a system will look at:
h. 2 (d. 2 z.(t.)/dt. 2) + h. 1 (dZ.(t.)/dt.) + h. 0 z.(t.) = x.(t.). (2.10)
From the point of view of the general mathematical model (see paragraph 2.1) x.(t.) is the input (control) effect, and the state of the system S. In this case, it can be considered as an output characteristic, i.e. The output variable coincides with the system of the system at the moment y. = z..
Possible applications D.-schemes. To describe linear control systems, like any dynamic system, inhomogeneous differential equations have permanent coefficients
where, ..., - an unknown function of time and its derivatives; And - famous functions.
Using, for example, a Vissim software package, intended for imitation modeling of processes in control systems, which can be described by differential equations, we will modify the solution of an ordinary inhomogeneous differential equation.
where is some desired function of time on the segment at zero initial conditions, we take h. 3 =1, h. 2 =3, h. 1 =1, h. 0 =3:
Representing the specified equation on the highest of the derivatives, we obtain the equation
which can be modified using a set of standard Vissim package blocks: arithmetic blocks - GAIN (multiplication by constant), Summing-junction (adder); Integrator integrator blocks (numerical integration), Transfer Function (specifying the equation represented as a transfer function); block blocks of signals - const (constant), STEP (single function in the form of "steps"), Ramp (linearly increasing signal); Signal-receiving blocks - plot (display in the time field of signals, which are analyzed by the researcher during modeling).
In fig. 2.2 shows a graphical representation of this differential equation. The input of the leftmost integrator corresponds to the variable, the input of the average integrator - and the input of the extreme right integrator. The output of the extreme right integrator corresponds to the variable y..
A special case of dynamic systems described D.-Chemes are automatic control systems(Saoo) and regulation(Sar). The actual object is submitted in the form of two systems: control and controlled (control object). The structure of the multidimensional system of automatic control of the general form is shown in Fig. 2.3, where marked endogenic Variables: ( t.) - vector of input (specifying) impacts; ( t.) - the vector of disturbing effects; " (t.) - vector error signals; "" (t.) - vector control influences; exogenous Variables: ( t.) - system status vector S.; (t.) - vector output variables, usually ( t.) = (t.).
Fig. 2.2. Graphic representation of the equation
The control system is a set of software and technical means that achieve a certain purpose management object. How accurately the object reaches a given goal, can be judged (for a one-dimensional system) by state coordinate y.(t.). The difference between the specified y. ass t.) And valid y.(t.) The law of changing the controlled value is a management error " (t.) = y. ass t.) – y.(t.). If the prescribed law of changes in the controlled value complies with the law of changing the input (specifying) impact, i.e. x.(t.) = y. ass t.), T. " (t.) = x.(t.) – y.(t.).
Systems for which management errors " (t.) \u003d 0 at all times, called perfect. In practice, the implementation of ideal systems is impossible. The task of the automatic control system is to change the variable y.(t.) According to the specified law with a certain accuracy (with a valid error). The system parameters must provide the required control accuracy, as well as the stability of the system in the transition process. If the system is stable, then analyze the behavior of the system in time, the maximum deviation of the adjustable variable y.(t.) In the transition process, the transition time, etc. The order of the differential equation and the value of its coefficients is fully determined by the static and dynamic parameters of the system.
Fig. 2.3. Automatic control system structure:
Uc - control system; O - control object
So use D.-Shem allows you to formalize the process of functioning continuously deterministic systems S. and evaluate their main characteristics using an analytical or simulation approach implemented in the form of a corresponding language for modeling continuous systems or using analog and hybrid means of computing.
2.3. Discrete-deterministic models ( F.-schemes)
Basic relations. Consider the features of the discrete-deterministic approach on the example of use as a mathematical apparatus of machine theory. The system is represented as a machine as some device with input and output signals, processing discrete information and changes its internal states only at permissible moments of time. Eltimate machine gun A vehicle is called a set of internal states, input and output signals are finite sets.
Abstract final automatic (eng. Finite Automata) can be represented as a mathematical scheme ( F.-scheme), characterized by six elements: final multiple H. input signals (input alphabet); End multiple Y. output signals (output alphabet); End multiple Z. internal states (internal alphabet or alphabet of states); initial state z. 0 , z. 0 Î Z.; transition function j ( z., x.); Function y ( z., x.). Automatic, asked F.-Fee: F. = á Z., X., Y., y, j, z. 0 ñ, functions in discrete time, the moments of which are the clocks, each of which corresponds to the constant values \u200b\u200bof the input and output signals and internal states. Denote the state, as well as the input and output signals corresponding to t.- We have a tact t.\u003d 0, 1, 2, ..., through z.(t.), x.(t.), y.(t.). At the same time by condition z.(0) = z. 0, A. z.(t.)Î Z., x.(t.)Î X., y.(t.)Î Y..
The abstract finite machine has one input and one output channels. At every moment t.\u003d 0, 1, 2, ... discrete time F.-Avtomat is in a certain state z.(t.) From the set Z. Machine states, and at the initial moment of time t.\u003d 0 it is always in the initial state z.(0) = z. 0. In the moment t.Being able to z.(t.), the machine is able to perceive the signal on the input channel x.(t.)Î X. and give a signal on the output channel y.(t.) =
y [ z.(t.), X.(t.)], turning to the z state ( t.+1) =
j [ z.(t.), x.(t.)], z.(t.)Î Z., y.(t.)Î Y.. Abstract finite machine implements some display of multiple words of the input alphabet X.on many words of the weekend
Alphabet Y.. In other words, if on the inlet of the final automaton installed in the initial state z. 0, serve in some sequence the letter of the input alphabet x.(0), x.(1), x.(2), ..., i.e. Input word, then the letters of the output alphabet will appear at the output of the machine y.(0), y.(1), y.(2), ..., forming a weekend.
Thus, the operation of the final automaton occurs according to the following scheme: in each t.-Whte on the inlet of the automaton in a state z.(t.), Some signal is served x.(t.), which he reaches the transition ( t.+1) -Ho tact in a new condition z.(t.+1) and issuing some output signal. The above can be described in the following equations: for F.-Automat of the first kind called also millet Mili.,
z.(t.+1) \u003d j [ z.(t.), x.(t.)], t.= 0, 1, 2, …; (2.15)
y.(t.) \u003d y [ z.(t.), x.(t.)], t.= 0, 1, 2, …; (2.16)
for F.- Automatic second kind
z.(t.+1) \u003d j [ z.(t.), x.(t.)], t.= 0, 1, 2, …; (2.17)
y.(t.) \u003d y [ z.(t.), x.(t -1)], t.= 1, 2, 3,…. (2.18)
The machine of the second kind for which
y.(t.) \u003d y [ z.(t.)], t.= 0, 1, 2, …, (2.19)
those. The output function does not depend on the input variable x.(t.), called mura.
Thus, equations (2.15) - (2.19), fully specifying
F.- Automatic, are a special case of equations (2.3) and (2.4) when
system S. - deterministic and on its only login comes the discrete signal X..
According to the number of states, the final machines with memory and without memory are distinguished. Memory machines have more than one state, and automata without memory (combinational or logic schemes) have only one state. At the same time, according to (2.16), the operation of the combination circuit is that it puts in conformity to each input signal x.(t.) a specific output signal y.(t.), i.e. implements the logical function of the form
y.(t.) \u003d y [ X.(t.)], t.= 0, 1, 2, … .
This feature is called Boolean if the alphabet X. and Y.which own the values \u200b\u200bof the signals x. and y., consist of two letters.
By the nature of the discrete time countdown, the final machines are divided into synchronous and asynchronous. In synchronous F.- Automatic moments of time in which the automatic "reads" the input signals are determined by force synchronizing signals. After another synchronizing signal, taking into account the "read" and in accordance with equations (2.15) - (2.19), there is a transition to a new state and the output signal at the output, after which the machine can perceive the next input signal. Thus, the reaction of the automaton for each input signal value ends in one clock, the duration of which is determined by the interval between adjacent synchronizing signals. Asynchronous F.-Automat reads the input signal continuously and therefore, reacting to a sufficiently long input signal of a constant value x., It can, as follows from (2.15) - (2.19), change the state several times, issuing the corresponding number of output signals until it goes into a steady, which can no longer be changed by this input signal.
Possible applications F.-schemes.To set the final F.-Automat, it is necessary to describe all the elements of the set F.= <Z., X., Y., y, j, z. 0\u003e, i.e. input, internal and output alphabets, as well as the functions of transitions and outputs, and among the set of states it is necessary to highlight the state z. 0, in which the machine is in a state t.\u003d 0. There are several ways to job job. F.-Avtomatov, but the most commonly used tabular, graphic and matrix.
The table of transitions and outputs is specified in the table, the strings of which correspond to the input signals of the machine, and the columns are its states. The first left column corresponds to the initial state. z. 0. At intersection i.- Row I. k.-to column of the transition table is placed the corresponding value of J ( z K., x I.) Functions of transitions, and in the output table - the corresponding value of Y ( z k, x i) Output functions. For F.-Automat Moore Both tables can be combined.
Work description F.-Avtomat Mili Tables J and Outputs Y illustrate Table. 2.1, and description F.-Automat Moore - the table of transitions (Table 2.2).
Table 2.1
| X I. | z K. | |||
| z. 0 | z. 1 | … | z K. | |
| Transitions | ||||
| x. 1 | j ( z. 0 , x. 1) | j ( z. 1 , x. 1) | … | j ( z K., X. 1) |
| x. 2 | j ( z. 0 , x. 2) | j ( z. 1 , x. 2) | … | j ( z K., X. 2) |
| … | … | … | … | … |
| x I. | j ( z. 0 , x I.) | j ( z. 1 , x I.) | … | j ( z K., X I.) |
| Outputs | ||||
| x. 1 | y ( z. 0 , x. 1) | y ( z. 1 , x. 1) | … | y ( z K., x. 1) |
| x. 2 | y ( z. 0 , x. 2) | y ( z. 1 , x. 2) | … | y ( z K., x. 2) |
| … | … | … | … | … |
| x I. | y ( z. 0 , x I.) | y ( z. 1 , x I.) | … | y ( z K., x I.) |
Table 2.2.
| x I. | y ( z K.) | |||
| y ( z. 0) | y ( z. 1) | … | y ( z K.) | |
| z. 0 | z. 1 | … | z K. | |
| x. 1 | j ( z. 0 , x. 1) | j ( z. 1 , x. 1) | … | j ( z K., x. 1) |
| x. 2 | j ( z. 0 , x. 2) | j ( z. 1 , x. 2) | … | j ( z K., x. 2) |
| … | … | … | … | … |
| x I. | j ( z. 0 , x I.) | j ( z. 1 , x I.) | … | j ( z K., x I.) |
Examples of the table way of task F.-Automat Mili F.1 are given in Table. 2.3, and for F.-Automat Mura. F.2 - in table. 2.4.
Table 2.3.
| x I. | z K. | ||
| z. 0 | z. 1 | z. 2 | |
| Transitions | |||
| x. 1 | z. 2 | z. 0 | z. 0 |
| x. 2 | z. 0 | z. 2 | z. 1 |
| Outputs | |||
| x. 1 | y. 1 | y. 1 | y. 2 |
| x. 2 | y. 1 | y. 2 | y. 1 |
Table 2.4.
| Y. | |||||
| x I. | y. 1 | y. 1 | y. 3 | y. 2 | y. 3 |
| z. 0 | z. 1 | z. 2 | z. 3 | z. 4 | |
| x. 1 | z. 1 | z. 4 | z. 4 | z. 2 | z. 2 |
| x. 2 | z. 3 | z. 1 | z. 1 | z. 0 | z. 0 |
With a graphical method of setting a finite automaton, the concept of directed graph is used. The graph of the automaton is a set of vertices corresponding to different states of the machine and connecting the vertices of the graph of the graph corresponding to those or another transitions of the machine. If the input signal x K. causes a transition from a state z I. In a state z j.then on the arc machine column connecting the vertex z I.c vertex z j., denotes x K.. In order to set the function of the outputs, the arc of the graph must be noted by the corresponding output signals. For mile machines, this markup is made like this: if the input signal x K. acts on the state z I., it turns out an arc coming from z I. and labeled x K.; This arc is additionally marked with output y.\u003d Y ( z I., x K.). For the Moore machine, similar marking of the graph is: if the input signal x K., acting on some state of the machine, causes a transition to a state z j., then arc directed in z I. and labeled x K.additionally celebrate weekends
Signal y.\u003d Y ( z j., x K.).
In fig. 2.4. but, b. Previously given to the tables F.- Automatic Mili. F.1 and Mura. F.2, respectively.
Fig. 2.4. Counts of automatic machines A - mile and b - Mura
In case of matrix matrix, matrix of automatic compound matrix FROM=||with ij.||, lines correspond to the initial states, and the columns - the state of the transition. Element with ij. = x K./y S.intersection
i.- Row I. j.-to column, in the case of a mile machine corresponds to the input signal x K.causing a transition from a state z I. In a state z j., and output y S.issued with the transition. For Mili Machine F.1 considered above, the compound matrix has the form:
x. 2 / y. 1 – x. 1 / y. 1
C. 1 = x. 1 / y. 1 – x. 2 / y. 2 .
x. 1 / y. 2 x. 2 /y. 1 –
If the transition from state z I. In a state z j. occurs under the action of several signals, the element of the matrix c ij. It is a set of "input-output" pairs for this transition connected by the disjunction sign.
For F.- Automatic Moore element with ij. is equal to the set of input signals on the transition ( z i, z j), and the output is described by the output vector
= y ( z K.) ,
i.- Which component of which is an output signal marker z I..
For reviewed above F.-Automat Mura. F2. Connection matrices and vector outputs have the form:
– X. 1 – X. 2 – W. 1
– X. 2 – – X. 1 w. 1
C. 2 = – X. 2 – – X. 1 ; \u003d W. 3
x. 2 – X. 1 – – W. 2
x. 2 – X. 1 – – W. 3
For deterministic automata, the condition of the uniqueness of the transitions is performed: the machine, which is in a certain state, under the action of any input signal cannot go over more than one state. With reference to the graphic method of task F.-Avtatata This means that two or more ribs marked with the same input signal cannot go into the graph of the automaton from any vertex. And in the matrix of the compounds of the machine FROM In each row, any input signal should not meet more than once.
For F.- Automatic state z K. called sustainable If for any entrance x i îx.for which J ( z K., x I.) \u003d z k,takes place j ( z K.,x I.) \u003d at K.. F.- Automatic is called asynchronous If every state z k îz. Sustainable.
Thus, the concept in a discrete-deterministic approach to research on the properties of object properties is mathematical abstraction, convenient to describe a wide class of operational processes of real objects in automated control systems. Via F-the automaton can describe objects for which the presence of discrete states is characterized, and the discrete nature of work in time is the elements and nodes of the computer, control devices, control and control, system of temporary and spatial switching in the technology exchange technique, etc.
2.4. Discrete-stochastic models ( R-schemes)
Basic relations. Consider the features of constructing mathematical circuits at a discrete-stochastic approach on probabilistic (stochastic) automata. In general probabilistic automatic
R-diagrams (English Probabijistic Automat) can be defined as a discrete sweepable information converter with memory, the functioning of which in each clock depends only on the memory state in it, and can be described statistically.
We introduce a mathematical concept R-Avtomat, using the concepts introduced for F.- Automatic. Consider many G., whose elements are all sorts of pairs ( x i, z s), where x I. and z s - elements of the input subset H. and subset of states z respectively. If there are two functions J and Y that they are displayed with their help G.®Z I. G®Y, they say that F. =
Consider a more general mathematical scheme. Let be
F - a lot of all kinds of pairs of type ( z k, y i), where i.- element of the output subset Y.. We will require any element of the set G. Induced on the set f, some law of the distribution of the following form:
Wherein b KJ. \u003d 1, where b KJ.- probabilities of the transition of the machine to the state z K. and appearance at the output of the signal y J.if he was able z s and on his entrance at that moment a signal was received x I.. The number of such distributions presented in the form of tables is equal to the number of sets of sets G.. Denote the set of these tables through V. Then the Four of the elements P \u003d.
(R-Avtomatom).
Possible applications P.-schemes.Let the elements of the set G. Come on some laws of distribution on subsets Y.and Z.What can be represented accordingly in the form:
Wherein z k \u003d. 1 I. q j \u003d. 1, where z K.and q j - The probabilities of transition
R- Automatic in the state z K. and the appearance of the output signal y K. provided that
R z s And on his entrance entered the input signal X i.
If for all k.and j.there is a ratio q j z k \u003d b kj, That is
R- Automatic is called probabilistic mile gun. This requirement means fulfilling the conditions for the independence of distributions for the new state R- Automatic and its output signal.
Now let the output signal definition R-the automaton depends only on the state where the machine is located in this work tact. In other words, let each element of the output subset Y. Induces the distribution of probabilities of exits having the following form:
Here s i \u003d. 1, where s I. - the probability of appearance of output y I. for W.slovery, that R-Avtomat was in a state z K..
If for all k. and i.there is a ratio z k s i = B Ki. , then such
R- Automatic is called probabilistic Moore machine. Concept
R-Avtomatov mile and Moore introduced by analogy with deterministic
F.- Automatic. Private case R-automaton defined as P.=
R-Avtomat is determined deterministic, then such a machine is called
Y.-. Similarly,
Z.-determined probabilistic machine gun called R- Automatic, whose choice of a new state is deterministic.
Example 2.1.Let set Y.-derminated P.-machine
In fig. 2.5 shows the oriented graph of transitions of this automaton. The vertices of the graph are compared with the states of the machine, and the arcs are possible transitions from one state to another. Arcs have weights corresponding to the transition probabilities p IJ.And near the vertices of the graph are written the values \u200b\u200bof the output signals induced by these states. It is required to estimate the total final probabilities of being P.- Automatic in conditions z. 2 I. z. 3 .
Fig. 2.5. Count of probabilistic machine gun
When using an analytical approach, you can record well-known ratios from the theory of Markov chains and obtain a system of equations for determining final probabilities. In this case, the initial state z. 0 can not be taken into account, since the initial distribution does not affect the values \u200b\u200bof the final probabilities. Then have
where with K. - the final probability of stay R- Automatic in a state z K..
We get a system of equations
Add normalization to these equations. from 1 + from 2 + from 3 + from 4 \u003d 1. Then, solving the system of equations, we get from 1 = 5/23, from 2 = 8/23, from 3 = 5/23,
from 4 \u003d 5/23. In this way, from 2 + from 3 \u003d 13/23 \u003d 0.5652. In other words, with the endless work given in this example Y.-determinated
R-Automat at its outlet is formed a binary sequence with a probability of the appearance of a unit of 0.5652.
Similar R- Automatic can be used as generators of Markov sequences, which are necessary in constructing and implementing system operation processes S. or exposure to the external environment E.
2.5. Continuous stochastic models ( Q.-schemes)
Basic relations. Features of a continuous stochastic approach, consider on the example of typical mathematical Q-schemes - mass maintenance systems (eng. Queueing System).
As a process of service, various processes of functioning of economic, production, technical and other systems, such as product supply flows, for some enterprise, flows of parts and components on the assembly conveyor workshop, application for processing computer information from remote terminals and etc. At the same time, such objects characteristic of the work is the random appearance of applications (requirements) for maintenance and completion of maintenance at random moments of time, i.e. The stochastic nature of the process of their functioning.
Stream of events A sequence of events occurring one after another at some random moments of time is called. There are threads of homogeneous and inhomogeneous events. Flow of events called homogeneous If it is characterized only by the moments of receipt of these events (causing moments) and is given by the sequence ( t N.} = {0 £ t. 1 £. t. 2 ... £ t N.£ … }, where t N - The moment of the offensive p-event - non-negative real number. The homogeneous event flow can also be specified as a sequence of time intervals between p-m. and (n - 1) -M Events (T N.), which is uniquely connected with the caller sequence ( t N.} , where T. n \u003d t n– t N. -1 , P³ 1, t. 0 = 0, those. T 1. \u003d T. 1 . Stream of inhomogeneous events called sequence ( t n, f n} , Where t N -causing moments; f n -set of events. For example, as applied to the service process for an inhomogeneous application stream, an affiliation can be set to a particular source of applications, the presence of a priority, the possibility of maintaining one or another type of channel.
In any elementary service, you can allocate two main components: expectation of servicing the application and the actual application of the application. This can be depicted as some i.- Maintenance device P I. (Fig. 2.6) consisting of applicants H i in which can be simultaneously being j I.=
applications, where L i H.–
capacity
i.-Ho drive, and channel service channel (or just channel) K i. For each service device element P I. Event flows come: in the drive H I. Flow of applications w i, on canal K I - Service stream and I..
Fig. 2.6. Application service device
Channel applications K I, and applications left the device P I. For various reasons, non-listening (for example, due to the overflow of the drive H I.) form output stream y i î y, those. The time intervals between the moments of the requests of applications form a subset of the output variables.
Usually, the flow of applications w I îW, those. time intervals between the moments of appearance of applications at the entrance K I., forms a subset of unmanaged variables, and the service flow u i îu those. The time intervals between the beginning and the end of servicing the application forms a subset of controlled variables.
Maintenance Device Function P I. can be represented as a process of changing the states of its elementability z I.(t.). Transition to a new state for P I. means changing the number of applications that are in it (in the channel K I. and in the drain H I.). Thus, vector of states for P I. It has the form: , Where z i H. - Status status H I. (z i H. \u003d 0 - the drive is empty z i H.\u003d 1 - There is one application in the drive, ... z i H. \u003d L i h – the drive is completely filled); L i h - Capacity of the drive N I measured by the number of applications that may fit in it; z i k -channel status K I.(z i k \u003d0 – channel is free, z I K. \u003d 1 - Channel busy).
Possible applications Q-schemes. In the practice of modeling systems with more complex structural communications and behavior algorithms, not separate service devices are used for formalization, but
Q-schemes ,
formed by the composition of many elementary service devices P I. If channels To I.different service devices are connected in parallel, then multichannel maintenance ( multichannel Q-scheme) ,
And if the instruments P I. And their parallel compositions are connected consistently, there is a multiphase maintenance ( multiphase Q-scheme) .
So for the task Q-schemes need to use the pairing operator R.reflecting the relationship of the elements of the structure (channels and drives) among themselves.
