L’algorithme du simplexe, développé en 1947, est l’une des méthodes numériques permettant de maximiser ou minimiser une fonction linéaire sous des contraintes linéaires, ce qu’on appelle un problème de programmation linéaire. Concrètement, ce type de problème apparaît dès qu’une entreprise cherche à allouer des ressources limitées : temps de production, budget publicitaire, capacité logistique. C’est donc un outil fondamental, et Python permet de l’appréhender de manière concrète et visuelle.
Fondements mathématiques
Tout problème de programmation linéaire peut s’écrire sous la forme standard :
\[
\max z = c^\top x \quad \text{sous} \quad Ax \leq b, \quad x \geq 0
\]
Où \(x \in \mathbb{R}^n\) est le vecteur des variables de décision, \(c\) le vecteur des marges, \(A\) la matrice des contraintes et \(b\) le vecteur des ressources disponibles.
Exemple concret en petite dimension
Considérons une entreprise qui fabrique deux produits P1 et P2. P1 rapporte 5 € de marge, P2 rapporte 4 €. La contrainte de main-d’œuvre impose \(2x_1 + x_2 \leq 20\) et la contrainte de matières premières impose \(x_1 + 2x_2 \leq 20\), avec \(x_1, x_2 \geq 0\) puisqu’il s’agit du nombre de produit 1 et 2 créés. On cherche à maximiser le chiffre d’affaires \(z = 5x_1 + 4x_2\).
Pour transformer les inégalités en égalités, on introduit des variables d’écart \(s_1, s_2 \geq 0\) :
\[
2x_1 + x_2 + s_1 = 20 \qquad x_1 + 2x_2 + s_2 = 20
\]
Les variables d’écart ont une interprétation économique directe : \(s_1\) représente la main-d’œuvre inutilisée, \(s_2\) les matières premières non consommées. Quand une contrainte est saturée, la variable d’écart correspondante vaut 0. On part d’une solution de base initiale évidente : \(x_1 = x_2 = 0\), \(s_1 = 20\), \(s_2 = 20\). C’est le sommet origine, aucune production, toutes les ressources disponibles.
Le tableau simplexe
Le cœur de l’algorithme est le tableau simplexe, qui organise toutes les informations du problème en une matrice. On y inscrit les coefficients du système, plus la ligne objectif réécrite sous la forme \(-z + 5x_1 + 4x_2 = 0\) (l’algorithme nous permet de minimiser \(z\) et cela revient à maximiser \(-z\)), en basculant les coefficients de \(z\) avec un signe négatif :
\[
\begin{array}{c|ccccc}
\text{Base} & x_1 & x_2 & s_1 & s_2 & b \\
\hline
s_1 & 2 & 1 & 1 & 0 & 20 \\
s_2 & 1 & 2 & 0 & 1 & 20 \\
-z & -5 & -4 & 0 & 0 & 0 \\
\end{array}
\]
Chaque ligne (hors objectif) correspond à une contrainte. La colonne \(b\) donne la valeur actuelle de chaque variable de base et la ligne \(-z\) indique le gain marginal de chaque variable hors base : un coefficient de \(-5\) sur \(x_1\) signifie qu’augmenter \(x_1\) d’une unité améliore \(z\) de 5.
Le mécanisme de pivot
Ici, le raisonnement est sensiblement le même que pour l’inversion d’une matrice, puisqu’il fonctionne avec la méthode du pivot de Gauss.
Le critère d’entrée consiste à choisir la variable dont le coefficient dans la ligne objectif est le plus négatif. Ici, \(x_1\) (coefficient \(-5\)) entre en premier : c’est le produit qui améliore le plus \(z\) par unité produite. La colonne \(x_1\) est la colonne pivot.
Le critère de sortie, aussi appelé ratio test, détermine quelle contrainte devient saturée en premier quand on augmente \(x_1\). Pour chaque ligne, on calcule le ratio \(b_i / a_i\) en ne retenant que les coefficients strictement positifs :
\[
\text{Ligne } s_1 : \frac{20}{2} = 10 \qquad \text{Ligne } s_2 : \frac{20}{1} = 20
\]
Le minimum est 10 : la contrainte de main-d’œuvre est saturée en premier, donc \(s_1\) sort de la base. L’élément pivot est \(a_{11} = 2\). L’intuition économique est immédiate : si on augmente \(x_1\) au-delà de 10, la contrainte de main-d’œuvre est violée.
L’opération de pivot transforme la colonne \(x_1\) en vecteur unitaire, exactement comme en élimination de Gauss. On divise d’abord la ligne pivot par le pivot :
\[
L_1 \leftarrow L_1 / 2
\]
Puis on élimine \(x_1\) des autres lignes :
\[
L_2 \leftarrow L_2 – 1 \times L_1 \qquad L_z \leftarrow L_z + 5 \times L_1
\]
Le tableau devient :
\[
\begin{array}{c|ccccc}
\text{Base} & x_1 & x_2 & s_1 & s_2 & b \\
\hline
x_1 & 1 & 1/2 & 1/2 & 0 & 10 \\
s_2 & 0 & 3/2 & -1/2 & 1 & 10 \\
-z & 0 & -3/2 & 5/2 & 0 & 50 \\
\end{array}
\]
On lit : \(x_1 = 10\), \(s_2 = 10\), \(x_2 = s_1 = 0\), donc on est au sommet \((10, 0)\) avec \(z = 50\). Il reste \(-3/2\) dans la ligne objectif : on n’est pas encore à l’optimum.
On réitère ensuite le procédé identique pour obtenir la matrice suivante :
\[
\begin{array}{c|ccccc}
\text{Base} & x_1 & x_2 & s_1 & s_2 & b \\
\hline
x_1 & 1 & 0 & 2/3 & -1/3 & 20/3 \\
x_2 & 0 & 1 & -1/3 & 2/3 & 20/3 \\
-z & 0 & 0 & 2 & 1 & 140/3 \\
\end{array}
\]
Tous les coefficients de la ligne objectif (\(z\) sont désormais positifs ou nuls : critère d’optimalité atteint. On lit :
\[
x_1 = x_2 = \frac{20}{3} \approx 6,67 \quad s_1 = s_2 = 0 \quad z = \frac{140}{3} \approx 46,67 \text{ €}
\]
Implémentation Python
Retour à l’exemple précédent
Avec la bibliothèque scipy, le problème se résout en quelques lignes, contrairement à toute la manipulation que nous venons d’effectuer à la main. On remarquera que linprog minimise par convention, donc on passe \(-c\) pour maximiser :
Comme « linprog » minimise toujours, attention à bien inverser les signes. Ainsi, la ligne C minimise \(−5x_1 −4x_2\) donc à maximiser \(5x_1 + 4x_2\). On définit ensuite la matrice des contraintes \(2x_1
+x_2\) et
\(x_1+2x_2\). Le vecteur b correspond ensuite aux contraintes de telle sorte que l’on définit pour Python :
\(
\begin{cases}
2x_1 + x_2 \le 20 \\
x_1 + 2x_2 \le 20 \\
\end{cases}
\)
Ensuite, on définit les bornes d’intervalles pour les valeurs de \(x_1\) et \(x_2\). Comme vu plus haut, on cherche des valeurs positives d’où l’intervalle \([0; +\infty[\). Ensuite, on implémente la ligne qui permet de faire le calcul de la solution et les résultats qui nous intéressent vont être placés dans « res » (la solution, la valeur optimale, les marges, etc.). Pour obtenir la solution, on affiche « -res.fun » (évidemment cela dépend du nom que tu as donné à la ligne 8, mais dans notre cas, comme il s’agit de « res », on affiche « -res.fun »).
Ensuite, « res.x » est une matrice contenant la solution optimale, donc on affiche « res.x[0] » pour obtenir \(x_1\) et « res.x[1] » pour obtenir \(x_2\). Les ressources restantes (non utilisées) s’obtiennent avec « res.slack[0] » (resp. 1).
On obtient alors la sortie suivante, conformément aux résultats que nous avions trouvés manuellement :
Extension à plus de deux variables
Dès qu’on passe à trois produits ou plus, la visualisation graphique devient impossible, mais le simplexe reste identique. Ajoutons P3 (marge 6 €, consomme 1 unité de main-d’œuvre et 3 de matières premières) :
Conclusion
Ainsi, l’algorithme du simplexe est un formidable outil qui permet de trouver des solutions pour des problèmes d’optimisation. D’autant que Python permet de trouver ces solutions très rapidement grâce à la bibliothèque scipy. Il est toutefois de bon goût de se familiariser avec les fondements mathématiques de cet article afin de comprendre véritablement ce qui se cache derrière cette ligne de code.
Tu peux retrouver ici le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder ici à toutes nos autres ressources mathématiques !
