LES ÉTAPES DE L’ALGORITHME DU SIMPLEXE

Ce document présente les étapes essentielles de l'algorithme du simplexe, méthode fondamentale pour résoudre les programmes linéaires (PL). Il s'adresse aux étudiants en optimisation, mathématiques appliquées ou gestion qui souhaitent comprendre la transformation des contraintes, la construction des solutions de base, ainsi que le déroulement itératif de l'algorithme jusqu'à son critère d'arrêt.

Introduction

Un programme linéaire (PL) est dit sous forme standard lorsque toutes ses contraintes sont des équations et que toutes ses variables sont non négatives. Cette forme est notée (PL=). L'algorithme du simplexe nécessite que le programme soit sous cette forme pour pouvoir être appliqué efficacement.

Variables d’écart et d’excédent

Avant d'appliquer l'algorithme du simplexe, il faut convertir le programme linéaire en un programme équivalent où toutes les contraintes sont des équations et toutes les variables sont non négatives.

• Contraintes de type ≤ : Pour chaque contrainte de ce type, on ajoute une variable d’écart, notée généralement s, qui est positive ou nulle. Cela transforme la contrainte en une équation.
• Exemple : La contrainte 3x1 + 2x2 ≤ 2 devient 3x1 + 2x2 + s = 2 avec s ≥ 0.
• Contraintes de type ≥ : Pour chaque contrainte de ce type, on retranche une variable d’excédent, notée généralement e, qui est positive ou nulle, pour obtenir une équation.
• Exemple : La contrainte 3x1 + 2x2 ≥ 2 devient 3x1 + 2x2 – e = 2 avec e ≥ 0.

Un programme linéaire contenant uniquement des contraintes ≤ est noté (PL), tandis qu’un programme avec contraintes ≤, ≥, et = est noté (PG). Lorsqu’ils sont convertis pour que toutes les contraintes soient des équations avec variables non négatives, ils sont notés respectivement (PL=) et (PG=).

Variables de base et variables hors base

Considérons un système de m équations à n variables avec n ≥ m. Une solution de base est obtenue en procédant ainsi :

1. On fixe n – m variables à zéro. Ces variables sont appelées variables hors base (V.H.B.).
2. On résout le système pour les m variables restantes, appelées variables de base (V.B.).
3. Le vecteur formé par ces variables de base et hors base constitue une solution de base.

Une solution de base est dite admissible si toutes ses variables sont supérieures ou égales à zéro. Il est important que le nombre de variables soit égal au nombre d’équations pour que cette solution soit bien définie.

Solutions admissibles

Une solution de base admissible de (PL=) est une solution de base pour laquelle toutes les variables sont non négatives. Cette solution correspond à un point extrême du domaine admissible du programme linéaire.

Résolution du programme linéaire (PL)

Pour illustrer l’algorithme du simplexe, considérons l’exemple suivant :

Maximiser Z = 1000x1 + 1200x2
Sous contraintes :
10x1 + 5x2 ≤ 200
2x1 + 3x2 ≤ 60
x1 ≤ 34
x2 ≤ 14
x1, x2 ≥ 0

Après ajout des variables d’écart s1, s2, s3, s4, le système devient :

10x1 + 5x2 + s1 = 200
2x1 + 3x2 + s2 = 60
x1 + s3 = 34
x2 + s4 = 14
x1, x2, s1, s2, s3, s4 ≥ 0

Les variables hors base initiales sont x1 et x2 (fixées à 0), et les variables de base sont s1, s2, s3, s4.

Étape A : Construction du tableau initial

Le tableau initial se construit avec :

• Les coefficients des contraintes (encadré bleu).
• Les coefficients de la fonction objectif (encadré rose).
• Les coefficients des variables dans la fonction objectif (encadré vert).
• Les valeurs des variables de base (encadré gris).
• La valeur de la fonction objectif (encadré orange), calculée à partir des variables de base.

