Les processus aléatoires sont modélisés en utilisant quelles méthodes. Exemples de chaînes de Markov finies

Modélisation processus aléatoires- la direction la plus puissante de la modélisation mathématique moderne.

Un événement est dit aléatoire s’il est imprévisible de manière fiable. Le hasard entoure notre monde et joue le plus souvent un rôle négatif dans nos vies. Cependant, il existe des circonstances dans lesquelles le hasard peut être utile. Dans les calculs complexes, où le résultat souhaité dépend des résultats de nombreux facteurs, modèles et mesures, il est possible de réduire la quantité de calcul en utilisant des valeurs aléatoires de chiffres significatifs.

Dans la modélisation probabiliste, diverses méthodes sont utilisées pour résoudre des problèmes de divers domaines. Les domaines d'application des méthodes probabilistes sont énumérés ci-dessous.

Méthode de modélisation statistique : résolution de problèmes de valeurs limites de physique mathématique, résolution de systèmes d'équations algébriques linéaires, méthodes d'inversion matricielle et de grille qui s'y réduisent pour résoudre des systèmes d'équations différentielles, calculer des intégrales multiples, résoudre des équations intégrales, des problèmes physique nucléaire, dynamique des gaz, filtration, génie thermique.

Méthode de simulation : modélisation des systèmes faire la queue, tâches des systèmes de contrôle automatisés, des systèmes de contrôle automatisés et des systèmes de contrôle de processus, problèmes de sécurité de l'information, modélisation de situations de jeu complexes et de systèmes dynamiques.

Méthode d'approximation stochastique : algorithmes récurrents pour résoudre des problèmes d'estimation statistique.

Méthode de recherche aléatoire : résoudre des problèmes d'optimisation pour des systèmes qui dépendent d'un grand nombre de paramètres, trouver les extrema d'une fonction d'un grand nombre de variables.

Autres méthodes : méthodes probabilistes de reconnaissance de formes, modèles d'adaptation, formation et auto-apprentissage.

Dans la modélisation mathématique informatique de processus aléatoires, on ne peut se passer d'ensembles de nombres dits aléatoires qui satisfont à une loi de distribution donnée. En fait, ces nombres sont générés par un ordinateur à l'aide d'un algorithme spécifique, c'est-à-dire ils ne sont pas complètement aléatoires, ne serait-ce que parce que lorsque le programme sera redémarré avec les mêmes paramètres, la séquence se répétera ; ces nombres sont appelés « pseudo-aléatoires ».

Pour un utilisateur pas trop exigeant, les capacités du capteur (générateur) de nombres aléatoires intégré à la plupart des langages de programmation sont généralement suffisantes. Ainsi, dans le langage Pascal il existe une fonction aléatoire dont les valeurs sont nombres aléatoires de la portée. Son utilisation est généralement précédée de l'utilisation de la procédure de randomisation, qui sert initialement à « configurer » le capteur, c'est-à-dire recevoir différentes séquences de nombres aléatoires pour chaque appel au capteur. Pour les problèmes dont la solution nécessite des séquences non corrélées très longues, le problème devient plus compliqué et nécessite des

Caractéristiques de la modélisation par simulation des systèmes de production

Pour analyser des systèmes de production très complexes, diversifiés, ne disposant pas d'une description mathématique exhaustive et passant par plusieurs étapes de conception, de mise en œuvre et de développement, il n'est pas possible de construire des modèles mathématiques adéquats, qu'ils soient logiques ou numériques. Il est naturel ici d’utiliser des méthodes de modélisation par simulation.

Le système peut être décrit sans ambiguïté par un ensemble de valeurs de paramètres de production caractéristiques de chaque état spécifique. Si ces valeurs sont saisies dans l'ordinateur, leurs modifications au cours du processus de calcul peuvent être interprétées comme simulant la transition du système d'un état à un autre. Sous de telles hypothèses simulation peut être considéré comme une représentation dynamique d'un système en le faisant passer d'un état à un autre selon ses règles de fonctionnement caractéristiques.

Lors de la simulation des systèmes de production, des changements dans leur état se produisent à des moments discrets. Le concept principal de la simulation d'un système dans ce cas est d'afficher les changements de son état au fil du temps. Ainsi, le facteur déterminant ici est l'identification et la description sans ambiguïté des états du système modélisé.

Les modèles de simulation permettent, sans utiliser de dépendances analytiques ou autres dépendances fonctionnelles, d'afficher des objets complexes constitués d'éléments hétérogènes entre lesquels existent diverses connexions. Les humains peuvent également être inclus dans ces modèles.

Sans complications fondamentales, ces modèles peuvent inclure des flux à la fois déterministes et stochastiques (matériaux et informations). Grâce à la simulation, vous pouvez visualiser les relations entre les postes de travail, les flux de matières et de produits, les véhicules et le personnel.

Malgré ces avantages évidents, consistant principalement en l'étendue et la polyvalence des applications, cette méthode perd de vue l'existence de connexions logiques, ce qui exclut la possibilité d'une optimisation complète des solutions obtenues à l'aide de ce modèle. Seule la possibilité de sélectionner la meilleure des options consultées est garantie.

En pratique, la modélisation par simulation dans de nombreux cas réels est la seule méthode de recherche possible. Après avoir développé un modèle de simulation, des expérimentations informatiques sont réalisées sur celui-ci, qui permettent de tirer des conclusions sur le comportement du système de production.

L'émergence et le développement de méthodes de modélisation par simulation informatique sont également devenus possibles grâce au développement de la méthode de test statistique, qui a permis de simuler des événements et des processus aléatoires qui occupent une grande place dans la production réelle.

Lors de la compilation d'un modèle de simulation et de son utilisation pour modéliser l'objet étudié, il est nécessaire de résoudre plusieurs problèmes interdépendants. Ceux-ci incluent :

analyse du système simulé et préparation de sa description formalisée, comprenant l'identification de l'information et de la structure logique du système, l'identification de ses composants, la sélection des paramètres caractérisant l'état de ces composants, le développement modèle informatique un système capable de reproduire son comportement, en planifiant une expérience pour dérouler les événements dans un modèle informatique qui reflète les événements du système simulé ;

développement d'une méthodologie pour les expériences statistiques informatiques, y compris la génération de nombres aléatoires ou pseudo-aléatoires, la simulation de divers événements aléatoires, le traitement de données statistiques ;

