Optimisation lineaire avec contraintes -Programmation linair
Télécharger PDFOptimisation de la Production de Mines d'Or : Étude de Cas en Programmation Linéaire
Dans le cadre de la gestion industrielle, l'optimisation linéaire permet de minimiser les coûts de production tout en respectant des contraintes de ressources strictes. Ce guide technique analyse le cas d'une compagnie minière exploitant deux gisements d'or.
Problématique et Données de Production
Une compagnie possède deux mines, A et B. La production journalière varie selon la qualité du minerai extrait (exprimée en tonnes par jour) :
- Mine A : 1t (Haute), 3t (Moyenne), 5t (Basse). Coût journalier : 200 $.
- Mine B : 2t (Haute), 2t (Moyenne), 2t (Basse). Coût journalier : 200 $.
Les besoins minimaux de la compagnie sont de 80 tonnes de haute qualité, 160 tonnes de qualité moyenne et 200 tonnes de basse qualité.
Formalisation Mathématique du Problème Primal
L'objectif est de déterminer le nombre de jours de fonctionnement pour la mine A (noté x) et la mine B (noté y) afin de minimiser le coût total Z.
Fonction objective : Minimiser Z = 200x + 200y
Sous les contraintes :
- x + 2y ≥ 80 (Qualité haute)
- 3x + 2y ≥ 160 (Qualité moyenne)
- 5x + 2y ≥ 200 (Qualité basse)
- x ≥ 0, y ≥ 0
Résolution par la Méthode Géométrique
En traçant les droites de contraintes sur un plan cartésien, la zone de solutions réalisables est délimitée par les intersections des demi-plans. Le point optimal, qui minimise la fonction objective, se situe à l'intersection des droites D1 (x + 2y = 80) et D2 (3x + 2y = 160).
La résolution du système donne : x* = 40 jours et y* = 20 jours. Le coût minimal est donc de 12 000 $.
Résolution par la Méthode du Simplexe (Algorithme des Pénalités)
Pour résoudre ce problème de minimisation avec des contraintes de type "supérieur ou égal", on utilise la méthode des pénalités (Grand M). On introduit des variables d'écart (x3, x4, x5) et des variables artificielles (xa1, xa2, xa3).
La forme standard du problème devient alors :
Minimiser z = 200x + 200y + M(xa1 + xa2 + xa3)
Sous les contraintes d'égalité correspondantes.
Après plusieurs itérations et changements de base (entrées de x, puis y, puis x5), l'algorithme converge vers la solution optimale identique à la méthode géométrique : x = 40, y = 20, avec un coût total de 12 000.
Analyse de la Dualité
Le passage au problème dual permet d'interpréter la valeur intrinsèque des ressources (prix d'ombre). Le problème dual se définit ainsi :
Objectif : Maximiser W = 80u1 + 160u2 + 200u3
Sous les contraintes :
- u1 + 3u2 + 5u3 ≤ 200
- 2u1 + 2u2 + 2u3 ≤ 200
- u1, u2, u3 ≥ 0
La résolution du dual par le simplexe donne un maximum W = 12 000 pour u1 = 50 et u2 = 50 (avec u3 = 0).
Théorème de Complémentarité
La cohérence des résultats est confirmée par le théorème de dualité : la valeur minimale du primal est égale à la valeur maximale du dual (12 000). Le principe de complémentarité indique que puisque la troisième contrainte du primal est strictement satisfaite (5*40 + 2*20 = 240 > 200), la variable duale correspondante u3 est nulle.
Foire Aux Questions (FAQ)
Qu'est-ce qu'une variable artificielle dans la méthode du simplexe ?
Une variable artificielle est un outil mathématique utilisé pour trouver une base initiale réalisable lorsque l'origine n'est pas dans la zone de solution, notamment pour les contraintes de type "≥". Elles reçoivent une pénalité élevée (M) pour être éliminées lors de l'optimisation.
Pourquoi la solution optimale se trouve-t-elle souvent sur un sommet ?
Dans un problème de programmation linéaire, l'espace des solutions est un polyèdre convexe. La fonction objective étant linéaire, sa valeur optimale (maximum ou minimum) est nécessairement atteinte sur l'un des sommets du domaine réalisable.
Quelle est l'utilité concrète du problème dual ?
Le dual fournit des informations économiques cruciales. Par exemple, les variables u1, u2 et u3 représentent le montant maximal que la compagnie serait prête à payer pour obtenir une unité supplémentaire de chaque qualité d'or (prix d'ombre).