Bibliographie & annexes
Présentation
English
RÉSUMÉ
De nos jours, les problèmes d'optimisation continue linéaires ou convexes sont résolus assez facilement. Cependant, il n’en est pas de même d’applications industrielles imposant des contraintes d'intégrité sur tout ou partie des variables. Cet article introduit les principaux concepts et les principales méthodes algorithmiques pour la résolution de problèmes en nombres entiers en mettant l'accent sur les méthodes exactes. Tout d’abord, le sujet est illustré à travers un exemple en productique, faisant apparaître des caractéristiques distinctes des problèmes en nombres entiers par rapport à l'optimisation continue. Ensuite, l’ensemble des principaux outils théoriques et algorithmiques permettant d'aborder la résolution exacte de tels problèmes est présenté.
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleAuteur(s)
-
Michel MINOUX : Professeur à l'Université Pierre-et-Marie-Curie, Paris 6
INTRODUCTION
Les problèmes d'optimisation continue linéaires ou convexes sont résolus très efficacement. Par exemple, on résout couramment aujourd'hui des programmes linéaires continus ayant des dizaines, voire des centaines, de milliers de variables et de contraintes. Cependant, les applications industrielles imposent très fréquemment des contraintes d'intégrité sur tout ou partie des variables ; les problèmes qui en résultent sont généralement beaucoup plus difficiles que leurs versions continues. Les progrès réalisés depuis une vingtaine d'années permettent de résoudre efficacement beaucoup de ces problèmes, souvent de taille importante, mais on peut encore rencontrer aujourd'hui des problèmes comportant seulement quelques centaines de variables entières et de contraintes qui ne peuvent être résolus exactement en un temps raisonnable, disons en moins de quelques heures de calcul. Le présent dossier propose une vue d'ensemble des principaux outils théoriques et algorithmiques permettant d'aborder la résolution exacte de tels problèmes en mentionnant quelques-unes des applications les plus importantes.
L'expertise technique et scientifique de référence
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Présentation
Méthodes de programmation linéaire continue
English
2. Exemple d'application en productique
2.1 Premier modèle : problème d'optimisation continue (convexe)
On veut réaliser en temps minimal un ensemble de trois tâches T 1, T 2, T 3, les tâches T 2 et T 3 pouvant s'exécuter simultanément, mais leur exécution ne pouvant démarrer qu'à partir du moment où la tâche T 1 est terminée.
Pour chaque tâche i, la durée d'exécution qi est supposée être une fonction connue :
continue et décroissante de la quantité de ressource xi qui lui est affectée. On considère par exemple que la ressource en question est une ressource énergétique (des kilowatts) ou une ressource financière (des kiloeuros). On a alors qi ≥ fi (xi ) (durée d'exécution de la tâche i ). On suppose enfin que la quantité de ressource totale disponible est limitée, la limite étant une valeur donnée b > 0 (« budget »). Le problème d'optimisation de production (PROD) ci-avant se modélise aisément comme le problème d'optimisation sous contraintes :
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Exemple d'application en productique
BIBLIOGRAPHIE
-
(1) - BALAS (E.) - An Additive Algorithm for Solving Linear Programs with Zero-one Variables. - Operations Research, 13, 4, p. 517-546 (1965).
-
(2) - BALAS (E.) - Disjunctive Programming. - Annals of Discrete Mathematics, 5, p. 3-51 (1979).
-
(3) - BALAS (E.), CERIA (S.), CORNUEJOLS (G.) - Mixed 0-1 Programming by Lift & Project in a Branch-and-Cut Framework. - Management, 42, p. 1229-1246 (1996).
-
(4) - BALAS (E.), CERIA (S.), CORNUEJOLS (G.), NATRAJ (N.R.) - Gomory Cuts revisited. - Operations Research Letters, 19, p. 1-9 (1996).
-
(5) - BERTIER (P.), ROY (B.) - Une Procédure de résolution pour une classe de problèmes pouvant avoir un caractère combinatoire. - Cahiers du Centre d'Études de recherche Opérationnelle, 6, p. 202-208 (1964).
-
(6) - BLAND (R.G.) - A Combinatorial Abstraction of Linear...
ANNEXES
1.1 Logiciels de résolution de programmes linéaires continus et en nombres entiers
COIN (en libre accès) http://www.coin-or.org
CPLEX http://www.ilog.com/produits/cplex
XPRESS-MP http://www.dashoptimization.com/home/products
HAUT DE PAGE
Congrès annuel de la ROADEF (recherche opérationnelle et d'aide à la décision), France.
Congrès annuel INFORMS (Institute For Operations Research and The Management Sciences), USA.
Congrès annuel européen de recherche opérationnelle EURO.
Congrès SMAI (tous les 4 ans).
...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
