Probabilités et chaînes de Markov en tennis

Modélisation et simulation

• Le sujet porte sur la modélisation et la simulation.
• Le cours a été donné le 02 Octobre 2023.
• Le cours est pour la première année de Master Informatique, tronc commun.
• Le volume horaire hebdomadaire comprend 1h30 de cours et 1h30 de travaux pratiques (TP).
• Le responsable du cours est Dr. Bouras Ikram.
• Le contact est [email protected].
• Le bureau du professeur est le 32.
• L'évaluation comprend 60% d'examen et 40% de travaux pratiques (TP).

Programme

• Chapitre 01 : Introduction à la modélisation et à la simulation.
• Chapitre 02 : Technique d'évaluation des performances : Chaîne de Markov à temps discret.
• Chapitre 03 : Technique d'évaluation des performances : Les Files d'attente.
• Chapitre 04 : La simulation.
• Chapitre 05 : Les outils de simulation.

Présentation et objectifs

• La matière couvre les bases de la modélisation et la simulation informatique.
• L'objectif est d'introduire les concepts de modélisation et simulation.
• L'objectif est aussi d'apporter aux étudiants les savoir-faire nécessaires à la compréhension des systèmes et à l'amélioration de leurs performances.
• Les prérequis sont les probabilités et les statistiques.

Définition d'un système

• Un système est un ensemble de moyens et d'éléments (matériels, logiciels, naturels ou artificiels) organisés pour atteindre un objectif précis.

Exemples de systèmes

• Réseau de communication : Ensemble des ressources matérielles et logicielles pour la transmission et l'échange d'informations entre différentes entités.
• Système d'armes : Ensemble de dispositifs mécaniques, électroniques ou logiciels servant aux militaires pour accomplir une mission.
• Chaîne de production : Ensemble des opérations de fabrication nécessaires à la production d'un certain produit.

Caractéristiques d'un système

