Linear programming

rdf:langString Optimisation linéaire

rdf:langString 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 x1 + 2x2 ≥ 2 et les contraintes de positivité des xi est un problème d'optimisation linéaire. Sa solution est (x1 , x2) = (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 x1,...,xn à 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)i ≤ 0. L'ensemble 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. Typiquement, un algorithme de points intérieurs requerra théoriquement au plus de l'ordre de O(√n) itérations pour une formulation du problème voisine de celle donnée ci-dessus. Beaucoup de problèmes de recherche opérationnelle peuvent être exprimés comme des problèmes d'optimisation linéaire. Ces problèmes apparaissent aussi comme sous-produits dans des algorithmes conçus pour résoudre des problèmes plus difficiles. Dans certains problèmes d'OL, on requiert en plus que les variables ne prennent que des valeurs entières (contraintes dites d'intégrité), voire que les valeurs 0 ou 1. On parle alors de problème d'optimisation linéaire en nombres entiers. Ces derniers problèmes sont beaucoup plus difficiles à résoudre que les problèmes d'OL à variables continues décrits ci-dessus.