Plan de cours : Outils de résolution de problèmes
d’optimisation
Année académique 2024- 2025
Unité d'enseignement : Recherche Opérationnelle
APERCU GENERAL
Université : Université d’Abomey-Calavi
Etablissement : Institut de Formation et de Recherche en Informatique (IFRI)
Grade : Licence en Intelligence Artificielle
Masse horaire : 30 heures
Nombre de crédits : 2 crédits
Chargé du cours : Dr Ing. Houndji Vinasetan Ratheil
OBJECTIF GÉNÉRAL:
L'objectif général de ce cours est de donner aux apprenants les outils nécessaires
pour comprendre les principales techniques de base en Recherche
Opérationnelle (Formulation des problèmes d’optimisation et méthodes de
résolution).
OBJECTIFS DU COURS POUR L’APPRENANT:
Au terme de ce cours, l’apprenant sera capable:
Ø de formuler une situation problème sous la forme d'un modèle
d'optimisation ;
Ø d’analyser un modèle d'optimisation. En particulier, déterminer s'il est
linéaire ou s'il est convexe ;
Ø de caractériser les solutions optimales d'un modèle d'optimisation et,
lorsque c'est possible, les calculer analytiquement (à l'aide des conditions
d'optimalité), analyser leur sensibilité à l'aide de la dualité dans le cas
linéaire ;
Ø de rendre compte par écrit d'un travail de formulation, d'analyse et/ou de
résolution de modèles d'optimisation.
1
CONTENU DE COURS
Partie1 : Programmation Linéaire
Chapitre 1: Introduction aux problèmes d’optimisation
Chapitre 2: Formulation de problèmes linéaires
Forme générale
Forme géométrique
Forme standard
Chapitre 3: Géométrie des polyèdres
Le théorème fondamental
Polyèdre et représentation
Notion de convexité
Solution graphique pour le cas de deux variables
Chapitre 4: Méthode du simplexe
Principe
Tableau simplexe
Forme canonique
Algorithme du simplexe
Convergence
Chapitre 5: Dualité
Différentes formes du dual
Interprétation économique du dual
Analyse de sensibilité
Partie 2 : Programmation en Nombres Entiers
Chapitre 1: Formulations de problèmes en nombres entiers
Chapitre 2: Contraintes alternatives
Chapitre 3: Algorithme du Branch and Bound
Partie 3 : Introduction à l’optimisation non linéaire
Chapitre 1: Motivation
2
Chapitre 2: Conditions d’optimalité
Problèmes sans contraintes
Problèmes avec contraintes
Conditions d’optimalité de Karush-Kuhn-Tucker
Chapitre 3: Problèmes convexes
Reconnaître un problème convexe
Propriétés des problèmes convexes
Chapitre 4: Méthodes de recherche en ligne
Méthode du gradient
Méthode de quasi-newton
Méthode de Newton
METHODES D’ENSEIGNEMENTS ET D’APPRENTISSAGE
Cours magistral
Travaux Dirigés
Classes inversées
Travaux Pratiques avec le solveur ORTools
Travaux Personnels des Etudiants
MATERIEL PEDAGOGIQUE
Vidéo projecteur
Tableau blanc/marqueur
EVALUATION DES APPRENTISSAGES
1 Examen écrit (sur des questions de compréhension, de connaissance et
d'application) – 50 %
2 Travail à rendre (Exercices théoriques + Implémentation avec ORTools) –
groupe de 3 apprenants – 25 %
Séminaire/Participation – 25 %
3
REFERENCES BIBLIOGRAPHIQUES
Vincent Blondel and François Glineur, Slides du cours de INMA1702:
Méthodes et Modèles d’Optimisation I, Université catholique de Louvain, 2013.
Dimitris Bertsimas, John N. Tsitsiklis, Introduction to Linear Optimization,
2008.
C. Gueret, C. Prins, M. Ssevaux, Programmation Linéaire, Eyrolles, 2000
Y. Norbert, R. Oullet, R. Parent, La recherche opérationnelle, Gaétan Morin,
1995.
Laurence Wolsey, Integer Programming, Wiley Interscience publication, 1998.
Autres: Séminaires animés par les étudiants
Méthodes des points intérieurs
Théorie des graphes
La génération de colonnes
Méthodes des ellipsoïdes
La dualité de Lagrange
La théorie des jeux à deux personnes et à somme zéro
Problème du voyageur de commerce : Etat de l’art
Programmation dynamique
Les algorithmes de coupes
Méthode de quasi-Newton et méthode du gradient conjugué
