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éairesOn devrait dire affines., d'où le nom donné à ces problèmes. Loptimisation 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 et les contraintes de positivité des , est un problème d'optimisation linéaire. Sa solution est . 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 à optimiser, et les données sont des vecteurs et et une matrice . L'inégalité vectorielle doit être entendue composante par composante : pour tout indice , on doit avoir . Lensemble admissible est donc bien un polyèdre convexe, puisqu'il s'agit de l'intersection des demi-espaces , pour , 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 un nombre d'itérations de l'ordre de 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.

Introduction sur un exemple en dimension 2 On peut pressentir la problématique en dimension deux en observant la situation suivante : « Une firme a le projet de construire deux produits nécessitant l'utilisation de 3 machines. la machine A ne peut travailler que 150 heures par mois, la machine B, 210 heures, et la machine C, 180 heures. Le premier produit P1 nécessite 1 heure de la machine A et 1 heure de la machine B et il est vendu 300 euros à l'unité. Le second produit P2 nécessite une heure de la machine A, trois heures de la machine B et 3 heures de la machine C et il est vendu 500 euros à l'unité. La firme cherche à définir le programme de fabrication lui permettant de rendre maximal son bénéfice. »

thumb|upright=1.5|Exemple pratique d'un problème d'optimisation linéaire

Une modélisation mathématique conduit à appeler le nombre de produits P1 à fabriquer et le nombre de produits P2 ; sera le point de coordonnées . Les contraintes de fabrication s'expriment à l'aide des inégalités suivantes :

Chacune de ces contraintes définit un demi-plan auquel doit appartenir. L'intersection de ces demi-plans dessine un polygone convexe (OABCD) appelé ensemble admissible.

Sur cet ensemble admissible, on définit la fonction revenu net : que l'on cherche à rendre maximale. Les programmes de fabrication permettant de rentrer, par exemple, correspondent aux points de la droite (d40000) : . Cette droite partage le plan en deux demi-plans, un dans lequel et l'autre dans lequel . Comme il existe des points de l'ensemble admissible appartenant au deuxième demi-plan, on peut trouver des programmes de fabrication donnant un revenu supérieur. Les programmes de fabrication donnant un revenu correspondent aux points d'une droite (dS) parallèle à (d40000). Pour maximiser le revenu net, il suffit de trouver la droite (dS) parallèle à (d40000) qui contient au moins un point de l'ensemble admissible sans traverser celui-ci : une telle droite passe nécessairement par un sommet du polygone et une simple observation graphique place la droite en question au point B.

Une optimisation linéaire en dimension deux consiste en général à dessiner l'ensemble admissible (polygone convexe borné ou non) et à chercher la meilleure position d'une droite de direction fixée pour rendre maximale ou minimale une valeur donnée. Cette droite, si elle existe, passe toujours par un sommet du polygone. Dans une optimisation linéaire de dimension trois, l'ensemble admissible est un polyèdre et l'optimisation consiste à trouver la meilleure position d'un plan de direction fixée.

Le problème devient plus complexe en dimension supérieure où une résolution graphique est inenvisageable et nécessite des outils demandant une formalisation sous forme matricielle.Formalisation canonique : dans l'exemple ci-dessus, on pose

Les contraintes se résument à . La fonction revenu net est qu'il faut maximiser. La formalisation canonique s'écrit enfin

que l'on peut écrire sous la forme de l'introduction en changeant , , et en leurs opposés.

Formalisation standard Il est parfois utile de remplacer l'inégalité définissant l'ensemble admissible par une égalité. Cela peut se faire en augmentant la dimension d'étude du problème. Dans l'exemple ci-dessus, les trois inégalités se traduisent par trois égalités et trois contraintes positives sous la forme suivante : . Il suffit alors de poser

pour obtenir la formalisation . C'est sur ces formes (canonique ou standard) que se mettent en place les techniques d'optimisation en dimension . Elles supposent la connaissance de l'algèbre linéaire, des notations matricielles et des bases de l'optimisation (en particulier, du vocabulaire de cette discipline).

Analyse du problème

Définitions

Formulations du problème

On peut représenter un polyèdre convexe de différentes manières. Lorsqu'on le voit comme ci-dessus, à savoir comme une intersection d'un nombre fini de demi-espaces :

