Chapitre 3: La Méthode de Simplexe

Ce chapitre présente la méthode du simplexe, une technique fondamentale en programmation linéaire utilisée pour résoudre des problèmes d’optimisation à plusieurs variables. Après une introduction sur les limites des méthodes géométriques, il détaille l’algorithme du simplexe, ses différentes formes, son application pratique à travers des exemples, ainsi que les cas particuliers et irrégularités pouvant survenir lors de son utilisation.

Introduction à la méthode du simplexe

La méthode géométrique est limitée aux problèmes à deux variables de décision. Pour des problèmes de taille quelconque, la méthode du simplexe, développée par George Dantzig en 1947, est la méthode privilégiée. Elle est très efficace et performante, notamment pour les problèmes de grande taille.

Principe et algorithme de la méthode du simplexe

L’algorithme du simplexe permet de déterminer la solution optimale d’un problème de programmation linéaire à n variables, si elle existe. Le principe consiste à transformer les contraintes, initialement des inéquations, en équations en ajoutant des variables dites variables d’écart (VE) qui sont positives. Ensuite, on transforme ce système d’équations linéaires jusqu’à obtenir la solution optimale.

Étapes de la méthode du simplexe

• Formulation mathématique du problème : Traduire le problème en expressions mathématiques.
• Mise sous forme standard : Transformer les contraintes en égalités en introduisant des variables d’écart et éventuellement des variables artificielles.
• Application de l’algorithme du simplexe : Résoudre le problème à l’aide du tableau de simplexe.

Différentes formes de problèmes en programmation linéaire

Formes canoniques

Les contraintes sont sous forme d’inégalités (≤ ou ≥). On distingue :

• Forme canonique de type 1 : contraintes ≤, objectif de maximisation.
• Forme canonique de type 2 : contraintes ≥, objectif de minimisation.

Forme mixte

Les contraintes sont un mélange d’inégalités supérieures ou égales (≥) et inférieures ou égales (≤). La fonction objective peut être de maximisation ou de minimisation.

Forme standard

• Toutes les contraintes sont des égalités.
• L’objectif est soit de maximiser soit de minimiser.

Introduction des variables d’écart et variables artificielles

Pour passer des formes canoniques à la forme standard, on introduit :

• Variables d’écart (VE) : variables positives ajoutées pour transformer les inégalités en égalités.
• Variables artificielles (VA) : variables introduites pour faciliter le démarrage de l’algorithme dans certains cas, notamment pour les contraintes ≥.
• Variables réelles (VR) : variables initiales du programme.

La méthode du simplexe en détail

Le principe est basé sur la solution graphique où la solution optimale se trouve à un sommet du polyèdre des solutions réalisables. La méthode consiste à se déplacer de sommet en sommet en améliorant la fonction objective à chaque étape.

Les données sont regroupées dans un tableau appelé tableau de simplexe. L’algorithme nécessite une solution de base initiale, c’est-à-dire une solution où toutes les variables hors base sont nulles.

Premier cas : inégalités de type inférieure ou égale (≤)

On construit le premier tableau de simplexe en transformant les contraintes en égalités en ajoutant des variables d’écart. Chaque colonne correspond à une variable, et la deuxième colonne indique les variables de base.

Les variables présentes dans la fonction objective sont hors base.

Étapes de l’algorithme pour la maximisation

1. Construire le tableau initial.
2. Identifier la variable entrante : choisir l’élément positif le plus grand dans la dernière ligne (ligne des coefficients réduits). Si aucun élément n’est positif, la solution est optimale.
3. Pour chaque ligne, calculer le quotient bi / aik (si aik > 0).
4. Choisir le plus petit quotient positif, correspondant à la ligne pivot. La variable sortante est celle associée à cette ligne.
5. Effectuer le pivot pour mettre à jour le tableau selon les formules de transformation.
6. Répéter les étapes 2 à 5 jusqu’à ce que tous les coefficients réduits soient négatifs ou nuls.

Exemple d’application

