14.6 Systèmes d’inéquations linéaires

Dans cette section, nous montrons que l’on peut utiliser les méthodes pour des systèmes linéaires afin de résoudre des systèmes d’inéquations linéaires.

Soient $\mathbf{A} \in \mathbb{R}^{m \times n}$ et $\mathbf{b} \in \mathbb{R}^m$. Supposons que l’on cherche à déterminer si le système $$\begin{equation*} \mathbf{A}\mathbf{x} \geq \mathbf{b}. \end{equation*}$$ admet une solution, ce qui n’est le cas que si et seulement si le système suivant possède lui-même une solution : $$\begin{align*} \mathbf{A}\mathbf{x} - \mathbf{I}_m\mathbf{s} & = \mathbf{b} \\ \mathbf{s} & \geq \mathbf{0}. \end{align*}$$ En réécrivant $\mathbf{x}$ sous la forme $\mathbf{u}-\mathbf{v}$, où $\mathbf{u},\mathbf{v} \in \mathbb{R}^n$ avec $\mathbf{u},\mathbf{v}\geq \mathbf{0}$, nous obtenons le système équivalent $$\begin{align*} \mathbf{A}\mathbf{u} - \mathbf{A}\mathbf{v} - \mathbf{I}_m \mathbf{s} & = \mathbf{b} \\ \mathbf{u}, \mathbf{v}, \mathbf{s} & \geq \mathbf{0}. \end{align*}$$ Par conséquent, nous pouvons nous concentrer sur les systèmes de la forme $$\begin{align} \begin{split} \mathbf{A}\mathbf{x} & = \mathbf{b} \\ \mathbf{x} & \geq \mathbf{0}. \end{split}\tag{14.2} \end{align}$$ Nous avons donc un système d’équations linéaires pour lequel nous exigeons que les valeurs des variables soient non négatives.

On rappelle que si $\mathbf{A}\mathbf{x} = \mathbf{b}$ admet une solution, alors il existe une solution qui a au plus $m$ éléments non nuls puisque ${\operatorname{Col}({\mathbf{A}})}$ est de dimension au plus $ m$. Fait surprenant, la même chose peut être dite du système (14.2).

Proposition 14.1 Si (14.2) admet une solution, alors il existe une solution qui a au plus $m$ éléments positifs.

Démonstration. Soit $\mathbf{x}^*$ une solution de (14.2). Soit $J = \{ i \,:\,\mathbf{x}^*_i > 0\}$. On choisit $\mathbf{x}^*$ de façon à ce que $\lvert J \rvert$ soit aussi petit que possible.

Supposons que $\lvert J \rvert > m$. Alors les colonnes de $\mathbf{A}$, indicées par les éléments de $J,$ sont linéairement dépendantes. Il existe alors un vecteur non nul $\mathbf{d} \in \mathbb{R}^n$ tel que $\mathbf{A} \mathbf{d} = \mathbf{0}$ et $\mathbf{d}_j = 0$ pour tout $j \notin J$. On peut supposer qu’au moins un des éléments de $\mathbf{d}$ soit négatif. (Sinon, il suffit de prendre la réciproque additive de chacun des éléments de $\mathbf{d}$.) Soit $\lambda$ le nombre réel maximal tel que $\mathbf{x}^* + \lambda \mathbf{d} \geq \mathbf{0},$ et posons $\mathbf{x}' = \mathbf{x}^* + \lambda \mathbf{d}$. Alors, $\mathbf{x}'$ est une solution de (14.2) puisque $\mathbf{x}' \geq \mathbf{0}$ et $\mathbf{A}\mathbf{x}' = \mathbf{A}\mathbf{x}^* + \lambda \mathbf{A}\mathbf{d} = \mathbf{b}$. Cependant, $\mathbf{x}'$ a au moins une composante positive en moins que $\mathbf{x}^*,$ ce qui contredit notre choix de $\mathbf{x}^*.$

La proposition 14.1 nous suggère un algorithme naïf afin de résoudre (14.2) : on passe simplement en revue tous les sous-ensembles de colonnes de $\mathbf{A}$ formant une base de ${\operatorname{Col}({\mathbf{A}})}$ et on vérifie s’il existe une combinaison linéaire non négative qui donne $\mathbf{b}$.

