Optimisation linéaire

Optimisation linéaire: En optimisation, qui est une branche des mathématiques, un problème d'optimisation linéaire est un problème d'optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe. La fonction-coût et les contraintes peuvent donc être décrites par des fonctions linéaires (on devrait dire affines), d'où vient le nom donné à ces problèmes. Ceux-ci ne sont cependant pas linéaires dans le sens où leurs solutions dépendraient linéairement de certaines données ; une non-linéarité importante est en effet induite par la présence des inégalités définissant les contraintes (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). L'optimisation linéaire (OL) est la discipline qui étudie ces problèmes.

Typiquement, un problème d'OL s'écrira donc en notation matricielle de la manière suivante

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

où $x\in\R^n$ est l'inconnue, le vecteur des variables réelles $x_1,\ldots,x_n$ à optimiser, et les données sont des vecteurs $c\in\R^n$ et $b\in\R^m$ et une matrice $A\in\R^{m\times n}$ . L'inégalité vectorielle $Ax\leqslant b$ doit être entendue composante par composante : pour tout indice $i$ , on doit avoir $(Ax-b)_i\leqslant 0$ . L'ensemble admissible $\{x\in\R^n:Ax\leqslant b\}$ est donc bien un polyèdre convexe, puisqu'il s'agit de l'intersection des demi-espaces $\{x\in\R^n:(Ax-b)_i\leqslant 0\}$ , pour $i=1,\ldots,m$ , en nombre fini. Bien sûr, comme toujours en optimisation, un problème de maximisation se ramènera à 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 connait 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(\sqrt{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 (OLNE). Ces derniers problèmes sont beaucoup plus difficiles à résoudre que les problèmes d'OL à variables continues décrits ci-dessus.

Sommaire

1 Exemple

2 Analyse du problème

2.1 Définitions

2.1.1 Formulations du problème

2.1.2 Sommet

2.2 Existence de solution

2.3 Conditions d'optimalité

2.3.1 Énoncé

2.3.2 Solution strictement complémentaire

2.4 Dualité lagrangienne

2.4.1 Le problème dual standard

2.4.2 Technique de dualisation

2.4.3 Propriétés de dualité

3 Algorithmes

3.1 Algorithme du simplexe

3.2 Algorithmes de points intérieurs

3.3 Algorithmes pour problèmes de grande taille

4 Optimisation linéaire en nombres entiers

5 Applications

5.1 Applications dans le pétrole

6 Logiciels

7 Annexes

7.1 Notes

7.2 Articles connexes

7.3 Liens externes

7.4 Bibliographie

Exemple

Considérons un agriculteur qui possède des terres, de superficie égale à H hectares, dans lesquelles il peut planter du blé et du maïs. L'agriculteur possède une quantité E d'engrais et I d'insecticide. Le blé nécessite une quantité E₁ d'engrais par hectare et I₁ d'insecticide par hectare. Les quantités correspondantes pour le maïs sont notées E₂ et I₂.

Soit P₁ le prix de vente du blé et P₂ celui du maïs. Si l'on note par x₁ et x₂ le nombre d'hectares à planter en blé et en maïs, alors le nombre optimal d'hectares à planter en blé et en maïs peut être exprimé comme un problème d'optimisation linéaire:

$maximiser$ $P 1 x 1 + P 2 x 2$ (maximiser le revenu net)

$sous contraintes$ $x_1 + x_2 \leqslant H$ (borne sur le nombre total d'hectares)

$E_1 x_1 + E_2 x_2 \leqslant E$ (borne sur la quantité d'engrais)

$I_1 x_1 + I_2 x_2 \leqslant I$ (borne sur la quantité d'insecticide)

$x_1 \geqslant 0,\, x_2 \geqslant 0$ (on ne peut pas planter un nombre négatif d'hectares)

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 :

$\{x\in\R^n:Ax\leqslant b\},$

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 :

$\{x\in\R^n:Ax=b,~x\geqslant 0\},$

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 :

$A_Ex= b,\qquad l_I\leqslant A_Ix\leqslant u_I,\qquad l_B\leqslant x\leqslant u_B.$

Les bons solveurs permettent d'utiliser de telles représentations de l'ensemble admissible. Cependant, autant de contraintes complique et alourdit 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 :

$Au-Av+s=b,\qquad u\geqslant 0,\qquad v\geqslant 0,\qquad s\geqslant 0,$

le lien entre la variable $x$ de la forme canonique et les variables $(u, v, s)$ de la formulation standard ci-dessus se faisant par $x = u - v$ . Réciproquement un ensemble admissible écrit sous forme standard pourra se représenter sous la forme canonique suivante :

$\begin{pmatrix}A\\-A\\-I\end{pmatrix}x\leqslant \begin{pmatrix}b\\-b\\0\end{pmatrix}.$

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 :

$(P_L)\quad \left\{\begin{array}{l} \inf_x\;c^{\top\!}x\\ Ax=b\\ x\geqslant 0. \end{array}\right.$

On note

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

la valeur optimale de $(P L)$ et

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

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

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 $x$ est un sommet du polyèdre convexe $P$ si $x\in P$ et si

$y,z\in P,\quad x=\frac{y+z}{2} \qquad\Longrightarrow\qquad x=y=z.$

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

Sommet d'un polyèdre convexe sous forme standard — Soient $P:=\{x\in\R^n:Ax=b,~x\geqslant 0\}$ un polyèdre convexe et $x\in P$ . Alors les propriétés suivantes sont équivalentes :

$x$ est un sommet de $P$ ,

les colonnes $\{A^j\in\R^m:x_j>0\}$ de $A$ sont linéairement indépendantes.

De plus $P$ a au moins un sommet.

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 lorsque les contraintes ne sont pas compatibles (par exemple $x \ge 2$ et $x \le 1$ ). La valeur optimale du problème de minimisation vaut alors $+\infty$ , par convention. On dit alors 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 $-\infty$ (par exemple lorsqu'on cherche à minimiser $x$ sous la contrainte $x\leqslant 0$ ). 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.

Existence de solution — Pour un problème d'optimisation linéaire, les propriétés suivantes sont équivalentes :

le problème a une solution,

le problème est réalisable et borné,

la valeur optimale du problème est finie.

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 $(P L)$ 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 $(P L)$ .

Existence de solution-sommet — Si le problème $(P L)$ a une solution, il a une solution en un sommet de son ensemble admissible.

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 $(P L)$ 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é.

Conditions d'optimalité — Le point $x\in\R^n$ est solution de $(P L)$ si, et seulement si, il existe des vecteurs $y \in \R^m$ et $s \in \R^n$ tels que

$\left\{\begin{array}{ll} (a) & A^{\top\!} y + s = c, \quad s\geqslant 0 \\ (b) & Ax = b, \quad x\geqslant 0 \\ (c) & x^{\top\!} s= 0. \end{array}\right.$

Les variables $y$ et $s$ 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 $x$ . Comme on aura l'occasion de le voir ci-dessous ces variables cachées dans le problème $(P L)$ jouent un rôle important dans son analyse. On note

$\mathcal{S}_{PD}$

l'ensemble des solutions primales-duales, c'est-à-dire l'ensemble des triplets $(x, y, s)$ vérifiant les conditions d'optimalité ci-dessus.

Les relations $(a)$ expriment l'admissibilité duale et la première de ces relations est le gradient en $x$ du Lagrangien du problème, qui est la fonction

$\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.$

Les relations $(b)$ expriment l'admissibilité primale et la relation $(c)$ exprime la complémentarité existant entre les variables primales $x$ et leurs multiplicateurs $s$ : soit $x i$ , soit $s i$ est nul (ou les deux) ; voir aussi plus loin.

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

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.

Produit cartésien des solutions — L'ensemble des solutions primales-duales est un produit cartésien :

$\mathcal{S}_{PD}=\mathcal{S}_{P}\times\mathcal{S}_{D}.$

Autrement dit, si $(x 1, y 1, s 1)$ et $(x 2, y 2, s 2)$ sont des solutions primales-duales, alors $(x 1, y 2, s 2)$ est aussi une solution primale-duale.

Solution strictement complémentaire

Revenons sur les conditions de complémentarité, la condition $(c)$ du système d'optimalité. Cette condition s'écrit

$\sum_{i=1}^n\,x_is_i=0.$

Comme $x$ et $s$ ont leurs composantes positives, cela revient au même d 'écrire

$\forall\,i\in\{1,\ldots,n\} :\quad x_is_i=0$

ou encore

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

Ceci n'implique pas que $s i > 0$ lorsque $x i = 0$ .

Une solution primale-duale $(x, y, s)$ est dite strictement complémentaire, si

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

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

$\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}$

Solution primale-duale strictement complémentaire — Si le problème $(P L)$ a une solution, alors il a une solution primale-duale strictement complémentaire. Cette affirmation revient à dire que $(B, N)$ forme une partition de $[\![1,n]\!]$ :

$B\cap N=\varnothing\quad\mbox{et}\quad B\cup N=[\![1,n]\!].$

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 $(P L)$ , la dualisation lagrangienne conduit au problème dual standard suivant

$(D_L)\quad \left\{\begin{array}{ll} \sup_{(y,s)}\;b^{\top\!}y\\ A^{\top\!}y+s=c\\ s\geqslant 0 \end{array}\right. \quad\mbox{ou}\quad \left\{\begin{array}{ll} \sup_y\;b^{\top\!}y\\ A^{\top\!}y\leqslant c. \end{array}\right.$

Il s'agit de deux problèmes maximisation ; celui de droite est obtenu à partir de celui de gauche en éliminant la variable $s\in\R^n$ , si bien qu'il ne lui reste que la variable $y\in\R^m$ .

On note

$\operatorname{val}(D_L)=\sup_{A^{\top\!}y\leqslant c}\;b^{\top\!}y$

la valeur optimale de $(D L)$ et

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

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

Comment obtenir le problème dual associé à une autre formulation du problème d'optimisation linéaire ? À quoi cela sert-il ? Cette section répond à ces interrogations.

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. Partons du problème $(P L)$ , qualifié ici de primal.

La première étape consiste à écrire le problème primal comme un $\inf\,\sup$ . Par exemple, comme à $x\in\R^n$ fixé

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

on a

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

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

$(P_L)\quad\equiv\quad \inf_{x\geqslant 0}\,\sup_{y\in\R^m}\;\Bigl[c^{\top\!}x-y^{\top\!}(Ax-b)\Bigr].$

On dit que l'on a dualisé la contrainte d'égalité $A x = b$ , car c'est avec elle que l'on a construit le lagrangien $c^{\top\!}x-y^{\top\!}(Ax-b)$ 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

$(D_L)\quad\equiv\quad \sup_{y\in\R^m}\,\inf_{x\geqslant 0}\;\Bigl[c^{\top\!}x-y^{\top\!}(Ax-b)\Bigr].$

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

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

Comme, par convention, le supremum sur un ensemble vide vaut $-\infty$ , le problème dual s'écrit

$(D_L)\quad \sup_{A^{\top\!}y\leqslant c}\;b^{\top\!}y,$

comme annoncé ci-dessus.

Propriétés de dualité

Quelle que soit la fonction $\varphi:X\times Y\to\bar{\R}$ sur des ensembles quelconques $X$ et $Y$ , on a

$\sup_{y\in Y}\,\inf_{x\in X}\;\varphi(x,y)\leqslant \inf_{x\in X}\,\sup_{y\in Y}\;\varphi(x,y).$

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.

Dualité faible — $\operatorname{val}(D_L)\leqslant\operatorname{val}(P_L)$ .

Dans le cas de l'optimisation linéaire, cette inégalité s'obtient par simple calcul : on prend un point $x$ admissible primal, un point $y$ admissible dual, on en déduit que $b^{\top\!}y\leqslant c^{\top\!}x$ 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.

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

$\mbox{saut de dualité}=\operatorname{val}(P_L)-\operatorname{val}(D_L).$

On dit qu'il n'y a pas de saut de dualité si $\operatorname{val}(P_L)=\operatorname{val}(D_L)$ . En optimisation linéaire, il est rare d'avoir un saut de dualité. La seule possibilité est que l'on ait $\operatorname{val}(P_L)=+\infty$ (i.e., le problème primal n'est pas réalisable) et $\operatorname{val}(D_L)=-\infty$ (i.e., le problème dual n'est pas réalisable). 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.

Dualité forte — Les propriétés suivantes sont équivalentes :

les problèmes primal et dual sont réalisables,

le problème primal a une solution,

le problème dual a une solution.

Dans ce cas, il n'y a pas de saut de dualité.

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 $(y,s)\in\R^m\times\R^n$ 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

L'algorithme du simplexe, développé par Dantzig à partir de 1947^[1], 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^[2]) ont en effet construit un problème, dans lequel l'ensemble admissible est un «cube» de $\R^n$ légèrement déformé, pour lequel l'algorithme du simplexe visite les $2 n$ sommets de l'ensemble admissible. Des variantes de l'exemple de Klee et Minty existent pour la plupart des règles de pivotage^[3]. 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. 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^[4], 1987^[5]), Smale (1983^[6]), Megiddo (1987^[7]), Sharmir (1987^[8]).

Algorithmes de points intérieurs

Le premier algorithme polynomial pour l'OL a été proposé par Leonid Khachiyan (en) 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 (en). 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 2003), 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 (en) 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 implémentées est l'algorithme prédicteur-correcteur.

Algorithmes pour problèmes de grande taille

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 décomposition de Dantzig-Wolfe (en) ou la «génération de colonnes» ou méthode des plans coupants, interprétable comme de la relaxation lagrangienne.

Optimisation linéaire en nombres entiers

Un problème d'optimisation linéaire en nombres entiers n'est pas un problème d'optimisation linéaire dans le sens où son domaine admissible n'est pas un polyèdre mais un ensemble discret de points. Pourtant, on peut le décrire comme un problème d'OL auquel on ajoute la contrainte supplémentaire que certaines variables ne peuvent prendre que des valeurs entières. On distingue l'optimisation linéaire mixte avec variables entières et continues du problème entier avec toutes ses variables entières.

L'OLNE est un problème NP-complet car de nombreux problèmes NP-complets peuvent être exprimés comme des problèmes d'OLNE (par exemple trouver un stable dans un graphe $G = (V, E)$ revient à trouver un vecteur $x\in \{0,1\}^E$ satisfaisant $x_u +x_v \le 1$ pour tout arête $uv \in E$ ). Les algorithmes décrits ci-dessus pour l'OL ne résolvent pas les problèmes d'OLNE. Algorithmiquement donc, la résolution d'un problème d'OLNE est autrement plus difficile celle d'un problème d'OL qui joue pourtant un rôle crucial quant à leur résolution, principalement pour deux raisons. Premièrement, la relaxation continue d'un problème d'OLNE (c'est le problème d'OLNE sans les contraintes d'intégrité) est un problème d'OL qui peut être résolu efficacement et fournir ainsi une borne duale (dans le sens non-réalisable). Les algorithmes de résolution de problème d'OLNE, tels que les algorithmes par séparation et évaluation se basent sur cette relaxation continue pour diminuer au maximum l'énumération des solutions. Deuxièmement, le théorème Optimisation/Séparation de Grötschel, Lovasz et Schrijver permet de résoudre en pratique par l'OL les problèmes entiers dont on connait une bonne description polyèdrale (c'est-à-dire dont on peut séparer les contraintes en temps polynomial). C'est le principe de fonctionnement de la méthode des plans sécants.

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.

Applications dans le pétrole

Articles détaillés : Pétrole, Raffinage du pétrole et Plans d'approvisionnement, de production et de distribution du pétrole.

La technique d'optimisation linéaire est couramment appliquée dans l'industrie pétrolière. C'est l'une des industries, si ce n'est la principale qui utilise quotidiennement l'OL. Elle est l'outil qui permet au raffineur de faire la détermination optimale de production d'une raffinerie. Pour ce faire, le problème doit tenir compte d'un certain nombre de contraintes telles que :

bruts disponibles, leurs rendements et les qualités des coupes,

spécifications des produits à fabriquer,

limitations de débouchés pour certains produits,

capacités des unités,

modes de réglages des installations,

capacités de stockage disponibles.

L'OL peut également être utilisée dans d'autres domaines du raffinage, par exemple :

calculs de la composition optimale des mélanges de produits (carburants, gasoils, fuels) en tenant compte des spécifications.

l'optimisation dans l'utilisation des installations,

calculs de l'obtention du meilleur préchauffage des bruts et des charges,

détermination du meilleur équilibre «vapeur-électricité» d'une raffinerie.

En dehors des raffineries, on peut utiliser l'OL dans la recherche opérationnelle pour :

bâtir des plans à long/moyen et court termes d'une compagnie pétrolière,

optimiser le fonctionnement d'une flotte de tankers et la mise en place des produits.

Logiciels

(en) AIMMS Optimization Modeling AIMMS — include linear programming in industry solutions (free trial license available);

(en) CGAL — The Computational Geometry Algorithms Library includes a linear solver, which is exact and optimized for problems with few constraints or few variables

(en) COIN-OR — COmputational INfrastructure for Operations Research, open-source library

(en) Cplex — Commercial library for linear programming

(en) DecisionPro Linear Programming Optimization Software

(en) GNU Linear Programming Kit, Bibliothèque libre GLPK (en) pour l'optimisation linéaire, méthode du simplex, du point intérieur…

(en) GIPALS — Linear programming environment and dynamic link library (DLL)

(en) HOPDM — Higher Order Primal Dual Method

(en) LINDO — LP, IP, Global solver/modeling langage

(en) LiPS — Free easy-to-use program intended for solving linear, integer and goal programming problems.

(en) Linear programming and linear goal programming A freeware program for MS-DOS

(en) MOSEK — Optimization software for LP, IP, QP, SOCP and MIP. Free trial is available. Free for students.

(en) Mathematica — General technical computing system includes large scale linear programming support

(en) Microarray Data Classification Server (MDCS) based on linear programming

(en) Optimj OptimJ is an extension of the Java programming langage with langage support for writing optimization models and powerful abstractions for bulk data processing.

(en) Orstat2000 — Includes easy-to-use modules for linear and integer programming (free for educational purposes).

(en) Premium Solver — Spreadsheet add-in

(en) QSopt Optimization software for LP (free for research purposes).

(en) R Logiciel libre de calcul statistique contenant des librairies additionnelles pour l'OL: glpk, linprog (simplex), Rglpk (interface R pour GPLK (en))

(en) Simplex Method Tool A quick-loading web page

(en) What's Best! — Spreadsheet add-in

(en) Xpress-MP — Optimization software free to students

(fr) IMSL — implémentations pour Fortran, C/C++, Java et C#

Annexes

Notes

↑ (en) G.B. Dantzig (1951). Maximization of a linear function of variables subject to linear inequalities. In Tj.C. Koopmans, éditeur, Activity Analysis of Production and Allocation, pages 339–347. Wiley, New York.

↑ (en) 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.

↑ (en) T. Terlaky, S. Zhang (1993). Pivot rules for linear programming – a survey. Annals of Operations Research, 46, 203–233.

↑ (en) K.-H. Borgwardt (1982). The average number of pivot steps required by the simplex-method is polynomial. Z. Oper. Res., (26), A157–A177.

↑ (en) K.-H. Borgwardt (1987). The Simplex Method: A Probabilistic Analysis. Springer, Berlin.

↑ (en) S. Smale (1983). On the average number of steps of the simplex method of linear programming. Mathematical Programming, 27, 241–262.

↑ (en) N. Megiddo (1987). On the complexity of linear programming. In T. Bewley, éditeur, Advances in Economic Theory, pages 225–268. Cambridge Univ. Press, Cambridge.

↑ (en) R.Shamir(1987). The efficiency of the simplex method: a survey. Management Science, 33, 301–334.

Articles connexes

Algorithme du simplexe

Branch and cut

Liens externes

(en) J. E. Beasley. Guidance on Formulating LP problems.

(en) R. Freund. George Dantzig.

J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.

(en) A. Hosein. Linear Programming: Guide to Formulation, Simplex Algorithm, Goal Programming and Excel Solver examples.

(en) IBM. IBM's article on GLPK. Un article technique sur GLPK (en) avec une introduction à l'optimisation linéaire.

(en) H. Mittelmann. Benchmark de différents logiciels sur différentes instances de problèmes d'OLNE.

(en) Site NEOS. Linear Programming Directory.

(en) ORMS. Linear Programming Software Survey.

(en) M. A. Trick. A Tutorial on Integer Programming.

(en) R. Vanderbei. Linear Programming: Foundations and Extensions.

(en) K. Xu. 0-1 Integer Programming Benchmarks with Hidden Optimum Solutions.

Bibliographie

(en) J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal (2006). Numerical Optimization - Theoretical and Numerical Aspects, Spinger. [détail des éditions]

Christelle Guéret, Christian Prins et Marc Sevaux, Programmation Linéaire, Eyrolles, 2000 (ISBN 2-212-09202-4), 365 pages.

Eric Jacquet-Lagrèze. Programmation Linéaire - Modélisation et mise en œuvre informatique. Collection : P.I.Q. Poche - Éditeur : Economica.

v · Ensemble convexe
Outils et résultats fondamentaux : Enveloppe convexe • Adhérence, intérieur et frontière d'un convexe • Projection sur un convexe fermé • Séparation des convexes • Points remarquables à la frontière d'un convexe • Polytope • Théorème de Krein-Milman • Lemme de Farkas
Géométrie combinatoire : Théorème de Carathéodory • Théorème de Radon • Théorème de Helly
Géométrie métrique : Courbe de largeur constante • Théorème des quatre sommets
Algorithmes de géométrie convexe : Approche polyédrique • Marche de Jarvis • Parcours de Graham • Théorème optimisation/séparation
Optimisation linéaire : Optimisation linéaire • Algorithme du simplexe • Génération de colonnes

Interactions géométrie-analyse

Théorème de Hahn-Banach • Jauge

Analyse convexe

Articles principaux : Ensemble convexe • Fonction convexe
Outils et résultats fondamentaux : Conditions de Kuhn-Tucker • Inégalité de Jensen
Algorithmique : Méthodes de points intérieurs

Utilisations de la convexité

Inégalités de convexité : Inégalité arithmético-géométrique • Inégalité de Hölder
Analyse fonctionnelle : Espace localement convexe • Théorème du point fixe de Schauder
Localisation de zéros de polynômes : Théorème de Gauss-Lucas
Théorie des nombres : Théorème de Minkowski

Portail des mathématiques

Portail de l'informatique théorique

Catégories :
Optimisation
Recherche opérationnelle
Optimisation combinatoire

Contenu soumis à la licence CC-BY-SA. Source : Article Optimisation linéaire de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

Optimisation (mathématiques) — L optimisation est une branche des mathématiques, cherchant à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à déterminer le meilleur élément d un ensemble, au sens d un critère quantitatif donné. Ce mot vient … Wikipédia en Français
Optimisation combinatoire — L’optimisation combinatoire est une branche de l optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l algorithmique et la théorie de la complexité. On parle également d’optimisation discrète … Wikipédia en Français
OPTIMISATION ET CONTRÔLE — L’avènement du calcul différentiel, au XVIIe siècle, a permis de caractériser le minimum d’une fonction f par l’équation f (x ) = 0. On résolvait ainsi d’un coup une foule de problèmes pratiques, tout en soulevant de grandes questions théoriques … Encyclopédie Universelle
Optimisation (mathematiques) — Optimisation (mathématiques) En mathématiques, l optimisation est l’étude des problèmes qui sont de la forme : Étant donné : une fonction d’un ensemble A dans l ensemble des nombre réels Rechercher : un élément x0 de A tel que pour … Wikipédia en Français
Optimisation multi-objectif — L optimisation multiobjectif est branche de l optimisation combinatoire dont la particularité est de chercher à optimiser simultanément plusieurs objectifs d un même problème (contre un seul objectif pour l optimisation combinatoire classique).… … Wikipédia en Français
Optimisation non linéaire — En optimisation, vue comme branche des mathématiques, l optimisation non linéaire (en anglais : nonlinear programming – NLP) s occupe principalement des problèmes d optimisation dont les données, i.e., les fonctions et ensembles définissant… … Wikipédia en Français
Optimisation difficile — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Optimisation des performances des architectures multi-cœurs — Un microprocesseur multi cœur (multi core en anglais) est un processeur possédant plusieurs cœurs physiques. Depuis l’arrivée des premiers microprocesseurs double cœurs en 2005, le nombre de cœurs ne cesse d’augmenter dans l’objectif d’améliorer… … Wikipédia en Français
Optimisation multiobjectif — L optimisation multiobjectif est une branche de l optimisation combinatoire dont la particularité est de chercher à optimiser simultanément plusieurs objectifs d un même problème (contre un seul objectif pour l optimisation combinatoire… … Wikipédia en Français
Optimisation quadratique — En optimisation, qui est une branche des mathématiques, un problème d optimisation quadratique est un problème d optimisation dans lequel on minimise une fonction quadratique sur un polyèdre convexe. Les contraintes peuvent donc être décrites par … Wikipédia en Français

Mark and share
Search through all dictionaries
Translate…
Search Internet

Share the article and excerpts