Recherche Opérationnelle

[PDF] recherche opérationnelle exercices corrigés gratui

[PDF] cours de recherche operationnelle gratuit pdf

[PDF] programmation linéaire exercices corrigés simplex

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule

[PDF] multiplicateur des dépenses publiques macroéconomi

Recherche Opérationnelle:

Programmation dynamique, chaînes de Markov, files d"attente

Cours de Tronc Commun Scientifique

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) 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 simplifié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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.1 Un problème de plus court chemin . . . . . . . . . . . . . . . .

1.1.2 Principe d"optimalité de Bellman . . . . . . . . . . . . . . . .

1.2 L"équation de Bellman . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.1 Un système dynamique . . . . . . . . . . . . . . . . . . . . . .

1.2.2 Équation de Bellman et principe d"optimalité . . . . . . . . . .

1.2.3 Un exemple de recherche de plus courts chemins . . . . . . . .

1.2.4 La résolution d"une équation de Bellman vue comme une re-

cherche de plus courts chemins . . . . . . . . . . . . . . . . . . 10

1.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3.1 La distance d"édition . . . . . . . . . . . . . . . . . . . . . . .

1.3.2 Problème de location de skis . . . . . . . . . . . . . . . . . . .

1.3.3 Équilibrage de charge sur deux machines en parallèle . . . . . .

1.3.4 Un problème d"économie mathématique . . . . . . . . . . . . .

1.3.5 Gestion de stock . . . . . . . . . . . . . . . . . . . . . . . . .

1.3.6 Problème du sac à dos . . . . . . . . . . . . . . . . . . . . . .

2 Les chaînes de Markov 19

2.1 Exemple introductif . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1 Définitions et premières propriétés . . . . . . . . . . . . . . . .

2.2.2 Représentation graphique des chaînes de Markov . . . . . . . .

2.2.3 Chaînes réductibles et irréductibles . . . . . . . . . . . . . . .

2.2.4 Chaînes périodiques et apériodiques . . . . . . . . . . . . . . .

2.3 Comportement asymptotique des chaînes ergodiques . . . . . . . . . .

2.4 Le " théorème » des coupes . . . . . . . . . . . . . . . . . . . . . . . .

2.5 Comportement asymptotique des chaînes absorbantes . . . . . . . . . .

2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6.1 L"anatomie d"un moteur de recherche (examen 2010-2011) . . .

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) . . . . . .

3 Les files d"attentes 39

3.1 Rappels : loi de Poisson et loi exponentielle . . . . . . . . . . . . . . .

3.2 Caractéristiques d"un système d"attente . . . . . . . . . . . . . . . . .

3.3 La formule de Little . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.1 Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . .

3.5 Modélisation dans le cadre Markovien . . . . . . . . . . . . . . . . . .

3.5.1 La propriété PASTA . . . . . . . . . . . . . . . . . . . . . . .

3.5.2 Les clients et les serveurs sont sans mémoire . . . . . . . . . .

3.5.3 Les files d"attente M/M/1 . . . . . . . . . . . . . . . . . . . . .

3.5.4 Processus de naissance et de mort . . . . . . . . . . . . . . . .

3.6 Formulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.1 File M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.2 File M/M/1/K . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.3 File M/M/m . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.4 File M/M/m/m . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7 Les files M/G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7.1 Processus de Markov par lot . . . . . . . . . . . . . . . . . . .

3.7.2 File M/G/1 générale . . . . . . . . . . . . . . . . . . . . . . .

3.8 Réseaux de files d"attente . . . . . . . . . . . . . . . . . . . . . . . . .

3.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.9.1 Paradoxe de l"autobus . . . . . . . . . . . . . . . . . . . . . .

3.9.2 Dimensionnement d"un service-client . . . . . . . . . . . . . .

3.9.3 Vélos en libre service (rattrapage 2010-2011) . . . . . . . . . .

3.9.4 Chez le médecin (examen 2010-2011) . . . . . . . . . . . . . .

3.9.5 Un serveur informatique (rattrapage 2011-2012) . . . . . . . .

3.9.6 Problème de maintenance informatique (examen 2010-2011) . .

3.9.7 Étude d"une file M/G/1 (examen 2010-2011) . . . . . . . . . .

3.9.8 Maintenanced"unsystèmeindustrielcritique(examen2011-2012)

3.9.9 Approvisionnement et gestion d"un stock (examen 2013-2014) .

3.9.10 Un guichet avec des clients prioritaires (rattrapage 2013-2014) .

4 Correction des exercices 75

4.1 La programmation dynamique . . . . . . . . . . . . . . . . . . . . . .

4.1.1 La distance d"édition . . . . . . . . . . . . . . . . . . . . . . .

4.1.2 Problème de location de skis . . . . . . . . . . . . . . . . . . .

4.1.3 Équilibrage de charge sur deux machines en parallèle . . . . . .

4.1.4 Un problème d"économie mathématique . . . . . . . . . . . . .

4.1.5 Gestion de stock . . . . . . . . . . . . . . . . . . . . . . . . .

F. Sur 2013-2014

5 TABLE DES MATIÈRES

4.1.6 Problème du sac à dos . . . . . . . . . . . . . . . . . . . . . .

4.2 Les chaînes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.1 L"anatomie d"un moteur de recherche . . . . . . . . . . . . . .

4.2.2 Modèle économique de Leontief . . . . . . . . . . . . . . . . .

4.2.3 Problème de la ruine du joueur . . . . . . . . . . . . . . . . . .

4.3 Les files d"attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

[PDF] Recherche Opérationnelle - LORIA