Exemple 14.4 Soient $\mathbf{A} = \begin{bmatrix} 1 & 1 & 2 \\ -1 & 2 & 1 \end{bmatrix}$ et $\mathbf{b} = \begin{bmatrix} 0 \\ 3\end{bmatrix}.$

Notons que chaque paire de colonnes de $\mathbf{A}$ forme une base de ${\operatorname{Col}({\mathbf{A}})}.$ Nous avons donc les résultats suivants :

• l’unique combinaison linéaire de $\mathbf{A}_1$ et $\mathbf{A}_2$ donnant $\mathbf{b}$ est $-\mathbf{A}_1+\mathbf{A}_2$, qui n’est pas une combinaison linéaire non négative.

• l’unique combinaison linéaire de $\mathbf{A}_1$ et $\mathbf{A}_3$ donnant $\mathbf{b}$ est $-2\mathbf{A}_1+\mathbf{A}_3$, qui n’est pas une combinaison linéaire non négative.

• l’unique combinaison linéaire de $\mathbf{A}_2$ et $\mathbf{A}_3$ donnant $\mathbf{b}$ est $2\mathbf{A}_2-\mathbf{A}_3$, qui n’est pas une combinaison linéaire non négative.

Donc, $\mathbf{A}\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}$ n’admet pas de solution d’après la proposition 14.1.

Cette méthode est relativement inefficace. Nous aimerions au moins éliminer des choix de colonnes qui sont évidemment peu prometteurs.

Pour faciliter la discussion, supposons que le rang de $\mathbf{A}$ soit $m$. L’ensemble $B \subseteq \{1,\ldots,n\}$ est appelé une base de $\mathbf{A}$ si les colonnes de $\mathbf{A}$, indicées par les éléments de $B$, forment une base de $\mathbb{R}^m$. (« Base d’indices » serait sans doute une appellation plus appropriée, mais c’est quand même assez long à écrire. Par convention, dans la littérature sur l’optimisation, on appelle simplement un tel ensemble une base.) Pour une base $B$, $\mathbf{x}^*\in \mathbb{R}^n$ est une solution de base associée à $B$ si $\mathbf{A}\mathbf{x}^* = \mathbf{b}$ et $x^*_i = 0$ pour tout $i \notin B$.

On peut aussi effectuer une recherche plus systématique de la façon suivante : supposons que $B$ soit une base déterminant la solution de base $\mathbf{x}^*$, où $x^*_r < 0$ pour un $r \in B$ particulier. Nous pouvons créer une nouvelle base $B'$ en retirant l’indice $r$ et en ajoutant un nouvel indice $k$. On continue cette approche jusqu’à l’obtention d’une solution de base ne possédant que des éléments non négatifs.

Il y a un problème potentiel : cette approche peut ne jamais se terminer. En fait, en ne choisissant pas bien les indices $r$ et $k$, il est possible de se retrouver avec une base déjà rencontrée. On appelle un tel phénomène cyclage. Dans la section suivante, nous voyons qu’en choisissant les plus petits $r$ et $k$ à chaque reprise, l’algorithme devra nécessairement se terminer.

14.6.1 Trouver une solution de base admissible

Soient $\mathbf{A} \in \mathbb{R}^{m \times n}$ et $\mathbf{b} \in \mathbb{R}^m$. Supposons que $\mathbf{A}$ soit de rang $m.$ L’algorithme suivant va déterminer si $\mathbf{A}\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}$ admet une solution de base dont les éléments sont non négatifs que l’on appelle une une solution de base admissible.

Étapes :

1. Obtenir le système $\mathbf{A}'\mathbf{x} = \mathbf{b}'$, où $\mathbf{A}' = \mathbf{A}_B^{-1} \mathbf{A}$ et $\mathbf{b}' = \mathbf{A}_B^{-1}\mathbf{b}$, et la solution de base $\mathbf{x}'$ associée à $B$.

2. Si $\mathbf{b}' \geq \mathbf{0}$, retourner $B$ et s’arrêter. Sinon, chosir le plus petit indice $r$ tel que $x'_r < 0$.