mener l'expérience informatique proprement dite sur un modèle de simulation, y compris gérer les paramètres et les variables du modèle lors de son étude sur un ordinateur.

Brèves informations

Les processus aléatoires étudiés par modélisation de simulation (méthode de Monte Carlo) comprennent notamment les processus associés à la formation et au service des files d'attente (les processus dits faire la queue). La tâche la plus simple de cette classe c'est comme ça. Il existe un système de file d'attente avec un centre de service (un magasin avec un vendeur, un espace de réparation dans une flotte automobile, une salle d'urgence avec un médecin, un central téléphonique avec une entrée, un serveur avec un canal d'entrée, etc.). Les clients recourent aux services du système de manière aléatoire (avec fonction donnée répartition des plages horaires entre les arrivées). Si le système est libre, il commence immédiatement à servir le client, sinon il le met dans une file d'attente. La durée de service pour chaque client est une variable aléatoire dont la loi de distribution est connue.

Pour résoudre ce problème, il est nécessaire de répondre à des questions telles que « quelle est la fonction de distribution de probabilité du temps d’attente du client dans la file d’attente ? « quel est le temps d'arrêt du système en attente des clients ? », « si ces fonctions elles-mêmes sont difficiles à déterminer, alors quelles sont leurs principales caractéristiques importantes(c'est-à-dire espérance mathématique, variance, etc.) ?

La base de cette tâche est le processus aléatoire d'entrée des clients dans le système de services. Les intervalles entre les arrivées de toute paire consécutive de clients sont des événements aléatoires indépendants distribués selon une certaine loi. Le caractère réel de cette loi ne peut être établi que par de nombreuses observations ; En tant que fonction de densité de probabilité du modèle la plus simple, nous pouvons prendre une distribution équiprobable dans la plage temporelle de 0 à quelques T- l'intervalle maximum possible entre les arrivées de deux clients consécutifs. Avec cette répartition, la probabilité qu'il s'écoule 1 minute, 3 minutes ou 8 minutes entre les arrivées de deux clients est la même (si T> 8 minutes).

Une telle répartition est évidemment irréaliste ; En réalité, pour la plupart des processus de file d'attente, la fonction de distribution passe de t= 0, a un maximum à une certaine valeur t = τ et diminue rapidement dans son ensemble t, ceux. a la forme montrée sur la Fig. 7.6.

Bien sûr, vous pouvez choisir beaucoup fonctions élémentaires, ayant qualitativement cet aspect. En théorie des files d'attente, la famille des fonctions de Poisson est largement utilisée

Où λ - une constante p- entier arbitraire.

Les fonctions (35) ont un maximum en x = p/λ et normalisé.

Le deuxième processus aléatoire de ce problème, qui n'a rien à voir avec le premier, est déterminé par une séquence d'événements aléatoires - la durée du service pour chaque client. La distribution de probabilité de la durée du service a la même aspect de qualité, comme dans le cas précédent.

Par exemple, dans le tableau de la colonne UN des nombres aléatoires sont enregistrés - intervalles entre les arrivées des clients (en minutes), dans la colonne DANS - nombres aléatoires - durée du service (en minutes). Pris pour la certitude un maximum= 10 et bmax= 5.

Riz. .6. Représentation schématique de la densité de probabilité de la répartition temporelle entre les apparitions des clients dans un système de file d'attente

A partir de ce petit tableau, il est bien entendu impossible d'établir quelles lois de répartition sont acceptées pour les quantités UN Et DANS. Les colonnes restantes sont fournies pour faciliter l'analyse ; les nombres qui y sont inclus sont trouvés par calcul élémentaire. La colonne C montre temps conditionnel arrivée du client ; D- moment du début du service ; E- fin de service ; F- la durée pendant laquelle le client a passé dans le système dans son ensemble ; G- temps passé à faire la queue pour obtenir un service ; N- temps passé par le système à attendre les clients (s'il n'y en a pas). Il est pratique de remplir le tableau horizontalement, en passant de ligne en ligne. Depuis le début de la prestation le prochain client est déterminé soit par l'heure de son arrivée, si le système n'est pas occupé, soit par l'heure de départ du client précédent, nous vous présentons pour plus de commodité formules correspondantes(en eux je= 1, 2, 3, ...):

c 1 = 0, c je+1 = c je + une je+1 ; ré 1 = 0, ré je+1 = max(c je+l, e je);(36a)

e 1 = b 1 e je = ré je + b je ; f je = e je + c je ; g1 = 0 ; g je+1 = f je+1 + b je+1 h 1 = 0; h je+1 = ré je+1 - e je(36b)

Ainsi, étant donné les séries aléatoires de nombres dans les colonnes A et B, les clients devaient faire la queue (colonne G), et le système était inactif en attendant le client (colonne N).

Non.	UN	DANS	AVEC	D	E	F	G	N



								1-

Lors de la modélisation de systèmes de ce type, la première question qui se pose est la suivante : quel est le temps moyen dont vous disposez pour faire la queue ? Il semble facile de répondre - il vous suffit de trouver

(37)

dans certaines séries de tests. De même, vous pouvez trouver la valeur moyenne de h . Il est plus difficile de répondre à la question de la fiabilité des résultats obtenus ; Pour ce faire, vous devez effectuer plusieurs séries de tests et utiliser méthodes standards statistiques mathématiques (un traitement utilisant la distribution de Student est souvent approprié).

Plus question difficile- quelle est la distribution des variables aléatoires G Et Nà distributions données variables aléatoires UN Et DANS? Vous pouvez essayer d'obtenir une réponse qualitative à cette question en construisant des histogrammes correspondants basés sur les résultats de la simulation. Ensuite, une hypothèse est formulée sur le type de distribution et un ou plusieurs critères statistiques sont utilisés pour tester la fiabilité de cette hypothèse.

Disposant d'une fonction de distribution (même empirique, mais assez fiable), il est possible de répondre à toute question sur la nature du processus d'attente. Par exemple : quelle est la probabilité d’attendre plus longtemps T minutes? La réponse sera obtenue si nous trouvons le rapport de surface trapèze courbé, limité par le calendrier densité de distribution, droite x = t Et y=0 superficie de la figure entière.

Questions de sécurité

1. Qu'est-ce qu'un « processus aléatoire » ?