Base	Coef. Z	x1	x2	s1	s2	s3	s4	bi
s1	0	10	5	1	0	0	0	200
s2	0	2	3	0	1	0	0	60
s3	0	1	0	0	0	1	0	34
s4	0	0	1	0	0	0	1	14

Étape B : Choix de la variable entrante

Pour un problème de maximisation, on choisit la variable hors base dont le coefficient Cj – zj est le plus grand.

Dans notre exemple, la variable x2 a le plus grand Cj – zj, donc elle entre dans la base.

Étape C : Choix de la variable sortante

La variable sortante est déterminée par le minimum des rapports bi / aij, où aij est le coefficient de la variable entrante dans la contrainte i, et bi la valeur de la contrainte i.

Calculs dans notre exemple :

• 200 / 5 = 40
• 60 / 3 = 20
• 14 / 1 = 14 (minimum)

La variable s4 sort donc de la base.

Étape D : Pivotage

Le pivot est l’élément à l’intersection de la ligne de la variable sortante et de la colonne de la variable entrante (ici 1).

Le pivotage consiste à :

1. Diviser la ligne du pivot par le pivot (ici division par 1).
2. Mettre à jour les autres lignes pour que la colonne de la variable entrante ait des coefficients nuls ailleurs.

Après pivotage, on obtient un nouveau tableau où la variable entrante remplace la variable sortante dans la base. Les coefficients sont recalculés selon la formule :

Cj – zj = Cj – Σ (Coef. Z de la base * coefficient de la variable dans la contrainte)

Par exemple, le coefficient 10 dans le tableau initial se calcule ainsi :

10 – 0 * 5 / 1 = 10

Un autre exemple pour obtenir -3 :

0 – 3 * 1 / 1 = -3

Les autres coefficients sont calculés de la même manière. Une fois le tableau rempli, on peut passer à l’itération suivante.

Le critère d’arrêt

L’algorithme du simplexe s’arrête lorsque le critère d’optimalité est atteint :

• Pour un problème de maximisation : tous les Cj – zj ≤ 0.
• Pour un problème de minimisation : tous les Cj – zj ≥ 0.

À ce stade, la solution courante est optimale.

Glossaire des termes clés

• Programme linéaire (PL) : Problème d’optimisation avec une fonction objectif linéaire et des contraintes linéaires.
• Forme standard : Forme d’un PL où toutes les contraintes sont des équations et toutes les variables sont non négatives.
• Variable d’écart : Variable ajoutée pour transformer une contrainte ≤ en équation.
• Variable d’excédent : Variable soustraite pour transformer une contrainte ≥ en équation.
• Variables de base (V.B.) : Variables choisies pour être résolues dans le système d’équations, non nulles dans la solution de base.
• Variables hors base (V.H.B.) : Variables fixées à zéro dans la solution de base.
• Solution de base : Solution obtenue en fixant les variables hors base à zéro et en résolvant pour les variables de base.
• Solution de base admissible : Solution de base avec toutes les variables ≥ 0.
• Tableau du simplexe : Tableau regroupant les coefficients des contraintes, de la fonction objectif, et les valeurs des variables pour chaque itération.
• Pivot : Élément clé du tableau utilisé pour effectuer le changement de base lors d’une itération.
• Critère d’arrêt : Condition indiquant que la solution optimale a été trouvée (Cj – zj ≤ 0 pour maximisation).

Points clés à retenir

• L’algorithme du simplexe nécessite que le programme linéaire soit sous forme standard.
• Les variables d’écart et d’excédent permettent de convertir les inégalités en équations.
• Une solution de base est obtenue en fixant certaines variables à zéro et en résolvant pour les autres.
• Le tableau du simplexe organise les données du problème et facilite les calculs itératifs.
• Le choix des variables entrantes et sortantes repose sur les coefficients Cj – zj et les rapports bi / aij.
• Le pivotage met à jour le tableau pour passer à une nouvelle solution de base.
• L’algorithme s’arrête lorsque le critère d’optimalité est satisfait, garantissant une solution optimale.