Methodes numeriques optimisation lineaire -Programmation lin
Télécharger PDFCorrigé des Exercices d'Optimisation Linéaire
Ce document présente les solutions détaillées pour divers exercices de programmation linéaire, en mettant l'accent sur la méthode du simplexe, la gestion des variables d'écart et la dualité.
1. Méthode du Simplexe : Résolution de Programmes Linéaires
La méthode du simplexe est un algorithme itératif utilisé pour trouver la solution optimale d'un programme linéaire. Voici la résolution d'un premier modèle de maximisation.
Programme 1 :
Max (x1 + 2x2)
Sous les contraintes :
x1 + 3x2 ≤ 21
-x1 + 3x2 ≤ 18
x1 - x2 ≤ 5
Avec x1, x2 ≥ 0
Pour résoudre ce problème, on introduit des variables d’écart (x3, x4, x5) pour transformer les inégalités en équations :
x1 + 3x2 + x3 = 21
-x1 + 3x2 + x4 = 18
x1 - x2 + x5 = 5
Après plusieurs itérations et transformations du pivot (choix de la variable entrante selon le coefficient le plus négatif dans la ligne de la fonction objectif), on obtient la solution optimale suivante :
x*1 = 9
x*2 = 4
x*4 = 15
Les variables x3 et x5 sont nulles, ce qui indique que la première et la troisième contrainte sont saturées.
Programme 2 :
Pour un problème de minimisation comme Min (x1 - 3x2), on transforme l'objectif en maximisation : Max (-x1 + 3x2). La procédure suit les mêmes étapes de pivotage jusqu'à ce qu'il n'y ait plus de termes négatifs dans la dernière ligne du tableau.
2. Application Pratique : Cas de la Raffinerie de Pétrole
Dans ce scénario, on cherche à maximiser la marge totale liée au traitement de deux types de pétrole brut (x1 et x2). La fonction objectif est Max (3x1 + 4x2) sous des contraintes de production pour l'essence, le gasoil et le fuel.
Les contraintes simplifiées sont :
5x1 + 7x2 ≤ 16500
x1 + x2 ≤ 2500
9x1 + 7x2 ≤ 21300
La solution optimale donne x*1 = 500 et x*2 = 2000, pour une valeur optimale de 9500. À ce stade, les quotas d'essence et de gasoil sont atteints (contraintes saturées), tandis qu'il reste un écart pour le fuel.
3. Méthode des Variables Ajoutées (ou Artificielles)
Cette méthode est indispensable lorsque l'origine (0,0) ne fait pas partie du domaine réalisable. On introduit des variables artificielles (xa) pour obtenir une solution de base initiale. L'objectif intermédiaire est de minimiser la somme de ces variables ajoutées pour les ramener à zéro.
Une fois que toutes les variables ajoutées sont sorties de la base, on reprend la fonction objectif initiale pour finaliser l'optimisation. Cette approche en deux phases permet de traiter des systèmes de contraintes plus complexes incluant des égalités ou des inégalités de type "supérieur ou égal".
4. Optimisation de la Production et Indices d'Octane
Le problème des indices d'octane illustre comment la programmation linéaire gère les mélanges. On définit x1A, x2A, x1B, x2B comme les quantités de ressources P1 et P2 pour fabriquer les essences A et B. Les contraintes portent sur la qualité finale (indice d'octane ≥ seuil) et la disponibilité des ressources.
L'optimisation montre que pour maximiser le profit, il faut saturer les quatre contraintes de ressources et de qualité. Par exemple, la solution peut mener à la fabrication de 1400 barils d'essence A et 7500 barils d'essence B.
5. Planification dans une Fabrique de Pièces Détachées
Ici, l'objectif est de maximiser la marge sur coût variable pour deux types de lots (A et B) produits dans trois ateliers (T, F, M).
Fonction objectif : Max (50x1 + 30x2).
La solution optimale indique une production de 60 lots de type A et 80 lots de type B. Les ateliers T et M sont utilisés à pleine capacité, tandis que l'atelier F présente une sous-utilisation (capacité résiduelle).
FAQ : Questions Fréquentes sur l'Optimisation Linéaire
Qu'est-ce qu'une variable d'écart ?
Une variable d'écart est ajoutée à une contrainte d'inégalité (≤) pour la transformer en égalité. Elle représente la différence entre la ressource disponible et la ressource réellement utilisée. Si elle est nulle à l'optimum, la contrainte est dite saturée.
Pourquoi transformer un problème de minimisation en maximisation ?
L'algorithme du simplexe standard est souvent formulé pour la maximisation. En multipliant la fonction objectif par -1, on peut utiliser le même algorithme. Il suffit de changer à nouveau le signe du résultat final pour obtenir la valeur minimale réelle.
Comment interpréter un prix dual ?
Le prix dual (ou variable duale) associé à une contrainte indique de combien la fonction objectif augmenterait si l'on disposait d'une unité supplémentaire de la ressource limitée. C'est un indicateur précieux pour l'aide à la décision économique.