Présentation

Article

1 - EXEMPLES DE PROBLÈMES D’OPTIMISATION DISCRÈTE

2 - COMPLEXITÉ DES ALGORITHMES ET DES PROBLÈMES

3 - MÉTHODES EXACTES DE RÉSOLUTION

4 - MÉTHODES APPROCHÉES DE RÉSOLUTION

5 - CONCLUSION

Article de référence | Réf : S7211 v1

Exemples de problèmes d’optimisation discrète
Optimisation discrète

Auteur(s) : Marie-Claude PORTMANN, Ammar OULAMARA

Date de publication : 10 déc. 2006

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

Version en anglais En anglais

RÉ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’article

ABSTRACT

 

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.

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-s7211


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

ABONNEZ-VOUS

Version en anglais En anglais

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 est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

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

ABONNEZ-VOUS

Lecture en cours
Exemples de problèmes d’optimisation discrète
Sommaire
Sommaire

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 est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

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

ABONNEZ-VOUS