Scribd
Importer
88 vues2 pages

Exercice méthode à grand M en LP

Le document présente un problème de programmation linéaire (LP) à résoudre en utilisant la méthode de grand M. Il décrit la transformation du problème en forme standard, l'introduction de variables artificielles, et la construction de tableaux pour appliquer l'algorithme Simplex. La solution optimale est trouvée avec une valeur de z = 70 et des valeurs spécifiques pour les variables x1, x2 et x3.

Transféré par

samadani
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
88 vues2 pages

Exercice méthode à grand M en LP

Le document présente un problème de programmation linéaire (LP) à résoudre en utilisant la méthode de grand M. Il décrit la transformation du problème en forme standard, l'introduction de variables artificielles, et la construction de tableaux pour appliquer l'algorithme Simplex. La solution optimale est trouvée avec une valeur de z = 70 et des valeurs spécifiques pour les variables x1, x2 et x3.

Transféré par

samadani
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

MATH 60606 : exercice sur la méthode à

grand-M.

On considère le problème LP suivant.

max z = 2x1 + 3x2 + x3


s.l.c. x1 + x2 + x3 ≤ 40
2x1 + x2 − x3 ≥ 10
− x2 + x3 ≥ 10
x1 , x2 , x3 ≥ 0
Elle peut être transformée en forme standard en introduisant 3 variables
x4 , x5 and x6 .

max z = 2x1 + 3x2 + x3


s.l.c. x1 + x2 + x3 + x4 = 40
2x1 + x2 − x3 − x5 = 10
−x2 + x3 − x6 = 10
x1 , x2 , x3 , x4 , x5 , x6 ≥0
Il n’y a pas de solution initiale réalisable évidente, et on ne sait même pas
s’il en existe une. Nous pouvons utiliser la méthode de grand M. Considérons le
problème LP suivant, dérivé du problème original en introduisant deux nouvelles
variables et une nouvelle fonction objectif.

max w = 2x1 + 3x2 + x3 − M x7 − M x8


s.t. 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
Si la valeur optimal 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.
La valeur objective w doit être écrite en termes de variables hors-base (à partir
des deuxième et troisième contraintes ci-dessus):

w = 2x1 + 3x2 + x3 − M x7 − M x8
= 2x1 + 3x2 + x3 − M (10 − 2x1 − x2 + x3 + x5 ) − M (10 + x2 − x3 + x6 )
= −20M + (2 + 2M )x1 + 3x2 + x3 − M x5 − M x6 .

1
En d’autres termes, w − (2 + 2M )x1 − 3x2 − x3 + M x5 + M x6 = −20M .
Le tableau initial est présenté ci-dessous (les variables de base sont indiquées
en caractères gras).

w x1 x2 x3 x4 x5 x6 x7 x8
0 1 1 1 1 0 0 0 0 = 40
0 2 1 −1 0 −1 0 1 0 = 10
0 0 −1 1 0 0 −1 0 1 = 10
1 −(2 + 2M ) −3 −1 0 M M 0 0 = −20M

Les variables entrante et sortante seraient respectivement x1 et x7 (Notez


que x7 a sorti de la base et nous pouvons supprimer la colonne correspondante,
car il ne reviendra jamais dans la base) :

w x1 x2 x3 x4 x5 x6 x8
0 0 0.5 1.5 1 0.5 0 0 = 35
0 1 0.5 −0.5 0 −0.5 0 0 = 5
0 0 −1 1 0 0 −1 1 = 10
1 0 (M − 2) −(M + 2) 0 −1 −M 0 = (10 − 10M )

Les variables entrante et sortante seraient respectivement x3 et x8 (Notez


que x8 a sorti de la base et nous pouvons supprimer la colonne correspondante,
car il ne reviendra jamais dans la base) :

z x1 x2 x3 x4 x5 x6
0 0 2 0 1 0.5 1.5 = 20
0 1 0 0 0 −0.5 −0.5 = 10
0 0 −1 1 0 0 −1 = 10
1 0 −4 0 0 −1 −2 = 30

Notez que les variables artificielles ont sorti de la base et que la solution que
nous avons sous la main est réalisable pour le problème original. Maintenant,
nous continuons avec la solution de l’algorithme Simplex pour trouver la solution
optimale du modèle original.
Les variables entrante et sortante seraient respectivement x2 et x4 :

z x1 x2 x3 x4 x5 x6
0 0 1 0 0.5 0.25 0.75 = 10
0 1 0 0 0 −0.5 −0.5 = 10
0 0 0 1 0.5 0.25 −0.25 = 20
1 0 0 0 2 0 1 = 70

Ainsi, la valeur optimale z = 70, et la solution optimale est x1 = x2 =


10, x3 = 20, x4 = x5 = x6 = 0.

Vous aimerez peut-être aussi