Recherche opérationnelle 2

Ce cours de recherche opérationnelle du semestre 4 fait suite à celui du semestre 3 (programmation linéaire, simplexe, premiers éléments de théorie des graphes). Il est consacré aux problèmes d’optimisation sur les graphes et réseaux, omniprésents dans la vie commerciale : organiser la tournée d’un commercial entre les boutiques de Niamey, trouver l’itinéraire le plus court d’un livreur, planifier le lancement d’un produit ou d’une boutique en ligne, affecter les commerciaux aux zones de vente, acheminer des marchandises des dépôts vers les clients au moindre coût.

On approfondit d’abord le vocabulaire des graphes (graphes orientés, chemins, circuits) et l’on étudie les chemins et circuits hamiltoniens (problème du voyageur de commerce). On aborde ensuite les applications aux chemins optimaux, à l’ordonnancement, aux flots et à l’affectation, puis le problème de transport (solution de base par le coin Nord-Ouest et par le coût minimum, puis recherche de la solution optimale).

Objectifs d’apprentissage

• Utiliser le vocabulaire des graphes orientés et reconnaître chaînes eulériennes et circuits hamiltoniens.
• Résoudre un petit problème de tournée (voyageur de commerce) par énumération et par l’heuristique du plus proche voisin.
• Calculer un plus court chemin par l’algorithme de Dijkstra.
• Ordonnancer un projet : dates au plus tôt et au plus tard, marges, chemin critique.
• Déterminer un flot maximal et résoudre un problème d’affectation par la méthode hongroise.
• Résoudre un problème de transport : solution de base (coin Nord-Ouest, coût minimum) puis optimisation par la méthode des potentiels.

Prérequis

Cours de recherche opérationnelle du semestre 3 (systèmes linéaires, programmation linéaire, vocabulaire de base des graphes, arbres).

Plan du cours

1. Leçon 1 — Vocabulaire des graphes orientés, chaînes eulériennes, chemins et circuits hamiltoniens
2. Leçon 2 — Chemins optimaux et ordonnancement de projets (Dijkstra, MPM/PERT)
3. Leçon 3 — Flots maximaux et affectation optimale (Ford-Fulkerson, méthode hongroise)
4. Leçon 4 — Le problème de transport : coin Nord-Ouest, coût minimum et solution optimale

Modalités d’évaluation

Volume horaire (maquette) : 10 h de CM, 0 h de TD, 0 h de TP, 10 h de TPE ; 1 crédit. Le travail personnel consiste à refaire les exemples et exercices corrigés. Évaluation : contrôle continu (quiz en ligne et devoir, 40 %) et examen terminal écrit (60 %). Calculatrice autorisée.

Bibliographie

• Hillier F. S., Lieberman G. J., Introduction to Operations Research, McGraw-Hill.
• Taha H. A., Operations Research: An Introduction, Pearson.
• Faure R., Lemaire B., Picouleau C., Précis de recherche opérationnelle, Dunod.
• Gondran M., Minoux M., Graphes et algorithmes, Eyrolles.