2. Quels sont les principes de la génération informatique de nombres aléatoires uniformément distribués ?

3. Comment obtenir une séquence de nombres aléatoires avec une loi de distribution de Poisson ?

4. Qu'est-ce qu'un « système de file d'attente » ? Donnez des exemples.

5. Quelle est la méthode de Monte Carlo pour calculer les superficies chiffres plats? volumes de corps ?

6. Quels exemples de processus aléatoires pouvez-vous donner ?

Sujets de dissertation

1. Principes de génération informatique de séquences de nombres aléatoires et critères statistiques déterminer les propriétés des séquences.

2. Méthodes traitement statistique résultats obtenus à partir de la modélisation informatique de processus aléatoires.

Sujet séminaires

Obtention de séquences de nombres aléatoires avec une loi de distribution donnée.

Travaux de laboratoire

1. Lors de l'exécution de ce travail, il est nécessaire de générer de longues séquences de nombres pseudo-aléatoires avec une loi de distribution de probabilité donnée. Elle peut s'appuyer sur un capteur standard de nombres aléatoires uniformément répartis, intégré au système de programmation appliqué, utilisant l'une des procédures de conversion de cette séquence en une séquence avec la loi de distribution souhaitée (par exemple, la procédure « sélection-rejet »). .

2. L'une des tâches centrales de la modélisation des processus aléatoires consiste à trouver les caractéristiques des variables aléatoires qui font l'objet de la modélisation. La principale de ces caractéristiques est la fonction de distribution. Son apparence peut être évaluée qualitativement à partir de l'histogramme construit lors de la simulation et de l'hypothèse sur forme fonctionnelle vérifier en utilisant l'un des critères standards utilisés dans statistiques mathématiques(par exemple, critère % 2). Cependant, cela n'est pas toujours conseillé, surtout si le problème nécessite de déterminer uniquement certaines caractéristiques d'une variable aléatoire - le plus souvent la valeur moyenne et la variance. Ils peuvent être trouvés sans modéliser la fonction de distribution elle-même. En même temps évaluation statistique la fiabilité des résultats est obligatoire.

3. Il convient d'afficher les résultats de la simulation sur l'écran de l'ordinateur sous la forme suivante : sous forme de tableaux de valeurs de la valeur calculée (généralement en plusieurs échantillons), sous forme d'histogrammes de distribution de variables aléatoires construits lors de la simulation.

4. Il est conseillé, dans la mesure du possible, d'accompagner la modélisation de simulation d'une visualisation visuelle du processus correspondant sur l'écran de l'ordinateur (le processus de formation de file d'attente, la naissance et la disparition d'objets dans les problèmes de modélisation de population, etc.).

Temps de réalisation approximatif 16 heures.

Affectation à travail de laboratoire

Réaliser une simulation du processus aléatoire spécifié et évaluer la fiabilité des résultats obtenus à l'aide de critères statistiques.

Options de tâche

Option 1

Simulez une file d'attente dans un magasin avec un vendeur selon les lois de distribution équiprobables des variables aléatoires décrites ci-dessus : l'arrivée des clients et la durée du service (pour un certain ensemble fixe de paramètres). Obtenir des caractéristiques stables : valeurs moyennes d'attente en file d'attente de l'acheteur et de temps d'inactivité du vendeur en attendant l'arrivée des acheteurs. Évaluez leur fiabilité. Évaluer la nature de la fonction de distribution des quantités g Et h.

Option 2

Réalisez la même modélisation avec les lois de Poisson de distribution de probabilité des événements d'entrée : l'arrivée des clients et la durée du service (pour un certain ensemble fixe de paramètres).

Option 3

Réalisez la même modélisation sous la loi normale de distribution de probabilité des événements d'entrée : l'arrivée des clients et la durée du service (pour un certain ensemble fixe de paramètres).

Option 4

Dans le système évoqué ci-dessus, une situation critique peut survenir lorsque la file d'attente augmente sans limite au fil du temps. En fait, si les clients entrent très souvent dans le magasin (ou si le vendeur est trop lent), la file d'attente commence à s'allonger, et dans ce système avec dernière fois une crise de service viendra.

Construire une relation entre les quantités (a max, bmax), reflétant la bordure du spécifié situation critique, avec une distribution également probable des événements d'entrée.

Option 5

Sur l'interurbain central téléphonique deux opérateurs téléphoniques servent une file d'attente commune de commandes. La commande suivante est servie par l'opérateur téléphonique qui s'est montré le premier disponible. Si les deux sont occupés au moment de la réception de la commande, l'appel est annulé et vous devez rappeler. Modélisez le processus en considérant que les flux d'entrée sont de Poisson.

Option 6

Simulez la situation décrite dans la version précédente, mais supposez que si au moment de tenter de passer une commande les deux opérateurs téléphoniques sont occupés, une file d'attente se forme.

Option 7

Laissez le central téléphonique avec une entrée être utilisé système conventionnel: si l'abonné est occupé, alors la file d'attente ne se forme pas et vous devez rappeler. Simulez la situation : trois abonnés tentent d'appeler le même propriétaire du numéro et, en cas de succès, lui parlent pendant un certain temps (durée aléatoire). Quelle est la probabilité que quelqu'un essayant d'appeler ne puisse pas le faire dans certaine heure T?

Option 8

Simulez la situation décrite dans la version précédente, mais supposons que si au moment de la tentative de contact, le téléphone de l'abonné est occupé, une file d'attente se forme.

Option 9

Il n’y a qu’un seul médecin travaillant aux urgences. La durée du traitement du patient et les intervalles de temps entre les admissions des patients - variables aléatoires, distribué selon la loi de Poisson. Selon la gravité des blessures, les patients sont divisés en trois catégories : l'admission d'un patient de n'importe quelle catégorie : événement aléatoire avec une distribution de probabilité égale. Le médecin traite d'abord les patients présentant les blessures les plus graves (dans l'ordre de leur admission), puis, s'il n'y en a pas, les patients présentant des blessures modérées (dans l'ordre de leur admission), et ensuite seulement - les patients présentant des blessures mineures. Modélisez le processus et estimez les temps d’attente moyens dans la file d’attente pour les patients de chaque catégorie.

Option 10

Simulez la situation décrite dans la version précédente, à condition que deux médecins travaillent aux urgences et que les patients soient répartis en deux catégories au lieu de trois.

