Programmation linéaire
La programmation linéaire est une branche de la programmation mathématique et une méthode largement utilisée en recherche opérationnelle, consacrée au développement de la théorie et des méthodes pour résoudre des problèmes de recherche d'un extrémum (maximum ou minimum) d'une fonction linéaire soumise à des contraintes linéaires.
La programmation linéaire (PL) est l'un des outils les plus puissants et les plus fréquemment utilisés pour résoudre des problèmes d'optimisation dans les domaines de l'économie, de la gestion, de la planification, de la logistique et autres.
Objet et finalité
L'objectif principal de la programmation linéaire est de trouver la meilleure manière (optimale) d'allouer des ressources limitées pour atteindre un certain objectif, lorsque l'objectif et les contraintes sur l'utilisation des ressources peuvent être exprimés par des relations linéaires.
- La programmation linéaire permet de résoudre des problèmes pratiques tels que :
- La planification optimale de la production.
- L'optimisation des flux de transport (problème de transport).
- L'allocation optimale des investissements.
- La découpe optimale de matériaux. Le problème d'affectation.
Formulation mathématique du problème de PL
Un problème standard de programmation linéaire se formule de la manière suivante :
Il s'agit de trouver les valeurs des variables de décision qui maximisent ou minimisent une fonction objectif linéaire. Ces variables de décision sont soumises à des contraintes sous la forme d'un système d'égalités et/ou d'inégalités linéaires. En règle générale, une condition de non-négativité est ajoutée pour les variables de décision (leurs valeurs doivent être supérieures ou égales à zéro), ce qui est souvent dicté par le sens physique ou économique du problème.
Mathématiquement, cela implique de travailler avec des fonctions linéaires et des systèmes d'équations/inéquations linéaires.
Concepts fondamentaux de la PL
- Variables de décision (ou variables contrôlées) : Grandeurs dont les valeurs doivent être déterminées lors de la résolution du problème (par exemple, les volumes de production de différents produits, la quantité de ressources allouées à différentes fins).
- Fonction objectif : Fonction linéaire des variables de décision dont la valeur doit être maximisée ou minimisée. Elle exprime quantitativement le but du problème (par exemple, le profit total, les coûts totaux).
- Contraintes : Système d'égalités et/ou d'inégalités linéaires que les variables de décision doivent satisfaire. Les contraintes reflètent les limites des ressources, les exigences technologiques, les objectifs de planification et d'autres conditions du problème.
- Région admissible (ou ensemble des solutions réalisables) : L'ensemble de toutes les combinaisons de valeurs des variables de décision qui satisfont à toutes les contraintes du problème. Géométriquement, dans un espace multidimensionnel, la région admissible est un polytope convexe (ou polyèdre), qui peut être non borné ou vide.
- Solution admissible : Toute combinaison de valeurs des variables appartenant à la région admissible.
- Solution optimale : Une solution admissible pour laquelle la fonction objectif atteint sa valeur extrémale (maximale ou minimale). Si une solution optimale existe, elle se trouve toujours à la frontière de la région admissible, et au moins dans l'un des sommets du polytope convexe de la région admissible (théorème fondamental de la programmation linéaire).
Méthodes de résolution des problèmes de PL
Il existe plusieurs méthodes principales pour résoudre les problèmes de programmation linéaire :
- Méthode graphique : Applicable aux problèmes à deux variables de décision. Elle permet de représenter visuellement la région admissible et la fonction objectif sur un plan et de trouver la solution optimale en analysant les sommets de la région admissible ou en déplaçant la ligne de niveau de la fonction objectif.
- Méthode du simplexe : Algorithme itératif universel développé par George Dantzig. La méthode se déplace séquentiellement d'un sommet de la région admissible à un sommet adjacent, en améliorant la valeur de la fonction objectif à chaque étape, jusqu'à ce que la solution optimale soit trouvée. C'est la méthode classique et la plus connue pour résoudre les problèmes de PL.
- Méthodes de points intérieurs : Une classe alternative d'algorithmes, apparue après la méthode du simplexe. Elles progressent vers la solution optimale à l'intérieur de la région admissible, plutôt que le long de ses frontières. Ces méthodes sont particulièrement efficaces pour résoudre des problèmes de PL de très grande dimension.
Dualité en programmation linéaire
À chaque problème de programmation linéaire (appelé problème primal), on peut associer un autre problème de PL, appelé problème dual. Les problèmes primal et dual sont étroitement liés :
La solution de l'un des problèmes fournit des informations sur la solution de l'autre. Les valeurs optimales des fonctions objectif des deux problèmes coïncident (si elles existent). Les variables du problème dual ont une interprétation économique importante : elles correspondent aux prix d'ombre (ou évaluations duales) des ressources, indiquant de combien la valeur optimale de la fonction objectif du problème primal changerait pour une petite variation de la contrainte sur la ressource correspondante.
Applications de la PL
La programmation linéaire trouve de nombreuses applications dans :
- L'économie et le commerce (planification de la production, logistique, finance, marketing).
- L'industrie (optimisation des processus technologiques, gestion des stocks, découpe de matériaux).
- Les transports (optimisation des itinéraires, des horaires). L'agriculture (optimisation des surfaces de culture, des rations alimentaires).
- L'énergie (optimisation de la charge des capacités de production).
Bibliographie
- Dantzig, G. Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966.
- Ioudine, D. B., Golstein, E. G. Линейное программирование (теория, методы и приложения). — М.: Наука, 1969.
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)
Voir aussi
- Recherche opérationnelle
- Optimisation
- Fonction objectif
- Contraintes
- Région admissible
- Solution optimale