Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Recherche Opérationnelle: Programmation dynamique, chaînes de Markov, ﬁles d’at

Recherche Opérationnelle: Programmation dynamique, chaînes de Markov, ﬁles d’attente Cours de Tronc Commun Scientiﬁque FICM 2A Notes de cours et exercices corrigés Frédéric SUR sur@loria.fr http://www.loria.fr/∼sur/enseignement/RO/ École des Mines de Nancy 2013-2014 (version du 27 février 2014) Avertissement. Ce document est constitué de notes de cours qui contiennent vraisem- blablement des coquilles et erreurs. Merci de bien vouloir me les signaler. Il s’agit d’un résumé très condensé de notions dont l’étude approfondie nécessiterait bien plus de temps. On essaie ici de donner les éléments simpliﬁés, mais autant que pos- sible rigoureux, de la théorie qui permettent d’aller au delà de l’application de formules. N’hésitez pas à consulter la littérature dédiée. Table des matières 1 La programmation dynamique 7 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Un problème de plus court chemin . . . . . . . . . . . . . . . . 7 1.1.2 Principe d’optimalité de Bellman . . . . . . . . . . . . . . . . 8 1.2 L’équation de Bellman . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 Un système dynamique . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Équation de Bellman et principe d’optimalité . . . . . . . . . . 9 1.2.3 Un exemple de recherche de plus courts chemins . . . . . . . . 10 1.2.4 La résolution d’une équation de Bellman vue comme une re- cherche de plus courts chemins . . . . . . . . . . . . . . . . . . 10 1.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.1 La distance d’édition . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.2 Problème de location de skis . . . . . . . . . . . . . . . . . . . 14 1.3.3 Équilibrage de charge sur deux machines en parallèle . . . . . . 15 1.3.4 Un problème d’économie mathématique . . . . . . . . . . . . . 15 1.3.5 Gestion de stock . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.6 Problème du sac à dos . . . . . . . . . . . . . . . . . . . . . . 17 2 Les chaînes de Markov 19 2.1 Exemple introductif . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.1 Déﬁnitions et premières propriétés . . . . . . . . . . . . . . . . 21 2.2.2 Représentation graphique des chaînes de Markov . . . . . . . . 22 2.2.3 Chaînes réductibles et irréductibles . . . . . . . . . . . . . . . 24 2.2.4 Chaînes périodiques et apériodiques . . . . . . . . . . . . . . . 26 2.3 Comportement asymptotique des chaînes ergodiques . . . . . . . . . . 27 2.4 Le « théorème » des coupes . . . . . . . . . . . . . . . . . . . . . . . . 30 2.5 Comportement asymptotique des chaînes absorbantes . . . . . . . . . . 32 2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.6.1 L’anatomie d’un moteur de recherche (examen 2010-2011) . . . 35 2.6.2 Modèle économique de Leontief (examen 2011-2012) . . . . . 36 3 TABLE DES MATIÈRES 4 2.6.3 Problème de la ruine du joueur (examen 2013-2014) . . . . . . 37 3 Les ﬁles d’attentes 39 3.1 Rappels : loi de Poisson et loi exponentielle . . . . . . . . . . . . . . . 39 3.2 Caractéristiques d’un système d’attente . . . . . . . . . . . . . . . . . 40 3.3 La formule de Little . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.4 Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.4.1 Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . 44 3.5 Modélisation dans le cadre Markovien . . . . . . . . . . . . . . . . . . 47 3.5.1 La propriété PASTA . . . . . . . . . . . . . . . . . . . . . . . 47 3.5.2 Les clients et les serveurs sont sans mémoire . . . . . . . . . . 48 3.5.3 Les ﬁles d’attente M/M/1 . . . . . . . . . . . . . . . . . . . . . 50 3.5.4 Processus de naissance et de mort . . . . . . . . . . . . . . . . 55 3.6 Formulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.6.1 File M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.6.2 File M/M/1/K . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.6.3 File M/M/m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.6.4 File M/M/m/m . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.7 Les ﬁles M/G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.7.1 Processus de Markov par lot . . . . . . . . . . . . . . . . . . . 60 3.7.2 File M/G/1 générale . . . . . . . . . . . . . . . . . . . . . . . 61 3.8 Réseaux de ﬁles d’attente . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.9.1 Paradoxe de l’autobus . . . . . . . . . . . . . . . . . . . . . . 67 3.9.2 Dimensionnement d’un service-client . . . . . . . . . . . . . . 67 3.9.3 Vélos en libre service (rattrapage 2010-2011) . . . . . . . . . . 67 3.9.4 Chez le médecin (examen 2010-2011) . . . . . . . . . . . . . . 68 3.9.5 Un serveur informatique (rattrapage 2011-2012) . . . . . . . uploads/Industriel/ poly-ro-fsur.pdf