Optimisation linéaire – Méthode du simplexe appliquée

Cette ressource porte sur l’optimisation linéaire et la méthode du simplexe, un outil fondamental en économie, gestion et ingénierie pour résoudre des problèmes d’allocation optimale de ressources. Elle s’adresse aux étudiants et chercheurs débutants souhaitant comprendre comment modéliser et résoudre des problèmes d’optimisation linéaire, notamment à travers des exemples concrets comme la production industrielle ou la gestion de ressources.

La question

Le travail aborde la résolution de problèmes d’optimisation linéaire, c’est-à-dire la maximisation ou la minimisation d’une fonction linéaire sous des contraintes linéaires. Le défi est de trouver la meilleure solution possible dans un ensemble de solutions réalisables, souvent limité par des ressources ou des capacités. La méthode du simplexe est présentée comme une technique efficace pour résoudre ces problèmes, même lorsque le domaine des solutions est complexe. L’étude inclut également la question de la dualité, qui permet d’interpréter économiquement les contraintes et les ressources.

Concepts de base

L’optimisation linéaire consiste à maximiser ou minimiser une fonction objectif linéaire, par exemple :

Max (c1 x1 + c2 x2 + ... + cn xn)

soumise à des contraintes linéaires exprimées sous forme d’inégalités ou d’égalités :

a11 x1 + a12 x2 + ... + a1n xn ≤ b1
a21 x1 + a22 x2 + ... + a2n xn ≤ b2
...
am1 x1 + am2 x2 + ... + amn xn ≤ bm
x1, x2, ..., xn ≥ 0

Les variables x1, x2, ..., xn représentent les quantités à déterminer, les coefficients aij définissent les contraintes, et les bi sont les ressources disponibles.

La méthode du simplexe est une procédure itérative qui permet de parcourir les sommets du polyèdre formé par les contraintes pour trouver la solution optimale. Elle repose sur :

• L’introduction de variables d’écart (ou variables slack) pour transformer les inégalités en égalités.
• La sélection d’une base initiale, c’est-à-dire un ensemble de variables dites de base, qui permet d’exprimer les autres variables.
• Le choix à chaque étape d’une variable entrante (qui améliore la fonction objectif) et d’une variable sortante (qui quitte la base pour conserver la faisabilité).
• La réalisation d’un pivot pour mettre à jour le tableau du simplexe et avancer vers l’optimum.

La dualité est un concept clé qui associe à chaque problème primal un problème dual. Les prix duaux (ou multiplicateurs de Lagrange) sont des coefficients qui mesurent la valeur marginale des ressources. Ils permettent d’interpréter économiquement les contraintes et d’évaluer l’impact des variations des ressources sur la fonction objectif.

Approche

La méthode appliquée consiste à :

• Formuler le problème d’optimisation linéaire en introduisant les variables d’écart pour convertir les inégalités en égalités.
• Construire le tableau initial du simplexe, avec la fonction objectif exprimée en fonction des variables hors-base.
• Identifier la variable entrante en choisissant celle qui améliore le plus la fonction objectif (correspondant à l’élément le plus négatif dans la dernière ligne du tableau).
• Déterminer la variable sortante en calculant le plus petit rapport positif entre les valeurs de la colonne de droite et la colonne de la variable entrante.
• Effectuer un pivot pour mettre à jour le tableau, puis répéter le processus jusqu’à ce qu’il n’y ait plus de termes négatifs dans la dernière ligne, indiquant l’optimalité.
• Dans les cas où l’origine n’est pas réalisable (les contraintes ne sont pas satisfaites pour x = 0), utiliser la méthode des variables ajoutées qui introduit des variables supplémentaires pour trouver un point de départ réalisable.

Cette méthode est illustrée par plusieurs exemples concrets :

• Maximisation de marges dans une raffinerie de pétrole avec contraintes sur les quotas de production.
• Planification de production dans une fabrique de pièces détachées avec contraintes sur les ateliers.
• Optimisation de la production de moteurs avec contraintes de temps opératoire et quotas de marché.
• Gestion des matériaux extraits dans une carrière avec contraintes de rendement et de redevance.
• Calcul des indices d’octane dans la fabrication d’essences, avec contraintes de qualité et disponibilité des ressources.
• Analyse de la dualité pour comprendre la valeur des ressources et la rentabilité des investissements.

Résultats

Les exercices corrigés montrent que la méthode du simplexe permet de trouver des solutions optimales précises, avec :

• Des valeurs optimales des variables de décision (quantités à produire, extraire, etc.).
• La saturation ou non des contraintes, indiquant quelles ressources sont pleinement utilisées.
• Des marges maximales ou coûts minimaux associés à ces solutions.
• La possibilité d’interpréter les prix duaux pour évaluer la pertinence d’augmenter les capacités ou ressources.
• La méthode des variables ajoutées permet de traiter des problèmes où le point initial n’est pas réalisable, en trouvant un point de départ admissible.

Par exemple, dans le cas de la raffinerie, la solution optimale consiste à traiter 500 unités de brut 1 et 2000 unités de brut 2, avec une marge totale de 9500. Certaines contraintes sont saturées, ce qui signifie que les quotas sont atteints, tandis que d’autres présentent un écart, indiquant une sous-utilisation.

Dans l’exemple de la fabrique de pièces détachées, la solution optimale maximise la marge totale à 5400, avec une pleine utilisation de certains ateliers et un reste de capacité dans d’autres.

Les exercices sur la dualité montrent comment les prix duaux peuvent guider les décisions d’investissement : une augmentation de capacité est rentable si son coût est inférieur au prix dual associé.

Limites et questions ouvertes

Le document souligne certaines limites :

• La méthode du simplexe nécessite un point de départ réalisable ; lorsque ce n’est pas le cas, la méthode des variables ajoutées est nécessaire, mais elle ajoute une complexité supplémentaire.
• Les problèmes présentés sont linéaires et ne prennent pas en compte d’éventuelles non-linéarités ou incertitudes.
• La validité des prix duaux dépend du maintien de la base optimale ; des variations trop importantes des ressources peuvent changer la base et donc les prix duaux.
• La résolution graphique est limitée à deux variables et ne peut être utilisée que pour des problèmes simples.

Glossaire

• Optimisation linéaire : Recherche d’un maximum ou minimum d’une fonction linéaire sous contraintes linéaires.
• Méthode du simplexe : Algorithme itératif pour résoudre les problèmes d’optimisation linéaire en parcourant les sommets du domaine réalisable.
• Variables d’écart : Variables ajoutées pour transformer des inégalités en égalités dans les contraintes.
• Variables de base : Variables sélectionnées à chaque étape du simplexe qui forment une base pour exprimer les autres variables.
• Pivot : Opération mathématique qui permet de changer la base dans le tableau du simplexe.
• Variables hors-base : Variables non incluses dans la base à un instant donné, généralement mises à zéro.
• Prix duaux : Coefficients associés aux contraintes dans le problème dual, représentant la valeur marginale des ressources.
• Méthode des variables ajoutées : Technique pour trouver un point de départ réalisable lorsque l’origine ne satisfait pas les contraintes.
• Contrainte saturée : Contrainte pour laquelle la solution optimale atteint exactement la limite imposée.
• Domaine réalisable : Ensemble des solutions qui satisfont toutes les contraintes du problème.