Modélisation et Aide à la décision

Ects : 2

Enseignant responsable :

Volume horaire : 15

Description du contenu de l'enseignement :

1 - Introduction : comprendre les enjeux de la modélisation dans le cadre général de la programmation linéaire en variables mixtes Notion de relaxation Comparaison de formulations alternatives : application au problème de lot sizing Symétrie : comparaison du modèle d'affectation et du modèle étendu pour le problème du Bin Packing

2 - Techniques de modélisation Variables indicateur : application au coût fixe Conditions logiques : modélisation sous forme normale conjonctive Contraintes disjonctives Linéarisation des termes quadratiques Linéarisation des valeurs absolues Linéarisation des fonctions objectifs

3 - Applications des méthodes de modélisation à divers problèmes Problèmes d'affectation, de transport, et de transbordement Problèmes de flot TSP, CVRP Newsvendor problem Facility location problem

Utilisation de la librairie pulp de Python.

Pré-requis obligatoires :

Avoir suivi l'UE de Modélisation en programmation linéaire de L3 MIAGE et l'UE de Décision collective, décision multicritère de M1 MIAGE.

Compétence à acquérir :

  • Identifier une situation décisionnelle (production, transport, localisation, tournées, etc.) et la traduire en modèle d ’ optimisation linéaire ou linéaire en variables mixtes (MIP).
  • Choisir des variables adaptées (continues, entières, binaires), notamment les variables indicatrices, et formuler les contraintes et la fonction objectif en cohérence avec le problème réel.
  • Comparer des formulations alternatives (avec ou sans relaxation, modèles symétriques / brisés, formulations étendues) et en analyser les conséquences sur la qualité du modèle et la difficulté de résolution.
  • Maîtriser les principales techniques de linéarisation (termes quadratiques, valeurs absolues, conditions logiques, contraintes disjonctives) pour obtenir un modèle MILP solvable.
  • Comprendre la notion de relaxation continue, l ’ impact des variables entières et la notion d ’ espace des solutions réalisables.
  • Appréhender la symétrie dans les modèles (affectation, bin packing, etc.) et savoir pourquoi et comment la réduire.
  • Modéliser et résoudre des problèmes standard : affectation, transport, transbordement, flots, TSP, CVRP, newsvendor, facility location, et interpréter les résultats en termes de décisions concrètes.
  • Être capable de adapter ces modèles à des variantes réalistes (capacités, coûts fixes, contraintes opérationnelles spécifiques, etc.)
  • Utiliser une librairie de modélisation (ici PuLP en Python) pour implémenter un modèle, appeler un solveur, récupérer la solution et la présenter.
  • ​ Vérifier et tester un modèle sur des jeux de données simples, analyser les messages du solveur (optimalité, faisabilité, temps de calcul) et ajuster la formulation si nécessaire.
  • Expliquer le rôle d ’ un modèle d ’ optimisation comme outil d ’ aide à la décision, et non comme substitut au décideur, dans un processus décisionnel plus large.

Bibliographie, lectures recommandées

  • Robert Faure, Bernard Lemaire, Christophe Picouleau, "Précis de Recherche Opérationnelle - 7ème édition", Dunod, 2014
  • Laurence Wolsey, Integer Programming. Wiley, 2020
  • coin-or.github.io/pulp/