Exemple resolution d'un pl avec la methode des 2 phases -Pro
Télécharger PDFLa Méthode du Simplexe en Deux Phases : Un Exemple Détaillé
Ce document présente un exemple d'application de la méthode du simplexe en deux phases pour résoudre un problème de programmation linéaire.
Présentation du Problème Original
Considérons le problème de programmation linéaire (PL) suivant :
maximiser z = 2x1 + 3x2 + x3
sous réserve de :
x1 + x2 + x3 ≤ 40
2x1 + x2 − x3 ≥ 10
−x2 + x3 ≥ 10
x1, x2, x3 ≥ 0
Transformation en Forme Standard
Le problème peut être transformé en forme standard en introduisant 3 variables d'écart x4, x5 et x6 :
maximiser z = 2x1 + 3x2 + x3
sous réserve de :
x1 + x2 + x3 + x4 = 40
2x1 + x2 − x3 − x5 = 10
−x2 + x3 − x6 = 10
x1, x2, x3, x4, x5, x6 ≥ 0
Ici, x4 est une variable d'écart pour la première contrainte (de type ≤), tandis que x5 et x6 sont des variables d'excédent pour les contraintes de type ≥.
Phase I : Recherche d'une Solution de Base Réalisable
Il n'y a pas de solution de base réalisable initiale évidente, et on ne sait même pas s'il en existe une. Nous pouvons utiliser la méthode de la Phase I pour le déterminer. Cette phase cherche à trouver une solution de base réalisable pour le problème original, si elle existe.
Problème Auxiliaire de la Phase I
Considérons le problème de PL suivant, dérivé du problème original en relâchant les deuxième et troisième contraintes et en introduisant une nouvelle fonction objectif, ainsi que des variables artificielles x7 et x8 :
minimiser x7 + x8 (ou maximiser w = −x7 − x8)
sous réserve de :
x1 + x2 + x3 + x4 = 40
2x1 + x2 − x3 − x5 + x7 = 10
−x2 + x3 − x6 + x8 = 10
x1, x2, x3, x4, x5, x6, x7, x8 ≥ 0
Ce problème (Phase I) a une solution de base réalisable initiale avec les variables de base x4, x7 et x8. Si la valeur minimale de x7 + x8 est 0, alors x7 et x8 sont tous deux égaux à 0. Par conséquent, la solution optimale du problème de la Phase I est une solution de base réalisable du problème original. Si la valeur minimale de x7 + x8 est supérieure à 0, alors le problème original n'est pas réalisable. Nous construisons des tableaux pour résoudre le problème de la Phase I. La valeur de la fonction objectif w doit être exprimée en termes de variables hors base : w = −x7 − x8 = −20 + 2x1 − x5 − x6. Le tableau initial est présenté ci-dessous (les variables de base sont indiquées en gras).
Tableaux du Simplexe pour la Phase I
Tableau Initial de la Phase I
| w | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | RHS | |
|---|---|---|---|---|---|---|---|---|---|---|
| w | 1 | -2 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | -20 |
| x4 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 40 |
| x7 | 0 | 2 | 1 | -1 | 0 | -1 | 0 | 1 | 0 | 10 |
| x8 | 0 | 0 | -1 | 1 | 0 | 0 | -1 | 0 | 1 | 10 |
Première Itération de la Phase I
Les variables entrante et sortante seraient respectivement x1 et x7 :
| w | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | RHS | |
|---|---|---|---|---|---|---|---|---|---|---|
| w | 1 | 0 | 1 | -1 | 0 | 0 | 1 | 1 | 0 | -10 |
| x4 | 0 | 0 | 0.5 | 1.5 | 1 | 0.5 | 0 | -0.5 | 0 | 35 |
| x1 | 0 | 1 | 0.5 | -0.5 | 0 | -0.5 | 0 | 0.5 | 0 | 5 |
| x8 | 0 | 0 | -1 | 1 | 0 | 0 | -1 | 0 | 1 | 10 |
Deuxième Itération de la Phase I (Tableau Optimal de la Phase I)
Les variables entrante et sortante seraient respectivement x3 et x8 :
| w | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | RHS | |
|---|---|---|---|---|---|---|---|---|---|---|
| w | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| x4 | 0 | 0 | 2 | 0 | 1 | 0.5 | 1.5 | -0.5 | -1.5 | 20 |
| x1 | 0 | 1 | 0 | 0 | 0 | -0.5 | -0.5 | 0.5 | 0.5 | 10 |
| x3 | 0 | 0 | -1 | 1 | 0 | 0 | -1 | 0 | 1 | 10 |
La valeur optimale du problème de la Phase I est w = 0. Le problème original est donc réalisable, et une solution de base réalisable est x1 = 10, x3 = 10, x4 = 20, avec x2 = x5 = x6 = 0.
Phase II : Optimisation du Problème Original
Nous pouvons maintenant commencer la Phase II. Encore une fois, la valeur de la fonction objectif z doit être représentée par les variables hors base : z = 2x1 + 3x2 + x3 = 30 + 4x2 + x5 + 2x6.
Tableaux du Simplexe pour la Phase II
Tableau Initial de la Phase II
Le tableau initial de la Phase II est le dernier tableau de la Phase I, sans les variables artificielles x7 et x8, et avec la ligne de la fonction objectif originale mise à jour :
| z | x1 | x2 | x3 | x4 | x5 | x6 | RHS | |
|---|---|---|---|---|---|---|---|---|
| z | 1 | 0 | -4 | 0 | 0 | -1 | -2 | 30 |
| x4 | 0 | 0 | 2 | 0 | 1 | 0.5 | 1.5 | 20 |
| x1 | 0 | 1 | 0 | 0 | 0 | -0.5 | -0.5 | 10 |
| x3 | 0 | 0 | -1 | 1 | 0 | 0 | -1 | 10 |
Première Itération de la Phase II (Tableau Optimal)
Les variables entrante et sortante seraient respectivement x2 et x4 :
| z | x1 | x2 | x3 | x4 | x5 | x6 | RHS | |
|---|---|---|---|---|---|---|---|---|
| z | 1 | 0 | 0 | 0 | 2 | 0 | 1 | 70 |
| x2 | 0 | 0 | 1 | 0 | 0.5 | 0.25 | 0.75 | 10 |
| x1 | 0 | 1 | 0 | 0 | 0 | -0.5 | -0.5 | 10 |
| x3 | 0 | 0 | 0 | 1 | 0.5 | 0.25 | -0.25 | 20 |
Conclusion et Solution Optimale
Ainsi, la valeur optimale de la fonction objectif est z = 70, et la solution optimale pour le problème original est :
- x1 = 10
- x2 = 10
- x3 = 20
- x4 = 0
- x5 = 0
- x6 = 0
Foire Aux Questions (FAQ)
Qu'est-ce que la méthode du simplexe en deux phases ?
La méthode du simplexe en deux phases est une technique utilisée en programmation linéaire pour résoudre des problèmes où il n'est pas possible de trouver une solution de base réalisable initiale évidente. Elle se déroule en deux étapes : la Phase I cherche une solution de base réalisable, et la Phase II optimise la fonction objectif principale à partir de cette solution.
Pourquoi utilise-t-on des variables artificielles dans la Phase I ?
Les variables artificielles (comme x7 et x8 dans cet exemple) sont introduites dans la Phase I pour créer une solution de base réalisable initiale pour le problème auxiliaire, même lorsque les contraintes originales (notamment celles de type ≥ ou d'égalité) ne permettent pas de former une base simple avec des variables d'écart ou d'excédent. Ces variables n'ont pas de signification physique et doivent être éliminées (devenir nulles) à la fin de la Phase I pour que la solution soit valide pour le problème original.
Que se passe-t-il si la valeur optimale de la Phase I est supérieure à zéro ?
Si la valeur optimale de la fonction objectif de la Phase I (la somme des variables artificielles) est strictement supérieure à zéro, cela signifie qu'il n'est pas possible d'éliminer toutes les variables artificielles de la base tout en respectant les contraintes. Dans ce cas, le problème de programmation linéaire original n'admet pas de solution réalisable.