Optimisation linéaire
thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes. L’optimisation linéaire (OL) est la discipline qui étudie ces problèmes. Elle est également désignée par le nom de programmation linéaire, terme introduit par George Dantzig vers 1947, mais cette appellation tend à être abandonnée à cause de la confusion possible avec la notion de programmation informatique. Par exemple, le problème à deux variables suivant qui consiste à minimiser la fonction linéaire sous la contrainte d'inégalité affine x + 2x ≥ 2 et les contraintes de positivité des x est un problème d'optimisation linéaire. Sa solution est (x , x) = (0,1). Dès que le nombre de variables et de contraintes augmente, le problème ne peut plus se résoudre par tâtonnement. Plus généralement, un problème d'OL s'écrira donc en notation matricielle de la manière suivante où est l'inconnue, le vecteur des variables réelles x,...,x à optimiser, et les données sont des vecteurs et et une matrice . L'inégalité vectorielle Ax ≤ b doit être entendue composante par composante : pour tout indice i, on doit avoir (Ax – b) ≤ 0. Lensemble admissible est donc bien un polyèdre convexe, puisqu'il s'agit de l'intersection des demi-espaces , pour i = 1,...,m, en nombre fini. Un problème de maximisation se ramène à la formulation précédente en minimisant l'opposé de la fonction-coût sur le même polyèdre convexe. Parmi les problèmes d'optimisation avec contraintes d'inégalité, les problèmes linéaires sont simples à résoudre numériquement. On connaît en effet des algorithmes polynomiaux efficaces, requérant donc un nombre d'itérations qui est majoré par un polynôme, fonction des dimensions du problème.