Recherche opérationnelle 1

La recherche opérationnelle (RO) regroupe les méthodes mathématiques qui aident à prendre la meilleure décision possible sous contraintes : combien produire, comment mélanger des matières premières, comment répartir un budget ou des heures de travail. Pour un futur administrateur systèmes et réseaux orienté sécurité, ces méthodes servent aussi à dimensionner des infrastructures, à répartir un budget de sécurité ou à planifier des équipes de supervision (SOC). Ce premier cours (semestre 3) est consacré à la programmation linéaire : modélisation, résolution graphique, algorithme du simplexe, dualité et analyse de sensibilité, avec une initiation au logiciel LINDO. La suite (semestre 4) traitera la programmation en nombres entiers, les problèmes de réseaux et de flots.

Objectifs d’apprentissage

• Reconnaître les structures courantes de problèmes de décision (production, mélange, choix de médias, placements financiers).
• Formuler un programme linéaire : variables de décision, fonction objectif, contraintes, conditions de non-négativité.
• Résoudre graphiquement un programme linéaire à deux variables et identifier les cas particuliers (solution multiple, non bornée, impossible).
• Appliquer l’algorithme du simplexe sous forme de tableaux et en interpréter chaque itération.
• Écrire le dual d’un programme linéaire, interpréter les prix duaux (prix fantômes) et les intervalles de sensibilité, en connaître les limites.
• Saisir un modèle dans LINDO et lire son rapport de résolution.

Prérequis

Mathématiques de première année : équations et inéquations linéaires, représentation graphique de droites, systèmes d’équations, notions de matrices. Pratique élémentaire d’un tableur.

Plan du cours

1. Leçon 1 — Modélisation et formulation de programmes linéaires
2. Leçon 2 — Résolution graphique et cas particuliers
3. Leçon 3 — L’algorithme du simplexe
4. Leçon 4 — Dualité, analyse de sensibilité et initiation à LINDO

Modalités d’évaluation

Volume horaire : 13 h de cours magistral (CM), 7 h de travaux dirigés (TD), 0 h de travaux pratiques, 20 h de travail personnel de l’étudiant (TPE) ; 2 crédits. Évaluation : contrôle continu (40 % : interrogations écrites en TD, un devoir de modélisation à rendre) et examen terminal écrit de 2 heures (60 %) comportant une formulation de problème, une résolution par le simplexe et une question d’interprétation de sensibilité.

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.
• V. Chvátal, Linear Programming, W. H. Freeman, 1983.
• D. de Werra, T. M. Liebling, J.-F. Hêche, Recherche opérationnelle pour ingénieurs, tome I, Presses polytechniques et universitaires romandes.