on dit que le polyèdre (ou le problème d'optimisation linéaire avec un tel polyèdre) est écrit sous forme canonique. Lorsque le polyèdre convexe est vu comme l'intersection de l'orthant positif et d'un sous-espace affine :

on dit que le polyèdre (ou le problème d'optimisation linéaire avec un tel polyèdre) est écrit sous forme standard.

En pratique, les problèmes peuvent présenter des contraintes plus variées ou plus structurées telles que des contraintes d'égalité ou des contraintes de borne inférieures et supérieures :

Les bons solveurs permettent d'utiliser de telles représentations de l'ensemble admissible. Cependant, autant de contraintes compliquent et alourdissent inutilement l'analyse des problèmes d'optimisation linéaire, si bien que celle-ci se fait en général sur une formulation simplifiée de l'ensemble admissible permettant toutefois de représenter toutes les contraintes affines imaginables. Les formulations canonique et standard possèdent cette propriété de généricité, pourvu que l'on introduise des données et des variables supplémentaires. En particulier, à partir d'un ensemble admissible écrit sous forme canonique, on peut faire correspondre un ensemble admissible écrit sous la forme standard suivante :

Explications : La variable à valeur dans tout correspond à la différence entre deux variables positives et . De plus, une variable positive de dimension (le nombre de contraintes) est introduite pour transformer l'inégalité en égalité. On retrouve l'expression de la forme standard avec comme vecteur de variables : et comme matrice des contraintes

Réciproquement un ensemble admissible écrit sous forme standard pourra se représenter sous la forme canonique suivante :

Les analyses du problème d'optimisation linéaire se font le plus souvent sur le problème dont l'ensemble admissible est représenté sous la forme standard, problème que nous écrirons comme suit :

On note

la valeur optimale de et

l'ensemble de ses solutions (qui peut être vide).

Le qualificatif linéaire donné au problème défini ci-dessus peut être trompeur. En effet, ces problèmes ne sont pas linéaires dans le sens où leurs solutions dépendraient linéairement de certaines de leurs données. Ce sont les inégalités définissant les contraintes qui introduisent de la non-linéarité. En l'absence d'inégalités, le problème devient linéaire dans ce sens, mais est alors trivial : soit il n'y a pas de solution, soit tous les points admissibles sont solutions.

Sommet

Certains algorithmes s'intéressent aux sommets du polyèdre convexe sur lequel on minimise une fonction linéaire. Dans l'algorithme du simplexe, par exemple, tous les itérés sont des sommets du polyèdre convexe qu'est l'ensemble admissible.

Un sommet d'un polyèdre convexe est une face de dimension zéro de cet ensemble, c'est-à-dire un point que l'on peut ôter du convexe sans remettre en cause sa convexité ; dit encore autrement et c'est la définition précise, c'est un point qui ne peut pas s'écrire comme la demi-somme de deux points distincts du polyèdre convexe. Donc est un sommet du polyèdre convexe si et si

Tous les polyèdres convexes n'ont pas nécessairement un sommet. Par exemple, le demi-espace n'en a pas. Cependant un polyèdre convexe écrit sous la forme standard en a toujours ; c'est une des raisons pour lesquelles l'algorithme du simplexe est défini sur un problème d'OL ayant son ensemble admissible écrit sous cette forme. De plus, il est alors aisé de les reconnaître par une technique d'algèbre linéaire.

On note la colonne de la matrice .

Existence de solution

Il y a exactement deux cas (exclusifs) dans lesquels le problème d'optimisation linéaire n'a pas de solution. Le premier est celui où les contraintes ne sont pas compatibles (par exemple et ). La valeur optimale du problème de minimisation vaut alors , par convention. Dans ce cas, on dit que le problème n'est pas réalisable. Le second se produit lorsque le problème de minimisation est réalisable mais que sa valeur optimale vaut (par exemple lorsqu'on cherche à minimiser sous la contrainte ). Dans ce cas, on dit que le problème n'est pas borné ou est non borné. Dans tous les autres cas, la valeur optimale du problème d'optimisation linéaire est finie et le problème a une solution.

Un autre résultat d'existence de solution, fondé sur le précédent et très souvent utilisé, est donné par le théorème de dualité forte dans la section Propriétés de dualité.

Comme l'ensemble des solutions de est un polyèdre convexe écrit sous forme standard, il aura un sommet s'il est non vide et ce sommet sera aussi un sommet de l'ensemble admissible de .

Ce résultat est important pour l'algorithme du simplexe, car celui-ci, générant ses itérés sur des sommets, cherche une solution-sommet (qui doit donc exister pour qu'il en trouve une !).

Conditions d'optimalité

Énoncé