Programmation linéaire — Optimisation d'objectifs linéaires sous contraintes linéaires
- Introduite par
- George B. Dantzig
- Année
- 1947
- Type
- Mathematical programming / continuous optimization
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
La programmation linéaire (PL), dont George B. Dantzig fut le pionnier en 1947, est une méthode mathématique permettant de trouver la meilleure valeur d'une fonction objectif linéaire — comme un coût minimal ou un profit maximal — sous réserve d'un ensemble de contraintes d'inégalité et d'égalité linéaires.
C'est la technique fondamentale en recherche opérationnelle et elle sous-tend la planification de la production, l'allocation des ressources, la logistique, les problèmes de régime alimentaire, et d'innombrables autres scénarios de prise de décision dans l'ingénierie, l'économie et les sciences naturelles.
L’intuition derrière la méthode
Imaginez que vous dirigez une petite usine produisant deux articles. Chaque article vous rapporte un certain profit, mais sa fabrication consomme des matières premières et du temps machine limités. La programmation linéaire trouve le mélange exact de produits qui maximise le profit à partir de vos ressources fixes — sans violer aucune limite physique ou contractuelle. Le terme « linéaire » signifie que le profit et la consommation de ressources évoluent selon une relation de proportionnalité directe avec les quantités que vous produisez. Les choix réalisables forment un polygone (en deux dimensions) ou un polyèdre (en dimensions supérieures), et la réponse optimale se trouve toujours à l'un de ses sommets.
Histoire
Le développement systématique de la programmation linéaire a commencé en 1947 lorsque George B. Dantzig, travaillant pour l'US Air Force, a inventé l'algorithme du Simplexe pour automatiser la planification logistique militaire. Dantzig a publié la théorie fondamentale dans sa monographie de 1963, qui reste la référence canonique. Des travaux indépendants et parallèles de Leonid Kantorovich en Union soviétique (1939) ont abordé la planification de la production en utilisant des idées mathématiques similaires, et Kantorovich a reçu le prix Nobel d'économie en 1975 en partie pour cette contribution. La question théorique de la résolubilité en temps polynomial a été réglée par la méthode des ellipsoïdes de Khachian (1979) et plus tard par la méthode des points intérieurs de Karmarkar (1984), qui se sont avérées pratiquement rapides pour les problèmes à grande échelle. Aujourd'hui, les solveurs PL commerciaux et open-source sont intégrés dans la planification des ressources d'entreprise, la planification des horaires des compagnies aériennes et les systèmes énergétiques dans le monde entier.
Quand l’utiliser
La programmation linéaire est appropriée chaque fois que vous devez optimiser une quantité qui dépend linéairement d'un ensemble de variables de décision, et que toutes les contraintes sont également linéaires. Elle ne nécessite aucune hypothèse distributionnelle ni aucune taille d'échantillon minimale — c'est un modèle mathématique déterministe, pas un estimateur statistique. La méthode s'applique lorsque les variables de décision sont continues (les valeurs fractionnaires ont un sens) ; si les variables doivent être des nombres entiers ou binaires, la programmation en nombres entiers est nécessaire à la place. La PL est largement utilisée dans la planification de la production, la logistique de la chaîne d'approvisionnement, les problèmes de régime alimentaire et de mélange, l'optimisation de portefeuille financier, les problèmes de transport et d'affectation, et la répartition de l'énergie.
Limites et points d’attention
- Exigence de linéarité : si l'objectif ou une contrainte est non linéaire, le modèle PL est mal spécifié et la solution peut être incorrecte ou infaisable.
- Variables continues uniquement : lorsque les variables de décision doivent prendre des valeurs entières ou binaires, la relaxation PL donne une borne inférieure mais pas une solution valide ; la programmation en nombres entiers doit être utilisée.
- Déterministe : la PL ne modélise pas l'incertitude dans les paramètres ; la programmation stochastique ou l'optimisation robuste est nécessaire lorsque les données sont incertaines.
- Dégénérescence et cyclage : dans de rares cas, la méthode du Simplexe peut cycler entre des bases dégénérées sans converger, bien que des règles anti-cyclage (par exemple, la règle de Bland) résolvent ce problème.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Optimum global garanti : comme la région réalisable est un polyèdre convexe, tout optimum local est aussi un optimum global, sans risque d'être piégé dans une solution sous-optimale.
- Haute scalabilité : les solveurs modernes (HiGHS, Gurobi, CPLEX) traitent des modèles avec des millions de variables et de contraintes en quelques secondes.
- Richesse des informations post-solution : les prix fictifs et les plages de sensibilité fournissent des informations exploitables sur la valeur des ressources et la robustesse de la solution sans exécutions supplémentaires.
- Aucune hypothèse distributionnelle : la PL est un modèle purement algébrique, elle ne requiert donc ni normalité ni aucune propriété statistique des données.
Applications
- Planification de la production : trouver le mélange de produits optimal qui maximise le profit tout en respectant la capacité des machines et les limites des matières premières.
- Logistique de la chaîne d'approvisionnement et du transport : minimiser les coûts d'expédition sur un réseau d'entrepôts et de clients.
- Problèmes de régime alimentaire et de mélange : sélectionner les quantités d'ingrédients qui répondent aux exigences nutritionnelles au coût minimum.
- Optimisation de portefeuille financier : allouer du capital entre différents actifs pour maximiser le rendement attendu sous contraintes de risque et réglementaires.
- Répartition de l'énergie et planification du réseau électrique : minimiser le coût du combustible tout en satisfaisant la demande d'électricité et les limites de capacité des générateurs.
- Planification du personnel et de la main-d'œuvre : affecter les équipes aux travailleurs pour couvrir la demande au coût de main-d'œuvre minimum.
Comment ça marche
Comment ça marche
Le problème de décision du monde réel est traduit en symboles mathématiques. Vous identifiez les variables de décision (les quantités que vous pouvez contrôler), écrivez la fonction objectif (ce que vous voulez maximiser ou minimiser) comme une combinaison linéaire de ces variables, et écrivez chaque contrainte — limites de ressources, capacités maximales, exigences de demande — comme une inégalité ou une égalité linéaire. Une PL bien formulée a un objectif clair, des bornes de variables explicites, et chaque contrainte structurelle exprimée linéairement.
Le modèle est mis sous une forme canonique ou standard que le solveur peut traiter. Les inégalités sont converties en égalités en introduisant des variables d'écart (slack) ou de surplus non négatives, et toute variable sans restriction est remplacée par la différence de deux variables non négatives. Cette étape mécanique produit le tableau ou la représentation matricielle sur laquelle l'algorithme opère, et elle ne modifie pas le problème — elle le remodèle seulement pour le calcul.
Un solveur recherche le polyèdre réalisable pour le sommet optimal. La méthode du Simplexe classique pivote de sommet en sommet le long des arêtes du polyèdre, améliorant (ou maintenant) toujours l'objectif, jusqu'à ce qu'aucun voisin n'offre d'amélioration. Les méthodes de points intérieurs (barrière) voyagent plutôt à travers l'intérieur de la région réalisable le long d'un chemin central, ce qui est particulièrement efficace pour les très grands modèles. Les deux familles sont garanties de trouver un optimum global lorsqu'il en existe un, car la région réalisable est convexe.
Le solveur renvoie les valeurs optimales des variables de décision et la valeur objectif optimale, ainsi que les variables duales (prix fictifs) et les plages de sensibilité. Les prix fictifs quantifient dans quelle mesure l'objectif s'améliorerait si une contrainte contraignante était relâchée d'une unité — indiquant directement à un décideur où des ressources supplémentaires seraient les plus précieuses. L'analyse de sensibilité identifie dans quelle mesure un coefficient de coût ou une valeur du côté droit peut changer avant que la base actuelle ne cesse d'être optimale.
Pièges courants
- Appliquer la PL lorsque les contraintes ou l'objectif sont non linéaires — la solution sera erronée ou le solveur rejettera le modèle.
- Ignorer les exigences d'intégralité : arrondir une solution PL continue à des entiers ne donne généralement pas une solution entière réalisable ou optimale ; utiliser la programmation en nombres entiers à la place.
- Modèles infaisables ou non bornés : si la région réalisable est vide (contraintes conflictuelles) ou si l'objectif n'est pas borné (contraintes de bornes manquantes), le solveur signalera un échec — toujours vérifier la structure du modèle avant l'exécution.
- Traiter la sortie de la PL comme une recommandation sans analyse de sensibilité : une solution techniquement optimale peut se trouver sur une crête si fine qu'un petit changement dans les données inverse la recommandation — les plages de sensibilité doivent toujours être inspectées.
Questions fréquentes
Qu'est-ce qui rend un problème « linéaire » aux fins de la PL ?
La fonction objectif et chaque contrainte doivent être linéaires — ce qui signifie que chaque terme est une constante multipliée par une seule variable de décision, sans produits de variables, sans exposants et sans fonctions non linéaires. Si ne serait-ce qu'une contrainte ou l'objectif implique, par exemple, x fois y ou x au carré, la PL standard ne s'applique plus et un solveur de programmation non linéaire ou quadratique est nécessaire.
Pourquoi la solution optimale se trouve-t-elle toujours à un sommet de la région réalisable ?
La région réalisable définie par des contraintes linéaires est un polyèdre (ou polytope) convexe. Une fonction objectif linéaire est elle-même linéaire, elle ne peut donc pas être « tirée » vers l'intérieur d'un ensemble convexe — elle atteint toujours sa valeur extrême sur la frontière, et spécifiquement à un sommet (point d'angle). C'est l'intuition géométrique qui sous-tend la stratégie de sommet en sommet de la méthode du Simplexe.
Quand dois-je utiliser la programmation en nombres entiers à la place de la PL ?
Chaque fois qu'une ou plusieurs variables de décision doivent prendre des valeurs entières ou binaires (0/1) — par exemple, s'il faut ouvrir une installation (oui/non), combien de camions expédier (nombres entiers), ou quels articles inclure dans une sélection. Simplement résoudre la PL et arrondir la solution continue n'est pas fiable : les solutions arrondies peuvent être infaisables ou loin de l'optimum. La programmation en nombres entiers gère correctement l'intégralité, moyennant un coût de calcul plus élevé.
Que me disent les prix fictifs ?
Un prix fictif (variable duale) pour une contrainte contraignante indique dans quelle mesure la valeur objectif optimale s'améliorerait si le côté droit de cette contrainte était relâché d'une unité, toutes choses égales par ailleurs. Par exemple, un prix fictif de 3 sur une contrainte d'heures de travail signifie qu'ajouter une heure de travail supplémentaire améliorerait l'objectif de 3 unités. Les contraintes qui ne sont pas contraignantes ont un prix fictif de zéro — elles ne limitent pas l'optimum actuel.
Méthodes associées
Sources
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ISBN : 9780691059136Copié.Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
Ouvrir la référence DOICopié.