Skip to content
Retour aux résultats

Programmation Linéaire Multi-Objectif (PLMO)

Introduite par
Steuer, R. E.; Charnes, A.; Cooper, W. W.
Année
1955–1986
Type
Mathematical optimization / vector optimization
Famille
Simulation / optimization

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La Programmation Linéaire Multi-Objectif (PLMO) étend la programmation linéaire classique pour gérer plusieurs fonctions d'objectif linéaires conflictuelles simultanément sur une région réalisable définie par des contraintes linéaires.

Au lieu d'une solution optimale unique, la PLMO produit une frontière de Pareto-efficacité à partir de laquelle un décideur sélectionne un compromis préféré. Elle est fondamentale en recherche opérationnelle et en sciences de gestion pour les problèmes d'allocation de ressources, de planification et de conception avec des objectifs concurrents.

L’intuition derrière la méthode

Dans la programmation linéaire ordinaire, on minimise un coût ou maximise un profit, mais les décisions réelles impliquent presque toujours plusieurs objectifs concurrents : minimiser le coût tout en maximisant le niveau de service tout en minimisant les émissions. La PLMO reconnaît qu'aucune solution unique n'est la meilleure pour tous les objectifs à la fois. Elle cartographie la frontière complète des solutions non dominées (de Pareto-efficacité) où l'amélioration d'un objectif entraînerait nécessairement la détérioration d'un autre. Le décideur utilise ensuite des informations de préférence – poids, niveaux d'aspiration ou requêtes interactives – pour sélectionner une solution finale à partir de cette frontière, rendant les compromis explicites plutôt que cachés dans un score composite.

Histoire

Les fondements théoriques de la programmation linéaire multi-objectif remontent aux travaux de Charnes et Cooper dans les années 1950 sur la programmation par objectifs et de Koopmans sur la production efficace. Le manuel de Steuer en 1986 a consolidé le domaine, systématisant les méthodes de somme pondérée, d'epsilon-contrainte et interactives qui restent standard aujourd'hui. La PLMO est maintenant un sujet central dans les cursus de recherche opérationnelle dans le monde entier.

Quand l’utiliser

Utiliser la PLMO lorsque le problème comporte plusieurs objectifs linéaires concurrents et des contraintes linéaires, que les données sont continues et connues avec précision (ou peuvent être traitées comme déterministes), et que le décideur a besoin de comprendre explicitement les compromis plutôt que d'accepter un score pré-agrégé. Les contextes typiques incluent la planification de la production, l'allocation de portefeuille, le routage des transports et la budgétisation des ressources publiques. NE PAS utiliser lorsque les objectifs ou les contraintes sont non linéaires (utiliser la programmation non linéaire multi-objectif ou les métaheuristiques à la place), lorsque les données sont discrètes ou binaires (utiliser la programmation entière multi-objectif), lorsque le nombre d'objectifs dépasse cinq ou six (la frontière efficace devient calculatoirement ingérable), ou lorsque le décideur n'est pas disposé à s'engager dans une elicitation itérative des préférences.

Limites et points d’attention

  • Restreint aux fonctions d'objectif linéaires et aux contraintes linéaires ; les problèmes du monde réel sont souvent non linéaires.
  • La frontière efficace peut contenir un nombre exponentiel de points extrêmes dans des dimensions plus élevées, rendant l'énumération complète impraticable.
  • Nécessite des données numériques précises ; l'incertitude ou le flou dans les coefficients n'est pas géré nativement.
  • Les méthodes interactives dépendent fortement de la disponibilité du décideur et de sa capacité à articuler ses préférences de manière cohérente.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Produit la frontière complète de Pareto-efficacité, offrant aux décideurs une image complète des compromis.
  • Calculatoirement traitable pour des tailles de problèmes modérées via des solveurs basés sur le simplexe.
  • Garantit l'optimalité mathématique de chaque point sur la frontière efficace.
  • Bien supporté par des logiciels matures (CPLEX, Gurobi, alternatives open-source).
  • Les compromis sont rendus explicites plutôt que réduits à un indice composite opaque.

Applications

  • Planification de la production équilibrant coût, débit et utilisation des ressources.
  • Optimisation de portefeuille négociant le rendement, le risque et la liquidité.
  • Conception de réseaux de transport et de logistique avec des objectifs concurrents de coût et de service.
  • Planification de systèmes énergétiques minimisant le coût tout en respectant les objectifs d'émissions et de fiabilité.
  • Allocation des ressources de santé équilibrant équité, efficacité et contraintes budgétaires.
  • Gestion environnementale optimisant simultanément les performances économiques et écologiques.

