Présentation
En anglaisRÉSUMÉ
Cet article présente les méthodes et techniques les plus usitées pour résoudre les problèmes d’optimisation discrète, à savoir la complexité des algorithmes contenant des variables discrètes. Pour cela, il aborde la modélisation de quatre problèmes concrets à l’aide d’équations linéaires ou éventuellement quadratiques. Sont ainsi détaillées les méthodes de résolution exacte, les méthodes exponentielles appelées procédures par séparation et évaluation, ou celles de résolution approchée, comme les méta-heuristiques.
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleABSTRACT
Auteur(s)
-
Marie-Claude PORTMANN : Docteur ès sciences mathématiques, Université Nancy 1 - Professeur à l’École Nationale Supérieure des Mines de Nancy, INPL
-
Ammar OULAMARA : Docteur en informatique de l’Université Joseph Fourier, Grenoble - Maître de Conférences à l’École Nationale Supérieure des Mines de Nancy, INPL
INTRODUCTION
Résoudre un problème d’optimisation, c’est rechercher, parmi un ensemble de solutions qui vérifient des contraintes données, la ou les solutions qui rendent minimale (ou maximale) une fonction mesurant la qualité de cette solution. Cette fonction est appelée fonction-objectif. En général, pour modéliser un problème d’optimisation, on commence par définir les éléments qui composent les contraintes et la fonction objectif. Parmi ces éléments, certains sont connus et sont appelés paramètres du problème. On lit leur valeur dans des bases de données ou on les fournit dans des fichiers ou encore en les tapant au clavier d’un ordinateur. D’autres éléments sont inconnus et sont appelés inconnues ou variables. Les contraintes et la fonction objectif s’expriment à l’aide de formules mathématiques qui combinent les paramètres connus et les variables du problème. Les variables correspondent souvent à des décisions à prendre de manière à obtenir l’optimum souhaité. On parle d’optimisation continue (cf. [Optimisation continue], si les variables représentant les décisions prennent leur valeur sur un ensemble continu de valeurs : par exemple, tous les réels contenus entre deux limites. On parle d’optimisation discrète si les variables prennent leur valeur dans un ensemble fini ou dans un ensemble dénombrable, comme par exemple l’ensemble des entiers. Dans le cas le plus général, une partie des variables sont continues et une autre partie des variables sont discrètes. C’est la difficulté des problèmes contenant des variables discrètes qui nous intéressent ici.
Nous présentons ici quatre problèmes concrets et nous les modélisons en utilisant des équations linéaires ou éventuellement quadratiques. Nous introduisons ensuite les notions de complexité d’algorithmes et de problèmes. La suite du dossier est composée de deux grandes parties.
Une partie est consacrée à la présentation de méthodes de résolution exacte, certaines sont polynomiales, spécifiques du problème « facile » considéré et donc utilisables même pour des problèmes de grandes tailles ; d’autres sont pseudo-polynomiales et encore utilisables pour des problèmes de tailles importantes ; enfin, des méthodes exponentielles, construites sur des schémas généraux, appelés procédures par séparation et évaluation ne peuvent être utilisées que sur des problèmes de taille relativement restreinte. Ce sont des méthodes exponentielles de ce type qui sont utilisées dans les solveurs généraux, à base de programmation linéaire ou de propagation de contraintes, qui sont actuellement disponibles sur le marché des progiciels. L’amélioration progressive de ces solveurs et l’augmentation spectaculaire de la rapidité des ordinateurs permettent de résoudre, avec ces progiciels, des problèmes de taille relativement importante. Néanmoins, la durée des exécutions augmente toujours exponentiellement avec la taille des problèmes.
Une deuxième partie est consacrée aux méthodes de résolution approchées, quand on accepte de ne plus avoir la preuve d’obtenir une solution optimale, mais que l’on espère utiliser des approches suffisamment astucieuses pour obtenir de très bonnes solutions. Nous présentons, en particulier, les méta-heuristiques les plus connues telles que le recuit simulé, la méthode Taboue et les algorithmes génétiques. Nous incitons également le lecteur à croiser les méthodes de manière à essayer d’obtenir les meilleurs résultats.
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Automatique et ingénierie système
(138 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
1. Exemples de problèmes d’optimisation discrète
Les exemples concrets sur lesquels vont s’appuyer l’ensemble du dossier sont les suivants :
-
un problème d’affectation de personnel ;
-
un problème d’agencement de bureaux ;
-
un problème de choix d’investissements ;
-
des problèmes d’ordonnancement à une machine.
Dans ce paragraphe, nous décrivons l’application concrète correspondante et proposons une modélisation pour chacun d’entre eux.
1.1 Problème d’affectation de personnel
-
Description du problème
Dans un atelier de conditionnement où toutes les tâches sont des tâches manuelles, m tâches de la durée d’un poste (7 h) ont été constituées par le gestionnaire d’atelier la veille au soir. En début de poste, les employés pointent et certains d’entre eux sont absents pour différentes raisons dont certaines sont non prévisibles (maladie, enfant malade...). Lorsque tous les employés ont pointé, on connaît leur nombre exact n et on les désigne par un indice j variant de 1 à n . En fonction de sa qualification, l’employé désigné par l’indice j peut faire ou non la tâche désignée par l’indice i . On note A i, j une valeur entière connue qui vaut 1 si l’employé j peut faire la tâche i et 0 dans le cas contraire. Les tâches non exécutées sont reportées au poste suivant et si on n’arrive pas à occuper un employé parce que sa qualification ne lui permet pas de faire une des tâches non exécutées, alors on l’occupe à des tâches non rentables (nettoyage, par exemple). L’intérêt de l’entreprise est d’exécuter un maximum de tâches pendant le poste.
-
Modélisation du problème
Nous modélisons le problème sous forme de programmation linéaire en variables entières de type 0-1, en utilisant l’inconnue entière xi, j qui vaut 1 si l’employé j exécute la tâche i et 0 dans le cas contraire.
La première famille de contraintes exprime le fait que tout employé j ne peut pas exécuter plus d’une tâche :
Cet article fait partie de l’offre
Automatique et ingénierie système
(138 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
Exemples de problèmes d’optimisation discrète
BIBLIOGRAPHIE
-
(1) - * - Dash Optimization. http://www.dashoptimization.com
-
(2) - FAURE (R.), LEMAIRE (B.), PICOULEAU (C.) - Précis de recherche opérationnelle : Méthodes et exercices. - Dunod, Collection Sciences Sup Mathematiques, 520 pages (2004).
-
(3) - Groupe Gotha - Modèles et Algorithmes en Ordonnancement. - Éditions Ellipses, 240 pages (2004).
-
(4) - PIRLOT (M.), TEGHEM (J.) - Résolution de problèmes de RO par les métaheuristiques. - Hermès – Lavoisier, 256 pages (2003).
-
(5) - PIRLOT (M.), TEGHEM (J.) - Optimisation approchée en recherche opérationnelle : recherches locales, réseaux neuronaux et satisfaction de contraintes. - Hermès – Lavoisier, 238 pages (2002).
-
(6) - * - ROADEF. Société française...
Cet article fait partie de l’offre
Automatique et ingénierie système
(138 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