D. Avis et B. Kaluzny^* D. Avis & B. Kaluzny (2004). Solving inequalities and proving Farkas' lemma made easy. The American Mathematical Monthly, 2, 152-157. ont proposé une autre méthode qui se rapproche de la méthode canonique de la programmation linéaire. Soit le système d'inégalités :

où $\boldsymbol{A}$ est une matrice $m\times n$, $\boldsymbol{x}$ et $\boldsymbol{b}$ des vecteurs $n\times 1$. On introduit un vecteur $\boldsymbol{e}$ de variables d'écart non négatives ($\boldsymbol{e}\geq \boldsymbol{0}$) qui permettent de transformer l'inégalité en égalité, c'est-à-dire :

Un tel système s'appelle un dictionnaire. Les variables qui sont dans le membre de gauche de l'égalité (pour l'instant les $e_i$) sont appelées variables basiques. Les variables qui sont dans le membre de droite sont appelées variables hors-base. On remarque que toute solution positive du système d'égalités s'étend aisément au système initial d'inégalités.

Maintenant, de deux choses l'une, ou bien $\boldsymbol{b}> \boldsymbol{0}$, ce qui signifie que tous les éléments qui composent $\boldsymbol{b}$ sont positif, ou $\boldsymbol{b}$ est constitué d'éléments positifs ou nuls. Dans le premier cas, si on pose $\boldsymbol{x} = \boldsymbol{e} = \boldsymbol{0}$, l'inégalité est vérifiée trivialement puisque $\boldsymbol{0}= \boldsymbol{A}\boldsymbol{x} \leq \boldsymbol{b}$ et $\boldsymbol{x} = \boldsymbol{0}\geq \boldsymbol{0}$. Dans le second cas, on a une solution immédiate : $\boldsymbol{e} = \boldsymbol{b}$ et $\boldsymbol{x} = \boldsymbol{0}$. Elle n'est pas admissible puisque dans ce cas, tous les $e_i$ ne sont pas positifs. L'algorithme suggérée par D. Avis et B. Kaluzny^* D. Avis & B. Kaluzny (2004). Solving inequalities and proving Farkas' lemma made easy. The American Mathematical Monthly, 2, 152-157. consiste à  sauter de solutions irréalisables voisines jusqu'à  ce qu'éventuellement, si le système est solvable, on aboutisse sur une solution réalisable (on dit encore faisable). On commence par unifier les indices de telle sorte à  ce que : \[ i = \underbrace{1, 2, \ldots, n}_{x_i}, \underbrace{n+1,n+2,\ldots, 2n}_{e_i} \]

Ainsi, quand on parle des indices, toutes les variables sont confondues (quand on parle du plus petit indice, il s'agit conjointement des indices des $x_i$ et des $e_i$). L'algorithme proposé est le suivant (on le nomme la Règle-b) :

Considérons l'exemple suivant emprunté à l'article d'Avis et Kaluzni :

On commence par transformer ce système en égalités^! On doit faire attention à  l'effet de présentation qui est lié à  l'isolation des variables et qui force à  inverser le signe des coefficients associés aux variables hors base.}

La solution $\begin{bmatrix}e_4 & e_5 & e_6\end{bmatrix}^\top = \begin{bmatrix}-1 & 2 & -2\end{bmatrix}^\top, \begin{bmatrix}x_1 & x_2 & x_3\end{bmatrix}^\top = \begin{bmatrix}0 & 0 & 0\end{bmatrix}^\top$ n'est pas faisable puisque $e_1$ et $e_3$ prennent des valeurs négatives. Considérons la quand même. Comme dans ce cas, $e_4$ est la variable de base ayant le plus petit indice prenant une valeur négative et comme, dans cette équation, $x_1$ est la variable hors base ayant le plus petit indice associé à  un coefficient positif, on résout cette équation en $x_1$, ce qui donne :

Par substitution dans la seconde équation, on obtient :

et

ce qui donne le système :

Il n'est pas possible de s'arrêter là , car la solution $\begin{bmatrix}e_4 & e_5 & e_6\end{bmatrix}^\top = \begin{bmatrix}0 & 1 & -1\end{bmatrix}^\top$, $\begin{bmatrix}x_1 & x_2 & x_3\end{bmatrix}^\top = \begin{bmatrix}1 & 0 & 0\end{bmatrix}^\top$ n'est pas faisable puisque $e_6 = -1.$ Donc, on réitère. La variable de base prenant une valeur négative ayant le plus petit indice est $e_6$. Dans l'équation qui définit $e_6$, la variable hors base dont le coefficient est positif ayant le plus petit indice est $e_4$. On fait entrer $e_4$ dans la base et sortir $e_6$, soit :

Par substitution, on obtient :

et

ce qui donne le système suivant :

Nous pouvons nous arrêter là. En effet, en fixant les variables de bases à  $x_1$, $e_5$ et $e_4$, l'attribution des valeurs $\begin{bmatrix}e_4 & e_5 & e_6\end{bmatrix}^\top = \begin{bmatrix}1 & 0 & 0\end{bmatrix}^\top$, $\begin{bmatrix}x_1 & x_2 & x_3\end{bmatrix}^\top = \begin{bmatrix}2 & 0 & 0\end{bmatrix}^\top$ donne une solution faisable. Il existe donc bien une solution au problème.

Appliquons la méthode au système :

encore une fois emprunté à  D. Avis et B. Kaluzny. Commençons par introduire les variables d'écart $e_4$, $e_5$ et $e_7$.

Comme précédemment des valeurs $\begin{bmatrix}e_4 & e_5 & e_6\end{bmatrix}^\top = \begin{bmatrix}3& -17 & 19\end{bmatrix}^\top$, $\begin{bmatrix}x_1 & x_2 & x_3\end{bmatrix}^\top = \begin{bmatrix}0 & 0 & 0\end{bmatrix}^\top$ ne constituent pas une solution faisable du fait que $e_5$ prend une valeur négative. Comme $x_2$ a un coefficient positif, il rentre dans la base, ce qui donne :

Par substitution, on a :

et

Ainsi, on a le système :

mais la solution $\begin{bmatrix}e_4 & e_5 & e_6\end{bmatrix}^\top = \begin{bmatrix}-14& 0 & 70\end{bmatrix}^\top$, $\begin{bmatrix}x_1 & x_2 & x_3\end{bmatrix}^\top = \begin{bmatrix}0 & 17/2 & 0\end{bmatrix}^\top$ n'est pas plus acceptable puisque $e_4 \leq 0$. Il serait donc bien venu de sortir $e_4$ de la base mais, cette fois, on ne sait comment faire puisque tous les coefficients du membre de droite de l'équation de $e_4$ sont négatifs. Cette équation est inconsistante dans la mesure où $e_4 \geq 0$, $x_1 \geq0$, $x_3 \geq 0$ et $e_5 \geq0$. Elle ne peut donc être satisfaite :

Étant donnée la simplicité de cet algorithme, il est particulièrement intéressant de montrer ses propriétés :

1. il s'arrête après un nombre fini de pas.
2. S'il termine à  l'étape ⑦ de sa description de la règle-b, la solution de base proposée est faisable.
3. s'il termine à  l'étape ④, elle est infaisable.

Pour discuter de ces propriétés, nous allons simplifier les notations en notant les variables d'écart comme les variables initiales (i.e. : $e_i= x_i$, $i = n+1, \ldots, n+m$). Par définition, le système qui doit être analysé comporte $m$ inégalités et $n$ variables. Après transformation en système d'égalités, il comporte toujours $m$ inégalités mais, cette fois, il a $n+m$ variables. Au plus a-t-il donc $\complement_{n+m}^n$ vecteurs candidats pour constituer une base. Si l'algorithme ne s'arrête pas en un nombre fini de pas, c'est donc qu'après avoir exploré toutes les bases potentielles, il revient sur une base déjà  explorée. En d'autres termes, il cycle.

Supposons que le système analysé cycle. Puisque toutes les variables entrent un moment donné dans la base, considérons la dernière $x_{n+m}$. Au moment où elle entre dans la base, une des équations doit être du type :

Précisons : $k\in \mathcal{B}$, où $\mathcal{B}$ est l'ensemble des variables de base au moment du choix de $x_{n+m}$ comme variable entrante et $\mathcal{N}$ est l'ensemble des variables qui ne sont pas dans la base. Puisque $x_k$ va sortir, $-b^\prime_k< 0$. Puisque $x_{n+m}$ entre, elle doit posséder l'indice le plus petit associé à  un coefficient strictement positif. Donc pour tout $j\in \mathcal{N}/\{n+m\}$, on doit avoir $-a^\prime_{jk}\leq0$ et $a^\prime_{j{n+m}} >0$. En particulier, ceci montre que toute solution du système d'équations pour laquelle $x_1\geq 0,\ldots x_{n+m-1} \geq 0$ doit vérifier $x_{n+m} > 0$.

Maintenant, considérons le cas où $x_{n+m}$ vas être choisit pour quitter la base. On doit avoir :

Puisque $x_{n+m}$ doit sortir, on a nécessairement $b^\prime _i \geq 0$ pour tout $i \in \mathcal{B}\setminus \{n+m\}$ et $-b^\prime_{n+m}< 0$. Si l'on fixe les variables hors base à  $0$ (pour tout $i \in \mathcal{B}\setminus \{n+m\}$, $x_i = 0$, le système d'équations \eqref{eq:sample}-\eqref{eq:sample} montre qu'il existe une solution telle que $x_1\geq 0, \ldots x_{n+m -1}\geq 0$ et $x_{n+m} < 0$. Mais, ceci contredit ce qui a été montré à  partir de l'équation~\ref{ak1}. Il n'est donc pas possible que l'algorithme cycle sur la variable $x_{n+m}$.

Maintenant, supposons qu'il existe un cycle dans lequel $x_{n+m}$ demeure toujours dans la base. On peut donc retirer l'équation correspondant à  $x_{n+m}$ sans changer les valeurs des pivots durant le cycle et il en va de même si pendant le cycle $x_{n+m}$ demeure toujours une variable hors base. Dans les deux cas, on peut réduire le système en éliminant une contrainte et redémarrer le raisonnement initial sur le nouveau système et ainsi de suite. Ceci montre que l'algorithme est bien fini (i.e. : stoppe après un nombre fini de pas).

Puisque $x_{n+m}$ doit sortir, on a nécessairement $b^\prime _i \geq 0$ pour tout $i \in \mathcal{B}\setminus \{n+m\}$ et $-b^\prime_{n+m}< 0$. Si l'on fixe les variables hors base à  $0$ (pour tout $i \in \mathcal{B}\setminus \{n+m\}$, $x_i = 0$, le système d'équations \ref{ak2}-\ref{ak3} montre qu'il existe une solution telle que $x_1\geq 0, \ldots x_{n+m -1}\geq 0$ et $x_{n+m} < 0$). Mais, ceci contredit ce qui a été montré à  partir de l'équation~\ref{ak1}. Il n'est donc pas possible que l'algorithme cycle sur la variable $x_{n+m}$.

Maintenant, supposons qu'il existe un cycle dans lequel $x_{n+m}$ demeure toujours dans la base. On peut donc retirer l'équation correspondant à  $x_{n+m}$ sans changer les valeurs des pivots durant le cycle et il en va de même si pendant le cycle $x_{n+m}$ demeure toujours une variable hors base. Dans les deux cas, on peut réduire le système en éliminant une contrainte et redémarrer le raisonnement initial sur le nouveau système et ainsi de suite. Ceci montre que l'algorithme est bien fini (i.e. : stoppe après un nombre de pas fini).

Par conséquent, l'algorithme soit s'arrête par ce qu'il a trouvé une solution, soit parce qu'il donne un certificat d'infaisabilité.

En terme générique, la finitude de l'algorithme donne une démonstration simple du lemme de Farkas, qui est généralement démontré à l'aide de l'élimination de Fourier-Motzkin.

Montrer, en appliquant la méthode d'Avis et Kaluzni, que le système suivant est infaisable :

👈 ☝ 👉