Option 11

Un tisserand dessert un groupe de métiers à tisser, effectuant selon les besoins des interventions à court terme, dont la durée est une variable aléatoire. Quelle est la probabilité d’arrêt de deux machines à la fois ? Quelle est la durée moyenne du temps d’arrêt d’une machine ?

Option 12

Simulez la situation décrite dans la version précédente, si un groupe de métiers à tisser est desservi conjointement par deux tisserands.

Option 13

DANS Le parc automobile de la ville compte deux zones de réparation. One - sert aux réparations de courte et durée moyenne, l'autre - à moyen et long terme (c'est-à-dire que des réparations à moyen terme peuvent être effectuées par chacune des zones). Au fur et à mesure des pannes, les véhicules sont livrés à la flotte ; intervalle de temps entre les livraisons - aléatoire Valeur de Poisson. La durée de réparation est une variable aléatoire avec une loi de distribution normale. Modélisez le système décrit. Quels sont les temps d'attente moyens en file d'attente pour les véhicules nécessitant respectivement des réparations à court, moyen et long terme ?

Option 14

Implémenter un modèle de simulation de modélisation statistique pour résoudre le problème de Buffon (XVIIIe siècle). L'auteur a découvert analytiquement que si sur un champ représenté graphiquement par des lignes parallèles, la distance qui les sépare L, jette une aiguille au hasard je, alors la probabilité que l'aiguille traverse au moins une ligne droite est déterminée par la formule .

Ce problème a fourni un moyen de simuler la détermination du nombre p. En effet, si L = 2l, Que . Pendant la simulation, effectuez ce calcul.

Option 15

Développer un modèle de marche aléatoire unidimensionnel (le modèle « ivrogne »). La marche est définie selon la règle : si le nombre aléatoire du segment est inférieur à 0,5, alors un pas est fait vers la droite d'une distance h, sinon - à gauche. La distribution des nombres aléatoires est supposée équiprobable.

Résoudre le problème : quelle est la probabilité qu'une telle marche s'éloigne du point de départ de n mesures?

Option 16

DANS conditions du problème de la version précédente, obtenez une réponse à la question : quelle est la probabilité qu'un « ivrogne » revienne après n entre dans point de départ?

Option 17

Un point erre aléatoirement sur un plan le long des nœuds d'une grille carrée avec la possibilité de faire probabilité égale pas de gauche à droite de haut en bas à un pas fixe (en un seul mouvement). Le mouvement s'effectue dans un espace fermé volume rectangulaire, et au contact du mur se produit image miroir d'elle.

Lors de la simulation, répondez à la question : comment la fréquence des visites à chaque nœud est-elle liée à la distance qui le sépare du nœud à partir duquel le mouvement commence.

Option 18

Modélisez la même situation que dans la tâche de l'option 17, à condition que la zone d'errance soit illimitée et répondez à la question posée.

Option 19

Simulez le vol d'une abeille. Sur un plan (clairière), les plantes mellifères poussent de manière aléatoire avec une concentration donnée (pour 1 m2). Au centre se trouve une ruche d'où s'envole une abeille. Une abeille peut voler d'une plante à n'importe quelle autre plante, mais la probabilité de choix diminue de façon monotone avec l'augmentation de la distance entre les plantes (selon une loi). Quelle est la probabilité qu’une abeille visite une plante donnée pendant un nombre de vols élémentaires donné ?

Option 20

Implémenter un modèle plat Mouvement brownien n particules dans un rectangle. Considérons les particules comme des boules de taille finie. Les impacts des particules les unes sur les autres et sur les murs doivent être modélisés comme absolument élastiques. Déterminez dans ce modèle la dépendance de la pression du gaz sur les parois sur le nombre de particules.

Option 21

Développer en détail et mettre en œuvre un modèle de mélange (diffusion) de gaz dans une cuve fermée. DANS moment de départ temps, chaque gaz occupe la moitié du récipient. À l’aide de ce modèle, étudiez la dépendance du taux de diffusion sur divers paramètres d’entrée.

Option 22

Implémenter un modèle de simulation du système « prédateur-proie » selon le schéma suivant.

L’« île » de 20x20 est habitée par des lapins sauvages, des loups et des louves. Il existe plusieurs représentants de chaque espèce. Les lapins à chaque instant avec la même probabilité de 1/9 se déplacent vers l'un des huit carrés voisins (à l'exception des zones limitées littoral) ou restez simplement assis, immobile. Chaque lapin a une probabilité de 0,2 de se transformer en deux lapins. Chaque louve se déplace aléatoirement jusqu'à ce que le lapin qu'elle chasse se trouve dans l'une des huit cases adjacentes. Si la louve et le lapin sont sur la même case, la louve mange le lapin et marque un point. Sinon, elle perd 0,1 point.

Les loups et les louves avec zéro point meurent. Au moment initial, tous les loups et toutes les louves ont 1 point. Le loup se comporte comme une louve jusqu'à ce que tous les lapins des cases voisines disparaissent ; puis, si la louve se trouve dans l'une des huit cases voisines, le loup la poursuit.

Si un loup et une louve se trouvent sur la même case et qu’il n’y a pas de lapin à manger, ils produiront une progéniture d’un sexe aléatoire.

Observez les changements de population sur une période de temps. Surveillez comment les changements dans les paramètres du modèle affectent l’évolution des populations.

Option 23

Pour modéliser le processus de propagation de l'infection par la teigne sur une zone de peau de la taille n x p(p- impairs) cellules.

On suppose que la cellule cutanée infectée d’origine est la cellule centrale. À chaque intervalle de temps, une cellule infectée peut infecter n’importe quelle cellule saine voisine avec une probabilité de 0,5. Après six unités de temps, la cellule infectée devient immunisée contre l'infection, l'immunité qui en résulte dure les quatre unités de temps suivantes, puis la cellule s'avère saine. Lors de la simulation du processus décrit, la sortie état actuel zone cutanée simulée à chaque intervalle de temps, notant les cellules infectées, résistantes à l'infection et saines.

Observez comment les changements dans la taille du champ et la probabilité d’infection affectent les résultats de la simulation.

Option 24