3. Soit $\mathbf{a}^\mathsf{T}$ la ligne de $\mathbf{A}$ telle que $a_r = 1.$ Si $\mathbf{a} \geq \mathbf{0}$, alors signaler qu’il n’y a aucune solution et s’arrêter. Sinon, choisir le plus petit indice $k$ tel que $a_k < 0$.

4. Retirer $r$ de $B$, ajouter $k$ à $B$, et retourner à l’étape 1.

Le système $\mathbf{A}'\mathbf{x} = \mathbf{b}'$ de l’étape 1 est le tableau associé à $B$. Chaque équation de ce tableau prend la forme $$x_i + \sum_{j \notin B} \bar{a}_{ij} x_j = \beta_i,~\forall i \in B.$$ On appelle $x_i + \sum_{j \notin B} \bar{a}_{ij} x_j = \beta_i$ la rangée (du tableau) associée à $x_i$. Ainsi, pour chaque $i \in B$, $x'_i$ prend la valeur du côté droit de la rangée associée à $x_i$.

Avant d’analyser l’algorithme, nous présentons un exemple.

Supposons que l’on cherche une solution de $\mathbf{A}\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}$, où $\mathbf{A} = \begin{bmatrix} 1 & 1 & 1 & 0 & -1 \\ 0 & -1 & 0 & 2 & 1 \\ 3 & 3 & 2 & -1 & -2 \\ \end{bmatrix}$ et $\mathbf{b} = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}$. Puisque les trois premières colonnes de $\mathbf{A}$ sont linéairement indépendantes, nous pouvons débuter avec $B = \{1,2,3\}$.

Itération 1 :

1. Pour obtenir le tableau associé à $B = \{1,2,3\}$, nous n’avons pas besoin de calculer $\mathbf{A}_B^{-1}$ explicitement. Nous devons simplement réduire la matrice augmentée de $\mathbf{A}\mathbf{x} = \mathbf{b}$ de sorte que les colonnes indicées par les éléments de $B$ forment la matrice identité : $$\begin{align*} & \left[ \begin{array}{ccccc|c} 1 & 1 & 1 & 0 & -1 & 0 \\ 0 & -1 & 0 & 2 & 1 & 1 \\ 3 & 3 & 2 & -1 & -2 & 1 \end{array} \right] \\ \xrightarrow{L_3 \leftarrow L_3 - 3L_1} & \left[ \begin{array}{ccccc|c} 1 & 1 & 1 & 0 & -1 & 0 \\ 0 & -1 & 0 & 2 & 1 & 1 \\ 0 & 0 & -1 & -1 & 1 & 1 \end{array} \right] \\ \xrightarrow{L_1 \leftarrow L_1 + L_2} & \left[ \begin{array}{ccccc|c} 1 & 0 & 1 & 2 & 0 & 1 \\ 0 & -1 & 0 & 2 & 1 & 1 \\ 0 & 0 & -1 & -1 & 1 & 1 \\ \end{array} \right] \\ \xrightarrow{L_1 \leftarrow L_1 + L_3} & \left[ \begin{array}{ccccc|c} 1 & 0 & 0 & 1 & 1 & 2 \\ 0 & -1 & 0 & 2 & 1 & 1 \\ 0 & 0 & -1 & -1 & 1 & 1 \end{array} \right] \\ \xrightarrow{L_2 \leftarrow\, -L_2} & \left[ \begin{array}{ccccc|c} 1 & 0 & 0 & 1 & 1 & 2 \\ 0 & 1 & 0 & -2 & -1 & -1 \\ 0 & 0 & -1 & -1 & 1 & 1 \end{array} \right] \\ \xrightarrow{L_3 \leftarrow\, -L_3} & \left[ \begin{array}{ccccc|c} 1 & 0 & 0 & 1 & 1 & 2 \\ 0 & 1 & 0 & -2 & -1 & -1 \\ 0 & 0 & 1 & 1 & -1 & -1 \end{array} \right] \end{align*}$$ La solution de base associée à $B$ est alors $\mathbf{x}' = \begin{bmatrix} 2 \\ -1 \\ -1 \\ 0 \\ 0\end{bmatrix}$.

2. Choisissons $r = 2$ puisque c’est le plus petit indice $i$ tel que $x'_i < 0$.

