Avant de s’engouffrer dans les subtilités de l’algorithme du simplexe, il est utile de rappeler ce que peuvent apporter et comment utiliser certaines méthodes de résolution d’équations. Bien entendu, dans la pratique, tout se fait par recours à des logiciels spécialisés. Mais avoir fait tourner les algorithmes de la recherche opérationnelle à la main sur des exemples simples est une condition nécessaire pour comprendre les méthodes qu’ils permettent de développer. Il ne s’agit pourtant pas de proposer une substitution à un cours d’algèbre linéaire. Ce cours repose sur $\texttt{SageMath}$. Les méthodes pour automatiser les calculs seront donc proposées. Il n'en demeure pas moins vrai, qu'il est conseillé de commencer par réellement faire les calculs à la main.

Dans tout ce qui suit, on remarquera qu'en général ne seront utilisés que des nombres appartenant à $\mathbb{N}$ (des entiers) ou des nombres appartenant à $\mathbb{Q}$ (des rationnels). Pour un mathématicien ou un informaticien la raison va de soi, mais il n'est pas sûr qu'un économiste comprenne immédiatement le pourquoi d'un tel usage.

Bien entendu, il est plus simple de manipuler des nombres appartenant à ces deux ensembles dans les exemples réalisés à la main. Mais, il faut se rappeler que la programmation linéaire a un objectif pratique : résoudre des problèmes qui se posent dans la vie réelle. Or, il n'y a aucune raison, a priori, pour que ces problèmes soient formalisables avec des nombres qui appartiennent à ces deux ensembles. Depuis, que l'on sait que $\sqrt{2}$ n'appartient ni à l'un ni à l'autre de ces deux ensembles, on sait qu'en calcul rien n'est simple.

La raison est la suivante : un ordinateur a une capacité mémoire limitée. Or, les réels qui ne sont ni des entiers, ni des rationnels (ceux qui sont donc des irrationnels) nécessitent une capacité mémoire infinie pour être stockés autrement que formellement (on peut stocker un symbole comme $\pi$ mais pas son développement décimal. Il est donc nécessaire de les tronquer. Or, les tronquer revient à utiliser des rationnels. La raison en elle-même est élémentaire : $\mathbb{Q}$ est dense dans $\mathbb{R}$, ce qui est la manière des mathématiciens d'affirmer qu'entre deux réels, il existe toujours une infinité de rationnels. Cela peut sembler étonnant pour des êtres humains qui sont habitués à compter et dénombrer. Pour fixer ce point, imaginez que si vous faîtes une soiréechez vous et que votre appartement ne pouvait recevoir que 10 entiers, il pourrait recevoir aussi une infinité dénombrable de rationnels et une infinité non-dénombrable d'irrationnels. C'est la magie des nombres qui perturbe beaucoup de personnes peut réceptives à la beauté des mathématiques.

Il n'est pas question de donner une démonstration de cette propriété fondamentale de la topologie mathématique. En revanche, il est important de réaliser qu'entre deux rationnels il existe toujours un autre rationnel : on dit que $\mathbb{Q}$ est dense.

Pourquoi ? Rappelons que $x \in \mathbb{Q}$ si et seulement si il existe $p$ et $q$ appartenant tous deux à  $\mathbb{N}$ tels que $ x = p/q$. Considérons $x$ et $y$ dans $\mathbb{Q}$ et prenons en la moyenne arithmétique $z$ (i.e. : $z = (x+y)/2$).

Est-ce un rationnel? Comme $x$ est rationnel, il existe $x_1$ et $x_2$ dans $\mathbb{N}$ tel que $x = x_1/x_2$ et il en va de même pour $y$ (il existe $y_1$ et $y_2$ dans $\mathbb{R}$ tels que $y = y_1/y_2$). Donc :

Comme $x_1$,$x_2$, $y_1$ et $y_2$ sont des entiers, il en va de même pour $x_1 y_2$, $y_1 x_2$ et $x_2 y_2$ sont aussi des entiers. Donc $x_1 y_2 + y_1x_2$ est aussi un entier et $z$ est bien le rapport de deux entiers. Donc $z \in \mathbb{Q}$. Il reste à  démontrer que si $x < y$ alors $x < z < y$.

Mais, si $x < y$, il en va de même pour $x/2 < y/2$. Or : \[ z = \frac{x+y}{2}<\frac{y+y}{2} = y \hspace{.25cm}\text{et}\hspace{.25cm} z = \frac{x+y}{2}>\frac{x+x}{2} = x \]

Par conséquent, on a bien : $x < z < y$. En conséquence, $\mathbb{Q}$ est un ensemble dense. On peut donc toujours trouver un rationnel plus petit que deux rationnels donnés.

Le fait de travailler avec des rationnels est une nécessité quand on pense aux problèmes que peuvent poser les troncations liées à  l'usage pratique des réels et ce particulièrement si ces réels sont petits ou s'ils sont grands. Mais ce n'est pas la panacée. En effet, pour les grands nombres, on est obligé d'employer une notation en puissance de 10 qui est moins précise que la notation habituelle et qui peut concourir à  des erreurs de calcul, surtout quand ces erreurs se composent les unes avec les autres.

☝ 👉