Élaborer en détail et mettre en œuvre un modèle de répartition des polluants environnement particules d'une substance émises dans l'atmosphère par une cheminée d'usine (par exemple, cendres résultant de la combustion du charbon dans une centrale électrique). Considérons que le mouvement d'une particule est constitué de deux composantes : plan horizontal- sous l'influence de rafales de vent aléatoires, à la verticale - sous l'influence de la gravité.

Lectures complémentaires

1. Bailey N. Méthodes statistiques en biologie : Trad. de l'anglais - M. : IL, 1962.

2. Gnedenko B.V., Kovalenko I.N. Introduction à la théorie des files d'attente. - M. : Nauka, 1966.

3. Saati T.Éléments de théorie des files d'attente et ses applications : Trans. de l'anglais - M. : Sov. radio, 1991.

4. Shannon R. Modélisation par simulation des systèmes - art et science : Trad. de l'anglais - M. : Mir, 1978.

Tests pour le chapitre 7

Considérons les algorithmes de modélisation des processus stationnaires normaux et aléatoires de Markov. Ces procédés sont largement utilisés comme modèles mathématiques divers types de processus réels se produisant dans des systèmes techniques complexes. Nous présentons ci-dessous quelques définitions et concepts essentiels adoptés dans le cadre de la corrélation et théories spectrales fonctions aléatoires.

Fonction aléatoire est appelée fonction d'un argument non aléatoire t, qui pour chaque valeur fixe de l'argument est une variable aléatoire. Fonction aléatoire temps appelé processus aléatoire. Fonction aléatoire coordonnées les points dans l'espace sont appelés champ aléatoire. Vue spécifique, acceptée par un processus aléatoire à la suite de l'expérience, est appelée la réalisation (trajectoire) du processus aléatoire. Toutes les réalisations obtenues d'un processus aléatoire constituent un ensemble de réalisations. Les valeurs des réalisations à des instants précis (tranches de temps) sont appelées valeurs instantanées du processus aléatoire.

Introduisons la notation suivante : X(t) - processus aléatoire ; x i (t) - i-ième implémentation du processus X(t) ; x i (t j) - valeur instantanée du processus X(t), correspondant à la i-ème implémentation au j-ème instant. L'ensemble des valeurs instantanées correspondant aux valeurs des différentes implémentations au même instant t j sera appelé la j-ième séquence du processus X(t) et noté x(t j). De ce qui précède, il s'ensuit que les arguments d'un processus aléatoire peuvent être le temps et le numéro de mise en œuvre. A cet égard, deux approches pour étudier les propriétés d'un processus aléatoire sont légitimes : la première repose sur l'analyse d'un ensemble d'implémentations, la seconde opère avec un ensemble de séquences - tranches temporelles. La présence ou l'absence de dépendance des valeurs des caractéristiques probabilistes d'un processus aléatoire au temps ou au nombre de mise en œuvre détermine telle propriétés fondamentales processus, tels que la stationnarité et l’ergodicité. Stationnaire le processus s'appelle caractéristiques probabilistes qui ne dépend pas du temps. Ergodique est un processus dont les caractéristiques probabilistes ne dépendent pas du numéro d’implémentation.

Le processus aléatoire est appelé normale(ou gaussien), s'il est unidimensionnel et lois bidimensionnelles les distributions de chacune de ses sections sont normales. Les caractéristiques complètes d’un processus aléatoire normal sont son espérance mathématique et sa fonction de corrélation. Pour un processus aléatoire normal stationnaire, le MOF est constant et la fonction de corrélation dépend uniquement de la différence entre les instants pour lesquels les ordonnées du processus aléatoire sont prises ( =t 2 -t 1). Pour un processus aléatoire stationnaire, avec un écart suffisamment grand de l'ordonnée du processus aléatoire X(t 2) par rapport à son espérance mathématique m x au temps t 2 devient pratiquement indépendant de la valeur de cet écart au temps t 1 . Dans ce cas, la fonction de corrélation K(t), qui donne la valeur du moment de connexion entre X(t 2) et X(t 1), tendra vers zéro. Par conséquent, K() peut soit diminuer de façon monotone, comme le montre la figure 2.2, soit avoir la forme illustrée à la figure 2.3. Une fonction de la forme (Fig. 2.2.), en règle générale, est approximée par les expressions :

(2.38)

et une fonction de la forme (Fig. 2.3.) - avec des expressions :

Figure 2.2. Figure 2.3.

La stabilité d'un processus aléatoire stationnaire dans le temps nous permet de remplacer l'argument - le temps - par une variable auxiliaire qui, dans de nombreuses applications, a la dimension de la fréquence. Ce remplacement vous permet de simplifier considérablement les calculs et d'obtenir une plus grande clarté des résultats. La fonction résultante (S()) est appelée densité spectrale d'un processus aléatoire stationnaire et est mutuellement liée à la fonction de corrélation transformations inverses Fourier :

(2.42)

(2.43)

Il existe d'autres normalisations de densité spectrale, par exemple :

(2.44)

A partir des transformées de Fourier, il est facile d'obtenir, par exemple, pour un processus aléatoire avec K(t) de la forme (2.38) :

(2.45)

Un processus aléatoire stationnaire dont la densité spectrale est constante (S(w)=S=const) est appelé stationnaire bruit blanc. La fonction de corrélation du bruit blanc stationnaire est égale à zéro pour tous, ce qui signifie que deux de ses sections ne sont pas corrélées.