3. Choisissons $k = 4$ puisque c’est le plus petit indice $k$ tel que le coefficient de $x_k$ dans la rangée associée à $x_2$ est négatif.

4. La nouvelle base est alors $B = \{1,3,4\}$.

Itération 2 :

1. On obtient le tableau associé à $B = \{1,3,4\}$ : $$\begin{align*} & \left[\begin{array}{ccccc|c} 1 & 0 & 0 & 1 & 1 & 2 \\ 0 & 1 & 0 & -2 & -1 & -1 \\ 0 & 0 & 1 & 1 & -1 & -1 \end{array}\right] \\ \xrightarrow{L_2 \leftarrow \, -\frac{1}{2}L_2} & \left[\begin{array}{ccccc|c} 1 & 0 & 0 & 1 & 1 & 2 \\ 0 & -\frac{1}{2} & 0 & 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 1 & 1 & -1 & -1 \end{array}\right] \\ \xrightarrow{L_1 \leftarrow L_1 -L_2} & \left[\begin{array}{ccccc|c} 1 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & \frac{3}{2} \\ 0 & -\frac{1}{2} & 0 & 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 1 & 1 & -1 & -1 \end{array}\right] \\ \xrightarrow{L_3 \leftarrow L_3 -L_2} & \left[\begin{array}{ccccc|c} 1 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & \frac{3}{2} \\ 0 & -\frac{1}{2} & 0 & 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & \frac{1}{2} & 1 & 0 & -\frac{3}{2} & -\frac{3}{2} \end{array}\right] \\ \xrightarrow{L_2 \leftrightarrow L_3} & \left[\begin{array}{ccccc|c} 1 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & \frac{3}{2} \\ 0 & \frac{1}{2} & 1 & 0 & -\frac{3}{2} & -\frac{3}{2} \\ 0 & -\frac{1}{2} & 0 & 1 & \frac{1}{2} & \frac{1}{2} \end{array}\right] \\ \end{align*}$$ Donc, la solution de base déterminé par $B$ est $\mathbf{x}' = \begin{bmatrix} \frac{3}{2} \\ 0 \\ -\frac{3}{2} \\ \frac{1}{2} \\ 0\end{bmatrix}$.

2. Choisissons $r = 3$ puisque c’est le plus petit indice $i$ où $x'_i < 0$.

3. Choisissons $k = 5$ puisque c’est le plus petit indice $k$ tel que le coefficient de $x_k$ dans la rangée associée à $x_3$ est négatif. (Notons que la rangée associée à $x_3$ correspond à la deuxième ligne de la dernière matrice augmentée ci-dessus.)

4. La nouvelle base est alors $B = \{1,4,5\}$.

Itération 3 :

1. On obtient le tableau associé à $B = \{1,4,5\}$ : $$\begin{align*} & \left[\begin{array}{ccccc|c} 1 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & \frac{3}{2} \\ 0 & \frac{1}{2} & 1 & 0 & -\frac{3}{2} & -\frac{3}{2} \\ 0 & -\frac{1}{2} & 0 & 1 & \frac{1}{2} & \frac{1}{2} \end{array}\right] \\ \xrightarrow{L_2 \leftarrow \, -\frac{2}{3} L_2} & \left[\begin{array}{ccccc|c} 1 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & \frac{3}{2} \\ 0 & -\frac{1}{3} & -\frac{2}{3} & 0 & 1 & 1 \\ 0 & -\frac{1}{2} & 0 & 1 & \frac{1}{2} & \frac{1}{2} \end{array}\right] \\ \xrightarrow{L_1 \leftarrow L_1 -\frac{1}{2} L_2} & \left[\begin{array}{ccccc|c} 1 & \frac{2}{3} & \frac{1}{3} & 0 & 0 & 1 \\ 0 & -\frac{1}{3} & -\frac{2}{3} & 0 & 1 & 1 \\ 0 & -\frac{1}{2} & 0 & 1 & \frac{1}{2} & \frac{1}{2} \end{array}\right] \\ \xrightarrow{L_3 \leftarrow L_3 -\frac{1}{2} L_2} & \left[\begin{array}{ccccc|c} 1 & \frac{2}{3} & \frac{1}{3} & 0 & 0 & 1 \\ 0 & -\frac{1}{3} & -\frac{2}{3} & 0 & 1 & 1 \\ 0 & -\frac{1}{3} & \frac{1}{3} & 1 & 0 & 0 \end{array}\right] \\ \xrightarrow{L_2 \leftrightarrow L_3} & \left[\begin{array}{ccccc|c} 1 & \frac{2}{3} & \frac{1}{3} & 0 & 0 & 1 \\ 0 & -\frac{1}{3} & \frac{1}{3} & 1 & 0 & 0 \\ 0 & -\frac{1}{3} & -\frac{2}{3} & 0 & 1 & 1 \end{array}\right] \\ \end{align*}$$ Donc, la solution de base déterminée par $B$ est $\mathbf{x}' = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1\end{bmatrix}$.

