Methode des 2 phases programmation lineaire et optimisation
Télécharger PDFTD 4 : Programmation linéaire et optimisation
Ce document traite de la résolution de problèmes de programmation linéaire en utilisant la méthode des deux phases de Dantzig et la méthode de pénalités, également connue sous le nom de méthode du Grand M.
Exercice 1 : Méthode des pénalités et méthode des deux phases
L'objectif est de trouver le maximum de la fonction objective suivante :
z = 3x1 + 4x2 + x3
Sous les contraintes :
x1 + 2x2 + 2x3 ≤ 8/3
x1 + 2x2 + 3x3 ≥ 7/3
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
1. Résolution par la méthode de pénalités (Grand M)
On introduit d'abord les variables d'écart pour transformer les inégalités en égalités :
x1 + 2x2 + 2x3 + t1 = 8/3
x1 + 2x2 + 3x3 – t2 = 7/3
Comme nous ne disposons pas d'une solution réalisable de départ évidente (car x1 = x2 = x3 = 0 donne t2 = -7/3), on ajoute une variable artificielle a2. Le programme linéaire devient :
Maximiser z' = 3x1 + 4x2 + x3 + 0t1 + 0t2 – Ma2
| HB | B | x1 | x2 | x3 | t1 | t2 | a2 | bi | ratio |
|---|---|---|---|---|---|---|---|---|---|
| t1 | 1 | 2 | 2 | 1 | 0 | 0 | 8/3 | 8/3 | |
| a2 | 1 | 2 | 3 | 0 | -1 | 1 | 7/3 | 7/3 | |
| cj | -3-M | -4-2M | -1-3M | 0 | M | 0 | -7/3*M |
La variable x3 entre dans la base et la variable a2 en sort.
| HB | B | x1 | x2 | x3 | t1 | t2 | bi | ratio |
|---|---|---|---|---|---|---|---|---|
| t1 | 1/3 | 2/3 | 0 | 1 | 2/3 | 10/9 | 10/9 * 3/2 | |
| x3 | 1/3 | 2/3 | 1 | 0 | -1/3 | 7/9 | 7/9 * 3/2 | |
| ∆j | -8/3 | -10/3 | 0 | 0 | -1/3 | +7/9 |
Après plusieurs itérations, la solution optimale obtenue est :
x1 = 8/3, t2 = 1/3, x2 = 0, x3 = 0, t1 = 0. Le maximum est z = 24/3 = 8.
2. Résolution par la méthode en deux phases de Dantzig
Phase 1 : On minimise la somme des variables artificielles. Min z' = a2.
Si à l'optimum la somme des variables artificielles est nulle, nous disposons d'une solution de base réalisable pour la phase 2.
Phase 2 : On reprend la fonction objectif initiale en utilisant la solution de base trouvée à la fin de la phase 1.
Exercice 2 : Résolution d'un programme linéaire spécifique
Soit le programme linéaire suivant :
Max z = x1 + 7x2
Sous les contraintes :
x1 + x2 ≥ 6
x1 ≥ 4
x2 ≤ 3
x1 ≥ 0, x2 ≥ 0
Phase I : Forme standard
On cherche à minimiser z' = e1 + e2 (variables artificielles) :
x1 + x2 - t1 + e1 = 6
x1 - t2 + e2 = 4
x2 + t3 = 3
Après résolution de la Phase I, nous obtenons une solution de base admissible : x1 = 4, x2 = 2, t1 = 0, t2 = 0, t3 = 1.
Phase II : Optimisation de la fonction initiale
On reprend la fonction Max z = 5x1 + 7x2 (selon les données du tableau de correction). La solution finale montre une tendance vers l'infini pour x1, car une variable hors base a une valeur marginale négative avec des coefficients techniques tous positifs ou nuls.
FAQ sur la programmation linéaire
Qu'est-ce que la méthode du Grand M ?
La méthode du Grand M est une technique utilisée dans l'algorithme du simplexe pour gérer les contraintes de type "supérieur ou égal" (≥) ou "égal" (=). Elle consiste à ajouter des variables artificielles avec un coefficient de pénalité très élevé (M) dans la fonction objectif pour forcer ces variables à devenir nulles à l'optimum.
Pourquoi utiliser la méthode des deux phases ?
La méthode des deux phases est une alternative à la méthode du Grand M. La première phase consiste à trouver une solution de base réalisable en éliminant les variables artificielles. Si une telle solution existe, la seconde phase procède à l'optimisation de la fonction objectif réelle.
Quelle est la différence entre une variable d'écart et une variable artificielle ?
Une variable d'écart est ajoutée pour transformer une inégalité en équation et représente la différence entre les deux membres de la contrainte. Une variable artificielle est ajoutée temporairement pour obtenir une solution de base de départ immédiate lorsque l'origine n'est pas réalisable.