Le premier auteur a s'être inquiété de ce problème semble avoir été Joseph Fourier* J. Fourier (1826). Solution d'une question particulière du calcul des inégalités. Nouveau Bulletin des Sciences par la Société Philomatique de Paris, 99-100. . Il fut relayé par George Boole* G. Boole (1854). On the conditions by wich the solutions of questions in the theory of probabilities are limited. The Philosophical Magazine, VIII. et au XXe siècle par par Loyd L. Dines* L. L. Dines (1918). System of linear inequalities. Annals of Mathematics, 20, 191-199. , Theodore Motzkin* T. Motzkin (1936). Beiträge zur Theorie der linearen Ungleichungen. Université de Bale. puis, conjointement, par David Avis et Bohdan Kaluzni* D. Avis et B. Kaluzny (2004). Solving inequalities and proving Farkas' lemma made easy. The American Mathematical Monthly, 2, 152-157. .
On doit tout d'abord réaliser la principale différence entre une égalité et une inégalité. Dans le cas de la première, multiplier les deux membres par un nombre négatif ne change pas la nature de l'inégalité. En revanche, en présence d'une inégalité du type $\geq$, la multiplication par un nombre négatif inverse le sens de l'inégalité vers $\leq$ (et réciproquement si l'on part de l'inégalité opposée).
\[ \begin{array}{c} 3 x + 1 \leq 6\\ 2 x - 1 \leq 6\\ -x + 3 \leq 4\\ x \geq 0 \end{array} \hspace{.25cm}\Longleftrightarrow\hspace{.25cm} \begin{array}{c} x \leq 5/3\\ x \leq 7/2\\ x \geq -1\\ x \geq 0 \end{array} \]inégalités qui peuvent s'écrire de manière plus compacte comme :
\[ x\leq\min\left\{\frac{5}{3},\frac{7}{2}\right\} = \frac{5}{3}\hspace{.25cm}\text{et}\hspace{.25cm}0 = \max\left\{-1, 0\right\}\leq x \]ou encore $0\leq x \leq 5/3$. On a ainsi réussi à remplacer 4 inégalités par deux inégalités qui caractérisent le même problème. Globalement, l'idée de l'élimination de Fourier-Motzkin consiste à dériver du système initial un système d'inégalités dans lequel une variable a été éliminée (le choix de cette variable est arbitraire. En itérant cette démarche un nombre suffisant de fois, on peut aboutir sur un système à une, voir deux variables et en déduire la faisabilité du système initial).
Avant de développer la méthode pour plusieurs variables, il est intéressant de développer une fonction qui permette de retrouver ce résultat pour une unique variable dans $\texttt{SageMath}$.
Il est facile de demander à $\texttt{SageMath}$ de faire tourner la méthode de Gauss sur une matrice. Dans une discution du forum $\texttt{Ask SageMath}$ (pour avoir accès à ce forum et/ou poser une question, il suffit de passer par une barre de recherche), le code qui suit a été proposé. Comme, ce code est utilisé uniquement pour des raisons pédagogiques, on ne s'intéresse qu'à des matrices de rationnels.
$\texttt{Code}$ : on commence par évaluer la cellule qui suit (elle prépare la fonction qui va faire le travail) :
On peut donc appliquer cette fonction sur l'exemple suivant :
De manière générale, dans le système linéaire $\boldsymbol{A}\boldsymbol{x}\leq \boldsymbol{b}$, on peut avoir les trois types de lignes suivantes :
\[ \begin{array}{ccc} a_{i1} x_1 + a_{i2} x_2 + \cdots + a_{il} x_l+ \cdots+ a_{in} x_n \leq b_i & \text{avec}&a_{il} > 0\\ a_{j1} x_1 + a_{j2} x_2 + \cdots + a_{jl} x_l + \cdots+a_{jn} x_n \leq b_j & \text{avec}&a_{jl} < 0\\ a_{k1} x_1 + a_{k2} x_2 + \cdots + a_{kl} x_l + \cdots+a_{kn} x_n \leq b_j & \text{avec}&a_{kl} =0 \end{array} \]Oublions pour l'instant le dernier type de lignes (en fait, il est aisé de les remplacer par deux lignes identiques à l'inégalité près. On peut alors isoler $x_l$ dans les deux premiers types d'inégalités pour obtenir) :
\[ \begin{array}{cc} \text{pour } i & x_l \leq \displaystyle{\frac{b_i}{a_{il}} -\frac{a_{i1}}{a_{il}} x_ 1-\frac{a_{i2}}{a_{il}} x_ 2+\cdots -\frac{a_{i{l-1}}}{a_{il}} x_{l-1}-\frac{a_{i{l+1}}}{a_{il}} x_{l+1}-\cdots-\frac{a_{i{n}}}{a_{il}} x_{n}}\\ \text{pour } j & x_l \ge \displaystyle{\frac{b_j}{a_{jl}} -\frac{a_{j1}}{a_{jl}} x_ 1-\frac{a_{j2}}{a_{jl}} x_ 2+\cdots -\frac{a_{j{l-1}}}{a_{jl}} x_{l-1}-\frac{a_{j{l+1}}}{a_{jl}} x_{l+1}-\cdots-\frac{a_{j{n}}}{a_{jl}} x_{n}} \end{array} \]ou, en condensant les notations :
\[ \frac{b_{j}}{a_{jl}}- \sum_{\begin{array}{c}p=1\\p\not=l\end{array}} \frac{a_{jp}}{a_{jl}} x_p\leq x_l\hspace{.25cm}\text{et}\hspace{.25cm}x_l\leq \frac{b_{i}}{a_{il}}- \sum_{\begin{array}{c}p=1\\p\not=l\end{array}} \frac{a_{ip}}{a_{il}} x_p \]Supposons maintenant que, parmi les $m$ équations qui composent le système, il y en ait $m_1$ qui ont $a_{kl} >0$ et $m_2$ avec $a_{kl} <0$ (comme on l'a signalé précédemment on ne tient pas compte de $a_{kl} =0$). Il est alors évident que $x_k$ appartient à l'intervalle :
\[ \max_{\text{inequations de type }j} \left\{\frac{b_{j}}{a_{jl}}- \sum_{\begin{array}{c}p=1\\p\not=l\end{array}} \frac{a_{jp}}{a_{jl}} x_p\right\}\leq x_l \leq \min_{\text{inequations de type }i}\left\{\frac{b_{i}}{a_{il}}- \sum_{\begin{array}{c}p=1\\p\not=l\end{array}} \frac{a_{jp}}{a_{jl}} x_p\right\} \]On peut éliminer $x_k$ et conserver simplement l'inégalité
\begin{equation} \max_{\text{inequations de type }j}\left\{\frac{b_{j}}{a_{jl}}- \sum_{\begin{array}{c}p=1\\p\not=l\end{array}} \frac{a_{jp}}{a_{jl}} x_p\right\}\leq \min_{\text{inequations de type }i}\left\{\frac{b_{i}}{a_{il}}- \sum_{\begin{array}{c}p=1\\p\not=l\end{array}} \frac{a_{jp}}{a_{jl}} x_p\right\}\label{fme1} \end{equation}d'où l'on tire une nouvelle inégalité concernant toutes les autres variables $x_p$ ($x_l$ étant exclue) que l'on rajoute aux $m$ équations pour lesquelles $a_{kl} = 0$.
Notons que si $\max\{a_1, a_2, \ldots,a_{m_1}\} \leq \min\{b_1, b_2, \ldots,b_{m_2}\}$ alors :
\[ \begin{array}{cccc} a_1 \leq b_1 & a_2 \leq b_1 &\cdots & a_{m_1} \leq b_1 \\ a_1 \leq b_2 & a_2 \leq b_2 &\cdots& a_{m_1} \leq b_2\\ \vdots & \vdots&\ddots\\ a_1 \leq b_{m_2}& a_2 \leq b_{m_2}&\cdots& a_{m_1} \leq b_{m_2} \end{array} \]Donc, l'équation~\ref{fme1} permet de définir un ensemble de $m_1\times m_2$ inégalités pour $n-1$ variables. Notons qu'un polyèdre $\mathcal{P}\in \mathbb{R}^n$ est l'intersection d'un nombre fini de demi-hyperplans $\boldsymbol{a}_i^\top\boldsymbol{x}\leq \boldsymbol{b}_i$ ---~$\boldsymbol{a}_i$, $\boldsymbol{x}$ et $\boldsymbol{b}_i$ étant tous des vecteurs de $\mathbb{R}^n$. En d'autres termes :
\[ \mathcal{P}= \{\boldsymbol{x}\in \mathbb{R}^n|\boldsymbol{A}\boldsymbol{x}\leq \boldsymbol{b}\} \hspace{.25cm}\text{où}\hspace{.25cm} \boldsymbol{A} = \begin{bmatrix}\boldsymbol{a}^\top_1\\ \boldsymbol{a}^\top_2\\ \vdots\\ a_n^\top\end{bmatrix} \]L'opération d'élimination de Fourier-Motzkin part d'un polyèdre dans $\mathbb{R}^n$ puisqu'un ensemble de demi-hyperplans est donné et par élimination d'une variable aboutit à un autre ensemble d'hyper-plans donc à un autre polyèdre dans $\mathbb{R}^{n-1}$. En opérant ainsi, on réalise une projection de $\mathbb{R}^n$ sur $\mathbb{R}^{n-1}$. Or, il est possible de démontrer que l'objet projeté est lui-même un polyèdre. On peut donc recommencer sur une autre variable (en général, pour simplifier, on opère dans l'ordre croissant des indices) et réaliser une projection de $\mathbb{R}^{n-1}$ sur $\mathbb{R}^{n-2}$ (voir la figure suivante pour une projection de $\mathbb{R}^3$ dans $\mathbb{R}^2$). On opère ainsi de suite jusqu'à ce qu'il ne demeure qu'une seule variable.
Le graphique ci-dessus représente un cube. C'est un volume assez simple, car en fonction de sa position dans l'espace, il est assez facile de repérer ses coordonnées de ses sommets. Par contre, il est peut-être plus difficile de déterminer les demi-plans dont il est l'intersection. On reviendra plus loin sur ce point. Il est ici assez évident que son intérieur n'est pas vide. Appliquer la méthode de Fourier-Motzkin sur ce cube peut se faire de différentes manières (certaines flèches ne sont visibles que lorsqu'on effectue une rotation du graphique à l'aide de la souris) :
Dans tous les cas, on aboutit sur un un intervale final qui est clairement défini puisque les inégalités qui caractérisent le cube sont compatibles les unes avec les autres (le cube a un intérieur et une frontière clairement établis). Cependant, on notera que des inégalités ne déterminent pas toutes des polyèdres (solides délimités de toute part par des polygones plans). Pour exemplifier la méthode de Fourier-Motzkin, on peut commencer par le cas simple à deux variables suivant :
\[ \begin{array}{c} x_2 + x_1 \geq 3\\ 2 x_1 - x_2 \leq 6\\ 3 x_2 - x_1 \leq 3 \end{array} \]On isole $x_1$ :
\[ \begin{array}{c} x_2 \geq 3 - x_1\\ x_2 \geq 2 x_1- 6\\ x_2 \leq 1+\displaystyle{\frac{x_1}{3}} \end{array} \]ce qui implique que
\[ \max\left\{3 -x_1, 2x_1-6\right\}\leq x_2 \leq 1+ \frac{x_1}{3} \]inégalité qui donne naissance aux deux inéquations :
\[ \begin{array}{c} 3 -x_1 \leq1+ \displaystyle{\frac{x_1}{3}}\\ 2x_1-6 \leq \displaystyle{1+\frac{x_1}{3}} \end{array} \,\,\,\,\,\Longleftrightarrow\,\,\,\,\, \begin{array}{c} x_1\geq \displaystyle{\frac{3}{2}}\\ x_1\leq \frac{21}{5} \end{array} \]soit
\[ \frac{3}{2} \leq x_1 \leq\frac{21}{5} \]Ceci signifie que pour tout $x_2 \in [0, 12/5]$, il existe $x_1$ qui satisfait le système initial des trois inégalités comme cela est représenté à la figure suivante (ici encore, il est important de lire le code pour savoir comment obtenir une représentation avec $\texttt{SageMath}$).
On peut aisément résoudre le système d'inéquations précédent dans $\texttt{SageMath}$. La commande est assez simple mais une difficulté peut surgir selon que l'on désire utiliser des variables qui ne sont pas indexées ($x$, $y\ldots$) ou des variables qui le sont ($x_1$, $x_2\ldots$). Commençons par la première approche. $x$ est défini comme variable par défaut. Toutes les autres variables doivent être déclarées.
On note qu'ici, par l'observation du graphique, il est clair que les inégalités sont compatibles puisqu'elles définissent un triangle qui a des points intérieurs et des points sur sa frontière. Les réponses $R_0$, $R_1$ et $R_3$ donnent les sommets du triangle.
La réponse $R_2$ précise que pour tout $y$ compris entre $3/2$ et $12/5$ tout $ x = 3 y -3$. Par exemple, puisque $ y = 2$ appartient à l'intervalle, $(x,y)=(3,2)$ est une solution possible du système d'équations (Il ne faut pas oublier que ce que l'on recherche, c'est de vérifier qu'il existe au moins une solution). Dans ce cas, les points décrits sont ceux qui sont situés sur les "arrêtes" du triangle entre le sommet $B$ et le sommet $C$. La réponse $R_5$ signifie que pour tout point $y$ tel que $0 < y < 12/5$, il existe un point $x$ vérifiant $x =-y +3$ tel que $(x, y)$ vérifie les 3 inégalités. Enfin, $R_6$ balaye les point intérieurs du triangle.En ce qui concerne la seconde approche, voici comment on opère :
La seule différence entre les deux approches est la manière de définir les variables. Il est alors intéressant de se demander quelle est la réponse obtenue face à des inégalitées incompatibles. Considérons le système d'équation linéaires suivant :
\[ \begin{array}{c} x_2 + x_1 \leq -2\\ x_1 \geq 0\\ x_2 \geq 0 \end{array} \]Voici la représentation de ce système d'inégalités :
Clairement, ce système d'inégalités n'a pas de solution car un point ne peut pas à la fois être sous $1-x_1$ et sous $2 x_1 - 1$ (Il n'existe pas dans le graphe de zone dont la couleur soit celle du recouvrement des trois domaines). Voici donc ce qui se produit quand on essaye de résoudre le système d'inégalités :
Ce qui signifie qu'il n'y a pas de solution. La réponse de $\texttt{SageMath}$ n'est pas exactement du type que l'on attend du point de vue théorique. Mais elle essaye de trouver des points ou des conditions définissant des ensembles de points qui permettent de conclure à la validité d'un ensemble d'inéquations.
Pour finir sur ce point, on peut appliquer la méthode à un système à trois inconnues. Par exemple :
\[ x_1 - 5 x_2 +\ 2 x_3 \leq 10\\ 3 x_1 - 6 x_2 + x_3 \leq 8\\ 6 x_1 + 12 x_2 - 2 x_3 \leq 16\\ -2x_1 + 6 x_2 - 3 x_3 \leq -6\\ -5 x_1 +\ 2 x_2 - 4 x_3 \leq 8 \]Isolons $x_1$ dans toutes ces inégalités :
\[ \begin{array}{c} x_1 \leq 10 + 5 x_2 - 2 x_3\\ x_1 \leq \displaystyle{\frac{8}{3}}+\ 2 x_2-\displaystyle{\frac{x_3}{3}}\\ x_1 \leq \displaystyle{\frac{8}{3}}- 2 x_2 + \displaystyle{\frac{x_3}{3}}\\ x_1 \geq 3+ 3 x_2 - \displaystyle{\frac{3}{2}} x_3 \\ x_1 \geq \displaystyle{-\frac{8}{5}} +\displaystyle{\frac{2}{5}} x_2 - \displaystyle{\frac{4}{5}} x_3 \end{array} \]Ceci signifie que $x_1$ appartient à l'intervalle :
\[ \left[\max\left\{3+ 3 x_2 - \displaystyle{\frac{3}{2}} x_3, \displaystyle{-\frac{8}{5}} +\displaystyle{\frac{2}{5}} x_2 - \displaystyle{\frac{4}{5}} x_3\right\},\min\left\{ \displaystyle{10 + 5 x_2 - 2 x_3,\frac{8}{3}}+\ 2 x_2-\displaystyle{\frac{x_3}{3}}, \displaystyle{\frac{8}{3}}- 2 x_2 + \displaystyle{\frac{x_3}{3}}\right\}\right] \]Mais cet intervalle, après élimination de $x_1$, implique que :
\[ \max\left\{3+ 3 x_2 - \displaystyle{\frac{3}{2}} x_3, \displaystyle{-\frac{8}{5}} +\displaystyle{\frac{2}{5}} x_2 - \displaystyle{\frac{4}{5}} x_3\right\}\leq\min\left\{ \displaystyle{10 + 5 x_2 - 2 x_3,\frac{8}{3}}+\ 2 x_2-\displaystyle{\frac{x_3}{3}}, \displaystyle{\frac{8}{3}}- 2 x_2 + \displaystyle{\frac{x_3}{3}}\right\} \]signifie simplement que, les éléments de gauche sont termes à termes inférieurs aux éléments de droite. On a donc le système d'inégalités :
\[ \begin{array}{c} 3+ 3 x_2 - \displaystyle{\frac{3}{2}} x_3\leq 10 + 5 x_2 - 2 x_3\\ 3+ 3 x_2 - \displaystyle{\frac{3}{2}} x_3 \leq \displaystyle{\frac{8}{3}}+\ 2 x_2-\displaystyle{\frac{x_3}{3}}\\ 3+ 3 x_2 - \displaystyle{\frac{3}{2}} x_3\leq \displaystyle{\frac{8}{3}}- 2 x_2 + \displaystyle{\frac{x_3}{3}}\\ \displaystyle{-\frac{8}{5}} +\displaystyle{\frac{2}{5}} x_2 - \displaystyle{\frac{4}{5}} x_3\leq 10 + 5 x_2 - 2 x_3 \\ \displaystyle{-\frac{8}{5}} +\displaystyle{\frac{2}{5}} x_2 - \displaystyle{\frac{4}{5}} x_3 \leq \displaystyle{\frac{8}{3}}+\ 2 x_2-\displaystyle{\frac{x_3}{3}}\\ \displaystyle{-\frac{8}{5}} +\displaystyle{\frac{2}{5}} x_2 - \displaystyle{\frac{4}{5}} x_3 \leq \displaystyle{\frac{8}{3}}- 2 x_2 + \displaystyle{\frac{x_3}{3}} \end{array} \,\,\,\,\,\Longleftrightarrow\,\,\,\,\, \begin{array}{c} x_2 \geq \displaystyle{\frac{1}{4}}\left(x_3 - 14\right)\\ x_2 \leq \displaystyle{\frac{1}{6}}\left(7x_3 - 2\right)\\ x_2 \leq \displaystyle{\frac{1}{30}}\left(11 x_3 - 2\right)\\ x_2 \leq \displaystyle{\frac{1}{23}}\left(6x_3 - 58\right) \\ x_2 \geq \displaystyle{\frac{1}{24}}\left(-7x_3 - 64\right) \\ x_2 \leq\displaystyle{\frac{1}{36}}\left(17x_3 - 64\right) \end{array} \]soit
\[ \max\left\{ \frac{1}{4}\left(x_3 - 14\right),\frac{1}{24}\left(-7x_3 - 64\right) \right\} \leq x_2\leq\min\left\{\frac{1}{6}\left(7x_3 - 2\right),\frac{1}{30} \left(11 x_3 - 2\right), \frac{1}{23}\left(6x_3 - 58\right), -\frac{128}{48} - \frac{35}{48} x_3, \frac{1}{36}\left(17x_3 - 64\right) \right\} \]ce qui signifie que
\[ \max\left\{\frac{1}{4}\left(x_3 - 14\right),\frac{1}{24}\left(-7x_3 - 64\right)\right\}\leq \min\left\{\frac{1}{6}\left(7x_3 - 2\right),\frac{1}{30}\left(11 x_3 - 2\right), \frac{1}{23} \left(6x_3 - 58\right), \frac{1}{36}\left(17x_3 - 64\right) \right\} \]ou que l'on a encore affaire aux inégalités suivantes :
\[ \begin{array}{l} \frac{1}{4}\left(x_3 - 14\right)\leq \frac{1}{6}\left(7x_3 - 2\right)\\ \frac{1}{4}\left(x_3 - 14\right)\leq \frac{1}{30}\left(11 x_3 - 2\right)\\ \frac{1}{4}\left(x_3 - 14\right)\leq \frac{1}{23}\left(6x_3 - 58\right) \\ \frac{1}{4}\left(x_3 - 14\right) \leq \frac{1}{36}\left(17x_3 - 64\right) \\ \frac{1}{24}\left(-7x_3 - 64\right) \leq \frac{1}{6}\left(7x_3 - 2\right)\\ \frac{1}{24}\left(-7x_3 - 64\right) \leq \frac{1}{30}\left(11 x_3 - 2\right)\\ \frac{1}{24}\left(-7x_3 - 64\right) \leq \frac{1}{23}\left(6x_3 - 58\right)\\ \frac{1}{24}\left(-7x_3 - 64\right) \leq \frac{1}{36}\left(17x_3 - 64\right) \end{array} \,\,\,\,\,\Longleftrightarrow\,\,\,\,\, \begin{array}{l} x_3\leq -\frac{38}{11}\approx-3.45\\ x_3\leq -\frac{206}{7}\approx -29.42\\ x_3\leq -90\\ x_3 \leq -\frac{31}{4}\approx-7.55\\ x_3 \leq -\frac{8}{5}\approx-1.6\\ x_3 \leq -\frac{312}{79} \approx -3.94\\ { x_3 \leq -\frac{16}{61} \approx -0.26}\\ x_3 \leq -\frac{64}{65} \approx -0.98 \end{array} \]ce qui finalement donne :
\[ x_3\leq -90 \]Ainsi, ce système d'équations est parfaitement valide.
Non la cellule suivante n'est pas une erreur. Elle est là pour que vous permettre de vous exercer à coder le précédent système d'équations linéaires et d'interprêter le résultat étant donné ce qui vient d'être calculé à la main..
L'algorithme de Fourier-Motzkin est très coûteux en ressources, car il induit une multiplication des inégalités. Il est possible de de l'améliorer ---~voir \citet{Duffin74}\sindex[aut]{Duffin R. J.}.
Après quelques instants de réflexion, il est évident que la méthode peut être appliquée pour déterminer la solution d'un problème linéaire. En effet, supposons qu'il s'agisse d'un problème de maximisation du type :
\[ \max z = \sum_{i=1}^n a_i x_i \]Ceci signifie que $z\leq \sum_{i=1}^n a_i x_i$ ou, plus simplement, que $z- \sum_{i=1}^n a_i x_i\leq 0$. Inversement, si on est face à un problème de minimisation.
\[ \min z = \sum_{i=1}^n a_i x_i \]$z\geq \sum_{i=1}^n a_i x_i$ ou, plus simplement, que $z- \sum_{i=1}^n a_i x_i\geq 0$. On peut dans les deux cas traiter l'objectif comme une simple inégalité supplémentaire et si on prend soin à conserver $z$ jusqu'à la dernière étape, on obtiendra une borne de faisabilité qui, à l'égalité, donnera la valeur souhaitée de l'objectif.
Trouver l'intervalle de validité de la fonction $u = x_1+x_2$ quand $\boldsymbol{x}= \begin{bmatrix}x_1 & x_2\end{bmatrix}^\top$ est contraint par le système $\boldsymbol{A}\boldsymbol{x}\leq \boldsymbol{b}$ où les constantes sont définie par :
\[ \boldsymbol{A} = \begin{bmatrix}-2 & -1\\-1 & 2\\3 & -1\\3 & 1\end{bmatrix}\hspace{.25cm}\text{et}\hspace{.25cm} \boldsymbol{b}=\begin{bmatrix}20\\-10\\60\\80\end{bmatrix} \] ☕RéponseConsidérer les inégalités $\boldsymbol{A}\boldsymbol{x}\leq \boldsymbol{b}$ définies par :
\[ \boldsymbol{A} = \begin{bmatrix}0 & 4\\0 & -35\\0 & 12\\0 & -1\end{bmatrix}\hspace{.25cm}\text{et}\hspace{.25cm} \boldsymbol{b}=\begin{bmatrix}100\\-3\\72\\40\end{bmatrix}\hspace{.25cm}\text{pour}\hspace{.25cm}\boldsymbol{x} = \begin{bmatrix}x_1 \\x_2\end{bmatrix} \]Existe-t-il des valeurs de $x_2$ qui résolvent ces inégalités ?
☕RéponseConsidérer les inégalités $\boldsymbol{A}\boldsymbol{x}\leq \boldsymbol{b}$ définies par :
\[ \boldsymbol{A} = \begin{bmatrix}3 & 4\\5 & 6\\4 & -7\\2 & -3\end{bmatrix}\hspace{.25cm}\text{et}\hspace{.25cm} \boldsymbol{b}=\begin{bmatrix}14\\50\\18\\-8\end{bmatrix}\hspace{.25cm}\text{pour}\hspace{.25cm}\boldsymbol{x} = \begin{bmatrix}x_1 \\x_2\end{bmatrix} \]Considérons les inégalités $\boldsymbol{A}\boldsymbol{x}\leq \boldsymbol{b}$ définies par
\[ \boldsymbol{A} = \begin{bmatrix}-4 & -1\\- 1 & -2\\-2 & 1\\-1 & -6\\1 & 2\\6 & 2 \\0 & 1\end{bmatrix}\hspace{.25cm}\text{et}\hspace{.25cm} \boldsymbol{b}=\begin{bmatrix}-9\\-4\\0\\-6\\11\\17\\4\end{bmatrix} \]Considérer les inégalités $\boldsymbol{A}\boldsymbol{x}\leq \boldsymbol{b}$ définies par :
\[ \boldsymbol{A} = \begin{bmatrix}1&-2 & -3\\0 & 1 & -2\\0&2&1\\0& 0 & 1\\0 &-1&0\\0 & 0 & -1\end{bmatrix}\hspace{.25cm}\text{et}\hspace{.25cm} \boldsymbol{b}=\begin{bmatrix}0\\4\\18\\10\\0 \\0\end{bmatrix}\hspace{.25cm}\text{pour}\hspace{.25cm}\boldsymbol{x} = \begin{bmatrix}z\\x_1 \\x_2\end{bmatrix} \]