2. On s’arrête ici car le côté droit du tableau ne contient que des valeurs non négatives. On peut aussi constater que $\mathbf{x}' = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1\end{bmatrix}$ satisfait à $\mathbf{A}\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}$.

Remarque. L’algorithme présentée ci-dessus est en fait une spécialisation de l’algorithme du simplexe dual qui utilise la règle d’anti-cyclage de Robert Bland pour programmation linéaire.

14.6.2 Analyse de la méthode

Lors de l’étape 2, on peut s’arrêter lorsque $\mathbf{b}' \geq \mathbf{0}$ car pour chaque $j \in \{1,\ldots,n\}$, $x'_j$ est nul ou un des élément de $\mathbf{b}'$.

L’étape 3 jette un regard sur la rangée du tableau associée à $x_r$ : $$\begin{equation} x_r + \sum_{j \notin B} \bar{a}_{rj} x_j = \beta_r. \tag{14.3} \end{equation}$$ Par choix de $r$, on sait que $\beta_r < 0$. Mais si $\bar{a}_{rj} \geq 0$ pour tout $j \notin B$, le côté gauche de l’équation (14.3) n’est jamais négatif pour toutes les solutions de $\mathbf{A}\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}$, ce qui implique que le système n’admet aucune de solution admissible.

Pour l’indice $k$ choisit à l’étape 3, le coefficient de $x_k$ est négatif dans la rangée associée à $x_r$ . Donc, les colonnes de $\mathbf{A}'$, indicées par la nouvelle base $B$ formé à l’étape 4, sont linéairement indépendantes. Puisque $\mathbf{A}' = \mathbf{A}_B^{-1} \mathbf{A}$, on constate que les colonnes de $\mathbf{A}$ sont aussi linéairement indépendantes, ce qui implique que le nouveau $B$ est aussi une base pour $\mathbf{A}$.

Montrons maintenant que l’algorithme se termine.

Supposons, par contradiction, que l’algorithme ne se termine pas. Soit $B_1,B_2,\ldots$ la suite des bases que l’algorithme rencontre. Autrement dit, $B_i$ dénote la base au début de la $i$-ième itération pour chaque $i = 1,2,\ldots$. Soit $\mathbf{x}^{(i)}$ la solution de base associée à $B_i$ pour chaque $i = 1,2,\ldots$.

Puisqu’il n’existe qu’un nombre fini de bases différentes, on peut trouver $s < t$ tel que $B_s = B_t$. Soit $r_p$ l’indice retiré de $B_p$ pour tout $p \in \{s, \ldots, t\}$. Posons $h = \max \{r_s,\ldots, r_t\}.$ Puisque $B_t = B_s$, il doit y avoir $q \in \{s, t-1\}$ tel que $h$ a été ajouté à la base à la $q$-ième itération.

Soit $i$ l’indice choisit pour être retiré de la base lors de la $q$-ième itération. Puisque $h$ fût ajouté à la base lors de l’itération $q$, $i \neq h$. De plus, aucun indice plus élevé que $h$ peut être retiré lors de l’itération $q$. Ainsi, nous avons $i < h$.

Puisque la rangée associée à $x_i$ est une équation du système $\mathbf{A}^{-1}_{B_q}\mathbf{A} \mathbf{x} = \mathbf{A}^{-1}_{B_q} \mathbf{b}$, elle est égale à $$\mathbf{d}^\mathsf{T}\mathbf{A} \mathbf{x} = \mathbf{d}^\mathsf{T}\mathbf{b},$$ où $\mathbf{d}^\mathsf{T}$ est une ligne de $\mathbf{A}_{B_q}^{-1}$.

