Skip to content
Retour aux résultats

Méthode du Simplexe

Introduite par
George Dantzig
Année
1947
Type
algorithm
Famille
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 Méthode du Simplexe, développée par George Dantzig en 1947, est un algorithme fondamental pour résoudre les problèmes de programmation linéaire.

Elle explore systématiquement les sommets de la région réalisable pour trouver la solution optimale où la fonction objectif est maximisée ou minimisée sous des contraintes linéaires.

L’intuition derrière la méthode

La méthode fonctionne en partant d'un point d'angle (sommet) de la région réalisable définie par des contraintes linéaires, puis en se déplaçant vers des sommets adjacents qui améliorent la valeur de la fonction objectif. Elle continue jusqu'à atteindre un sommet où aucun sommet adjacent n'offre d'amélioration supplémentaire, garantissant ainsi l'optimalité. L'algorithme exploite la propriété géométrique selon laquelle les programmes linéaires ont leurs solutions optimales aux sommets du polytope de contraintes.

Histoire

George Dantzig a introduit la méthode du simplexe en 1947, révolutionnant la recherche opérationnelle et devenant l'algorithme standard pour la programmation linéaire pendant des décennies. Klee et Minty (1972) ont montré la complexité exponentielle dans le pire des cas, mais empiriquement la méthode est restée rapide. Les années 1980 ont vu le développement des méthodes de points intérieurs comme alternatives, mais la méthode du simplexe est restée dominante pour de nombreuses applications pratiques en raison de sa robustesse et de la sophistication des implémentations modernes.

Quand l’utiliser

Appliquer la méthode du simplexe lors de la résolution de problèmes de programmation linéaire avec des régions réalisables bornées et une fonction objectif linéaire. Elle est particulièrement efficace pour les problèmes comportant des centaines ou des milliers de variables et de contraintes. Éviter de l'utiliser si le problème est non linéaire ou non borné. Les méthodes de points intérieurs peuvent être préférées pour les problèmes à très grande échelle.

Limites et points d’attention

  • Complexité temporelle exponentielle dans le pire des cas (bien que rare en pratique)
  • Peut être peu performante sur des problèmes très dégénérés
  • Moins compétitive que les méthodes de points intérieurs sur des problèmes à très grande échelle
  • Nécessite que les problèmes soient sous forme standard avec une gestion explicite des contraintes

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

Points forts

  • Garantie de trouver une solution optimale en temps fini pour les programmes linéaires
  • Efficace en pratique avec une implémentation soignée et une gestion de la dégénérescence
  • Largement implémentée et supportée par des bibliothèques d'optimisation matures
  • Fondation pour la compréhension d'algorithmes d'optimisation plus avancés

Applications

  • Planification de la production : optimisation des quantités de production pour minimiser les coûts tout en satisfaisant les contraintes de demande
  • Transport et logistique : détermination des itinéraires et des quantités d'expédition optimales entre les entrepôts et les centres de distribution
  • Optimisation de portefeuille : allocation de capital entre les actifs pour maximiser les rendements sous contraintes de risque et de budget
  • Allocation des ressources : distribution de ressources limitées comme la main-d'œuvre et les matériaux pour maximiser la production organisationnelle
  • Problèmes de mélange : mélange de matières premières dans des proportions optimales pour satisfaire les spécifications de qualité et minimiser les coûts
  • Planification des effectifs : affectation des travailleurs aux quarts pour minimiser les coûts de main-d'œuvre tout en satisfaisant la demande

Comment ça marche

Comment ça marche

1

Convertir le programme linéaire en forme standard avec des variables d'écart, et identifier une solution de base réalisable initiale (généralement l'origine si elle est réalisable).

2

Effectuer des opérations de pivot sur le tableau du simplexe : sélectionner une variable entrante avec un coût réduit négatif, identifier la variable sortante par le test du ratio minimum, et mettre à jour la base.

3

Vérifier les conditions d'optimalité à l'aide des coûts réduits ; si tous les coûts réduits sont non négatifs pour une maximisation, la solution actuelle est optimale ; sinon, revenir à l'étape de pivot.

Pièges courants

  • Échec dans la gestion correcte du cyclage lors de la rencontre de bases dégénérées (utiliser la règle de Bland ou des méthodes de perturbation)
  • Sélection de pivot incorrecte ou erreurs arithmétiques dans les mises à jour du tableau entraînant une instabilité numérique
  • Ne pas vérifier l'absence de bornes ou l'inréalisabilité avant de démarrer l'algorithme

Questions fréquentes

Pourquoi la méthode du simplexe s'appelle-t-elle 'simplexe' ?

Le terme 'simplexe' fait référence à la forme la plus simple d'un polytope dans une dimension donnée. L'algorithme fonctionne en se déplaçant le long des arêtes et des sommets du polytope défini par les contraintes.

Quelle est la différence entre la méthode du simplexe et la méthode des points intérieurs ?

La méthode du simplexe reste à la frontière de la région réalisable au niveau des sommets, tandis que les méthodes de points intérieurs traversent l'intérieur. Les méthodes de points intérieurs ont une meilleure complexité dans le pire des cas, mais le simplexe est souvent plus rapide en pratique pour les problèmes de taille moyenne.

Comment gérer l'inréalisabilité ou l'absence de bornes ?

Utiliser la méthode du simplexe en deux phases : la phase un résout un problème auxiliaire pour trouver une solution de base réalisable ou déterminer l'inréalisabilité ; la phase deux applique la méthode du simplexe standard au problème d'origine.

Qu'est-ce que la dégénérescence et pourquoi est-elle importante ?

La dégénérescence se produit lorsqu'une solution de base réalisable a plus d'une représentation de base, ce qui peut provoquer un cyclage. La gérer en utilisant la règle de Bland (choisir les variables par ordre d'indice) ou des méthodes de perturbation.

Méthodes associées

Sources

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.

    Ouvrir la référence DOI
    Copié.
  2. Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.

    Ouvrir la référence DOI
    Copié.