Recherche opérationnelle 2

Ce cours de recherche opérationnelle du semestre 4 est la suite du cours du semestre 3 (programmation linéaire, simplexe, dualité et sensibilité). Il élargit la boîte à outils du futur technicien supérieur en informatique et cybersécurité à trois familles de modèles très présentes dans les métiers du numérique : les modèles linéaires multipériodes (planification de production, de stocks et de budgets), la programmation en nombres entiers (choix de projets de sécurité sous budget, coûts fixes, décisions oui/non) et les problèmes de réseaux (plus court chemin pour le routage, arbre couvrant minimal pour le dimensionnement d’un réseau de fibre, flot maximal pour la capacité d’une infrastructure, transport et affectation). Les modèles sont formulés, résolus à la main sur de petits exemples puis saisis dans LINDO.

Objectifs d’apprentissage

• Formuler des modèles de planification multipériode avec équations de stock et les saisir dans LINDO.
• Modéliser des décisions discrètes avec des variables entières et binaires (coûts fixes, choix exclusifs, contraintes logiques).
• Appliquer la méthode de séparation et évaluation (branch and bound).
• Résoudre des problèmes de plus court chemin (Dijkstra) et d’arbre couvrant minimal (Kruskal, Prim).
• Calculer un flot maximal et la coupe minimale associée ; résoudre des problèmes de transport et d’affectation.

Prérequis

Cours de recherche opérationnelle du semestre 3 (ROP2324) : formulation, simplexe, dualité. Notions de graphes (sommets, arcs, chemins).

Plan du cours

1. Leçon 1 — Modèles multipériodes : stocks, planification et mise en œuvre sous LINDO
2. Leçon 2 — Programmation en nombres entiers et séparation-évaluation
3. Leçon 3 — Réseaux : plus court chemin et arbre couvrant minimal
4. Leçon 4 — Flots, transport et affectation

Modalités d’évaluation

Volume horaire : 13 h de CM, 7 h de TD, 0 h de TP, 20 h de TPE ; 2 crédits. Contrôle continu (40 % : deux interrogations et un mini-projet de modélisation sous LINDO) et examen terminal écrit de 2 heures (60 %).

Bibliographie

• F. S. Hillier, G. J. Lieberman, Introduction to Operations Research, McGraw-Hill.
• W. L. Winston, Operations Research: Applications and Algorithms, Duxbury Press.
• H. A. Taha, Operations Research: An Introduction, Pearson Prentice Hall.
• R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
• L. A. Wolsey, Integer Programming, Wiley, 1998.