Optimisation linéaire

Fichier:Optimisation lineaire 2D.svg

Optimisation linéaire dans un espace à deux dimensions (x₁, x₂). La fonction-coût f_c 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<ref group="note">On devrait dire affines.</ref>, 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<ref name =dantzig/>, mais cette appellation tend à être abandonnéeModèle:Note à cause de la confusion possible avec la notion de programmation informatique.

Par exemple, le problème à deux variables <math>x=(x_1,x_2)\in\R^2</math> suivant :

<math>

\left\{\begin{array}{l} {\inf}_x\;x_1+x_2\\ x_1+2x_2\geqslant 2,\quad x_1\geqslant0,\quad x_2\geqslant0, \end{array}\right.

</math>

qui consiste à minimiser la fonction linéaire <math>x=(x_1,x_2)\in\R^2\mapsto x_1+x_2\in\R</math> sous la contrainte d'inégalité affine Modèle:Math et les contraintes de positivité des Modèle:Mvar, est un problème d'optimisation linéaire. Sa solution est Modèle:Math. 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 :

<math>

\left\{\begin{array}{l} {\inf}_x\;c^\top x\\ Ax\leqslant b, \end{array}\right.

</math>

où <math>x\in\R^n</math> est l'inconnue, le vecteur des variables réelles Modèle:Math à optimiser, et les données sont des vecteurs <math>c\in\R^n</math> et <math>b\in\R^m</math> et une matrice <math>A\in\R^{m\times n}</math>. L'inégalité vectorielle Modèle:Math doit être entendue composante par composante : pour tout indice Modèle:Mvar, on doit avoir Modèle:Math. L'ensemble admissible <math>\{x\in\R^n:Ax\leqslant b\}</math> est donc bien un polyèdre convexe, puisqu'il s'agit de l'intersection des demi-espaces <math>\{x\in\R^n:(Ax-b)_i\leqslant 0\}</math>, pour Modèle:Math, 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 Modèle:Math 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. »

Fichier:OptimisationLineaire.svg

Exemple pratique d'un problème d'optimisation linéaire

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

<math>

\left\{\begin{array}{ll} x+y \leqslant 150 \, &\text{(contraintes de fabrication de la machine A)}\\ x+3y \leqslant 210 \, &\text{(contraintes de fabrication de la machine B)}\\ 3y \leqslant 180 \, &\text{(contraintes de fabrication de la machine C)}\\ x \geqslant 0, \, y \geqslant 0 \, &\text{(contraintes logiques)}\\ \end{array}\right.

</math>

Chacune de ces contraintes définit un demi-plan auquel Modèle:Mvar 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 : Modèle:Math que l'on cherche à rendre maximale. Les programmes de fabrication permettant de rentrer, par exemple, Modèle:Unité, correspondent aux points de la droite (d₄₀₀₀₀) : Modèle:Math. Cette droite partage le plan en deux demi-plans, un dans lequel Modèle:Math et l'autre dans lequel Modèle:Math. 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 Modèle:Mvar correspondent aux points d'une droite (d_S) parallèle à (d₄₀₀₀₀) . Pour maximiser le revenu net, il suffit de trouver la droite (d_S) parallèle à (d₄₀₀₀₀) 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 Modèle:Retrait Les contraintes se résument à Modèle:Math. La fonction revenu net est <math>g: g(u)=c^{\top}u</math> qu'il faut maximiser. La formalisation canonique s'écrit enfin

<math>

\left\{\begin{array}{l} {\sup}_u\;c^\top u\\ Au\leqslant b\\

u\geqslant 0

\end{array}\right.

</math>

que l'on peut écrire sous la forme de l'introduction en changeant Modèle:Mvar, Modèle:Mvar, et Modèle:Mvar 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

<math>

\left\{\begin{array}{l} x+y +r =150, \quad r \geqslant 0\\ x+3y +s =210, \quad s \geqslant 0\\ 3y +t =180, \quad t \geqslant 0\\ \end{array}\right.

</math>

Il suffit alors de poser Modèle:Retrait pour obtenir la formalisation

<math>

\left\{\begin{array}{l} {\sup}_v\;c_1^\top v\\ Bv=b, \\v\geqslant 0 \end{array}\right.

</math>

C'est sur ces formes (canonique ou standard) que se mettent en place les techniques d'optimisation en dimension Modèle:Mvar. 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 :

<math> \{x\in\R^n:Ax\leqslant b\}, </math>

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 :

<math> \{x\in\R^n:Ax=b,~x\geqslant 0\}, </math>

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 :

<math> A_Ex= b,\qquad l_I\leqslant A_Ix\leqslant u_I,\qquad l_B\leqslant x\leqslant u_B. </math>

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, un ensemble admissible écrit sous forme canonique pourra se représenter sous la forme standard suivante :

<math> Au-Av+s=b,\qquad u\geqslant 0,\qquad v\geqslant 0,\qquad s\geqslant 0, </math>

le lien entre la variable Modèle:Mvar de la forme canonique et les variables Modèle:Math de la formulation standard ci-dessus se faisant par Modèle:Math. Réciproquement un ensemble admissible écrit sous forme standard pourra se représenter sous la forme canonique suivante :

<math> \begin{pmatrix}A\\-A\\-I\end{pmatrix}x\leqslant \begin{pmatrix}b\\-b\\0\end{pmatrix}. </math>

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 : Modèle:Ancre Modèle:Bloc emphase On note

<math> \operatorname{val}(P_L)=\inf_{Ax=b\atop x\geqslant 0}\;c^{\top\!}x </math>

la valeur optimale de Modèle:Math et

<math> \mathcal{S}_P\equiv\mathcal{S}(P_L):=\{x\in\R^n:Ax=b,~x\geqslant 0,~c^{\top\!}x=\operatorname{val}(P_L)\} </math>

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

Le qualificatif linéaire donné au problème Modèle:Math 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 Modèle:Mvar est un sommet du polyèdre convexe Modèle:Mvar si Modèle:Math et si

<math> y,z\in P,\quad x=\frac{y+z}{2} \qquad\Longrightarrow\qquad x=y=z. </math>

Tous les polyèdres convexes n'ont pas nécessairement un sommet. Par exemple, le demi-espace <math>\{x\in\R^2:x_1\leqslant 0\}</math> 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 Modèle:Mvar la colonne Modèle:Mvar de la matrice Modèle:Mvar.

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 Modèle:Math et Modèle:Math). La valeur optimale du problème de minimisation vaut alors Modèle:Math, 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 Modèle:Math (par exemple lorsqu'on cherche à minimiser Modèle:Mvar sous la contrainte Modèle:Math). 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 Modèle:Math 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 Modèle:Math.

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é

Les conditions d'optimalité du problème d'optimisation linéaire Modèle:Math peuvent être obtenues comme cas particulier de la théorie générale des problèmes d'optimisation différentiables en dimension finie (conditions de Karush, Kuhn et Tucker), avec la simplification supplémentaire de ne pas avoir à s'occuper de la qualification des contraintes du problème. L'affinité de celles-ci les rend en effet qualifiées (voir la section Affinité locale (QC-A)), si bien que l'on ne trouve pas de trace de ces questions dans les manuels d'optimisation linéaire. Par ailleurs, grâce à la convexité du problème d'OL, les conditions énoncées ci-dessous sont nécessaires et suffisantes à l'optimalité.

Les variables Modèle:Mvar et Modèle:Mvar introduites par ces conditions d'optimalité portent le nom de multiplicateurs de Lagrange ou de variables duales. Les premières sont associées aux contraintes d'égalité (il y en a une par contrainte) et les secondes aux contraintes de positivité de la variable primale Modèle:Mvar. Comme on aura l'occasion de le voir ci-dessous, ces variables cachées dans le problème Modèle:Math jouent un rôle important dans son analyse. On note <math>\mathcal{S}_{PD}</math> l'ensemble des solutions primales-duales, c'est-à-dire l'ensemble des triplets Modèle:Math vérifiant les conditions d'optimalité ci-dessus.

Les relations Modèle:Math expriment l'admissibilité duale et la première de ces relations est le gradient en Modèle:Mvar du lagrangien du problème, qui est la fonction

<math> \ell:(x,y,s)\in\R^n\times\R^m\times\R^n\mapsto\ell(x,y,s)=c^{\top\!}x-y^{\top\!}(Ax-b)-s^{\top\!}x. </math>

Les relations Modèle:Math expriment l'admissibilité primale et la relation Modèle:Math exprime la complémentarité existant entre les variables primales Modèle:Mvar et leurs multiplicateurs Modèle:Mvar : Modèle:Mvar ou Modèle:Mvar est nul (ou les deux) ; voir aussi plus loin.

Chaque variable optimale duale s'interprète comme le coût marginal associé à sa contrainte.

Après élimination de la variable d'écart duale Modèle:Mvar, les conditions d'optimalité peuvent s'écrire sous la forme de problème de complémentarité linéaire avec contrainte linéaire :

<math>

\left\{\begin{array}{l} Ax = b \\ 0\leqslant x \perp (c-A^{\top\!} y)\geqslant 0. \end{array}\right.

</math>

Ces conditions d'optimalité ont de multiples usages. Elles permettent en particulier de concevoir des algorithmes primaux-duaux (qualifiés ainsi parce qu'ils utilisent alors les variables primales et duales) de résolution. Elles permettent aussi d'établir diverses propriétés des problèmes d'OL.

Solution strictement complémentaire

Revenons sur les conditions de complémentarité, la condition Modèle:Math du système d'optimalité. Cette condition s'écrit

<math> \sum_{i=1}^n\,x_is_i=0. </math>

Comme Modèle:Mvar et Modèle:Mvar ont leurs composantes positives, cela revient au même d'écrire

<math> \forall\,i\in\{1,\ldots,n\} :\quad x_is_i=0 </math>

ou encore

<math> \forall\,i\in\{1,\ldots,n\} :\qquad x_i>0\quad\Longrightarrow\quad s_i=0. </math>

Ceci n'implique pas que Modèle:Math lorsque Modèle:Math.

Une solution primale-duale Modèle:Math est dite strictement complémentaire, si

<math> \forall\,i\in\{1,\ldots,n\} :\qquad x_i>0\quad\Longleftrightarrow\quad s_i=0. </math>

Un problème d'optimisation linéaire avec solution a toujours une solution primale-duale strictement complémentaire. On note

<math> \begin{array}{rcl} [\![1,n]\!] &:=& \{1,\ldots,n\} \\ B &:=& \{i\in[\![1,n]\!]:\exists\,x\in\mathcal{S}_P~\mbox{tel que}~x_i>0\} \\ N &:=& \{i\in[\![1,n]\!]:\exists\,(y,s)\in\mathcal{S}_D~\mbox{tel que}~s_i>0\}. \end{array} </math>

Dualité lagrangienne

Le problème dual standard

La dualisation lagrangienne est une technique utilisée pour introduire un problème dual d'un problème d'optimisation. Si l'on considère le problème d'optimisation Modèle:Math, la dualisation lagrangienne conduit au problème dual standard suivant Modèle:Ancre Modèle:Bloc emphase Il s'agit de deux problèmes de maximisation ; celui de droite est obtenu à partir de celui de gauche en éliminant la variable <math>s\in\R^n</math>, si bien qu'il ne lui reste que la variable <math>y\in\R^m</math>.

On note

<math> \operatorname{val}(D_L)=\sup_{A^{\top\!}y\leqslant c}\;b^{\top\!}y </math>

la valeur optimale de Modèle:Math et

<math> \mathcal{S}_D\equiv\mathcal{S}(D_L):=\{y\in\R^y:A^{\top\!}y\leqslant c,~b^{\top\!}y=\operatorname{val}(D_L)\} </math>

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

Technique de dualisation

On pourrait énoncer le problème dual du problème d'optimisation linéaire le plus général, mais nous préférons donner ici la technique utilisée pour les établir, ce qui permettra de s'en sortir dans tous les cas. On part du problème Modèle:Math, qualifié ici de primal.

La première étape consiste à écrire le problème primal comme un Modèle:Math. Par exemple, comme à <math>x\in\R^n</math> fixé

<math> \sup_{y\in\R^m}\;\left[c^{\top\!}x-y^{\top\!}(Ax-b)\right]= \left\{\begin{array}{ll} c^{\top\!}x & \mbox{si}~Ax=b\\ +\infty & \mbox{sinon}, \end{array}\right. </math>

on a

<math> \inf_{x\geqslant 0}\,\left(\sup_{y\in\R^m}\;\left[c^{\top\!}x-y^{\top\!}(Ax-b)\right]\right)= \inf_{x\geqslant 0\atop Ax=b}\;c^{\top\!}x. </math>

L'égalité tient compte de la convention que l'infimum sur un ensemble vide vaut Modèle:Math ; donc, s'il n'y a pas de Modèle:Math vérifiant Modèle:Math, on trouvera Modèle:Math dans les deux membres. On a ainsi écrit le problème primal comme un Modèle:Math (on enlève les parenthèses, en gardant à l'esprit que la signification à donner à cet Modèle:Math est celle ci-dessus) :

<math> (P_L)\quad\equiv\quad \inf_{x\geqslant 0}\,\sup_{y\in\R^m}\;\left[c^{\top\!}x-y^{\top\!}(Ax-b)\right]. </math>

On dit que l'on a dualisé la contrainte d'égalité Modèle:Math, car c'est avec elle que l'on a construit le lagrangien <math>c^{\top\!}x-y^{\top\!}(Ax-b)</math> intervenant dans la technique de dualisation ci-dessus.

La seconde étape consiste à inverser l'ordre dans lequel sont pris l'infimum et le supremum, pour obtenir le problème dual

<math> (D_L)\quad\equiv\quad \sup_{y\in\R^m}\,\inf_{x\geqslant 0}\;\left[c^{\top\!}x-y^{\top\!}(Ax-b)\right]. </math>

Il reste à l'interpréter. Commençons par le problème interne :

<math> \inf_{x\geqslant 0}\;\left[c^{\top\!}x-y^{\top\!}(Ax-b)\right]= \inf_{x\geqslant 0}\;\left[b^{\top\!}y+(c-A^{\top\!}y)^{\top\!}x\right]= \left\{\begin{array}{ll} b^{\top\!}y & \mbox{si}~A^{\top\!}y\leqslant c\\ -\infty & \mbox{sinon}. \end{array}\right. </math>

Comme, par convention, le supremum sur un ensemble vide vaut Modèle:Math, le problème dual s'écrit

<math> (D_L)\quad \sup_{A^{\top\!}y\leqslant c}\;b^{\top\!}y, </math>

comme annoncé ci-dessus.

Propriétés de dualité

Quelle que soit la fonction <math>\varphi:X\times Y\to\bar{\R}</math> définie sur des ensembles quelconques Modèle:Mvar et Modèle:Mvar, on a

<math> \sup_{y\in Y}\,\inf_{x\in X}\;\varphi(x,y)\leqslant \inf_{x\in X}\,\sup_{y\in Y}\;\varphi(x,y). </math>

C'est ce que l'on appelle la relation de dualité faible. Par la technique de dualisation lagrangienne exposée ci-dessus, on obtient alors la relation suivante entre les valeurs optimales primale et duale.

Dans le cas de l'optimisation linéaire, cette inégalité s'obtient par simple calcul : on prend un point Modèle:Mvar admissible primal, un point Modèle:Mvar admissible dual, on en déduit que <math>b^{\top\!}y\leqslant c^{\top\!}x</math> et on conclut en prenant la borne supérieure à gauche et la borne inférieure à droite.

On déduit du résultat de dualité faible que si l'un des deux problèmes est non borné, l'autre n'est pas réalisable.

Modèle:Ancre L'écart entre les valeurs optimales primale et duale est ce que l'on appelle le saut de dualité :

<math> \mbox{saut de dualité}=\operatorname{val}(P_L)-\operatorname{val}(D_L). </math>

On dit qu'il n'y a pas de saut de dualité si Modèle:Math. En optimisation linéaire, il est rare d'avoir un saut de dualité. La seule possibilité est que l'on ait Modèle:Math (i.e., le problème primal n'est pas réalisable ; par exemple si Modèle:Math et Modèle:Math) et Modèle:Math (i.e., le problème dual n'est pas réalisable ; par exemple si Modèle:Math et <math>c\ngeqslant0</math>). C'est une conséquence du résultat d'existence de solution en OL (voir ci-dessus) et du résultat de dualité forte suivant.

La démonstration de ce résultat n'est pas sans intérêt. Donnons quelques éléments de preuve, ce qui permettra de donner quelques informations supplémentaires.

• L'implication 1 → 2 est une conséquence facile du résultat d'existence de solution et de la dualité faible.
• L'implication 2 → 3 est une conséquence du fait que les multiplicateurs <math>(y,s)\in\R^m\times\R^n</math> apparaissant dans les conditions d'optimalité du problème primal (qui a une solution) sont en réalité solutions du problème dual.
• L'implication 3 → 1 se démontre aussi à partir des conditions d'optimalité du problème dual, qui sont identiques à celles du problème primal.

L'implication 1 → 2 [resp. 1 → 3] est très souvent utilisée pour montrer que le problème primal [resp. dual] a une solution. Pour qu'il en soit ainsi, il suffit en effet de vérifier que les problèmes primal et dual sont réalisables, un fait qui peut se constater sans difficulté dans certains cas.

Algorithmes

Algorithme du simplexe

Modèle:Article détaillé L'algorithme du simplexe, développé par Dantzig à partir de 1947<ref name="dantzig">Modèle:Chapitre.</ref>, est une méthode de résolution finie d'un problème d'OL. Le qualificatif fini signifie qu'en un nombre fini d'étapes, l'algorithme trouve une solution ou montre que le problème est non borné ou encore montre que le problème n'est pas réalisable (les seules trois possibilités pour un problème d'OL, voir ci-dessus). L'algorithme a une interprétation géométrique simple. Les itérés sont des sommets de l'ensemble admissible (un polyèdre convexe). En un sommet, l'algorithme détermine une arête (face de dimension 1) de l'ensemble admissible le long de laquelle la fonction-coût décroît et prend comme nouvel itéré le sommet situé au bout de l'arête sélectionnée (opération appelée pivotage). Il peut y avoir plusieurs arêtes permettant de faire décroître la fonction-coût. Dans la règle du coût réduit minimal, l'algorithme choisit une arête le long de laquelle la fonction-coût décroît le plus.

Bien que l'algorithme du simplexe soit souvent efficace en pratique, ce n'est pas un algorithme polynomial : en réalité, il est exponentiel dans le pire des cas. Klee et Minty (1972) ont en effet construit un problème, dans lequel l'ensemble admissible est un « cube » de <math>\R^n</math> légèrement déformé, pour lequel l'algorithme du simplexe visite les Modèle:Math sommets de l'ensemble admissible. C'est le fait de prendre une décision à chaque itération à partir d'information locale (le coût réduit par exemple), ayant des effets globaux (le nombre d'itérations dépend du nombre de sommets visités avant d'arriver en une solution), qui ne permet pas d'obtenir la polynomialité de l'algorithme. Cet exemple est lié à une règle particulière de pivotage, mais des variantes de l'exemple de Klee et Minty existent pour la plupart des règles de pivotage, voir Terlaky et Zhang (1993). On ne sait d'ailleurs pas aujourd'hui (2011) s'il existe une règle de pivotage qui permettrait d'avoir la polynomialité, voir De Loera (2011). Ce contre-exemple a stimulé la recherche d'algorithmes pouvant être polynomiaux en optimisation linéaire, un problème jugé suffisamment simple pour admettre un tel algorithme. Ceci a conduit aux algorithmes de points intérieurs, qui ont ensuite été étendus à tous les problèmes d'optimisation (éventuellement non convexes).

L'efficacité souvent observée de l'algorithme du simplexe est justifiée aujourd'hui par le fait démontré de sa polynomialité en moyenne, pour des données distribuées aléatoirement suivant diverses lois de probabilité ; voir Borgwardt (1982, 1987), Smale (1983), Megiddo (1987), Sharmir (1987).

Algorithmes de points intérieurs

Modèle:Article détaillé Le premier algorithme polynomial pour l'OL a été proposé par Leonid Khatchian en 1979. Il est fondé sur la méthode de l'ellipsoïde en optimisation non linéaire précédemment proposée par Naum Z. Shor. Cette méthode est elle-même une généralisation de la méthode de l'ellipsoïde en optimisation convexe due à Arkadi Nemirovski (Prix John von Neumann 2003Modèle:Refsou), et à David B. Yudin. L'efficacité pratique de l'algorithme de Khachiyan est décevante : l'algorithme du simplexe est pratiquement toujours plus rapide. Cependant, ce résultat a encouragé la recherche sur les méthodes de points intérieurs.

En 1984, Narendra Karmarkar propose la méthode projective. C'est le premier algorithme efficace à la fois en théorie et en pratique. Sa complexité pire-cas est polynomiale et les expérimentations sur les problèmes pratiques montrent que la méthode peut raisonnablement être comparée à l'algorithme du simplexe.

Depuis lors, plusieurs méthodes de points intérieurs ont été proposées et étudiées. Contrairement à l'algorithme du simplexe dont les itérés sont des sommets du polyèdre convexe défini par les contraintes, appartenant donc à la frontière de ce polyèdre, les méthodes de points intérieurs (dans leur version admissible) génèrent des itérés dans l'intérieur relatif de l'ensemble admissible. Une des méthodes les plus couramment mises en œuvre est l'algorithme prédicteur-correcteur.

Comparaison des algorithmes du simplexe et de points intérieurs

Le tableau suivant donne quelques éléments de comparaison entre l'algorithme du simplexe primal et les algorithmes de points intérieurs les plus couramment utilisés, ceux qui génèrent des itérés suivant un chemin central.

Comparaison des algorithmes du simplexe et de points intérieurs

	Simplexe	Points intérieurs
Auteur-initiateur	Dantzig (vers 1947)	Karmarkar (1984)
Concept de base	sommet d'un polyèdre convexe	chemin central
Itération	d'un sommet à l'autre en suivant une arête	d'un voisinage d'un point central à l'autre par un pas de Newton
Type de convergence	finie	infinie
Polynomialité	probablement non polynomial, polynomial en moyenne	polynomial : convergence à Modèle:Math près en Modèle:Math itérations

Le but premier de ce tableau est de donner les grandes tendances des deux approches algorithmiques. Il manque certainement de nuance et de précision. On consultera les articles spécialisésModèle:LesquelsModèle:Référence nécessaire sur ces algorithmes pour plus d'information.

Algorithmes pour problèmes de grande taille

Dans le cas d'un grand nombre de variables et de contraintes, la résolution peut prendre beaucoup de temps. Dans certains cas, on peut accélérer la résolution en ne considérant pas toutes les données dès le départ (par exemple en ne prenant en compte qu'un sous-ensemble de contraintes) ou bien en profitant d'une forme particulière du problème. c'est ce que font les méthodes suivantes :

• Méthodes de décomposition de Benders ou la « génération de lignes » (pour problèmes avec une structure par blocs).
• Méthodes de Modèle:Lien ou la « génération de colonnes » ou méthodes des plans sécants, interprétable comme de la relaxation lagrangienne.

Applications

L'optimisation linéaire est essentiellement appliquée pour résoudre des problèmes d'optimisation à moyen et long terme (problèmes stratégiques et tactiques, dans le vocabulaire de la recherche opérationnelle). Les domaines d'application de ces problèmes sont très nombreux aussi bien dans la nature des problèmes abordés (planification et contrôle de la production, distribution dans des réseaux) que dans les secteurs d'industrie : industrie manufacturière, énergie (pétrole, gaz, électricité, nucléaire), transports (aériens, routiers et ferroviaires), télécommunications, industrie forestière, finance.

Logiciels

• {{#invoke:Langue|indicationDeLangue}} AIMMS Optimization Modeling AIMMS — include linear programming in industry solutions (free trial license available);
• {{#invoke:Langue|indicationDeLangue}} CGAL — The Computational Geometry Algorithms Library includes a linear solver, which is exact and optimized for problems with few constraints or few variables
• {{#invoke:Langue|indicationDeLangue}} COIN-OR — COmputational INfrastructure for Operations Research, open-source library
• {{#invoke:Langue|indicationDeLangue}} Cplex — Commercial library for linear programming
• {{#invoke:Langue|indicationDeLangue}} Vanguard System Linear Programming Optimization Add-In
• {{#invoke:Langue|indicationDeLangue}} GNU Linear Programming Kit, Bibliothèque libre Modèle:Lien pour l'optimisation linéaire, méthode du simplex, de points intérieurs, …
• {{#invoke:Langue|indicationDeLangue}} GIPALS — Linear programming environment and dynamic link library (DLL)
• {{#invoke:Langue|indicationDeLangue}} HOPDM — Higher Order Primal Dual Method
• {{#invoke:Langue|indicationDeLangue}} LINDO — LP, IP, Global solver/modeling langage
• {{#invoke:Langue|indicationDeLangue}} LiPS — Free easy-to-use program intended for solving linear, integer and goal programming problems.
• {{#invoke:Langue|indicationDeLangue}} Modèle:Lien brisé A freeware program for MS-DOS
• {{#invoke:Langue|indicationDeLangue}} MOSEK — Optimization software for LP, IP, QP, SOCP and MIP. Free trial is available. Free for students.
• {{#invoke:Langue|indicationDeLangue}} Mathematica — General technical computing system includes large scale linear programming support
• {{#invoke:Langue|indicationDeLangue}} Microarray Data Classification Server (MDCS) based on linear programming
• {{#invoke:Langue|indicationDeLangue}} Optimj OptimJ is an extension of the Java programming langage with langage support for writing optimization models and powerful abstractions for bulk data processing.
• {{#invoke:Langue|indicationDeLangue}} Orstat2000 — Includes easy-to-use modules for linear and integer programming (free for educational purposes).
• {{#invoke:Langue|indicationDeLangue}} Premium Solver — Spreadsheet add-in
• {{#invoke:Langue|indicationDeLangue}} QSopt Optimization software for LP (free for research purposes).
• {{#invoke:Langue|indicationDeLangue}} R Logiciel libre de calcul statistique contenant des librairies additionnelles pour l'OL: glpk, linprog (simplex), Rglpk (interface R pour Modèle:Lien)
• {{#invoke:Langue|indicationDeLangue}} Scilab dispose de la commande karmarkar() permettant de résoudre un problème d'optimisation linéaire par l'algorithme de Karmarkar.
• {{#invoke:Langue|indicationDeLangue}} Simplex Method Tool A quick-loading web page
• {{#invoke:Langue|indicationDeLangue}} What's Best! — Spreadsheet add-in
• {{#invoke:Langue|indicationDeLangue}} Xpress-MP — Optimization software free to students
• {{#invoke:Langue|indicationDeLangue}} IMSL — développements pour Fortran, C/C++, Java et C#
• {{#invoke:Langue|indicationDeLangue}} Gurobi — Commercial Solver: Linear Programming (LP) and Mixed Integer Programming (MILP) as well as quadratic and quadratically constrained programming (QP, QCP, MIQP, and MIQCP).

Annexes

Bibliographie

• {{#invoke:Langue|indicationDeLangue}} J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal (2006). Numerical Optimization - Theoretical and Numerical Aspects, Spinger. Modèle:Détail des éditions
• {{#invoke:Langue|indicationDeLangue}} K.-H. Borgwardt (1982). The average number of pivot steps required by the simplex-method is polynomial. Z. Oper. Res., (26), A157–A177.
• {{#invoke:Langue|indicationDeLangue}} K.-H. Borgwardt (1987). The Simplex Method: A Probabilistic Analysis. Springer, Berlin.
• {{#invoke:Langue|indicationDeLangue}} J. A. De Loera (2011). New insights into the complexity and geometry of linear optimization. Optima — Mathematical Optimization Society Newsletter 87.
• Christelle Guéret, Christian Prins et Marc Sevaux, Programmation Linéaire, Eyrolles, 2000 Modèle:ISBN, 365 pages.
• Eric Jacquet-Lagrèze. Programmation Linéaire - Modélisation et mise en œuvre informatique. Collection : P.I.Q. Poche - Éditeur : Economica.
• {{#invoke:Langue|indicationDeLangue}} V. Klee, G.L. Minty (1972). How good is the simplex algorithm ? In O. Shisha, éditeur, Inequalities III, pages 159–175. Academic Press, New York.
• {{#invoke:Langue|indicationDeLangue}} N. Megiddo (1987). On the complexity of linear programming. In T. Bewley, éditeur, Advances in Economic Theory, pages 225–268. Cambridge Univ. Press, Cambridge.
• {{#invoke:Langue|indicationDeLangue}} R. Shamir (1987). The efficiency of the simplex method: a survey. Management Science, 33, 301–334.
• {{#invoke:Langue|indicationDeLangue}} S. Smale (1983). On the average number of steps of the simplex method of linear programming. Mathematical Programming, 27, 241–262.
• {{#invoke:Langue|indicationDeLangue}} T. Terlaky, S. Zhang (1993). Pivot rules for linear programming – a survey. Annals of Operations Research, 46, 203–233.

Articles connexes

• Algèbre linéaire
• Algorithme du simplexe
• Branch and cut
• Conditions d'optimalité (dimension finie)
• Optimisation linéaire en nombres entiers
• Orthant positif

Liens externes

• {{#invoke:Langue|indicationDeLangue}} J. E. Beasley. Guidance on Formulating LP problems.
• {{#invoke:Langue|indicationDeLangue}} R. Freund. George Dantzig.
• J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.
• {{#invoke:Langue|indicationDeLangue}} A. Hosein. Linear Programming: Guide to Formulation, Simplex Algorithm, Goal Programming and Excel Solver examples.
• {{#invoke:Langue|indicationDeLangue}} IBM. IBM's article on GLPK. Un article technique sur Modèle:Lien avec une introduction à l'optimisation linéaire.
• {{#invoke:Langue|indicationDeLangue}} H. Mittelmann. Benchmark de différents logiciels sur différentes instances de problèmes d'OLNE.
• {{#invoke:Langue|indicationDeLangue}} Site NEOS. Modèle:Lien brisé.
• {{#invoke:Langue|indicationDeLangue}} ORMS. Linear Programming Software Survey.
• {{#invoke:Langue|indicationDeLangue}} M. A. Trick. A Tutorial on Integer Programming.
• {{#invoke:Langue|indicationDeLangue}} R. Vanderbei. Linear Programming: Foundations and Extensions.
• {{#invoke:Langue|indicationDeLangue}} K. Xu. 0-1 Integer Programming Benchmarks with Hidden Optimum Solutions.