Un exemple numérique illustre la méthode avec des variables, contraintes et coefficients précis. Après plusieurs itérations, la solution optimale est atteinte lorsque tous les coefficients réduits (Ci - Zi) sont négatifs ou nuls.

Problème de minimisation

Un problème de minimisation peut être transformé en un problème de maximisation en considérant Min Z = Max (-Z), puis traité de la même manière.

Deuxième cas : inégalités de type supérieure ou égale (≥)

Dans ce cas, on introduit des variables artificielles (VA) en plus des variables d’écart. La fonction objectif est modifiée en ajoutant un terme M très grand (positif ou négatif selon le problème) multiplié par les variables artificielles, afin de forcer leur sortie de la base.

Le tableau de simplexe est construit en tenant compte de ces variables, et l’algorithme suit les mêmes étapes que précédemment.

Troisième cas : inégalités mixtes

Lorsque les contraintes sont un mélange d’inégalités ≤ et ≥, on combine les méthodes précédentes en introduisant à la fois variables d’écart et variables artificielles. La fonction objectif est ajustée avec les termes en M correspondants.

Problèmes irréguliers en méthode du simplexe

Quantité négative

Si une contrainte a un second membre négatif, la méthode ne s’applique pas directement. On multiplie toute la contrainte par -1 pour rendre ce second membre positif.

Variable sans contrainte de signe

Si une variable n’a pas de contrainte de non-négativité, on la remplace par la différence de deux variables non négatives :

x = x' - x'' avec x', x'' ≥ 0

Ce changement permet d’intégrer la variable dans la méthode du simplexe.

Problèmes à solution impossible

Un problème est impossible si l’ensemble des solutions réalisables est vide. En méthode du simplexe, cela se traduit par la présence de variables artificielles dans la base à la fin de l’algorithme, avec une valeur non nulle. Cela signifie que la solution obtenue n’est pas réalisable.

Remarque : Un programme avec uniquement des contraintes de type ≤ et un second membre positif ne peut pas être impossible, car aucune variable artificielle n’est introduite.

Problèmes à solution infinie

Graphiquement, cela correspond à la possibilité de déplacer indéfiniment la droite de la fonction objectif tout en restant dans l’ensemble des solutions réalisables, ce qui fait croître la valeur de la fonction objective sans borne.

En méthode du simplexe, ce cas est détecté lorsque la variable entrante n’a aucune limite sur sa valeur, c’est-à-dire que tous les ratios bi / aik sont négatifs ou nuls.

Problèmes à solutions multiples

Graphiquement, ce cas se produit lorsque la pente de la fonction objectif est égale à la pente d’une contrainte restrictive, ce qui crée un segment de solutions optimales.

En méthode du simplexe, la présence d’une variable hors base avec un coefficient réduit (Cj - Zj) nul dans le tableau optimal indique l’existence de solutions multiples. Cette variable peut entrer dans la base sans modifier la valeur optimale.

Il suffit alors de connaître les points extrêmes de ce segment pour décrire l’ensemble des solutions optimales.

Points clés

• La méthode du simplexe est une méthode algorithmique efficace pour résoudre des problèmes de programmation linéaire à n variables.
• Elle transforme les contraintes en égalités en introduisant des variables d’écart et, si nécessaire, des variables artificielles.
• L’algorithme se base sur le déplacement d’un sommet à un autre du polyèdre des solutions réalisables, en améliorant la fonction objective à chaque étape.
• Le tableau de simplexe regroupe les données et permet de suivre les itérations de la méthode.
• Les problèmes peuvent être de maximisation ou de minimisation, et la minimisation peut être transformée en maximisation.
• Des cas particuliers comme les contraintes mixtes, variables sans contrainte de signe, ou quantités négatives nécessitent des adaptations spécifiques.
• La méthode détecte les problèmes irréguliers : solution impossible, solution infinie, ou solutions multiples.
• La présence de variables artificielles dans la solution finale signale un problème impossible.
• Un coefficient réduit nul pour une variable hors base dans la solution optimale indique des solutions multiples.