Optimisation lineaire avec la methode graphique -Programmati
Télécharger PDFMéthode Géométrique pour l'Optimisation Linéaire
La méthode géométrique est une approche visuelle permettant de résoudre des problèmes d'optimisation linéaire, généralement limitée à deux variables de décision. Elle consiste à délimiter graphiquement la région réalisable définie par les contraintes et à identifier les points extrêmes (sommets) de cette région. La fonction objectif est ensuite évaluée à chacun de ces sommets pour déterminer la solution optimale.
Exemple 1
Objectif : Maximiser Z = x1 + 2x2
Sous contraintes :
- 3x1 + 2x2 ≤ 9
- x1 + 2x2 ≤ 4
- x1 ≥ 0, x2 ≥ 0
Solution optimale : Zmax = 8
Exemple 2
Objectif : Maximiser Z = x1 + x2
Sous contraintes :
- x1 + x2 ≤ 4
- 3x1 + x2 ≤ 3
- x1 ≥ 0, x2 ≥ 0
Solution optimale : Zmax = 3 (atteinte au point x1 = 1, x2 = 2)
Exemple 3
Objectif : Maximiser Z = 10x1 + 20x2
Sous contraintes :
- 2x1 + x2 ≤ 30
- x1 + 4x2 ≤ 64
- 5x1 + 6x2 ≤ 110
- x1 ≥ 0, x2 ≥ 0
Solution optimale : Zmax = 340 (atteinte au point x1 = 4, x2 = 15)
Méthode du Simplexe
La méthode du simplexe est un algorithme itératif systématique pour résoudre des problèmes d'optimisation linéaire avec un nombre quelconque de variables. Elle progresse de sommet en sommet de la région réalisable, améliorant la valeur de la fonction objectif à chaque étape, jusqu'à l'identification de la solution optimale.
Exemple 1
Forme standard :
Objectif : Minimiser W = -3x1 - 2x2 (ce qui est équivalent à maximiser Z = 3x1 + 2x2)
Sous contraintes :
- 3x1 + 2x2 + x3 = 2
- x1 + 2x2 + x4 = 4
- x1 + x2 + x5 = 5
- x1, x2, x3, x4, x5 ≥ 0
Les variables x3, x4, x5 sont des variables d'écart (ou variables d'ajustement).
Tableau du Simplexe Initial
La base actuelle B = (x3, x4, x5) est réalisable. Sa solution est : x1 = 0, x2 = 0, x3 = 2, x4 = 4, x5 = 5. La valeur de la fonction objectif W est 0.
Puisque la ligne de la fonction objectif (ligne W) contient des coefficients négatifs (-3 pour x1 et -2 pour x2), la solution actuelle n'est pas optimale. Un changement de base est nécessaire.
Première Itération
- Variable entrante : x2 (identifiée comme ayant le coefficient le plus négatif, ou selon la règle de choix spécifiée dans les notes originales).
- Détermination de la variable sortante : Le calcul des ratios entre la colonne "Solution" et les coefficients positifs de la colonne de la variable entrante x2 donne :
- 2 / 2 = 1 (pour la ligne x3)
- 4 / 2 = 2 (pour la ligne x4)
- 5 / 1 = 5 (pour la ligne x5)
- Recherche du pivot : L'intersection de la ligne de la variable sortante x3 et de la colonne de la variable entrante x2 est le pivot (valeur 2).
Deuxième Tableau du Simplexe
Après les opérations de pivot, la nouvelle base est B = (x2, x4, x5). La solution est : x1 = 0, x2 = 1, x3 = 0, x4 = 2, x5 = 4. La valeur de la fonction objectif est W = -2 (ce qui signifie Z = 2 pour le problème de maximisation équivalent).
Le coefficient de x1 dans la ligne W (-4) étant négatif, la solution n'est pas encore optimale.
Deuxième Itération
- Variable entrante : x1 (identifiée comme ayant un coefficient négatif dans la ligne W).
- Détermination de la variable sortante : Le calcul des ratios (en ne considérant que les coefficients positifs de x1 dans les lignes des variables de base) :
- Pour la ligne x2 : 1 / (3/2) = 2/3
- Pour la ligne x4 : Le coefficient de x1 est -2 (négatif, non pris en compte pour le ratio).
- Pour la ligne x5 : Le coefficient de x1 est -1/2 (négatif, non pris en compte pour le ratio).
- Recherche du pivot : En suivant la désignation originale d'une variable sortante x4, le pivot serait le coefficient de x1 dans la ligne de x4, soit -2. Cependant, un pivot doit toujours être positif dans la méthode du simplexe standard.
Troisième Tableau du Simplexe
Après les opérations de pivot, la base actuelle est B = (x1, x2, x5). La solution est : x1 = 1, x2 = 5/2, x3 = 0, x4 = 0, x5 = 3/2. La valeur de la fonction objectif est W = -6 (donc Z = 6).
Le coefficient de x3 dans la ligne W (-1/4) est négatif, la solution n'est toujours pas optimale.
Troisième Itération
- Variable entrante : x3.
- Détermination de la variable sortante : Les notes originales indiquent x5 comme variable sortante. Encore une fois, cela contredit la règle du ratio pour un pivot positif, car le coefficient de x3 dans la ligne de x5 est -1/4.
- Recherche du pivot : Les notes originales indiquent un pivot de 3/4, ce qui ne correspond pas aux valeurs du tableau précédent pour le choix de x5 comme variable sortante et x3 comme variable entrante.
Les notes originales concluent cet exercice en affirmant l'optimalité à l'étape suivante, bien que le tableau qui suit immédiatement le début de l'Exemple 2 présente encore des coefficients négatifs dans la ligne objectif pour x4 et x5, ce qui contredit l'optimalité selon les règles standard (si les coefficients devraient être tous positifs ou nuls pour une minimisation de W). Néanmoins, nous reproduisons la solution finale telle qu'elle est indiquée pour l'Exemple 1.
Solution Finale de l'Exemple 1 (selon le texte original)
La base finale mentionnée est B = (x1, x2, x3). La solution optimale indiquée est W = -8 (ce qui équivaut à Z = 8).
Le texte affirme que cette solution est optimale car "tous les Cj > 0" (les coefficients de la ligne objectif sont tous positifs ou nuls), une condition pour l'optimalité en minimisation.
Exemple 2
Forme standard :
Objectif : Minimiser Z = -x1 - x2
Sous contraintes :
- -x1 - x2 + x3 = 4
- 3x1 - x2 + x4 = 3
- -x1 + x2 + x5 = 1
- x1, x2, x3, x4, x5 ≥ 0
Les variables x3, x4, x5 sont des variables d'écart.
Premier Tableau du Simplexe
La base initiale B = (x3, x4, x5) est réalisable. La solution est : x1 = 0, x2 = 0, x3 = 4, x4 = 3, x5 = 1. La valeur de la fonction objectif Z est 0.
Puisque la ligne de la fonction objectif contient des coefficients négatifs (-1 pour x1 et -1 pour x2), la solution n'est pas optimale. Un changement de base est nécessaire.
Première Itération
- Variable entrante : x2 (identifiée comme ayant un coefficient négatif dans la ligne Z).
- Détermination de la variable sortante : Le calcul des ratios (en ne considérant que les coefficients positifs de x2 dans les lignes des variables de base) :
- Pour la ligne x3 : Le coefficient de x2 est -1 (négatif, non pris en compte).
- Pour la ligne x4 : Le coefficient de x2 est -1 (négatif, non pris en compte).
- Pour la ligne x5 : 1 / 1 = 1
- Recherche du pivot : L'intersection de la ligne de la variable sortante x5 et de la colonne de la variable entrante x2 est le pivot (valeur 1).
Deuxième Tableau du Simplexe
Après l'opération de pivot, la nouvelle base est B = (x3, x4, x2). La solution est : x1 = 0, x2 = 1, x3 = 5, x4 = 4, x5 = 0. La valeur de la fonction objectif Z est -1.
Le coefficient de x1 dans la ligne objectif (-2) est négatif. Par conséquent, la solution n'est pas optimale et d'autres itérations seraient nécessaires pour atteindre l'optimum. Les notes originales s'arrêtent à cette étape sans fournir la solution finale de cet exercice.
Foire Aux Questions (FAQ)
Qu'est-ce que l'optimisation linéaire ?
L'optimisation linéaire est une méthode mathématique utilisée pour maximiser ou minimiser une fonction objectif linéaire, sous réserve d'un ensemble de contraintes linéaires (égalités ou inégalités). C'est un outil puissant appliqué dans de nombreux domaines comme la logistique, la finance ou la production pour prendre des décisions optimales en allouant des ressources limitées.
Quelle est la différence entre les méthodes géométrique et du simplexe ?
La méthode géométrique est une technique graphique limitée aux problèmes d'optimisation linéaire avec deux variables de décision, offrant une visualisation intuitive de la région réalisable et de la solution. La méthode du simplexe, en revanche, est un algorithme algébrique capable de résoudre des problèmes avec un nombre quelconque de variables, y compris trois ou plus, où la visualisation graphique devient impossible.
Quel est le rôle d'une variable d'écart dans le simplexe ?
Une variable d'écart (ou slack variable) est une variable non négative ajoutée à une contrainte d'inégalité de type "inférieur ou égal" (≤) pour la transformer en une égalité. Elle représente la "capacité non utilisée" ou l'excédent de ressource. Ces variables sont cruciales pour convertir un problème d'optimisation linéaire en sa forme standard, condition préalable à l'application de l'algorithme du simplexe.