Optimisation linéaire

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^{[note 1]}, 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^[1], mais cette appellation tend à être abandonnée^{[note 2]} à cause de la confusion possible avec la notion de programmation informatique.

Par exemple, le problème à deux variables $x=(x_{1},x_{2})\in \mathbb {R} ^{2}$ suivant :

\left\{{\begin{array}{l}{\inf }_{x}\;x_{1}+x_{2}\\x_{1}+2x_{2}\geqslant 2,\quad x_{1}\geqslant 0,\quad x_{2}\geqslant 0,\end{array}}\right.

qui consiste à minimiser la fonction linéaire $x=(x_{1},x_{2})\in \mathbb {R} ^{2}\mapsto x_{1}+x_{2}\in \mathbb {R}$ sous la contrainte d'inégalité affine $x 1 + 2 x 2 \geq 2$ et les contraintes de positivité des $x i$ , est un problème d'optimisation linéaire. Sa solution est $(x 1, x 2) = (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 :

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

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

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

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

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

Chacune de ces contraintes définit un demi-plan auquel $M$ 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 : $f (x, y) = 300 x + 500 y$ que l'on cherche à rendre maximale. Les programmes de fabrication permettant de rentrer, par exemple, 40 000 euros, correspondent aux points de la droite (d₄₀₀₀₀) : $300 x + 500 y = 40000$ . Cette droite partage le plan en deux demi-plans, un dans lequel $f (x, y) < 40000$ et l'autre dans lequel $f (x, y) > 40000$ . 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 $S$ 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.

Représentation d'une optimisation linéaire en dimension deux à 6 inégalités (au moins) : l'ensemble admissible est coloré en jaune et forme un polyèdre convexe. La fonction-coût minimisée a sa ligne de niveau en la solution représentée par la ligne rouge et la flèche indique le sens suivant lequel la fonction décroît (pour un problème de minimisation).

Optimisation en dimension trois: L'ensemble admissible est un polyèdre, la surface donnant une valeur fixée à la fonction à optimiser est un plan (non dessiné). Le problème d'optimisation consiste à trouver un sommet du polyèdre qui donne la valeur optimale à la fonction étudié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 $u={\begin{pmatrix}x\\y\end{pmatrix}}\quad A={\begin{pmatrix}1&1\\1&3\\0&3\end{pmatrix}}\quad b={\begin{pmatrix}150\\210\\180\end{pmatrix}}\quad c={\begin{pmatrix}300\\500\end{pmatrix}}$ Les contraintes se résument à $Au \leq b$ . La fonction revenu net est $g:g(u)=c^{\top }u$ qu'il faut maximiser. La formalisation canonique s'écrit enfin

\left\{{\begin{array}{l}{\sup }_{u}\;c^{\top }u\\Au\leqslant b\\u\geqslant 0\end{array}}\right.

que l'on peut écrire sous la forme de l'introduction en changeant $A$ , $b$ , et $c$ 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

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

Il suffit alors de poser $v={\begin{pmatrix}x\\y\\r\\s\\t\end{pmatrix}}\quad B={\begin{pmatrix}1&1&1&0&0\\1&3&0&1&0\\0&3&0&0&1\end{pmatrix}}\quad c_{1}={\begin{pmatrix}300\\500\\0\\0\\0\end{pmatrix}}$ pour obtenir la formalisation

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

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

$\{x\in \mathbb {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 \mathbb {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_{E}x=b,\qquad l_{I}\leqslant A_{I}x\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 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 :

$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 \mathbb {R} ^{n}:Ax=b,~x\geqslant 0,~c^{\top \!}x=\operatorname {val} (P_{L})\}$

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

Le qualificatif linéaire donné au problème $(P L)$ 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 $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 \mathbb {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 $c$ de la matrice $A$ .

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

$x$ est un sommet de $P$ ,
les colonnes $\{A^{j}\in \mathbb {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 celui où les contraintes ne sont pas compatibles (par exemple $x \geq 2$ et $x \leq 1$ ). La valeur optimale du problème de minimisation vaut alors $+\infty$ , 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 $-\infty$ (par exemple lorsqu'on cherche à minimiser $x$ sous la contrainte $x \leq 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 \mathbb {R} ^{n}

est solution de

(P L)

si, et seulement si, il existe des vecteurs

y\in \mathbb {R} ^{m}

s\in \mathbb {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

${\displaystyle \ell$

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$ : $x i$ ou $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.

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

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

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_{i}s_{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_{i}s_{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.\qquad {\mbox{ou}}\qquad \left\{{\begin{array}{ll}{\sup }_{y}\;b^{\top \!}y\\A^{\top \!}y\leqslant c.\end{array}}\right.

Il s'agit de deux problèmes de maximisation ; celui de droite est obtenu à partir de celui de gauche en éliminant la variable $s\in \mathbb {R} ^{n}$ , si bien qu'il ne lui reste que la variable $y\in \mathbb {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 \mathbb {R} ^{y}:A^{\top \!}y\leqslant c,~b^{\top \!}y=\operatorname {val} (D_{L})\}$

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 $(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 \mathbb {R} ^{n}$ fixé

$\sup _{y\in \mathbb {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.$

on a

$\inf _{x\geqslant 0}\,\left(\sup _{y\in \mathbb {R} ^{m}}\;\left[c^{\top \!}x-y^{\top \!}(Ax-b)\right]\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 \geq 0$ vérifiant $Ax = 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 \mathbb {R} ^{m}}\;\left[c^{\top \!}x-y^{\top \!}(Ax-b)\right].$

On dit que l'on a dualisé la contrainte d'égalité $Ax = 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 \mathbb {R} ^{m}}\,\inf _{x\geqslant 0}\;\left[c^{\top \!}x-y^{\top \!}(Ax-b)\right].$

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

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

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 {\mathbb {R} }}$ définie 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 $val(P L) = val(D L)$ . En optimisation linéaire, il est rare d'avoir un saut de dualité. La seule possibilité est que l'on ait $val(P L) = +\infty$ (i.e., le problème primal n'est pas réalisable ; par exemple si $A = 0$ et $b \neq 0$ ) et $val(D L) = -\infty$ (i.e., le problème dual n'est pas réalisable ; par exemple si $A = 0$ et $c\ngeqslant 0$ ). 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 \mathbb {R} ^{m}\times \mathbb {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) ont en effet construit un problème, dans lequel l'ensemble admissible est un « cube » de

\mathbb {R} ^{n}

légèrement déformé, pour lequel l'algorithme du simplexe visite les

2 n

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

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 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 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 à $ε > 0$ près en $O (n 1/2 log ε -1)$ 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és 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 décomposition de Dantzig-Wolfe (en) 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

(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) Vanguard System Linear Programming Optimization Add-In
(en) GNU Linear Programming Kit, Bibliothèque libre GLPK (en) pour l'optimisation linéaire, méthode du simplex, de points intérieurs, …
(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 »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)} 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))
(fr) Scilab dispose de la commande karmarkar() permettant de résoudre un problème d'optimisation linéaire par l'algorithme de Karmarkar.
(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 — développements pour Fortran, C/C++, Java et C#
(en) Gurobi — Commercial Solver: Linear Programming (LP) and Mixed Integer Programming (MILP) as well as quadratic and quadratically constrained programming (QP, QCP, MIQP, and MIQCP).

Notes et références

Notes

↑ On devrait dire affines.
↑ L'expression programmation mathématique tend à être abandonnée. Par exemple, en juin 2010, la société savante qui représente la discipline de l'optimisation mathématique a vu son nom antérieur Mathematical Programming Society changé en Mathematical Optimization Society^[2].

Références

1 2 (en) G. B. Dantzig, « Maximization of a linear function of variables subject to linear inequalities », dans T. C. Koopmans, Activity Analysis of Production and Allocation, New York, Wiley, 1951, p. 339–347.
↑ « Welcome to the website of the Mathematical Optimization Society », sur Mathematical Optimization Society.

Annexes

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]
(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) 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 (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.
(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) 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.
(en) S. Smale (1983). On the average number of steps of the simplex method of linear programming. Mathematical Programming, 27, 241–262.
(en) T. Terlaky, S. Zhang (1993). Pivot rules for linear programming – a survey. Annals of Operations Research, 46, 203–233.

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 »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)} (consulté le 7 novembre 2013).
(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.