Le lemme de Farkas : résultat clé en théorie des systèmes linéaires

Le lemme de Farkas est un résultat clé en théorie des systèmes linéaires et en programmation linéaire. Il a été formulé par le mathématicien hongrois Gyula Farkas au début du 20e siècle. Le concept établit une relation entre l'existence de solutions d'un système d'inégalités linéaires et l'impossibilité de trouver une solution d'un système d'équations linéaires lié.

Formellement, le lemme de Farkas s'énonce comme suit :

Considérons un système linéaire $Ax\le b$, où $A$ est une matrice $m\times n$, $x$ est un vecteur $n\times 1$ et $b$ est un vecteur $m\times 1$. Le lemme de Farkas affirme que l'une des deux assertions suivantes est vraie :

1. Il existe un vecteur $x$ qui satisfait le système d'inégalités linéaires $Ax\le b$.

2. Il existe un vecteur $y$ tel que $A^{T}y=0$ (le système d'équations linéaires associé) et (b^T y < 0.

En d'autres termes, soit on peut trouver une solution au système d'inégalités linéaires, soit on peut prouver qu'une solution au système d'équations linéaires n'existe pas et qu'il existe un vecteur $y$ qui montre cette impossibilité.

Le lemme de Farkas a des applications importantes en programmation linéaire et en théorie de l'optimisation. Il est utilisé pour formuler et résoudre des problèmes d'optimisation linéaire sous forme canonique, où l'objectif est de maximiser ou minimiser une fonction linéaire sous des contraintes linéaires.

En utilisant ce concept, il est possible de déterminer si un problème d'optimisation linéaire est réalisable (c'est-à-dire s'il existe une solution) ou s'il est non réalisable (c'est-à-dire qu'il n'existe aucune solution).

En outre, le lemme de Farkas a des implications profondes en théorie des nombres et en géométrie convexe. Il peut être utilisé pour prouver des résultats tels que le théorème de séparation de Hahn-Banach, qui est un résultat fondamental en analyse fonctionnelle.