Examens corriges

Notes de cours et exercices corrigés de Recherche Opérationnelle

Introduction à la recherche opérationnelle

Ce document rassemble les notes de cours et les exercices corrigés de recherche opérationnelle dispensés à l'École des Mines de Nancy. Conçu pour le tronc commun scientifique de la formation FICM 2A par Frédéric Sur pour l'année universitaire 2013-2014, cet ouvrage de référence aborde trois grands thèmes mathématiques appliqués à la modélisation et à l'optimisation des systèmes complexes : la programmation dynamique, les chaînes de Markov et la théorie des files d'attente.

L'approche pédagogique choisie privilégie la rigueur théorique tout en conservant une vision simplifiée permettant d'aller au-delà de la simple application de formules. Chaque chapitre est complété par une sélection d'exercices d'application et d'examens précédents, accompagnés de leurs corrigés détaillés en fin de volume.

La programmation dynamique

Le premier chapitre est consacré à la programmation dynamique et à son application aux problèmes d'optimisation. Il introduit le principe d'optimalité de Bellman, qui permet de résoudre un problème global en le décomposant en sous-problèmes emboîtés. L'étude commence par la recherche du plus court chemin dans un graphe orienté valué, avec notamment la présentation de l'algorithme de Floyd-Warshall. Le cours formalise ensuite le concept de système dynamique à temps discret et définit l'équation de Bellman, faisant le lien entre l'optimisation séquentielle et la recherche de chemins optimaux dans des graphes de décision.

Les exercices proposés dans cette partie permettent d'appliquer ces méthodes à des contextes variés : la distance d'édition entre chaînes de caractères (distance de Levenshtein), le problème de location de skis, l'équilibrage de charge sur des machines en parallèle, un modèle classique d'économie mathématique sur la consommation optimale, la gestion de stocks sur plusieurs périodes et le célèbre problème du sac à dos (knapsack problem).

Les chaînes de Markov

Le second chapitre aborde l'étude des processus stochastiques dont l'évolution future ne dépend que de l'état présent, formalisant ainsi les chaînes de Markov homogènes à états finis. Après des exemples introductifs basés sur l'observation météorologique, le cours détaille le vocabulaire fondamental : matrices de transition, graphes de transition, propriétés d'irréductibilité, périodicité, et classification des états en états récurrents, transitoires ou absorbants.

L'analyse se poursuit par le comportement asymptotique des chaînes ergodiques, l'étude de la convergence vers la distribution stationnaire via le théorème de Perron-Frobenius, et l'utilisation pratique du théorème des coupes pour la conservation des flux. Un accent particulier est mis sur les chaînes absorbantes, en introduisant la matrice fondamentale pour calculer le nombre moyen de passages par les états transitoires et les probabilités d'absorption. Les exercices corrigés illustrent ces notions à travers l'anatomie d'un moteur de recherche avec le calcul du PageRank, le modèle économique input-output de Wassily Leontief, et le problème classique de la ruine du joueur.

Les files d'attente

Le troisième chapitre s'intéresse à la modélisation mathématique des files d'attente, omniprésentes dans la gestion des réseaux informatiques, des centres d'appels ou des flux logistiques. Le cours pose d'abord les bases probabilistes avec la loi de Poisson et la loi exponentielle, caractérisée par sa propriété fondamentale d'absence de mémoire. La célèbre formule de Little est démontrée pour lier le nombre moyen de clients dans le système, leur temps de séjour et le taux d'arrivée.

Le cadre markovien est ensuite développé à travers la propriété PASTA (Poisson Arrivals See Time Averages) et l'étude détaillée des files de type M/M/1, M/M/m, ainsi que des processus de naissance et de mort. Le formulaire complet fourni dans le cours synthétise les expressions des probabilités d'état, des nombres moyens et des temps d'attente pour différents types de files, incluant les systèmes à capacité limitée. Enfin, l'analyse s'ouvre sur les files M/G/1 et les formules de Pollaczek-Khinchine, complétées par des exercices portant sur le paradoxe de l'autobus, le dimensionnement de services clients, la gestion de stocks par files d'attente, et des systèmes industriels critiques redondants.

Correction des exercices

Le dernier chapitre du document fournit l'intégralité des corrections détaillées pour l'ensemble des exercices proposés dans les chapitres précédents. Cette section permet aux étudiants de travailler en autonomie, de vérifier le raisonnement mathématique pas à pas et de comprendre les subtilités de la mise en œuvre algorithmique et analytique des méthodes d'optimisation et de probabilités.

Questions fréquentes

Quel est le niveau académique de ce document ?

Ce cours s'adresse aux étudiants en deuxième année de cycle ingénieur (FICM 2A) et aux élèves en tronc commun scientifique de l'École des Mines de Nancy.

Quels sont les trois grands thèmes abordés dans le cours ?

Le document couvre la programmation dynamique et l'équation de Bellman, les chaînes de Markov discrètes et leurs régimes asymptotiques, ainsi que la théorie mathématique des files d'attente.

Le document contient-il des exercices corrigés ?

Oui, le quatrième chapitre rassemble les corrections détaillées de tous les exercices proposés à la fin des chapitres sur la programmation dynamique, les chaînes de Markov et les files d'attente.

Qui est l'auteur de ces notes de cours ?

Ce support pédagogique a été rédigé par Frédéric Sur, enseignant-chercheur rattaché à l'École des Mines de Nancy et au Loria.

Testez vos connaissances

Question 1

Quel algorithme est présenté pour résoudre le problème du plus court chemin dans un graphe avec des valuations négatives mais sans circuit absorbant ?

  1. L'algorithme de Dijkstra
  2. L'algorithme de Floyd-Warshall
  3. L'algorithme du simplexe
  4. L'algorithme de Prim

Réponse correcte : L'algorithme de Floyd-Warshall

Explication : Le cours indique que l'algorithme de Dijkstra nécessite des valuations positives, tandis que l'algorithme de Floyd-Warshall permet de traiter les valuations négatives en l'absence de circuit de valuation totale négative.

Question 2

Que signifie l'acronyme PASTA dans le contexte des files d'attente ?

  1. Poisson Arrivals See Time Averages
  2. Probability And Service Time Analysis
  3. Processus Aléatoire Sans Temps d'Attente
  4. Parallel Arrivals System Time Allocation

Réponse correcte : Poisson Arrivals See Time Averages

Explication : Introduite par Wolff en 1982, la propriété PASTA énonce que lorsqu'les arrivées suivent un processus de Poisson, la distribution vue par un client entrant est égale à la distribution observée en régime permanent.

Question 3

Quelle est la condition de stabilité pour une file d'attente de type M/M/1 de taux d'arrivée λ et de taux de service µ ?

  1. λ = µ
  2. λ > µ
  3. λ < µ
  4. λ < µ²

Réponse correcte : λ < µ

Explication : Le cours précise que le rapport τ = λ/µ doit être strictement inférieur à 1 pour qu'un régime permanent s'établisse, faute de quoi la file s'allonge indéfiniment.

Question 4

Quelle est la forme de la relation fondamentale de la formule de Little reliant le nombre moyen de clients N, le taux d'arrivée λ et le temps de séjour moyen T ?

  1. N = λ + T
  2. N = T / λ
  3. N = λ · T
  4. N = λ² · T

Réponse correcte : N = λ · T

Explication : La formule de Little établit que le nombre moyen de clients dans le système est égal au produit du taux moyen d'arrivée par le temps de séjour moyen, valable de manière générale sans hypothèse particulière sur les lois d'arrivée ou de service.





Télécharger Notes de cours et exercices corrigés de Recherche Opérationnelle pdf