Comment ça marche

Comment ça marche

1

Formuler k fonctions d'objectif linéaires f1(x) à fk(x) et une région réalisable X définie par des contraintes d'inégalité et d'égalité linéaires (Ax <= b, x >= 0). Identifier quels objectifs doivent être minimisés et lesquels maximisés. Confirmer que toutes les fonctions d'objectif et contraintes sont linéaires par rapport aux variables de décision.

Formule
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0
2

Générer l'ensemble des solutions de Pareto-efficacité (non dominées). Les approches courantes incluent la méthode de la somme pondérée (variations des poids sur le simplexe), la méthode de l'epsilon-contrainte (optimiser un objectif tout en bornant les autres) et la méthode de Chebyshev. Chaque approche trace une partie ou la totalité de la frontière efficace.

3

Appliquer une technique de scalarisation pour convertir le problème vectoriel en une séquence de PL à objectif unique. Dans l'approche de la somme pondérée, résoudre min somme(wi * fi(x)) pour des vecteurs de poids systématiquement variés. Enregistrer chaque point extrême efficace de l'espace des objectifs.

Formule
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1
4

Collecter les points extrêmes efficaces et les arêtes qui les relient pour caractériser la frontière de Pareto. Analyser la plage de chaque objectif sur la frontière pour comprendre l'ampleur des compromis. Présenter la frontière au décideur via des tableaux ou des graphiques bi-objectifs.

5

Engager le décideur pour sélectionner une solution préférée parmi l'ensemble efficace. Les méthodes interactives (STEM, NIMBUS) alternent entre la présentation de solutions et la demande au décideur d'exprimer sa préférence, convergeant vers un choix final qui reflète le mieux ses priorités.

Pièges courants

  • L'utilisation de poids fixes dans la scalarisation par somme pondérée et la présentation d'une seule solution obscurcissent la frontière et vont à l'encontre de l'objectif de la PLMO.
  • Confondre l'efficacité de Pareto avec l'optimalité : chaque point de la frontière est efficace, mais aucun n'est globalement « le meilleur » sans informations de préférence.
  • Négliger de vérifier si la région réalisable est bornée ; un problème non borné ne produit pas d'ensemble efficace fini.
  • Traiter la PLMO comme une boîte noire sans impliquer le décideur dans la sélection conduit à des choix finaux arbitraires.
  • Appliquer la PLMO à des problèmes intrinsèquement entiers sans passer à la programmation entière multi-objectif, produisant des solutions qui violent l'intégralité.

Questions fréquentes

En quoi la PLMO diffère-t-elle de la programmation par objectifs ?

La programmation par objectifs est un cas particulier ou une variante : elle convertit chaque objectif en un niveau d'aspiration, puis minimise les écarts par rapport à ces cibles, produisant une solution unique. La PLMO dans sa forme générale cherche à caractériser la frontière efficace complète sans spécifier au préalable les niveaux cibles, offrant plus de flexibilité au décideur.

La PLMO peut-elle gérer plus de deux objectifs ?

Oui, mais la frontière de Pareto devient plus difficile à visualiser au-delà de deux ou trois objectifs et le nombre de points extrêmes efficaces peut croître exponentiellement. Les méthodes interactives et les techniques de sous-ensembles représentatifs sont recommandées pour quatre objectifs ou plus.

Et si mes données sont incertaines ?

La PLMO standard suppose des coefficients déterministes. L'incertitude peut être traitée en étendant à la programmation linéaire stochastique multi-objectif (contraintes de chance, approches basées sur des scénarios) ou à l'optimisation robuste multi-objectif, qui sont des méthodes distinctes.

La PLMO est-elle identique à l'optimisation multi-objectif ?

La PLMO est un cas particulier d'optimisation multi-objectif où tous les objectifs et contraintes sont linéaires. L'optimisation multi-objectif est le domaine plus large qui inclut également les variantes non linéaires, entières et combinatoires.

Quelle méthode de scalarisation dois-je utiliser ?

La méthode de la somme pondérée est simple mais manque les parties non convexes de la frontière. La méthode de l'epsilon-contrainte peut récupérer la frontière complète même pour des régions non convexes et est généralement préférée pour une analyse approfondie. Les méthodes interactives sont les meilleures lorsque l'engagement du décideur est possible.

Méthodes associées

Sources

  1. Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.

    ISBN : 9780471888468
    Copié.
  2. Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.

    Ouvrir la référence de la publication
    Copié.