Voir la source de Optimisation linéaire

[[Fichier:Optimisation lineaire 2D.svg|thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (''x''<sub>1</sub>, ''x''<sub>2</sub>). La fonction-coût ''f''<sub>c</sub> 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ématiques)|optimisation mathématique]], un '''problème d'optimisation linéaire''' demande de minimiser une fonction linéaire sur un [[polyèdre]] [[ensemble convexe|convexe]]. La fonction que l'on minimise ainsi que les [[Contrainte (mathématiques)|contraintes]] sont décrites par des fonctions [[application linéaire|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ée{{Note|texte=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''<ref>{{Lien web |titre=Welcome to the website of the Mathematical Optimization Society |url=https://www.mathopt.org/ |site=Mathematical Optimization Society}}.</ref>.|groupe=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 :
<center><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></center>
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 {{math|''x''{{ind|1}} + 2''x''{{ind|2}} ≥ 2}} et les contraintes de positivité des {{mvar|x{{ind|i}}}}, est un problème d'optimisation linéaire. Sa solution est {{math|(''x''{{ind|1}} , ''x''{{ind|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 :
<center><math>
\left\{\begin{array}{l}
{\inf}_x\;c^\top x\\
Ax\leqslant b,
\end{array}\right.
</math></center>
où <math>x\in\R^n</math> est l'inconnue, le vecteur des variables réelles {{math|''x''{{ind|1}},...,''x{{ind|n}}''}} à 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 {{math|''Ax'' ≤ ''b''}} doit être entendue composante par composante : pour tout indice {{mvar|i}}, on doit avoir {{math|(''Ax'' – ''b''){{ind|''i''}} ≤ 0}}. 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 {{math|''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ération]]s qui est majoré par un polynôme, fonction des dimensions du problème. Typiquement, un [[Méthodes de points intérieurs|algorithme de points intérieurs]] requerra ''théoriquement au plus'' un nombre d'itérations de l'ordre de {{math|''O''({{racine|''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 [[Théorie de la complexité (informatique théorique)|difficiles]] à résoudre que les problèmes d'OL à variables continues décrits ci-dessus.
<!--
En mathématiques, un '''problème d'optimisation linéaire''' (PL) est un problème d'[[optimisation (mathématiques)|optimisation]] dans lequel la [[fonction objectif]] et les [[Contrainte (mathématiques)|contraintes]] sont toutes [[application linéaire|linéaires]] (''affines''). La plupart des résultats présentés ici restent toutefois vrais si l'objectif est une ''[[fonction monotone]] croissante'' de ''chaque'' variable considérée. La [[programmation linéaire]] désigne également la manière de résoudre les problèmes linéaires.

L'optimisation linéaire est un problème de résolution facile, et la méthode est pour cette raison largement enseignée dans les écoles d'ingénieurs. De nombreux problèmes réels de [[recherche opérationnelle]] peuvent être exprimés comme un problème d'optimisation linéaire<ref>Allant du cas le plus simple (par exemple composition d'un sachet de graines apéritives maximisant le profit en fonction des cours du moment) aux plus complexes (gestion du [[cracking]] dans une raffinerie pour satisfaire au mieux la demande</ref>. De nombreux algorithmes de résolution existent, dont la [[méthode du simplexe]]. 

Le terme programmation linéaire suppose que les solutions à trouver doivent être représentées en variables réelles, continues.

Si le problème exige l'usage de variables discrètes (contraintes dites d'''intégrité''), on parle alors de problème d'optimisation linéaire en nombres entiers (PLNE). Ces derniers sont nettement plus [[Théorie de la complexité des algorithmes|complexes]] à résoudre que les PL à variables continues, bien que la solution continue la plus proche puisse constituer un bon point de départ.
-->

== 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|thumb|upright=1.5|Exemple pratique d'un problème d'optimisation linéaire]]

Une modélisation mathématique conduit à appeler {{mvar|x}} le nombre de produits P1 à fabriquer et {{mvar|y}} le nombre de produits P2 ; {{mvar|M}} sera le point de coordonnées {{math|(''x'', ''y'')}}. Les contraintes de fabrication s'expriment à l'aide des inégalités suivantes :
<center><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></center>