Le problème de la modélisation d'un processus aléatoire normal stationnaire (SNSP) peut être formulé comme le problème de trouver un algorithme permettant d'obtenir des implémentations discrètes de ce processus sur un ordinateur. Le processus X(t) est remplacé avec une précision donnée par le processus correspondant X(nDt) de temps discret t n = nDt (Dt est le pas d'échantillonnage du processus, n est un argument entier). En conséquence, le processus aléatoire x(t) sera associé à des séquences aléatoires :

xk [n]=xk (nDt), (2.46)

où k est le numéro de mise en œuvre.

Évidemment, un membre arbitraire d'une séquence aléatoire x(nDt) peut être considéré comme une fonction aléatoire de son nombre, c'est-à-dire argument entier n et, ainsi, exclure Dt de la considération, qui est prise en compte lors de l'écriture (2.46). De plus, pour distinguer un argument entier d’un argument variant continuellement, il est placé entre crochets.

Les séquences aléatoires sont souvent appelées processus aléatoires discrets ou séries chronologiques.

On sait que l’ajout d’une variable non aléatoire à une fonction aléatoire ne modifie pas la valeur de la fonction de corrélation. Ainsi, en pratique, des processus aléatoires centrés sont très souvent modélisés (le MOR est égal à zéro), à partir duquel on peut toujours passer au réel en ajoutant le MOR aux membres de la séquence aléatoire simulant le processus aléatoire.

Pour les séquences aléatoires, la fonction de corrélation et la densité spectrale sont calculées à partir des dépendances :

(2.47)

(2.48)

Réduire un processus aléatoire à une séquence aléatoire signifie essentiellement le remplacer par un vecteur multidimensionnel. Par conséquent, la méthode considérée de modélisation de vecteurs aléatoires est, d'une manière générale, adaptée à la modélisation de processus aléatoires spécifiés sur un intervalle de temps fini. Cependant, pour les processus aléatoires normaux stationnaires, il y a plus méthodes efficaces construction d'algorithmes de modélisation. Considérons deux méthodes les plus largement utilisées dans la pratique.

Méthodes de modélisation de processus et de champs aléatoires. La méthode de modélisation statistique (méthode de Monte Carlo) appliquée à la modélisation informatique de processus et de champs aléatoires vise à résoudre le problème de la reproduction de séquences discrètes qui simulent des séquences continues. fonctions aléatoires avec des caractéristiques probabilistes données.

Limitons-nous à considérer les algorithmes les plus couramment utilisés pour modéliser les processus et champs scalaires gaussiens stationnaires. Nous considérerons tous les processus et domaines considérés comme centrés.

Il existe deux types d'algorithmes à l'aide desquels des implémentations discrètes d'un processus aléatoire peuvent être générées sur un ordinateur. Les algorithmes du premier type impliquent le calcul d'une séquence discrète de valeurs, c'est-à-dire les valeurs des implémentations de processus dans un. ensemble d'instants présélectionnés dans le temps. Le pas de discrétisation est généralement considéré comme constant : alors de la stationnarité du processus découle la stationnarité de la séquence.

Les algorithmes de ce type sont basés sur la transformation linéaire d'une séquence stationnaire de nombres gaussiens indépendants avec paramètres en une séquence corrélée selon une loi donnée

où est la fonction de corrélation du processus modélisé. Dans ce cas, l'opérateur du correspondant transformation linéaireécrit ou sous forme de somme glissante avec poids

ou sous la forme d'une équation récurrente comme

Le type de fonction de corrélation du processus aléatoire reproduit à l'aide des relations (49), (50) détermine l'ensemble des valeurs des coefficients.

Le deuxième type comprend des algorithmes basés sur la représentation de processus simulés sous forme d'expansions.

où est un système de fonctions déterministes ; vecteur aléatoire. Dans ce cas, la modélisation d'un processus aléatoire se réduit à reproduire les implémentations de vecteurs et au calcul ultérieur des valeurs selon

formule (51). Des algorithmes de modélisation de vecteurs aléatoires dans le cadre de la théorie des corrélations peuvent être trouvés, par exemple, dans.

Le but de la modélisation statistique de champs aléatoires est de reproduire un ensemble de réalisations de valeurs de champ en des points discrets

Dans ce qui suit, nous ne ferons pas de distinction formelle entre coordonnées spatiales et temporelles et nous limiterons au cas de champs aléatoires homogènes. En règle générale, les algorithmes de modélisation de champs aléatoires sont une généralisation des algorithmes correspondants de modélisation de processus aléatoires dans le cas de variables.

Simulation du bruit blanc gaussien.À modélisation statistique processus et champs aléatoires, il est nécessaire de modéliser un processus gaussien stationnaire à corrélation delta (bruit blanc d'intensité ou son analogue multidimensionnel. Sur un ordinateur, seul un bruit blancà dispersion finie dont la densité spectrale et la fonction de corrélation sont données dans le tableau. 1 Le paramètre de modélisation est sélectionné de telle manière que la séquence ne soit pas corrélée. Cette condition sera satisfaite si vous choisissez où se situe l’étape d’échantillonnage. L'algorithme de modélisation a la forme

Méthode de sommation mobile pour modéliser des processus aléatoires. L'algorithme (49) permet de reproduire des séquences sur ordinateur à volonté longue longueur, qui ont dès le début la propriété de stationnarité. Des facteurs de pondération peuvent être calculés de diverses manières. Une méthode efficace est basée sur le développement en série de Fourier de la densité spectrale du processus simulé. La transformation (49) se prend sous la forme

et les coefficients

Le pas d'échantillonnage et le nombre de termes de la série sont sélectionnés à partir de la condition

où est l'erreur tolérée ;

Modélisation de processus aléatoires stationnaires avec densité spectrale fractionnaire-rationnelle. Pour modéliser des processus aléatoires avec une densité spectrale fractionnaire-rationnelle (voir tableau 1, processus n° 3, 4, 7, 8) de la forme

où les polynômes sont relatifs à l'ordre donc, un algorithme de type (50) est efficace. Densité spectrale séquences

peut être réduit à la forme

Les coefficients sont utilisés dans des équations de récurrence (50). Les relations (50) permettent d'obtenir des implémentations discrètes de processus aléatoires de longueur arbitrairement grande. Conditions initiales dans (50), lors du calcul des premières valeurs de la séquence, vous pouvez en choisir des valeurs arbitraires (par exemple zéro). Il en résulte un processus de transition au cours duquel section initiale la mise en œuvre générée sera faussée. La taille de cette surface de vente dépend propriétés de corrélation processus simulé.

Modélisation de processus aléatoires par expansion canonique. Pour les processus aléatoires gaussiens stationnaires, un développement similaire à (19) est valide :

où sont des fonctions aléatoires indépendantes et stochastiquement orthogonales. En supposant que pour et en remplaçant l'intégrale montant final, nous obtenons

Voici des variables aléatoires gaussiennes avec les caractéristiques probabilistes suivantes :

Le nombre de termes de la série (58) est choisi à partir de la condition

Avec (58), on peut utiliser le développement

Les réalisations obtenues à l'aide des expressions (58), (59) sont périodiques et n'ont donc pas la propriété d'ergodicité. Dignité générale extensions (58) et (59) - la simplicité de l'algorithme de modélisation, et l'inconvénient est la nécessité de prendre en compte grand nombre membres de la série.

Les extensions (58) et (59) sont pratiques à utiliser pour obtenir des implémentations discrètes de processus aléatoires en des points inégalement espacés.

Autres méthodes de modélisation de processus aléatoires. Dans de nombreux cas, une méthode de modélisation basée sur l’utilisation de la décomposition s’avère efficace

Voici des variables aléatoires avec densité des joints probabilités

Selon le théorème central limite, la distribution des réalisations (60) tend vers la Gaussienne. De plus, une fois mis en œuvre, ils seront asymptotiquement ergodiques par rapport à espérance mathématique et fonction de corrélation.

Avec (60), on peut utiliser le développement

Ici variables aléatoires avec densité de probabilité conjointe

De plus, la loi de distribution des grandeurs peut être supposée uniforme sur l'intervalle (0,1), tandis que leurs implémentations sont modélisées à l'aide des relations

Voici des nombres aléatoires, uniformément répartis sur l'intervalle (0,1), qui sont générés sur un ordinateur à l'aide de capteurs logiciels. La modélisation des implémentations est réalisée à l'aide d'une des méthodes de modélisation de valeurs aléatoires avec une loi de distribution donnée. Les algorithmes correspondants peuvent être trouvés, par exemple, dans.

Dans le tableau Le tableau 2 présente les types les plus courants de fonctions de corrélation de processus aléatoires stationnaires et les algorithmes de modélisation correspondants.

Méthodes de sommation mobile pour modéliser des champs aléatoires. Les algorithmes de ce type sont associés à la transformation d'un champ homogène corrélé delta en un champ de valeur donnée fonction de corrélation Cette transformation a la forme

La fonction de Green est trouvée à partir de l'équation

(voir scan)

Les implémentations discrètes du champ sont reproduites à l'aide de la formule de sommation glissante

Voici une constante déterminée par le choix du pas d'échantillonnage ; - valeurs discrètes dont les champs d'implémentation sont reproduits à l'aide d'une formule comme (52).

Autres moyens d'imitation

imiter- signifie se rapprocher de objets réels avec des lois de comportement spécifiques (réelles), ajoutant du caractère aléatoire au processus.

Équations différentielles tout est complètement moyenné. Les équations différentielles sont fondamentalement déterministes. Ils sont très bons car ils donnent une caractéristique intégrale (dans son ensemble).

Mais ce n’est que la première étape vers l’étude des systèmes réels. Dans un système réel, le chercheur s’intéresse aux détails.

1ère voie. Transition vers les équations aux différences(cette méthode a été activement utilisée pour développer méthodes numériques solutions DE). La méthode est appelée discrétisation des processus.

Nous avons un système de contrôle à distance

Nous remplaçons

intervalle infinitésimal en petit.

Nous calculons chacun valeur suivanteà travers les précédents.

Il faut ici garder à l'esprit que les coefficients ont déjà une dimension (et une signification) différente et dépendent de la taille de l'intervalle de temps sur lequel les valeurs sont recalculées.

Implémentation d'un processus discret dans l'environnement MVS - utilisant un nœud au comportement vide et des arcs de transition cycliques.

Riz. 1. Mise en œuvre d'un processus discret

Le diagramme temporel d'un processus discret a la forme d'une fonction constante par morceaux avec des sauts (discontinuités) en certains points je recalcul des valeurs.

Nous avons donc remplacé modèle continu discret avec fonction continue par morceaux, qui montre des sauts de nombres à certains intervalles.

2ème voie. Description lois locales comportement

Divisons la loi de changement de la quantité d'un produit en deux comportements : la loi de la perte de produit, la loi de la croissance du produit

De même pour la ressource

Riz. 2. Modèle structurel avec lois locales

3ème voie. Ajouter du hasard

Pour introduire le hasard, nous calculerons de nouvelles valeurs de coefficient à chaque itération comme des nombres aléatoires distribués, en première approximation, sur loi normale avec une moyenne (espérance) et une variance données.

Et si l'on prend également en compte comportements locaux déclin et croissance, vous pouvez alors fixer les probabilités de transitions selon l'une ou l'autre loi.

Et grâce aux probabilités, nous pourrons affiner et explorer ce modèle.

Ainsi, les principaux moyens de rapprocher le modèle du système réel sont :

détailler la structure du système ;
transition vers des processus discrets ;
comportement détaillé ;
transition vers des processus aléatoires.

La combinaison de toutes ces méthodes est la modélisation par simulation (la vraie).

Maintenant, ils utilisent autre chose nom moderne – modélisation basée sur des agents . Il s’agit en fait d’une modélisation statistique classique.

Il existe deux approches de modélisation.

Premièrement : de l'objet au modèle (on détermine l'état système réel au moment initial et simuler ce qui va se passer ensuite).

La situation inverse peut être : du modèle à l'objet (on construit un modèle, on étudie, à quelles probabilités et valeurs initiales l'image sera stable ou instable, et nous émettons des recommandations)

