Lemme de Farkas

Pour chaque colonne C_j de A (1 ≤ j ≤ k), notons f_j la forme linéaire définie sur Rⁿ par ${\displaystyle y\mapsto (^{\operatorname {t} }\!C_{j})y}$ ; notons par ailleurs g la forme linéaire ${\displaystyle y\mapsto (^{\operatorname {t} }\!b)y}$.

L'existence d'une solution pour la première branche de l'alternative, c'est l'existence d'un k-uplet ${\displaystyle (x_{1},\ldots ,x_{k})}$ de nombres positifs ou nuls tels que ${\displaystyle x_{1}C_{1}+\cdots +x_{k}C_{k}=b}$, autrement dit c'est la possibilité d'écrire g comme combinaison linéaire à coefficients positifs des f_j.

L'existence d'une solution pour la deuxième branche de l'alternative, c'est l'existence d'un y qui soit dans ${\displaystyle \{y\in E\,\mid \,f_{1}(y)\geq 0,\cdots ,f_{k}(y)\geq 0\}}$ mais qui ne soit pas dans ${\displaystyle \{y\in E\,\mid \,g(y)\geq 0\}}$.

L'équivalence annoncée par le théorème de Farkas garantit donc précisément qu'un et un seul des deux systèmes a une solution.

L'implication montante est évidente, montrons l'autre. On suppose donc ${\displaystyle \{y\in E\,\mid \,f_{1}(y)\geq 0,\ldots ,f_{k}(y)\geq 0\}}$ vide.

Introduisons un espace vectoriel Ê dans lequel E est un sous-espace affine de codimension 1 ne passant pas par l'origine. Toute forme affine sur E se prolonge d'une façon unique en une forme linéaire sur Ê. Notons ${\displaystyle {\hat {f}}_{j}}$ le prolongement linéaire de ${\displaystyle f_{j}}$ (1 ≤ j ≤ k) et ${\displaystyle {\hat {g}}}$ le prolongement de la constante -1, de sorte que E a pour équation ${\displaystyle {\hat {g}}(y)=-1}$ dans Ê. L'hypothèse revient à dire que si un point y de Ê vérifie les conditions ${\displaystyle {\hat {f}}_{1}(y)\geq 0,\cdots ,{\hat {f}}_{k}(y)\geq 0}$, il ne vérifie pas la condition ${\displaystyle {\hat {g}}(y)=-1}$. En jouant avec les homothéties de rapport strictement positif, il est immédiat qu'il ne peut pas non plus vérifier ${\displaystyle {\hat {g}}(y)=-c}$ pour un autre niveau strictement négatif. En d'autres termes l'ensemble ${\displaystyle \{y\in {\hat {E}}\,\mid \,{\hat {f}}_{1}(y)\geq 0,\cdots ,{\hat {f}}_{k}(y)\geq 0\}}$ est inclus dans l'ensemble ${\displaystyle \{y\in {\hat {E}}\,\mid \,{\hat {g}}(y)\geq 0\}}$. On applique alors Farkas et on en déduit que ${\displaystyle {\hat {g}}}$ est une combinaison linéaire à coefficients positifs des ${\displaystyle {\hat {f}}_{j}}$. Il n'y a plus qu'à restreindre à E la relation obtenue.

Comme dans la démonstration précédente l'implication montante est évidente. On montre l'autre, en supposant tout d'abord que ${\displaystyle \{y\in E\,\mid \,f_{1}(y)\geq 0,\ldots ,f_{k}(y)\geq 0\}\subset \{y\in E\,\mid \,g(y)\geq 0\}}$. On note de nouveau Ê un espace vectoriel dont E est un sous-espace affine de codimension 1 ne passant pas par l'origine, ${\displaystyle {\hat {f}}_{j}}$ l'extension linéaire de ${\displaystyle f_{j}}$ à cet espace, et naturellement ${\displaystyle {\hat {g}}}$ l'extension linéaire de ${\displaystyle g}$ à cet espace. On note cette fois ${\displaystyle h}$ la forme affine valant constamment 1 sur E et ${\displaystyle {\hat {h}}}$ son extension linéaire à Ê. On vérifie ensuite que :

${\displaystyle \{y\in {\hat {E}}\,\mid \,{\hat {f}}_{1}(y)\geq 0,\ldots ,{\hat {f}}_{k}(y)\geq 0,{\hat {h}}(y)\geq 0\}\subset \{y\in E\,\mid \,{\hat {g}}(y)\geq 0\}}$ :

pour un point y de l'ensemble de gauche, on discute selon la valeur de ${\displaystyle {\hat {h}}(y)}$ qui est supposé positif ou nul :

• si ${\displaystyle {\hat {h}}(y)=1}$, c'est qu'on est dans E et l'appartenance à l'ensemble de droite est assurée par l'hypothèse ;
• plus généralement, si ${\displaystyle {\hat {h}}(y)>0}$, on se ramène au cas précédent par homothétie de rapport strictement positif ;
• si ${\displaystyle {\hat {h}}(y)=0}$, on a besoin de l'hypothèse de consistance du système initial. On prend un point auxiliaire ${\displaystyle z\in E}$ vérifiant ce système, et on se dirige de z vers y le long du segment [ z, y [ : tout au long du voyage, les ${\displaystyle {\hat {f}}_{j}}$ gardent toutes des valeurs positives ou nulles tandis que ${\displaystyle {\hat {h}}}$ reste à valeurs strictement positives ; le cas précédent assure donc que ${\displaystyle {\hat {g}}}$ est lui aussi à valeurs positives ou nulles sur le segment. On conclut alors que ${\displaystyle {\hat {g}}(y)\geq 0}$ par passage à la limite.

Il ne reste plus qu'à appliquer le lemme de Farkas dans sa version vectorielle pour conclure que ${\displaystyle {\hat {g}}}$ est une combinaison linéaire à coefficients positifs des ${\displaystyle {\hat {f}}_{j}}$ et de ${\displaystyle {\hat {h}}}$ ; on termine en restreignant cette conclusion à E.