Chacune de ces contraintes définit un demi-plan auquel {{mvar|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 : {{math|''f''(''x'', ''y'') {{=}} 300''x'' + 500''y''}} que l'on cherche à rendre maximale. Les programmes de fabrication permettant de rentrer, par exemple, {{unité|40000|euros}} correspondent aux points de la droite (d<sub>40000</sub>) : {{math|300''x'' + 500''y'' {{=}} 40000}}. Cette droite partage le plan en deux demi-plans, un dans lequel {{math|''f''(''x'', ''y'') < 40000}} et l'autre dans lequel {{math|''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 {{mvar|S}} correspondent aux points d'une droite (d<sub>S</sub>) parallèle à (d<sub>40000</sub>) . Pour maximiser le revenu net, il suffit de trouver la droite (d<sub>S</sub>) parallèle à (d<sub>40000</sub>) 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. 

{{multiple image
| align = center
| direction = horizontal
| width = 240
| image1 = Linear optimization in a 2-dimensional polytope.svg
| caption1 = '''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).
| image2 = 3dpoly.svg
| caption2 = '''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
{{retrait|<math>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}</math>.}}
Les contraintes se résument à {{math|''Au'' ≤ ''b''}}. La fonction revenu net est <math>g: g(u)=c^{\top}u</math> qu'il faut maximiser. La formalisation canonique s'écrit enfin
<center><math>
\left\{\begin{array}{l}
{\sup}_u\;c^\top u\\
Au\leqslant b\\
 u\geqslant 0
\end{array}\right.
</math></center>
que l'on peut écrire sous la forme de l'introduction en changeant {{mvar|A}}, {{mvar|b}}, et {{mvar|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 : 
<center><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>.</center>
Il suffit alors de poser 
{{retrait| <math>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}</math>}}
pour obtenir la formalisation
 <center><math>
\left\{\begin{array}{l}
{\sup}_v\;c_1^\top v\\
Bv=b, \\v\geqslant 0
\end{array}\right.
</math>.</center>
C'est sur ces formes (canonique ou standard) que se mettent en place les techniques d'optimisation en dimension {{mvar|n}}. Elles supposent la connaissance de l'[[algèbre linéaire]], des [[Matrice (mathématiques)|notations matricielles]] et des bases de l'[[optimisation (mathématiques)|optimisation]] (en particulier, du [[optimisation (mathématiques)#Minimisation|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 :
<center>
<math>
\{x\in\R^n:Ax\leqslant b\},
</math>
</center>
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|orthant positif]] et d'un sous-espace affine :
<center>
<math>
\{x\in\R^n:Ax=b,~x\geqslant 0\},
</math>
</center>
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 :
<center>
<math>
A_Ex= b,\qquad
l_I\leqslant A_Ix\leqslant u_I,\qquad
l_B\leqslant x\leqslant u_B.
</math>
</center>
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 :
<center>
<math>
Au-Av+s=b,\qquad
u\geqslant 0,\qquad
v\geqslant 0,\qquad
s\geqslant 0,
</math>
</center>
le lien entre la variable {{mvar|x}} de la forme canonique et les variables {{math|(''u'',''v'',''s'')}} de la formulation standard ci-dessus se faisant par {{math|''x'' {{=}} ''u'' – ''v''}}. Réciproquement un ensemble admissible écrit sous forme standard pourra se représenter sous la forme canonique suivante :
<center>
<math>
\begin{pmatrix}A\\-A\\-I\end{pmatrix}x\leqslant
\begin{pmatrix}b\\-b\\0\end{pmatrix}.
</math>
</center>

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 :
{{ancre|probleme-primal}}
{{Bloc emphase|espacement=1.5ex|<math>
(P_L)\quad
\left\{\begin{array}{l}
{\inf}_x\;c^{\top\!}x\\
Ax=b\\
x\geqslant 0.
\end{array}\right.
</math>}}
On note
<center>
<math>
\operatorname{val}(P_L)=\inf_{Ax=b\atop x\geqslant 0}\;c^{\top\!}x
</math>
</center>
la valeur optimale de {{math|(''P{{ind|L}}'')}} et
<center>
<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>
</center>
l'ensemble de ses solutions (qui peut être vide).

Le qualificatif ''linéaire'' donné au problème {{math|(''P{{ind|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.

{{Ancre|sommet}}

==== 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 '''[[Points et parties remarquables de la frontière d'un convexe|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 {{mvar|x}} est un sommet du polyèdre convexe {{mvar|P}} si {{math|''x'' ∈ ''P''}} et si
<center>
<math>
y,z\in P,\quad
x=\frac{y+z}{2}
\qquad\Longrightarrow\qquad
x=y=z.
</math>
</center>

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 {{mvar|A{{exp|j}}}} la colonne {{mvar|c}} de la matrice {{mvar|A}}.

{{Théorème|Sommet d'un polyèdre convexe sous forme standard|Soient <math>P:= \{x\in\R^n:Ax=b,~x\geqslant 0\}</math> un polyèdre convexe non vide et {{math|''x'' ∈ ''P''}}. Alors les propriétés suivantes sont équivalentes :
# {{mvar|x}} est un sommet de {{mvar|P}},
# les colonnes <math>\{A^j\in\R^m:x_j>0\}</math> de {{mvar|A}} sont linéairement indépendantes.
De plus {{mvar|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 {{math|''x'' ≥ 2}} et {{math|''x'' ≤ 1}}). La valeur optimale du problème de minimisation vaut alors {{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 {{math|–∞}} (par exemple lorsqu'on cherche à minimiser {{mvar|x}} sous la contrainte {{math|''x'' ≤ 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.

{{Théorème|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é|Propriétés de dualité]].

Comme l'ensemble des solutions de {{math|(''P{{ind|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 {{math|(''P{{ind|L}}'')}}.

{{Théorème|Existence de solution-sommet|Si le problème {{math|(''P{{ind|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 !).
<!--
(par exemple <math>x_1 + 3 x_2</math> tel que <math>x_1 \ge 0</math>, <math>x_2 \ge 0</math>, <math>x_1 + x_2 \ge 10</math>). Dans ce cas, il n'y a pas de solution optimale puisqu'il est possible de construire des solutions satisfaisant les contraintes avec des valeurs arbitrairement élevées (ou basses) de la fonction objectif.

En dehors de ces deux cas (qui sont finalement rares dans les problèmes pratiques), l'optimum est toujours atteint à un sommet du polytope. Cependant, l'optimum n'est pas nécessairement unique : il est possible d'avoir un ensemble de solutions optimales correspondant à une arête ou à une face du polytope, voire au polytope en entier.
-->

=== Conditions d'optimalité ===

==== Énoncé ====

Les [[Conditions d'optimalité (dimension finie)|conditions d'optimalité]] du problème d'optimisation linéaire {{math|(''P{{ind|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 d'optimalité (dimension finie)#Conditions de Karush, Kuhn et Tucker (KKT)|conditions de Karush, Kuhn et Tucker]]), avec la simplification supplémentaire de ne pas avoir à s'occuper de la [[Qualification de contraintes|qualification des contraintes]] du problème. L'affinité de celles-ci les rend en effet qualifiées (voir la section [[Qualification de contraintes#Affinité locale (QC-A)|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é.

{{Théorème|Conditions d'optimalité|Le point <math>x\in\R^n</math> est solution de {{math|(''P{{ind|L}}'')}} si, et seulement si, il existe des vecteurs <math>y \in \R^m</math> et <math>s \in \R^n</math> tels que
<center>
<math>
\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.
</math>
</center>}}

Les variables {{mvar|y}} et {{mvar|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''' {{mvar|x}}. Comme on aura l'occasion de le voir ci-dessous, ces variables ''cachées'' dans le problème {{math|(''P{{ind|L}}'')}} 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 {{math|(''x'',''y'',''s'')}} vérifiant les conditions d'optimalité ci-dessus.

Les relations {{math|(''a'')}} expriment l'''admissibilité duale'' et la première de ces relations est le gradient en {{mvar|x}} du '''lagrangien''' du problème, qui est la fonction
<center>
<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>
</center>
Les relations {{math|(''b'')}} expriment l'''admissibilité primale'' et la relation {{math|(''c'')}} exprime la ''complémentarité'' existant entre les variables primales {{mvar|x}} et leurs multiplicateurs {{mvar|s}} : {{mvar|x{{ind|i}}}} ou {{mvar|s{{ind|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 {{mvar|s}}, les conditions d'optimalité peuvent s'écrire sous la forme de problème de [[complémentarité linéaire]] avec contrainte linéaire :
<center><math>
\left\{\begin{array}{l}
Ax = b \\
0\leqslant x \perp (c-A^{\top\!}  y)\geqslant 0.
\end{array}\right.
</math></center>

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.

{{Théorème|Produit cartésien des solutions|L'ensemble des solutions primales-duales est un [[produit cartésien]] :
<center>
<math>
\mathcal{S}_{PD}=\mathcal{S}_{P}\times\mathcal{S}_{D}.
</math>
</center>
Autrement dit, si {{math|(''x''{{exp|1}}, ''y''{{exp|1}}, ''s''{{exp|1}})}} et {{math|(''x''{{exp|2}}, ''y''{{exp|2}}, ''s''{{exp|2}})}} sont des solutions primales-duales, alors {{math|(''x''{{exp|1}}, ''y''{{exp|2}}, ''s''{{exp|2}})}} est aussi une solution primale-duale.}}

==== Solution strictement complémentaire ====

Revenons sur les conditions de complémentarité, la condition {{math|(''c'')}} du système d'optimalité. Cette condition s'écrit
<center>
<math>
\sum_{i=1}^n\,x_is_i=0.
</math>
</center>
Comme {{mvar|x}} et {{mvar|s}} ont leurs composantes positives, cela revient au même d'écrire
<center>
<math>
\forall\,i\in\{1,\ldots,n\} :\quad x_is_i=0
</math>
</center>
ou encore
<center>
<math>
\forall\,i\in\{1,\ldots,n\} :\qquad x_i>0\quad\Longrightarrow\quad s_i=0.
</math>
</center>
Ceci n'implique pas que {{math|''s{{ind|i}}'' > 0}} lorsque {{math|''x{{ind|i}}'' {{=}} 0}}.

Une solution primale-duale {{math|(''x'',''y'',''s'')}} est dite '''strictement complémentaire''', si
<center>
<math>
\forall\,i\in\{1,\ldots,n\} :\qquad x_i>0\quad\Longleftrightarrow\quad s_i=0.
</math>
</center>
Un problème d'optimisation linéaire avec solution a toujours une solution primale-duale strictement complémentaire. On note
<center>
<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>
</center>

{{Théorème|Solution primale-duale strictement complémentaire|Si le problème {{math|(''P{{ind|L}}'')}} a une solution, alors il a une solution primale-duale strictement complémentaire. Cette affirmation revient à dire que {{math|(''B'',''N'')}} forme une partition de <math>[\![1,n]\!]</math> :<br /><br /><center><math>B\cap N=\varnothing\quad\mbox{et}\quad B\cup N=[\![1,n]\!].</math><br /><br /></center>}}

=== Dualité lagrangienne ===
{{article détaillé|Dualité (optimisation)}}
==== 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 {{math|(''P{{ind|L}}'')}}, la dualisation lagrangienne conduit au '''problème dual standard''' suivant
{{ancre|probleme-dual}}
{{Bloc emphase|espacement=1.5ex|<math>
(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.
</math>}}
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
<center>
<math>
\operatorname{val}(D_L)=\sup_{A^{\top\!}y\leqslant c}\;b^{\top\!}y
</math>
</center>
la valeur optimale de {{math|(''D{{ind|L}}'')}} et
<center>
<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>
</center>
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 {{math|(''P{{ind|L}}'')}}, qualifié ici de '''primal'''.

La première étape consiste à écrire le problème primal comme un {{math|inf sup}}. Par exemple, comme à <math>x\in\R^n</math> fixé
<center>
<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>
</center>
on a
<center>
<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>
</center>
L'égalité tient compte de la convention que l'infimum sur un [[ensemble vide]] vaut {{math|+∞}} ; donc, s'il n'y a pas de {{math|''x'' ≥ 0}} vérifiant {{math|''Ax'' {{=}} ''b''}}, on trouvera {{math|+∞}} dans les deux membres. On a ainsi écrit le problème primal comme un {{math|inf sup}} (on enlève les parenthèses, en gardant à l'esprit que la signification à donner à cet {{math|inf sup}} est celle ci-dessus) :
<center>
<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>
</center>
On dit que l'on a ''dualisé la contrainte d'égalité'' {{math|''Ax'' {{=}} ''b''}}, 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
<center>
<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>
</center>
Il reste à l'interpréter. Commençons par le ''problème interne'' :
<center>
<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>
</center>
Comme, par convention, le supremum sur un ensemble vide vaut {{math|–∞}}, le problème dual s'écrit
<center>
<math>
(D_L)\quad
\sup_{A^{\top\!}y\leqslant c}\;b^{\top\!}y,
</math>
</center>
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 {{mvar|X}} et {{mvar|Y}}, on a
<center>
<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>
</center>
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.

{{Théorème|Dualité faible|<math>\operatorname{val}(D_L)\leqslant\operatorname{val}(P_L)</math>.}}

Dans le cas de l'optimisation linéaire, cette inégalité s'obtient par simple calcul : on prend un point {{mvar|x}} admissible primal, un point {{mvar|y}} 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 et borne inférieure|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.

{{ancre|saut-de-dualite}}
L'écart entre les valeurs optimales primale et duale est ce que l'on appelle le '''[[saut de dualité]]''' :
<center>
<math>
\mbox{saut de dualité}=\operatorname{val}(P_L)-\operatorname{val}(D_L).
</math>
</center>
On dit qu'''il n'y a pas de saut de dualité'' si {{math|val(''P{{ind|L}}'') {{=}} val(''D{{ind|L}}'')}}. En optimisation linéaire, il est rare d'avoir un saut de dualité. La seule possibilité est que l'on ait {{math|val(''P{{ind|L}}'') {{=}} +∞}} (i.e., le problème primal n'est pas réalisable ; par exemple si {{math|''A'' {{=}} 0}} et {{math|''b'' ≠ 0}}) et {{math|val(''D{{ind|L}}'') {{=}} –∞}} (i.e., le problème dual n'est pas réalisable ; par exemple si {{math|''A'' {{=}} 0}} 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.

{{ancre|dualite-forte}}
{{Théorème|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 <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.
<!--
Tous les problèmes d'optimisation linéaires peuvent s'écrire<ref>Les détails exacts des deux représentations varient beaucoup d'un ouvrage à l'autre</ref> sous la forme suivante :

<math>
\begin{array}{rrll}
\max z = & {}^tc\,x & &\\
     s.c & Ax   &\leqslant& b\\
         &  x   &\geqslant&0
\end{array}
</math>

où {{mvar|c}} et {{mvar|x}} sont des vecteurs de taille {{mvar|n}}, {{mvar|b}} un vecteur de taille {{mvar|m}}, et {{mvar|A}} une matrice de taille {{math|''m'' × ''n''}}. Si on désigne cette représentation sous le terme de ''forme primale'', on désigne alors sous le terme de ''forme duale'' le problème suivant :

<math>
\begin{array}{rrll}
\min w = & {}^tb\,y & &\\
     s.c & {}^tA\,y   &\geqslant& c\\
         &  y   &\geqslant&0
\end{array}
</math>

où {{mvar|A}}, {{mvar|b}} et {{mvar|c}} sont les mêmes et {{mvar|y}} un vecteur de taille {{mvar|m}}.

Les deux problèmes sont très fortement liés. Si l'un d'entre eux possède une solution, alors l'autre aussi. De plus, les deux solutions ont alors la même valeur ({{math|''w''{{exp|*}} {{=}} ''z''{{exp|*}}}}). Si l'un d'entre eux est non-borné, l'autre ne possède pas de solution.

Outre son intérêt théorique, le problème dual possède de très intéressantes applications économiques. À chaque contrainte primale correspond une variable duale. La valeur de cette variable dans la solution représente le [[coût marginal]] associé à la contrainte primale.
-->

== Algorithmes ==

=== Algorithme du simplexe ===
{{article détaillé|Algorithme du simplexe}}
L'[[algorithme du simplexe]], développé par [[George Dantzig|Dantzig]] à partir de 1947<ref name="dantzig">{{Chapitre|langue=en|auteur1=G. B. Dantzig|titre chapitre=Maximization of a linear function of variables subject to linear inequalities|auteurs ouvrage=T. C. Koopmans|titre ouvrage=Activity Analysis of Production and Allocation|lieu=New York|éditeur=[[Wiley]]|année=1951|passage=339–347}}.</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 [[#Existence de solution|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 {{math|2{{exp|''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 [[Méthodes de points intérieurs|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é ''[[Complexité en moyenne des algorithmes|en moyenne]]'', pour des données distribuées aléatoirement suivant diverses [[Loi de probabilité|lois de probabilité]] ; voir Borgwardt (1982, 1987), Smale (1983), Megiddo (1987), Sharmir (1987).
<!--
L'[[algorithme du simplexe]] permet de résoudre les problèmes d'OL en construisant tout d'abord une solution réalisable qui est un sommet du polytope puis en se déplaçant selon les arêtes du polytope pour atteindre des sommets pour lesquels la valeur de l'objectif est de plus en plus grande, jusqu'à atteindre l'optimum. Bien que cet algorithme soit efficace en pratique et qu'il soit assuré de trouver l'optimum, son comportement dans le pire cas peut être mauvais. Il est ainsi possible de construire un problème d'OL pour lequel la méthode du simplexe requiert un nombre d'étapes exponentiel en la taille du problème. Ainsi, pendant plusieurs années, savoir si la classe des problèmes d'OL était un problème [[Théorie de la complexité des algorithmes#Classes de complexité|NP-complet]] ou [[Théorie de la complexité des algorithmes#Classes de complexité|polynomial]] est resté une question ouverte.
-->

=== Algorithmes de points intérieurs ===
{{article détaillé|Méthodes 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]]{{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 d'un convexe|intérieur relatif]] de l'ensemble admissible. Une des méthodes les plus couramment mises en œuvre est l'[[Méthodes prédicteur-correcteur|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.

{| class="wikitable" align="center" style="text-align:center; width:90%;"
|+ Comparaison des algorithmes du simplexe et de points intérieurs
|-
|
! scope=col | Simplexe
! scope=col | Points intérieurs
|-
| Auteur-initiateur
| [[George Dantzig|Dantzig]] (vers 1947)
| [[Narendra Karmarkar|Karmarkar]] (1984)
|-
| Concept de base
| [[Sommet (géométrie)|sommet]] d'un polyèdre convexe
| chemin central
|-
| Itération
| d'un sommet à l'autre en suivant une [[Arête (géométrie)#Polyèdre|arête]]
| d'un voisinage d'un point central à l'autre par un [[Méthode de Newton|pas de Newton]]
|-
| Type de convergence
| finie
| infinie
|-
| Polynomialité
| probablement non polynomial, polynomial [[Complexité en moyenne des algorithmes|en moyenne]]
| polynomial : convergence à {{math|''ε'' > 0}} près en {{math|''O''(''n''{{exp|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{{Lesquels}}{{Référence nécessaire|date=16 novembre 2018}} 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 {{Lien|fr=Dantzig–Wolfe decomposition|lang=en|texte=décomposition de Dantzig-Wolfe}} ou la « [[génération de colonnes]] » ou [[Méthode des plans sécants|méthodes des plans sécants]], interprétable comme de la [[relaxation lagrangienne]].
<!-- Les commentaires ci-dessous me semblent trop généraux pour être vraiment utiles. -->
<!--
=== Implémentations ===

Pour la résolution pratique de problèmes d'optimisation linéaire ordinaires, il est commun de considérer comme équivalents les (bons) codes basés sur les méthodes dérivées du simplexe ou de [[Méthodes de points intérieurs|points intérieurs]]. De plus, pour la résolution de problèmes de grande taille, une technique comme la [[génération de colonnes]] peut se révéler extrêmement efficace.

Les solveurs d'OL sont de plus en plus utilisés pour l'optimisation de divers problèmes industriels tels que l'optimisation des flux de transports ou la planification de la production. Toutefois, les modèles d'optimisation linéaire se révèlent insuffisants pour représenter de nombreux problèmes. Une extension possible est alors l''''optimisation linéaire en nombres entiers'', qui permet de modéliser un grand nombre de problèmes supplémentaires, notamment les problèmes [[NP-complet]]s.

On retrouve des solveurs d'OL dans de nombreux outils comme MATLAB, SAGE ou Excel.
-->
<!-- Plus utile. Des renvois sont faits.-->
<!--
== Optimisation linéaire en nombres entiers ==

{{article détaillé|Optimisation linéaire en nombres entiers}}

Un ''problème d'optimisation linéaire en nombres entiers'' (''OLNE'') 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 [[Théorie de la complexité des algorithmes#Réduction de problèmes|NP-complet]] car de nombreux problèmes NP-complets peuvent être exprimés comme des problèmes d'OLNE (par exemple trouver un [[Stable (théorie des graphes)|stable]] dans un [[Théorie des graphes|graphe]] {{math|''G'' {{=}} (''V'',''E'')}} revient à trouver un vecteur {{math|''x'' ∈ {0,1}{{exp|''E''}}}}  satisfaisant <math> x_u +x_v \le 1 </math> pour tout arête <math> uv  \in E </math>). 

Les algorithmes décrits ci-dessus pour l'OL ne résolvent donc pas les problèmes d'OLNE : en général la solution optimale n'est pas entière. Cependant l'OL joue un rôle crucial quant à la résolution des problèmes d'OLNE, 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 inférieure sur la valeur optimale du problème. 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, [[László Lovász|Lovasz]] et Schrijver permet de résoudre en pratique par l'OL les problèmes entiers dont on connait une ''bonne'' description polyédrique (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 (commerce)|distribution]] dans des [[réseau]]x) que dans les secteurs d'industrie : [[industrie manufacturière]], [[énergie]] ([[pétrole]], [[gaz]], [[électricité]], [[Industrie nucléaire|nucléaire]]), [[transport]]s (aériens, routiers et ferroviaires), [[télécommunication]]s, industrie forestière, [[finance]].

== Logiciels ==

* {{en}} [http://www.aimms.com/operations-research/mathematical-programming/linear-programming AIMMS Optimization Modeling] [[AIMMS]] — include linear programming in industry solutions (free trial license available);
* {{en}} [http://www.cgal.org/Pkg/QPSolver CGAL] — The [[Computational Geometry Algorithms Library]] includes a linear solver, which is exact and optimized for problems with few constraints or few variables
* {{en}} [http://www.coin-or.org/ COIN-OR] — COmputational INfrastructure for Operations Research, open-source library
* {{en}} [http://www.ilog.com/products/cplex Cplex] — Commercial library for linear programming
* {{en}} [http://www.vanguardsw.com/products/vanguard-system/add-ins/optimization/ Vanguard System Linear Programming Optimization Add-In]
* {{en}} [http://www.gnu.org/software/glpk/glpk.html GNU Linear Programming Kit], Bibliothèque libre {{Lien|fr=GLPK|lang=en}} pour l'optimisation linéaire, méthode du simplex, de points intérieurs, …
* {{en}} [http://www.optimalon.com/ GIPALS] — Linear programming environment and [[Dynamic Link Library|dynamic link library]] (DLL)
* {{en}} [http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html HOPDM] — Higher Order Primal Dual Method
* {{en}} [http://www.lindo.com/ LINDO] — LP, IP, Global solver/modeling langage
* {{en}} [http://sourceforge.net/projects/lipside/ LiPS] — Free easy-to-use program intended for solving linear, integer and goal programming problems.
* {{en}} {{lien brisé|url=ftp://garbo.uwasa.fi/pc/ts/tslin35c.zip |titre=Linear programming and linear goal programming }} A [[freeware]] program for MS-DOS
* {{en}} [http://www.mosek.com/ MOSEK] — Optimization software for LP, IP, QP, SOCP and MIP. Free trial is available. Free for students.
* {{en}} [http://www.wolfram.com/ Mathematica] — General technical computing system includes large scale linear programming support
* {{en}} [http://mips.gsf.de/proj/mdcs Microarray Data Classification Server (MDCS)] based on linear programming
* {{en}} [http://www.ateji.com/optimj.html 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}} [http://staff.feweb.vu.nl/tijms/ Orstat2000] — Includes easy-to-use modules for linear and integer programming (free for educational purposes).
* {{en}} [http://www.solver.com/ Premium Solver] — Spreadsheet add-in
* {{en}} [http://www2.isye.gatech.edu/~wcook/qsopt/ QSopt] Optimization software for LP (free for research purposes).
* {{en}} [http://stat.ethz.ch/CRAN/index.html R] [[Logiciel libre]] de calcul [[statistique]] contenant des librairies additionnelles pour l'OL: glpk, linprog (simplex), Rglpk (interface R pour [[GPLK]])
* {{fr}} [[Scilab]] dispose de la commande <code>[[wikibooks:fr:Découvrir_Scilab/Calcul_numérique#Optimisation linéaire|karmarkar()]]</code> permettant de résoudre un problème d'optimisation linéaire par l'algorithme de Karmarkar.
* {{en}} [http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/simplex.html Simplex Method Tool] A quick-loading web page
* {{en}} [http://www.lindo.com/ What's Best!] — Spreadsheet add-in
* {{en}} [http://www.dashoptimization.com/ Xpress-MP] — Optimization software free to students
* {{fr}} [[IMSL]] — développements pour [[Fortran]], C/C++, Java et C#
* {{en}} [http://www.gurobi.com/ 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 ===
{{références|groupe=note}}

=== Références ===
{{références}}

== Annexes ==
{{Autres projets
  | wikiversity = Programmation linéaire
  | wikiversity titre = Programmation linéaire
}}

=== 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|Référence:Optimisation (Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006)}}
* {{en}} [[Karl Heinz Borgwardt|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.

=== 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 ===
* {{en}} J. E. Beasley. [http://people.brunel.ac.uk/~mastjjb/jeb/or/lp.html Guidance on Formulating LP problems].
* {{en}} R. Freund. {{Lien brisé|url=http://www.stanford.edu/group/SOL/dantzig.html|titre=George Dantzig}}.
* J. Ch. Gilbert, ''[https://hal.science/hal-03347060 Fragments d'Optimisation Différentiable — Théorie et Algorithmes]'', [[syllabus (enseignement)|syllabus de cours]] à l'[[École nationale supérieure de techniques avancées|ENSTA ParisTech]], Paris.
* {{en}} A. Hosein. [http://prejudice.tripod.com/ME30B/index.htm Linear Programming: Guide to Formulation, Simplex Algorithm, Goal Programming and Excel Solver examples].
* {{en}} [[IBM]]. {{Lien brisé|url=http://www-128.ibm.com/developerworks/linux/library/l-glpk1/index.html|titre=IBM's article on GLPK}}. Un article technique sur {{Lien|fr=GLPK|lang=en}} avec une introduction à l'optimisation linéaire.
* {{en}} H. Mittelmann. [http://plato.asu.edu/ftp/milpf.html Benchmark de différents logiciels sur différentes instances de problèmes d'OLNE].
* {{en}} Site NEOS. {{lien brisé|consulté le=2013-11-07|url=http://www.neos-guide.org/NEOS/index.php/Linear_Programming_Directory|titre=Linear Programming Directory}}.
* {{en}} ORMS. {{Lien brisé|url=http://www.lionhrtpub.com/orms/surveys/LP/LP-survey.html|titre=Linear Programming Software Survey}}.
* {{en}} M. A. Trick. {{Lien brisé|url=http://mat.gsia.cmu.edu/orclass/integer/integer.html|titre=A Tutorial on Integer Programming}}.
* {{en}} R. Vanderbei. [http://www.princeton.edu/~rvdb/LPbook ''Linear Programming: Foundations and Extensions''].
* {{en}} K. Xu. {{Lien brisé|url=http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/pb-benchmarks.htm|titre=0-1 Integer Programming Benchmarks with Hidden Optimum Solutions}}.

{{Palette|optimisation|Convexité}}
{{Portail|mathématiques|Informatique théorique}}

[[Catégorie:Optimisation]]
[[Catégorie:Recherche opérationnelle]]
[[Catégorie:Optimisation combinatoire]]