Ainsi se déroule le cycle Data Model Processing New Data.

Lorsque nous détaillons un système, nous fixons non pas des lois mathématiques, mais des interactions spécifiques (comportementales) ou, en d'autres termes, locales des parties du système les unes avec les autres.

Sur la 1ère mesure il y a une initiale distribution aléatoire la probabilité qu'un élément soit dans un état particulier.

Nous répétons le processus de manière cyclique. C’est ce qu’on appelle la modélisation basée sur des agents ou par simulation.

Dans ce cas, nous obtenons des fonctions discrètes (constantes par morceaux).

Modélisation de processus aléatoires

Processus de Markov

Fonction X(t) appelé aléatoire , si sa valeur pour un argument est une variable aléatoire.

Fonction aléatoire X(t), dont l'argument est le temps, s'appelle processus aléatoire .

Un processus aléatoire se produisant dans un système S, appelé Markovien (ou un processus sans séquelle), s'il a la propriété suivante: à tout moment t 0, la probabilité de tout état du système dans le futur (avec t > t 0) ne dépend que de son état au présent (avec t = t0) et ne dépend pas du moment et de la manière dont le système S est arrivé à cet état.

Les processus de Markov sont un type particulier de processus aléatoires. Un endroit spécial Processus de Markov entre autres classes de processus aléatoires, cela est dû aux circonstances suivantes :

