La programmation linéaire

La programmation linéaire est un domaine central de l'optimisation, car les problèmes de PL sont les problèmes d'optimisation les plus faciles - toutes les contraintes y étant linéaires. Beaucoup de problèmes réels de recherche opérationnelle peuvent être exprimés comme un problème de PL. Pour cette raison un grand nombre d'algorithmes pour la résolution d'autres problèmes d'optimisation sont fondés sur la résolution de problèmes linéaires.

Le terme programmation linéaire suppose que les solutions à trouver doivent être représentées en variables réelles. S'il est nécessaire d'utiliser des variables discrètes dans la modélisation du problème, on parle alors de programmation linéaire en nombres entiers (PLNE). Il est important de savoir que ces derniers sont nettement plus difficiles à résoudre que les PL à variables continues.

En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d'optimisation où la fonction objective et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont également vrais si l'objectif est une fonction monotone croissante de chaque variable considérée. La programmation linéaire désigne également la manière de résoudre les problèmes linéaires.