The two phase simplex method -Programmation linaire - Recher
Télécharger PDFIntroduction à la méthode du Simplexe à deux phases
La méthode du Simplexe à deux phases est une technique d'optimisation mathématique utilisée pour résoudre des problèmes de programmation linéaire. Elle est particulièrement utile lorsqu'une solution de base réalisable (SBR) initiale n'est pas immédiatement évidente, notamment dans les cas où les contraintes ne permettent pas d'utiliser l'origine comme point de départ.
Pourquoi diviser la résolution en deux étapes ?
Dans de nombreux problèmes, les contraintes de type "supérieur ou égal" ou les égalités strictes empêchent de trouver facilement une solution de départ. La Phase I sert à construire artificiellement une solution réalisable, tandis que la Phase II utilise cette solution pour optimiser la fonction objectif réelle du problème.
Phase I : Recherche d'une solution de base réalisable
L'objectif principal de la Phase I est de déterminer s'il existe une solution satisfaisant toutes les contraintes du problème d'origine. Pour ce faire, nous introduisons des variables artificielles dans les contraintes appropriées.
Procédure de la Phase I
1. Mise sous forme d'égalité : Toutes les contraintes sont transformées en équations. Pour chaque contrainte où la variable d'écart et le membre de droite ont des signes opposés, ou lorsqu'il n'y a pas de variable d'écart, on ajoute une variable artificielle positive.
2. Minimisation des variables artificielles : On définit une nouvelle fonction objectif qui est la somme de toutes les variables artificielles. Le but est de minimiser cette somme pour qu'elle atteigne zéro.
3. Analyse des résultats : Si, à l'optimum de la Phase I, une variable artificielle conserve une valeur positive, cela prouve que le problème original est impossible (non réalisable). Si la somme est égale à zéro, nous avons trouvé une solution de base réalisable pour passer à l'étape suivante.
Phase II : Optimisation du problème réel
Une fois la Phase I terminée avec succès, les variables artificielles sont supprimées du tableau. Nous reprenons alors la fonction objectif initiale du problème.
Application du Simplexe
En partant de la solution de base trouvée à la fin de la Phase I, on applique l'algorithme du Simplexe standard. Par exemple, dans un problème de minimisation de la fonction 6x1 + 3x2, on effectue des opérations de pivotage sur les lignes et colonnes du tableau pour atteindre le point optimal. Dans l'exemple étudié, la solution optimale est atteinte avec x1 = 2/3 et x2 = 1/3, pour une valeur finale de -5.
Questions Fréquemment Posées (FAQ)
Quelle est la fonction d'une variable artificielle ?
Une variable artificielle est un outil mathématique temporaire. Elle permet de créer une base initiale pour démarrer l'algorithme du Simplexe lorsque l'origine n'est pas dans le domaine réalisable. Elle doit impérativement être réduite à zéro pour que la solution finale soit valide.
Comment savoir si un problème n'a pas de solution ?
Si, à la fin de la Phase I, la valeur minimale de la somme des variables artificielles est supérieure à zéro, cela signifie qu'aucune combinaison de variables ne peut satisfaire simultanément toutes les contraintes. Le problème est alors déclaré "irréalisable".
Peut-on supprimer la Phase I dans certains cas ?
Oui, la Phase I est inutile si le problème est déjà sous forme standard avec des contraintes de type "inférieur ou égal" (≤) et des membres de droite positifs. Dans ce cas, les variables d'écart fournissent immédiatement la solution de base réalisable nécessaire pour commencer directement l'optimisation.