3.4.3 methode des deux phases -Programmation linaire - Reche
Télécharger PDFLa méthode des deux phases
La méthode des deux phases est un algorithme utilisé en programmation linéaire pour trouver une solution de base admissible lorsque celle-ci n'est pas évidente, ou pour prouver que le problème n'admet aucune solution réalisable. Elle est particulièrement utile quand les contraintes comprennent des égalités ou des inégalités de type "supérieur ou égal à".
Solution initiale artificielle
- Une solution de base admissible n’est pas toujours connue a priori, surtout quand il n'y a pas de variables d'écart disponibles pour former une base identité.
- Certains problèmes peuvent ne pas admettre de solution admissible du tout, ce qui rend impossible de trouver une base de départ.
- La méthode des deux phases permet de déterminer une base admissible si elle existe, ou de prouver que le problème est irréalisable.
Exemple 7 : Application de la méthode des deux phases
Considérons le problème de minimisation suivant :
Minimiser z = 4x1 + x2
Sous contraintes :
- 3x1 + x2 = 3
- 4x1 + 3x2 ≥ 6
- x1 + 2x2 ≤ 4
- x1, x2 ≥ 0
Introduction des variables d'écart
Pour transformer les inégalités en égalités et préparer le problème pour l'algorithme du simplexe, nous introduisons des variables d'écart (slack) et d'excédent (surplus) :
Minimiser z = 4x1 + x2
Sous contraintes :
- 3x1 + x2 = 3
- 4x1 + 3x2 - x3 = 6 (où x3 est une variable d'excédent)
- x1 + 2x2 + x4 = 4 (où x4 est une variable d'écart)
- x1, x2, x3, x4 ≥ 0
À ce stade, il n'y a pas de base admissible "triviale" (par exemple, une matrice identité). Les variables x3 et x4 ne forment pas une base complète. Pour résoudre ce problème, nous introduisons des variables artificielles.
Introduction des variables artificielles
Nous ajoutons des variables artificielles (R1, R2) aux contraintes qui n'ont pas de variable de base évidente. Ces variables sont temporaires et sont éliminées dans la Phase 1.
Minimiser z = 4x1 + x2
Sous contraintes :
- 3x1 + x2 + R1 = 3
- 4x1 + 3x2 - x3 + R2 = 6
- x1 + 2x2 + x4 = 4
- x1, x2, x3, R1, R2, x4 ≥ 0
Dans la Phase 1, un nouvel objectif auxiliaire est créé, r = R1 + R2, que l'on cherche à minimiser. Si la valeur minimale de r est 0, une solution de base admissible pour le problème original est trouvée.
Minimiser r = R1 + R2
En substituant R1 et R2 à partir des contraintes, la fonction objectif auxiliaire devient :
Minimiser r = (3 - 3x1 - x2) + (6 - 4x1 - 3x2 + x3)
Minimiser r = -7x1 - 4x2 + x3 + 9
- Les variables R1, R2 et x4 peuvent servir de base de départ admissible pour la Phase 1 du simplexe.
- L'objectif de cette phase est de forcer R1 et R2 à devenir nulles, les rendant ainsi des variables hors base.
- Si r = 0 à la fin de la Phase 1, on a trouvé une base admissible. On retire ensuite les variables artificielles et on passe à la Phase 2, en utilisant l'objectif original et la base trouvée.
Cas particuliers en programmation linéaire
La résolution de problèmes de programmation linéaire peut révéler des situations spécifiques qui nécessitent une interprétation particulière des résultats de l'algorithme du simplexe.
Solutions optimales multiples
Un problème de programmation linéaire peut admettre plusieurs solutions optimales lorsque la fonction objectif est parallèle à une contrainte active qui délimite la région admissible.
- Si la fonction objectif est parallèle à une contrainte active à la solution optimale, plusieurs solutions admissibles peuvent atteindre la même valeur optimale de l'objectif.
- Dans ce cas, il existe une infinité de solutions optimales. Celles-ci sont représentées par toutes les combinaisons convexes des sommets optimaux.
- Ceci se manifeste dans le tableau du simplexe par un "profit marginal" (coefficient réduit dans la ligne de la fonction objectif) nul pour une ou plusieurs variables hors base. Cela signifie que ces variables peuvent entrer en base sans modifier la valeur optimale de la fonction objectif.
Exemple 8 : Solutions optimales multiples
Maximiser z = 2x1 + 4x2
Sous contraintes :
- x1 + 2x2 ≤ 5
- x1 + x2 ≤ 4
- x1, x2 ≥ 0
Après l'application de l'algorithme du simplexe, un tableau final pourrait indiquer une variable hors base avec un coût réduit de 0, signalant des solutions optimales multiples. La solution optimale peut être exprimée sous forme paramétrique :
x1 = 3 - 3α
x2 = 1 + (3/2)α
(où 0 ≤ α ≤ 1)
Cette paramétrisation représente tous les points sur le segment de droite connectant les deux sommets optimaux : (3, 1) et (0, 5/2). Pour α=0, (x1, x2) = (3, 1) et pour α=1, (x1, x2) = (0, 5/2). Dans les deux cas, la valeur de z est 10.
Problèmes non bornés
Un problème est dit non borné si la fonction objectif peut croître indéfiniment (pour une maximisation) ou décroître indéfiniment (pour une minimisation) sans jamais violer les contraintes.
- Certains problèmes sont non bornés dans une direction donnée.
- Si cette direction permet d'améliorer la fonction objectif, celle-ci peut prendre une valeur arbitrairement grande (ou petite).
Exemple 9 : Problème non borné
Maximiser z = 2x1 + x2
Sous contraintes :
- x1 - x2 ≤ 1
- 2x1 ≤ 4
- x1, x2 ≥ 0
Tableau du simplexe initial (après introduction des variables d'écart s1 et s2) :
| Var. en base | z | x1 | x2 | s1 | s2 | Solution |
|---|---|---|---|---|---|---|
| z | -1 | 2 | 1 | 0 | 0 | 0 |
| s1 | 0 | 1 | -1 | 1 | 0 | 1 |
| s2 | 0 | 2 | 0 | 0 | 1 | 4 |
Dans ce tableau, si l'on tente de faire entrer la variable x2 dans la base (car son coefficient dans la ligne z est positif pour une maximisation), on observe ses coefficients dans les lignes de contraintes :
- Le coefficient de x2 dans la contrainte de s1 est -1 (négatif).
- Le coefficient de x2 dans la contrainte de s2 est 0 (nul).
Puisque tous les coefficients dans la colonne de x2 (sauf celui de la ligne z) sont négatifs ou nuls, cela signifie qu'il n'y a pas de variable de base qui serait forcée de devenir négative si x2 augmentait. En d'autres termes, x2 peut augmenter indéfiniment sans violer les contraintes de non-négativité, ce qui permet à la fonction objectif d'augmenter sans limite. Le problème est donc non borné.
Problèmes impossibles
Un problème de programmation linéaire est impossible s'il n'existe aucune solution qui satisfasse toutes les contraintes simultanément. La région admissible est vide.
- Le système de contraintes peut n’avoir aucune solution réalisable.
- Généralement, cela provient d’une mauvaise formulation du problème, où les contraintes sont mutuellement contradictoires.
- Dans la méthode des deux phases, un problème est impossible si la Phase 1 se termine avec une valeur minimale de l'objectif auxiliaire (somme des variables artificielles) strictement supérieure à zéro.
Exemple 10 : Problème impossible
Maximiser z = 3x1 + 2x2
Sous contraintes :
- 2x1 + x2 ≤ 2
- 3x1 + 4x2 ≥ 12
- x1, x2 ≥ 0
Graphiquement, la première contrainte (2x1 + x2 ≤ 2) définit une région en dessous d'une ligne, tandis que la seconde contrainte (3x1 + 4x2 ≥ 12) définit une région au-dessus d'une autre ligne. Ces deux régions ne se chevauchent pas, ce qui signifie qu'il n'y a pas de point (x1, x2) qui satisfasse les deux contraintes simultanément. La région admissible est vide.
Foire aux questions (FAQ)
Qu'est-ce que la méthode des deux phases et quand est-elle utilisée ?
La méthode des deux phases est un algorithme utilisé en programmation linéaire pour trouver une solution de base admissible lorsque l'approche simplexe standard ne peut pas être appliquée directement (absence d'une matrice identité). Elle est employée lorsque le problème inclut des contraintes d'égalité ou des contraintes de type "supérieur ou égal à".
Comment identifier un problème de solutions optimales multiples ?
Un problème de programmation linéaire présente des solutions optimales multiples si, dans le tableau final du simplexe, une ou plusieurs variables hors base ont un "profit marginal" (coefficient réduit dans la ligne de la fonction objectif) égal à zéro. Cela indique que ces variables peuvent entrer dans la base sans modifier la valeur optimale de la fonction objectif, générant ainsi d'autres solutions optimales le long d'un segment ou d'une face de la région admissible.
Comment reconnaître un problème non borné dans l'algorithme du simplexe ?
Un problème de maximisation est non borné si, lors du choix d'une variable pour entrer en base (avec un coefficient positif dans la ligne de la fonction objectif), tous les coefficients correspondants dans sa colonne (pour les lignes de contraintes) sont négatifs ou nuls. Cela signifie qu'aucune variable de base ne sera limitée, permettant à la variable entrante d'augmenter indéfiniment, et par conséquent à la fonction objectif d'atteindre une valeur infinie.