Programmation linéaire
La programmation linéaire optimise une fonction objectif linéaire soumise à des contraintes linéaires d'égalité et d'inégalité, constituant la classe de problèmes d'optimisation la plus largement appliquée.
Definition
Un programme linéaire minimise ou maximise une fonction linéaire de variables de décision soumise à des contraintes linéaires ; sa région admissible est un polyèdre convexe, et un optimum, s'il existe, est atteint à un sommet.
Scope
Ce sujet couvre la forme standard d'un programme linéaire, la géométrie des polyèdres admissibles et de leurs sommets, la méthode du simplexe, la dualité en programmation linéaire et les conditions de complémentarité, l'analyse de sensibilité, ainsi que les méthodes de points intérieurs pour les problèmes à grande échelle.
Core questions
- Comment un problème pratique de ressources est-il formulé comme un programme linéaire ?
- Pourquoi un optimum se produit-il à un sommet du polyèdre admissible ?
- Que nous apprend le programme linéaire dual sur le primal ?
- Quels algorithmes résolvent efficacement les grands programmes linéaires ?
Key theories
- Théorème fondamental de la programmation linéaire
- Si un programme linéaire possède une solution optimale, alors un optimum est atteint à un sommet du polyèdre admissible, réduisant la recherche à un nombre fini de points candidats.
- Dualité et conditions de complémentarité
- Tout programme linéaire possède un dual dont la valeur optimale est égale à celle du primal, et les conditions de complémentarité lient les contraintes actives aux variables duales non nulles, fournissant des certificats d'optimalité et des interprétations économiques.
- Méthodes du simplexe et des points intérieurs
- La méthode du simplexe se déplace entre les sommets pour améliorer la fonction objectif, tandis que les méthodes de points intérieurs traversent l'intérieur et résolvent les programmes linéaires en un temps polynomial prouvable.
Clinical relevance
La programmation linéaire est une pierre angulaire de la recherche opérationnelle, utilisée pour la planification de la production, le transport et la logistique, l'ordonnancement, les problèmes de régime alimentaire et de mélange, ainsi que les flux de réseau, et elle sert de sous-routine dans l'optimisation en nombres entiers et non linéaire.
History
Kantorovich a introduit l'optimisation linéaire pour la planification de la production en 1939, et Dantzig a formulé le problème général et la méthode du simplexe en 1947. Von Neumann a reconnu la dualité avec la théorie des jeux, et la méthode de l'ellipsoïde de Khachiyan et la méthode des points intérieurs de Karmarkar ont ensuite établi la résolvabilité en temps polynomial.
Key figures
- George Dantzig
- Leonid Kantorovich
- John von Neumann
- Narendra Karmarkar
Related topics
Seminal works
- dantzig1963
- luenberger2008
Frequently asked questions
- Pourquoi l'optimum se situe-t-il à un sommet ?
- Une fonction objectif linéaire augmente le plus rapidement dans une direction fixe ; ainsi, sur un polyèdre convexe, sa meilleure valeur est poussée vers la frontière et finalement vers un coin. À moins que la fonction objectif ne soit constante le long d'une arête ou d'une face, l'optimum est atteint à un sommet.
- La méthode du simplexe est-elle toujours rapide ?
- En pratique, la méthode du simplexe est très efficace, mais des exemples de cas les plus défavorables peuvent la faire prendre un nombre exponentiel d'étapes. Les méthodes de points intérieurs offrent une garantie de temps polynomial, et les solveurs modernes utilisent les deux selon le problème.