La méthode du simplexe

Objectifs du chapitre — À la fin de ce chapitre, vous saurez :

• définir une solution de base réalisable et son lien avec les sommets du domaine ;
• construire le tableau initial du simplexe à partir de la forme standard ;
• choisir la variable entrante et la variable sortante (critère du ratio minimal) ;
• effectuer un pivotage et reconnaître le tableau optimal ;
• traiter les contraintes de type supérieur ou égal (méthode du grand M) et les cas particuliers.

3.1 Pourquoi une méthode algébrique ?

La méthode graphique ne fonctionne qu'avec deux variables. Dans la pratique, une raffinerie, une compagnie aérienne ou un plan de production industriel comptent des centaines ou des milliers de variables. La méthode du simplexe (Dantzig, 1947) généralise l'idée du chapitre 2 : partir d'un sommet du domaine, puis passer à un sommet voisin qui améliore l'objectif, jusqu'à ce qu'aucun voisin ne soit meilleur.

3.2 Solutions de base

Sous forme standard, le programme comporte $m$ équations et $n$ variables (variables d'écart comprises), avec $n > m$.

Définition — Solution de base : solution obtenue en fixant $n - m$ variables à zéro (variables hors base) et en résolvant le système pour les $m$ autres (variables de base). Elle est réalisable si toutes les variables de base sont positives ou nulles.

Chaque solution de base réalisable correspond à un sommet du domaine. Pour l'atelier de meubles, $m = 3$ et $n = 5$ ($x_1, x_2, s_1, s_2, s_3$) : la solution $x_1 = x_2 = 0$, $s_1 = 100$, $s_2 = 80$, $s_3 = 40$ correspond à l'origine. C'est la solution de départ naturelle quand toutes les contraintes sont de type $\le$ avec des seconds membres positifs.

3.3 Le tableau du simplexe

On écrit les équations de la forme standard dans un tableau, avec une dernière ligne pour l'objectif, réécrit sous la forme $Z - 300\,x_1 - 200\,x_2 = 0$.

Tableau 1 (base : $s_1, s_2, s_3$ ; sommet O)

3.4 Les règles du pivotage

1. Variable entrante : la variable hors base dont le coefficient dans la ligne $Z$ est le plus négatif (c'est elle qui augmente le plus $Z$ par unité). Ici, $x_1$ (− 300).
2. Variable sortante : pour chaque ligne où le coefficient de la colonne entrante est strictement positif, on calcule le ratio second membre / coefficient. La ligne du plus petit ratio sort : c'est la première contrainte qui devient saturée quand $x_1$ augmente. Ici, $s_3$ (ratio 40).
3. Pivotage : on divise la ligne pivot par le pivot (ici 1), puis on annule les autres coefficients de la colonne entrante en retranchant des multiples de la ligne pivot.

Tableau 2 (base : $s_1, s_2, x_1$ ; sommet A)

Opérations : $L_1 \leftarrow L_1 - 2L_3$ ; $L_2 \leftarrow L_2 - L_3$ ; $L_Z \leftarrow L_Z + 300\,L_3$.

$x_2$ entre (− 200), $s_1$ sort (ratio 20).

Tableau 3 (base : $x_2, s_2, x_1$ ; sommet B)

Opérations : $L_2 \leftarrow L_2 - L_1$ ; $L_Z \leftarrow L_Z + 200\,L_1$.

$s_3$ entre (− 100) ; seules les lignes 2 et 3 ont un coefficient positif ; $s_2$ sort (ratio 20).

Tableau 4 (base : $x_2, s_3, x_1$ ; sommet C)

Opérations : $L_1 \leftarrow L_1 + 2L_2$ ; $L_3 \leftarrow L_3 - L_2$ ; $L_Z \leftarrow L_Z + 100\,L_2$.

3.5 Le critère d'optimalité et la lecture du tableau final

Critère d'optimalité (maximisation) : le tableau est optimal quand aucun coefficient de la ligne $Z$ n'est négatif.

Lecture du tableau 4 : $x_1 = 20$, $x_2 = 60$, $s_3 = 20$ (variables de base) ; $s_1 = s_2 = 0$ (hors base, contraintes saturées) ; $Z = 18\,000$. On retrouve exactement la solution graphique, après avoir parcouru les sommets O → A → B → C.

Les coefficients de $s_1$ et $s_2$ dans la ligne $Z$ (100 et 100) sont les coûts réduits des variables d'écart : ils indiquent de combien $Z$ diminuerait si l'on imposait une heure inutilisée de menuiserie ou de finition, donc la valeur d'une heure supplémentaire. Ce sont les prix fictifs du chapitre 4.

Un coût réduit nul pour une variable hors base à l'optimum signale un optimum multiple : la faire entrer donne un autre sommet de même valeur.

3.6 Les contraintes de type supérieur ou égal : la méthode du grand M

Une contrainte $x_1 + x_2 \ge 7$ devient $x_1 + x_2 - e = 7$ ; la variable d'excédent $e$ a un coefficient $-1$ et ne peut pas servir de variable de base de départ (elle vaudrait − 7). On ajoute une variable artificielle $a \ge 0$ : $x_1 + x_2 - e + a = 7$, et on la pénalise fortement dans l'objectif : $\max Z - M a$ avec $M$ très grand. Le simplexe chasse alors les variables artificielles de la base.

Si, à l'optimum, une variable artificielle reste positive, le programme est impossible. La méthode en deux phases est équivalente : on minimise d'abord la somme des variables artificielles, puis on optimise l'objectif réel.

3.7 Les cas particuliers dans le tableau

• Programme non borné : la colonne entrante n'a aucun coefficient positif, aucun ratio n'est calculable : $Z$ peut croître sans limite.
• Dégénérescence : égalité de deux ratios minimaux ; une variable de base vaut 0. Le simplexe peut alors « tourner » sans améliorer $Z$ (cyclage), d'où des règles de choix particulières (règle de Bland).
• Minimisation : on maximise $-Z$, ou l'on choisit comme entrante la variable de coefficient le plus positif et l'on s'arrête quand tous sont négatifs ou nuls.

3.8 Méthode : appliquer le simplexe

1. Écrire la forme standard (variables d'écart, éventuellement artificielles).
2. Construire le tableau initial ; la ligne $Z$ contient les coefficients de l'objectif changés de signe.
3. Choisir la variable entrante (coefficient le plus négatif de la ligne $Z$).
4. Calculer les ratios sur les coefficients strictement positifs ; la variable sortante a le plus petit ratio.
5. Pivoter ; recommencer jusqu'à ce que la ligne $Z$ n'ait plus de coefficient négatif.
6. Lire la solution, vérifier dans les contraintes d'origine et interpréter les coûts réduits.

Les pièges à éviter

• Calculer un ratio avec un coefficient nul ou négatif (il faut l'ignorer).
• Oublier de mettre à jour la ligne $Z$ lors du pivotage.
• Lire la valeur d'une variable hors base dans la colonne du second membre : une variable hors base vaut 0.
• Arrêter le simplexe alors qu'un coefficient de la ligne $Z$ est encore négatif.
• Oublier de vérifier la solution finale dans les contraintes initiales.