Make your own free website on Tripod.com

INDEX

III. Les problèmes de minimisation

Il y a deux manières de résoudre un problème de minimisation en utilisant la méthode de simplexe.

La première méthode nécessite le changement de la règle de choix de la variable entrante. Dans un problème de maximisation la règle est de choisir comme variable entrante celle qui a le plus grand effet net positif non nul. Ceci parce que notre objectif est de choisir la variable qui en entrant dans la base va engendrer un profit supplémentaire et ainsi accroître la valeur de la fonction objectif. Pour un problème de minimisation, on va utiliser la règle inverse. C’est-à-dire la variable entrante est celle à laquelle on associe la plus petite valeur négative non nulle de l’effet net cj - zj.

Ceci va nous amener aussi à changer notre règle d’arrêt de la procédure de simplexe et de définir le tableau optimal, comme celui où tous les effets nets
cj - zj sont positifs ou nuls.

Essayons d’appliquer la méthode de simplexe sur le problème de médecine :

Min x1 + x2

Sc 2x1 + x2 ³ 12

5x1 + 8x2 ³ 74

x1 + 6x2 ³ 24

x1 ³ 0 , x2 ³ 0

Pour permettre à la méthode de simplexe de démarrer de l’origine, il faut comme on l’a déjà vu dans le cas de problème de maximisation, introduire les variables artificielles.

Avec les problèmes de maximisation on attribue à ces variables un coefficient
-M dans la fonction objectif pour les contraindre à quitter la base rapidement. Dans le cas de problèmes de minimisation, on a intérêt à changer le coefficient de ces variables en M (M très grand) afin d’arriver au même résultat et de les faire sortir de la base.

Avant de construire le tableau de simplexe initial, on réécrit le programme linéaire relatif au problème de médecine avec les variables artificielles.

Min x1 + x2 + MA1 + MA2+ MA3

Sc 2x1 + x2 - S1 + A1 = 12

5x1 + 8x2 - S2 + A2 = 74

x1 + 6x2 - S3 + A3 = 24

x1 , x2 , S1 , S2 , S3 , A1 , A2 ³ 0

 Le tableau de simplexe initial est :

 

 

 

5

6

0

0

0

M

M

M

 

 

 

 

x1

x2

S1

S2

S3

A1

A2

A3

 

M

A1

12

2

1

-1

0

0

1

0

0

12

M

A2

74

5

8

0

-1

0

0

1

0

37/4


M

A3

24

1

6

0

0

-1

0

0

1

4

 

 

 

8M

15

-M

-M

-M

M

M

M

 

 

 

 

1-8M

1-15M

M

M

M

0

0

0

 

­

Après 4 itérations, on trouve le tableau de simplexe optimal suivant :

 

 

 

5

6

0

0

0

 

 

 

x1

x2

S1

S2

S3

1

x1

8

1

0

-8/11

1/11

0

0

S3

26

0

0

2

-1

1

1

x2

2

0

1

5/11

-2/11

0

 

 

 

1

1

-3/11

-1/11

0

 

 

 

0

0

3/11

1/11

0

On retrouve la même solution obtenue par la méthode graphique :

x1 = 8

x2 = 2

S1 = 0

S2 = 0

S3 = 26

Z = 10

Après avoir vérifier que le second membre des contraintes est positif, le tableau suivant résume les transformations à faire subir à notre programme linéaire avant de le résoudre par la méthode de simplexe :

Quand la contrainte est

Pour la fonction objectif d’un problème de

Maximisation

Minimisation

  1. de type " £ "

Ajouter une variable d’écart

Attribuer un coefficient nul pour la variable d’écart

II- de type " = " Ajouter une variable d’écart et une variable artificielle

Attribuer un coefficient -M pour variable artificielle

Attribuer un coefficient M pour la variable artificielle

III- de type " ³ "

Ajouter une variable artificielle et une variable d’écart avec un signe "-"

Attribuer un coefficient nul pour la variable d’écart et un coefficient - M pour variable

artificielle

Attribuer un coefficient nul pour la variable d’écart et un coefficient M pour variable artificielle

Le tableau suivant résume les étapes de la méthodes de simplexe relatif aux problèmes de maximisation et minimisation :

Etape

Maximisation

Minimisation

1

Formuler un programme linéaire pour le problème réel.

Formuler un programme linéaire pour le problème réel.

2

Vérifier que le second membre du programme linéaire est positif sinon modifier les contraintes

Vérifier que le second membre du programme linéaire est positif sinon modifier les contraintes

3

Ecrire le programme linéaire sous une forme standard

Ecrire le programme linéaire sous une forme standard

4

Construire le premier tableau de simplexe

Construire le premier tableau de simplexe

5

Choisir comme variable entrante dans la base celle qui admet le plus grand effet net positif cj-zj.

Choisir comme variable entrante dans la base celle qui admet le plus petit effet net négatif cj-zj.

6

Choisir la variable sortante de la base celle qui admet le plus petit ratio supérieur à zéro.

Choisir la variable sortante de la base celle qui admet le plus petit ratio supérieur à zéro.

7

Construire le nouveau tableau en utilisant la règle de pivot

Construire le nouveau tableau en utilisant la règle de pivot

8

Faire le test d’optimalité. Si
(cj-zj)
£ 0 pour toutes les variables (hors base) donc la solution obtenue est optimale. Sinon retourner à l’étape 5.

Faire le test d’optimalité. Si
(cj-zj)
³ 0 pour toutes les variables (hors base) donc la solution obtenue est optimale. Sinon retourner à l’étape 5.

La deuxième méthode pour résoudre un problème de se base sur le résultat suivant " Résoudre un problème min ctx sujet à un ensemble de contraintes est équivalent à résoudre un problème max -ctx sujet au même ensemble de contraintes ". Ces deux problèmes sont équivalents dans la mesure où ils donnent le même vecteur des solutions optimales. La seule différence est que la valeur de la solution max -ctx est l’opposé de la solution de min ctx; (i.e. min ctx = - max -ctx).

Donc pour résoudre le programme linéaire relatif au problème de médecine, on peut résoudre le problème de maximisation suivant:

Max - x1 - x2

S.c. 2x1 + x2 ³ 12

5x1 + 8x2 ³ 74

x1 + 6x2 ³ 24

x1 , x2 ³ 0

On peut vérifier facilement que la méthode de simplexe appliquée au programme ci-dessus, engendre le même vecteur de solutions optimales.

 

Cliquer ici pour enregistrer le chapitre 4 en format Word sur votre disque dur (125 Ko)


Pour tout commentaire envoyer un mail à hatem_masri@yahoo.com