Nous avons donc $0 > x^{(q)}_i = \mathbf{d}^\mathsf{T}\mathbf{b} = \mathbf{d}^\mathsf{T}(\mathbf{A} \mathbf{x}^{(p)}) = (\mathbf{d}^\mathsf{T}\mathbf{A}) \mathbf{x}^{(p)} = \sum_{j = 1}^n (\mathbf{d}^\mathsf{T}\mathbf{A}_j) x^{(p)}_j$. Ainsi, il existe $j'$ tel que $(\mathbf{d}^\mathsf{T}\mathbf{A}_{j'}) x^{(p)}_{j'} < 0,$ d’où $j' \in B_p$.

Supposons que $j' < h$. Puisque à la $p$-ième itération, $r = h$ fût le plus petit indice tel que $x^{(p)}_r < 0$ à l’étape 2, alors $x^{(p)}_{j'} \geq 0$. De plus, à la $q$-ième itération, $k = h$ fût le plus petite indice à l’étape 3 ayant été ajouté à la base, nous avons $\mathbf{d}^\mathsf{T}\mathbf{A}_{j'} \geq 0$, d’où $(\mathbf{d}^T \mathbf{A}_j') x^{(p)}_{j'} \geq 0$, ce qui est une contradiction. Ainsi, $j' \geq h$.

Supposons maintenant que $j' = h$. Puisque on a ajouté $h$ à la base lors de la $q$-ième itération, nous devons avoir $\mathbf{d}^\mathsf{T}\mathbf{A}_{j'} < 0$. Mais on a retiré $h$ lors de la $p$-ième itération. Ainsi, $x^{(p)}_{j'} < 0$, ce qui implique que $(\mathbf{d}^T \mathbf{A}_j') x^{(p)}_{j'} > 0$, une contradiction.

Finalement, supposons que $j' > h$. Puisque $h$ est le plus grand indice qui l’on a retiré d’une base lors entre la $p$-ième itération et la $q$-ième itération, $j'$ doit également se retrouver dans $B_q$, ce qui implique que $\mathbf{d}^\mathsf{T}\mathbf{A}_{j'} = 0$ puisque $i < h < j'$ et puisque le coefficient de $x_j$ dans la rangée associée à $x_i$ est nul pour chaque élément $j \in B_p$ autre que $i$. Ceci contredit que $(\mathbf{d}^\mathsf{T}\mathbf{A}_j') x^{(p)}_{j'} < 0$.

Ainsi, $j'$ n’existe pas, ce qui est une contradiction, d’où algorithme se termine.

Exercices

1. Pour chacun des problèmes suivants, appliquez la méthode du simplexe au système $\mathbf{A}\mathbf{x} = \mathbf{b}$ en débutant avec la base donnée $B$ :

   1. $\mathbf{A}=\begin{bmatrix} 1 & -1 & 1 & 0 \\ 0 & 1 & -2 & 1 \\ \end{bmatrix}$, $\mathbf{b} = \begin{bmatrix} -1 \\ 2 \end{bmatrix}$, $B = \{2,3\}$.

   2. $\mathbf{A}=\begin{bmatrix} 1 & -1 & 1 & 0 \\ 0 & 1 & 2 & -1 \\ \end{bmatrix}$, $\mathbf{b} = \begin{bmatrix} 1 \\ -1 \end{bmatrix}$, $B = \{1,2\}$.

Solutions

1. 1. Itération 1 :

      1. On obtient le tableau associé à $B = \{2,3\}$ : $$\begin{align*} & \left[\begin{array}{cccc|c} 1 & -1 & 1 & 0 & -1 \\ 0 & 1 & -2 & 1 & 2 \end{array}\right] \\ \xrightarrow{L_2 \leftarrow \, L_2 + 2L_1} & \left[\begin{array}{cccc|c} 1 & -1 & 1 & 0 & -1 \\ 2 & -1 & 0 & 1 & 0 \end{array}\right] \\ \xrightarrow{L_2 \leftarrow \, -L_2} & \left[\begin{array}{cccc|c} 1 & -1 & 1 & 0 & -1 \\ -2 & 1 & 0 & -1 & 0 \end{array}\right] \\ \xrightarrow{L_1 \leftarrow \, L_1 + L_2} & \left[\begin{array}{cccc|c} -1 & 0 & 1 & -1 & -1 \\ -2 & 1 & 0 & -1 & 0 \end{array}\right] \\ \xrightarrow{L_1 \leftrightarrow L_2} & \left[\begin{array}{cccc|c} -2 & 1 & 0 & -1 & 0 \\ -1 & 0 & 1 & -1 & -1 \end{array}\right] \\ \end{align*}$$ Donc, la solution de base associée à $B$ est $\mathbf{x}' = \begin{bmatrix} 0 \\ 0 \\ -1 \\ 0 \end{bmatrix}.$

      2. Choisissons $r = 3$ puisque c’est le plus petit indice $i$ tel que $x'_i < 0.$

      3. Choisissons $k = 4$ puisque c’est le plus petit indice $k$ tel que le coefficient de $x_k$ dans la rangée associée à $x_3$ est négatif.

      4. La nouvelle base est alors $B = \{2,4\}$.

      Itération 2 :

      1. On obtient le tableau associé à $B = \{2,4\}$ : $$\begin{align*} & \left[\begin{array}{cccc|c} -2 & 1 & 0 & -1 & 0 \\ -1 & 0 & 1 & -1 & -1 \end{array}\right] \\ \xrightarrow{L_2 \leftarrow \, -L_2} & \left[\begin{array}{cccc|c} -2 & 1 & 0 & -1 & 0 \\ 1 & 0 & -1 & 1 & 1 \end{array}\right] \\ \xrightarrow{L_1 \leftarrow \, L_1+L_2} & \left[\begin{array}{cccc|c} -1 & 1 & -1 & 0 & 1 \\ 1 & 0 & -1 & 1 & 1 \end{array}\right] \\ \end{align*}$$ Donc, la solution de base déterminée par $B$ est $\mathbf{x}' = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \end{bmatrix}$.

      2. On s’arrête ici car $\mathbf{x}'$ est une solution de base admissible.

   2. Itération 1 :

      1. On obtient le tableau associé à $B = \{1,2\}$ : $$\begin{align*} & \left[\begin{array}{cccc|c} 1 & -1 & 1 & 0 & 1 \\ 0 & 1 & 2 & -1 & -1 \end{array}\right] \\ \xrightarrow{L_1 \leftarrow \, L_1 + L_2} & \left[\begin{array}{cccc|c} 1 & 0 & 3 & -1 & 0 \\ 0 & 1 & 2 & -1 & -1 \end{array}\right] \\ \end{align*}$$ Donc, la solution de base déterminée par $B$ est $\mathbf{x}' = \begin{bmatrix} 0 \\ -1 \\ 0 \\ 0 \end{bmatrix}$.

      2. Choisissons $r = 2$ puisque c’est le plus petit indice $i$ tel que $x'_i < 0.$

      3. Choisissons $k = 4$ puisque c’est le plus petit indice $k$ tel que le coefficient de $x_k$ dans la rangée associée à $x_2$ est négatif.

      4. La nouvelle base est alors $B = \{1,4\}$.

      Itération 2 :

      1. On obtient le tableau associé à $B = \{1,4\}$ : $$\begin{align*} & \left[\begin{array}{cccc|c} 1 & 0 & 3 & -1 & 0 \\ 0 & 1 & 2 & -1 & -1 \end{array}\right] \\ \xrightarrow{L_2 \leftarrow \, -L_2} & \left[\begin{array}{cccc|c} 1 & 0 & 3 & -1 & 0 \\ 0 & -1 & -2 & 1 & 1 \end{array}\right] \\ \xrightarrow{L_1 \leftarrow \, L_1+L_2} & \left[\begin{array}{cccc|c} 1 & -1 & 1 & 0 & 1 \\ 0 & -1 & -2 & 1 & 1 \end{array}\right] \\ \end{align*}$$ Donc, la solution de base déterminée par $B$ est $\mathbf{x}' = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix}$.

      2. On s’arrête ici car $\mathbf{x}'$ est une solution de base admissible.