• Les composants qui le constituent.
• Les relations entre ces composants.
• Son environnement.
• Sa mission (objectifs et raison d'être).
• Ses évolutions au cours du temps.

Exemple d'un système (usine de production)

• Main d'œuvre
• Service achats
• Service approvisionnement
• Service de gestion de stocks
• Service fabrication
• Service ventes
• Service ordonnancement de la production
• Service administratif

État d'un système

• À chaque instant, un système se trouve dans un état particulier défini par l'état de ses composants et les relations qui les relient.
• L'état du système est décrit par les valeurs des variables qui le caractérisent (nombre de clients en attente, nombre de clients en service, état des serveurs, etc.).
• L'état du système évolue en fonction des changements des composants ou des relations entre eux.
• L'évolution du système est donnée par la succession des états traversés.

Types de systèmes

• Discret : Un système avec un nombre dénombrable d'états et une évolution par sauts à des instants discrets, espacés d'une période constante. (Ex: arrivée d'un client au guichet d'une poste).
• Continu : Un système dont l'évolution est continue dans le temps. (Ex: croissance d'une population).
• Déterministe : Un système qui réagit toujours de la même façon à un événement, quel que soit son historique. (Exemple: un programme s'exécutant en mono-programmation).
• Probabiliste (stochastique) : Un système dont le comportement dépend du hasard. (Exemple: le système de gestion de stock).

La modélisation

• Un modèle est une représentation mathématique, physique ou logique d'un système réel.
• Il sert à étudier le système et à en expliquer certains aspects de son comportement.
• Un modèle est parfois nécessaire car le système réel peut être inaccessible, trop coûteux ou changer trop vite ou trop lentement (système solaire, tir nucléaire, etc).
• L'étude se fait sur le modèle, car il est plus facile à manipuler.

Avantages de la simulation

• Éviter la construction d'un système qui n'existe pas.
• Éviter des expérimentations directes sur un système existant (problèmes de sécurité ou économiques).

Processus de modélisation

• Définir les objectifs du système.
• Examiner avec précision le niveau de détails du modèle.
• Identifier les frontières du modèle.
• Mesurer la performance du modèle.
• Recueillir des données.
• Évaluer et implémenter les processus.

La simulation

• L'implantation dynamique d'un ou plusieurs modèles.
• Faire évoluer le modèle dans le temps (vitesse, température, etc.).
• Traduire un modèle en programmes informatiques (algorithmes).

Étapes de la simulation

• Problème donné.
• Construction du modèle.
• Recherche de la solution.
• Implémentation.
• Résultats satisfaisants ?

Chapitre 02: Evaluation des performances

• L'évaluation des performances vise à prédire le comportement d'un système.
• Elle sert à évaluer l'impact des changements d'architecture ou d'implémentation sur la performance du système.
• L'évaluation des performances permet de mesurer divers aspects du comportement du système (réactivité, débit, utilisation des ressources, évolutivité).

Outils d'évaluation des performances

• Méthodes mathématiques (modélisation analytique): Utiliser des modèles mathématiques pour représenter le système et prédire ses performances en fonction de paramètres connus ou supposés. Les modèles analytiques sont rapides et efficaces en calcul mais limités aux systèmes décrites facilement par des équations.

• Simulation: Créer un modèle virtuel du système et y effectuer des expériences pour étudier son comportement dans différentes configurations et charges de travail ; utile pour des systèmes complexes où les solutions analytiques sont difficiles à obtenir.

Chaînes de Markov

• Les chaînes de Markov sont des suites de variables aléatoires qui ne dépendent que de l'état actuel.
• Elles décrivent l'état du système à chaque instant t (le temps).
• Un état est défini comme un événement possible du système.
• On décrit l'évolution du système grâce aux probabilités de transition entre les états (Pij): la probabilité de passer de l'état i à l'état j.

Définitions (Graphes pondérés et probabilistes)

• Un graphe pondéré est un graphe dont chaque arête est associée à un poids réel positif.
• Un graphe probabiliste est un graphe orienté pondéré par des réels compris entre 0 et 1, où la somme des poids des arêtes issues de chaque sommet est égale à 1.

Types de systèmes

• Discret: Évolution du système à des instants discrets. (Ex: files d'attente)
• Continu: Évolution du système à tout moment. (Ex: croissance de population)
• Déterministe: Évolution prévisible et non aléatoire.
• Probabiliste: Évolution dépendante du hasard.

États stables d'une chaîne de Markov homogène

• Une loi de probabilité π est stationnaire (ou loi stationnaire) si elle n'est pas modifiée par le temps.

Classification des états

• Un état est accessible depuis un autre; s'il existe un chemin entre les états.
• Deux états communiquent s'ils sont accessibles l'un de l'autre.
• Une classe est une ensemble d'états qui communiquent entre eux.
• Une chaîne est irréductible quand tous ses états communiquent.
• Un état est absorbant si la probabilité de revenir à l'état est égale à 1 quand on y est déjà.
• Une classe est fermée quand elle ne peut pas sortir de la classe.
• Périodicité: le temps séparant deux retours au même état. Une classe est apériodique si sa période est 1.

États récurrents et transients

• Un état est récurrent si partant de cet état, il y a une probabilité de 1 à revenir à cet état, en nombre fini de pas.
• Un état est transient si la probabilité de retour à cet état est strictement inférieure à 1, la possibilité de ne plus jamais le visiter existe.

Modélisation d'une chaîne de Markov (Exemple)

• Exemple de la grenouille sur une échelle : on suppose que chaque minute, la grenouille monte ou descend d'un barreau avec les mêmes chances.

Exemple de chaîne de Markov (Exemple 2)

• Exemple du temps (beau, neige, pluie) où à chaque jour de l'évolution du système on doit avoir la même probabilité.

Loi d'une chaîne de Markov

• Une suite d'états définit un chemin de longueur m allant de x1 à xm dans le graphe et P(x1, x2)...P(xm-1,xm) > 0.

Loi d'une Chaîne de Markov - Théorème

• Une chaîne de Markov de matrice de transition P, est une trajectoire aléatoire (X t ) t∈ N, dont la loi est donnée par la formule: P(Xo = x0, X1 = x1,..., Xm = xm) = μ(x0)P(x1, x2).P(x2, x3)...P(Xm-1, Xm).

• On dit alors que μ(xo) est la loi initiale de la chaîne de Markov.

La loi de Xn

• Probabilité sur E et le vecteur ligne dont la i-ème coordonnée est μ(xi).
• Loi de Xo et loi de X1 et Xn.

Exemple d'une chaîne de Markhov

• Exemple de calcul de probabilité de trajectoires avec une loi initiale.

### Files d’attente 

• La modélisation des Files d’attente permettent de prédire le comportement des Systèmes répondant a des demandes aléatoires en utilisant des modèles aléatoires.

• Des exemples sont les Réseaux informatiques et de télécommunications, les Centres d’appels téléphoniques, les hôpitaux, les banques, la Restauration rapide, …

• Les caractéristiques importantes d'une file d’attente : processus d’arrivées des clients, temps de service, nombre de serveurs, discipline de service, capacité de la file d’attente, taille de la population.

• La notation de Kendall (T/X/C/K/P/Z) décrit des systèmes de files d'attente en utilisant la notation T/X/C/K/P/Z, avec : T(distribution du temps des arrivées), X(distribution du temps de service), C(nombre de serveurs), K(capacité de la file d'attente), P(taille de la population), Z(discipline de service).

• Distributions de type de services: M (markovien) = distribution exponentielle, G (générale) = distribution générale, D (déterministe)

• Discipline de service: FIFO, LIFO,...,

• Les paramètres de performances des files d'attente : Nombre moyen de clients dans le système, la file, la durée d'attente, la durée de service.

• Exemple M/M/1 /k: Les clients se présentent au système aléatoirement suivant le processus de Poisson de taux λ. Le temps de service suit une loi exponentielle de taux μ. La file d’attente a une capacité k où lorsque un client arrive lors que la file est pleine, il est perdu.

• Exemple d’une chaîne de Markov à temps continu: La chaîne de Markov à temps continu sert a modéliser une évolution du système au cas où on a une famille de v.a a valeurs discretes dans un espace E et pour un temps t > 0.

• Processus de Naissance et Mort: C’est un processus qui sert à décrire une évolution aléatoire au cours du temps d’un nombre d’individus d'une population ou d'un système d'attente. Les variables aléatoires (Xt) prennent donc leurs valeurs dans l'ensemble des entiers. Le processus évolue comme un processus markovien à temps continu.

La simulation

• Les étapes de développement d'un modèle de simulation: Identification du problème, Évaluation de l’approche simulation, Formulation du problème, Collecte et entrée des données, Formulation du modèle mathématique, Estimation des paramètres, Validation, Production, Analyse/Documentation

• Les types de simulation: Simulation continue (changement continu des états du système) vs Simulation discrète (succession d'états changeant brusquement)

• Avantages de la simulation: Vérifier une solution analytique, moins chère que des expériences, plus de contrôle sur le temps et le déroulement, simulation sans danger

• Inconvénients de la simulation: Demande de temps et d’argent, exigences importantes sur les données, les modèles et le processus de mise en œuvre