Pour les processus de Markov, un appareil mathématique bien développé permet de résoudre de nombreux problèmes pratiques;
A l’aide des processus de Markov, on peut décrire (exactement ou approximativement) le comportement de systèmes assez complexes.

Classification des processus de Markov

La classification des processus aléatoires de Markov est effectuée en fonction de la continuité ou de la discrétion de l'ensemble des valeurs de fonction X(t) et paramètre t.

Il existe les principaux types de processus aléatoires de Markov suivants :

à états discrets et à temps discret (chaîne de Markov) ;
à états continus et à temps discret (séquences de Markov) ;
avec des états discrets et temps continu(chaîne de Markov continue) ;
Avec état continu et temps continu.

Nous étudierons les processus à états discrets les plus adaptés à la modélisation des processus économiques.

Graphique d'état

Les processus de Markov avec des états discrets sont commodément illustrés à l'aide du graphe d'état, où les états sont indiqués par des cercles. S je systèmes S, et les flèches indiquent les transitions possibles d’un état à l’autre. Le graphique ne marque que les transitions directes et non les transitions passant par d'autres états. Les retards possibles dans l’état précédent sont représentés par une « boucle », c’est-à-dire une flèche dirigée depuis cet état en lui.

Riz. 3. Graphique d'état

Il peut y avoir un nombre fini d’états ou un nombre infini mais dénombrable.

Un processus aléatoire de Markov avec des états discrets et un temps discret est appelé Chaîne de Markov . Pour un tel processus, des moments t 1, t 2,…. lorsque le système S peut changer d'état, il est considéré comme étapes séquentielles processus, et l'argument dont dépend le processus n'est pas le temps t, mais l'étape numéro 1, 2,..., k,... Le processus aléatoire dans ce cas est caractérisé par une séquence d'états S(0), S(1), S(2),..., S(k),..., où S(0) est l'état initial du système (avant la première étape) ; S(1)– état du système après la première étape ; S(k)– état du système après la kième étape...

Séquence d'états S(1), S(2),..., S(k) peut être considéré comme une séquence d’événements aléatoires.

Notons la probabilité d'être après kème étape dans l'état S k . Alors

Les systèmes avec nombre finiétats S je (je =1,…, n).

Exemples de chaînes de Markov finies

Exemple 1. Modèle 4 « Garage »

Les voitures dans le garage peuvent être dans deux états : en état de marche (1) et en réparation (2).

Nous surveillerons régulièrement l’état des voitures. Par exemple, une fois par jour (le matin, avant de commencer le travail), l'état de chaque véhicule est déterminé. Les situations suivantes sont possibles :

le véhicule était et reste en bon état ;
la voiture était défectueuse et est devenue opérationnelle ;
la voiture était en bon état de marche et est devenue défectueuse ;
la voiture était défectueuse et est restée défectueuse.

Traçons un graphique des états et des transitions de ce système

Riz. 4

p 11 , p 12 , p 21 , p 22 , sont les probabilités de transitions d'un état à l'autre.

Si le type de voiture est le même, alors toutes les probabilités seront les mêmes pour toutes les voitures.

Représentons les probabilités sous forme de matrice

Appelé matrice de transition .

Propriétés de la matrice de transition

Chaque ligne caractérise l'état sélectionné du système, et ses éléments représentent les probabilités de toutes les transitions possibles en une étape à partir de celle sélectionnée (de je e) état, y compris la transition vers soi.
Les éléments des colonnes montrent les probabilités de toutes les transitions possibles du système en une étape vers une étape donnée ( j-e) état (en d'autres termes, la ligne caractérise la probabilité que le système passe d'un état, la colonne - à un état).
La somme des probabilités de chaque ligne est égale à un, puisque les transitions forment groupe completévénements incompatibles.
Le long de la diagonale principale de la matrice de probabilité de transition se trouvent les probabilités Pii que le système ne quittera pas l'État je, mais y restera.

Introduisons le vecteur – k=0,1,2,3...une fonction qui calcule la probabilité à chaque étape (cycle) de rester dans l'un des deux états.

Vecteur de probabilités d'état initial pour chaque machine. Par exemple, nous pouvons supposer que dans son état initial, la machine est utilisable de manière fiable, alors .

Décrivons ce processus sous la forme d'un arbre

De plus, à la première étape, la probabilité de l'état initial est ajoutée (définie).

Si vous réparez k=const, alors nous connaissons tous les résultats finaux du système. Si les probabilités p ij=const, alors ce processus est une chaîne de Markov. Ce modèle met en œuvre un processus sans fin. Lors du fonctionnement à long terme du système, il peut s'avérer que les probabilités des états tendent vers un certain nombre. Ces probabilités marginales appelé probabilités du processus stable . Lors de la modélisation de processus infinis, il est intéressant de calculer les probabilités d’un processus en régime permanent.

Exemple 2. Modèle 5 « Cube et pièces »

Il y a deux pièces A et B et un cube K. L'une a des armoiries et des têtes, et l'autre a les deux têtes.

Jeu : choisissez une pièce au hasard et lancez-la. Si les armoiries apparaissent, on lance le dé, s'il sort face, on lance à nouveau la même pièce.

Traçons un graphique des états du jeu

L’espace des résultats est fini. Toutes les probabilités sont fixes. Il s'agit d'une chaîne de Markov. Dans ce modèle, on peut voir que le processus se termine tôt ou tard si la pièce A est choisie au hasard. Si la pièce B a été choisie, alors le processus est sans fin.

Mission de travail indépendant

Créez une matrice de transition pour ce système.

Exemple 3. Modèle 6 « Jeu »

Il y a 5 états. A un moment donné, la particule (boule) se trouve dans l'un des états S je. Pour chaque étape, la particule ne peut aller que vers l'état voisin : en S i-1 avec probabilité p, V S i+1 avec probabilité q. En même temps (comme on le sait) p +q=1. Si une particule atteint l’état final, elle y reste pour toujours. Les probabilités sont fixes. Dans les États S je, je=2,3,4 la particule ne peut pas rester.

Construisons une matrice P., qui décrit les probabilités qu'une particule passe de l'état S je dans un état S j.

Ce modèle montre que le processus se terminera tôt ou tard. Ce modèle représente donc une chaîne de Markov finie. Lors de la modélisation des processus finaux, il est intéressant de calculer les probabilités de fin du processus dans un nœud particulier, ainsi que la durée moyenne du processus.