Make your own free website on Tripod.com

INDEX

IV. Les problèmes irréguliers

Après avoir examiner comment on peut résoudre un programme linéaire par la méthode de simplexe, on s’intéresse dans cette section aux problèmes irréguliers, qu'on peut rencontrer lors de la résolution d’un programme linéaire par la méthode de simplexe. Donc, l’objet de cette section est de reconnaître ces problèmes et de les résoudre par la méthode de simplexe.

a. Les problèmes impossibles

Graphiquement, on a caractérisé ces problèmes par un ensemble de solutions réalisables vide. Avec la méthode de simplexe, on reconnaît que le problème est impossible si une ou plusieurs variables artificielles sont présentes dans la base dans le tableau de simplexe optimal, ce qui signifie que la solution donnée par ce tableau n’est pas réellement réalisable.

Exemple:

Vérifions à l’aide de la méthode de simplexe, que le problème suivant est réellement impossible :

Max 4 x1 + 3x2

Sc x1 + x2 £ 2

3x1 + x2 ³ 10

x1 , x2 ³ 0

En introduisant les variables d’écarts et les variables artificielles le programme s’écrit:

Max 4x1 + 3x2 - MA1

Sc x1 + x2 - S1 = 2

3x1 + x2 - S2 + a1 = 10

x1 , x2 , S1 , S2 , A1 ³ 0

 

 

 

4

3

0

0

-M

 

 

 

 

x1

x2

S1

S2

a1

 


0

S1

2

(1)

1

1

0

0

2

-M

a1

10

3

1

0

-1

1

10/3

 

 

 

-3M

-M

0

M

1

 

 

 

 

3M+4

M+3

0

-M

-M-1

 

­

 

 

 

4

3

0

0

-M

 

 

 

x1

x2

S1

S2

a1

4

x1

2

1

1

1

0

0

-M

a1

5

0

-2

-3

-1

1

 

 

 

4

4+2M

1+3M

M

-M

 

 

 

0

-1-2M

-1-3M

-M

0

Le tableau de simplexe ci-dessus est optimal avec une variable artificielle dans la base.

Remarque : Un programme de maximisation ou de minimisation avec seulement des contraintes de type " £  " ne peut pas être impossible (sous l’hypothèse que le second membre b est positif). Ceci est dû au fait que lors de la résolution de ce genre de programme par la méthode de simplexe on n'utilise pas des variables artificielles. Donc il est impossible de les retrouver dans la solution optimale.

b. Les problèmes à solutions multiples

Graphiquement, ce problème est caractérisé par le fait que la pente de la droite représentant la fonction objectif (z = 0) est égale à la pente de l’une des contraintes restrictives. Lorsqu’on utilise la méthode de simplexe, on identifie ce problème lorsqu’un des effets nets (relatif à une variable hors base) est nul. L’exemple de la section 3 du précédent chapitre représente un problème avec solutions multiples.

c. Les problèmes à solution infinie

Graphiquement, ce problème est caractérisé par le fait qu’on peut déplacer la droite de la fonction objectif indéfiniment de manière à accroître la valeur, en gardant toujours une intersection non vide avec l’ensemble des solutions réalisables.

Avec la méthode de simplexe, on reconnaît ce problème lorsque la variable entrante n’admet aucune limite sur sa valeur d’entrée, c’est à dire que tous les ratios Qi/aijo sont négatifs ou nuls.

Exemple

Max x1 + 2x2

Sc x1 + x2 ³ 2

x2 £ 3

x1 , x2 ³ 0

On introduit les variables d’écart et les variables artificielles, le programme linéaire devient :

Max x1 + 2x2 + 0S1 + 0S2 - Ma1

Sc x1 + x2 - S1 + a1 = 2

x2 + S2 = 3

x1 , x2 , S1 , S2 , a1 ³ 0

Les tableaux de simplexe sont :

 

 

 

1

2

0

0

-M

 

 

 

 

x1

x2

S1

S2

a1

 


-M

a1

2

1

(1)

-1

0

1

2

0

S2

3

0

1

0

1

0

3

 

 

 

-M

-M

M

0

-M

 

 

 

 

1+M

2+M

-M

0

0

 

­

 

 

 

1

2

0

0

 

 

 

 

x1

x2

S1

S2

 

2

x2

2

1

(1)

-1

0

-2


0

S2

1

-1

0

(1)

1

1

 

 

 

2

2

-2

0

 

 

 

 

-1

0

2

0

 

­

 

 

 

1

2

0

0

 

 

 

 

x1

x2

S1

S2

 

2

x2

3

0

1

0

1

¥

0

S1

1

-1

0

1

1

-1

 

 

 

0

2

0

2

 

 

 

 

1

0

0

-2

 

­

Le dernier tableau montre que la variable x1 n’admet aucune limite sur sa valeur de sortie.

 d. Les problèmes à solution dégénérée

Graphiquement, on appelle solution dégénérée le point où plusieurs contraintes concourent (un nombre supérieur ou égale à trois contraintes). Un programme linéaire est dit dégénérée si une ou plusieurs variables dans la base optimale sont nulles. Dans la résolution graphique ce problème n’est pas difficile à résoudre, mais avec la méthode de simplexe il peut causer des difficultés.

Exemple

Max z = 2x1 + 0 x2 + 3/2 x3

s.c. x1 - x2 £ 2

2x1 + x3 £ 4

x1 + x2 + x3 £ 3

x1, x2, x3 ³ 0

La solution optimale de ce problème est :

x1 = 1

x2 = 0

x3 = 2

z = 5

La forme standard du programme linéaire est

Max 2x1 + 0 x2 + 3/2x3 + 0 S1 + 0 S2 + 0 S3

Sc x1 - x2 + S1 = 2

2x1 + x3 + S2 = 4

x1 + x2 + x3 + S3 = 3

x1, x2, x3, S1, S2, S3 ³ 0

Le tableau de simplexe initial est :

 

 

 

2

0

3/2

0

0

0

 

 

 

 

x1

x2

x3

S1

S2

S3

 


0

S1

2

1

-1

0

1

0

0

2


0

S2

4

2

8

0

-1

0

0

2

0

S3

3

1

6

0

0

-1

0

3

 

 

 

0

15

-M

-M

-M

M

 

 

 

 

2

0

3/2

0

0

0

 

­

La variable entrante est x1, mais les deux premières contraintes donnent la même valeur minimale du ratio. Ceci indique que lorsque x1 passe à 2, les variables d’écart S1 et S2 vont s’annuler malgré que l’un des deux demeure encore dans la base.

Choisissons arbitrairement de faire sortir de la base la variable d’écart S1.

 

 

 

2

0

3/2

0

0

0

 

 

 

 

x1

x2

x3

S1

S2

S3

 

2

x1

2

1

-1

0

1

0

0

-2

0

S2

0

0

2

1

-2

1

0

0

0

S3

1

0

2

1

-1

0

1

1/2

 

 

 

2

-2

0

2

0

0

 

 

 

 

0

2

3/2

-2

0

0

 

­

La nouvelle solution réalisable de base est :

x1 = 0

x2 = 0

x3= 1

S1 = 2

S2 = 0

S3 = 0

et la valeur de la fonction objectif z = 4. Cette solution de base est dite dégénérée. Continuons les itérations relatives à la méthode de simplexe. La variable entrante est x2.

Le problème est qu’un des ratios est nul ce qui indique qu’on ne peut pas augmenter la valeur de x2 puisque la valeur de la fonction objectif ne va pas augmenter et reste égale à 4.

Si on réitère une autre fois, en remplaçant S2 par x2 dans la base on obtient :

 

 

 

2

0

3/2

0

0

0

 

 

 

 

x1

x2

x3

S1

S2

S3

 

2

x1

2

1

0

1/2

0

1/2

0

4


0

x2

0

0

1

1/2

-1

1/2

0

0

0

S3

1

0

0

0

1

-1

1

¥

 

 

 

2

0

0

0

1

0

 

 

 

 

0

0

1/2

0

-1

0

 

­

Ce tableau n’est pas optimal, la variable entrante est x3 et la variable sortante est x2. On remarque aussi que ce passage d’une solution à une autre ne s’accompagne pas d’une augmentation de la valeur de la fonction objectif.

On peut facilement vérifier que nous somme en train de cycler sans atteindre la solution optimale. Ce genre de cyclage dans la méthode de simplexe est dangereux et on doit l’identifier avant de commencer à résoudre le problème, sinon on passera un temps énorme sans atteindre la solution optimale.

Pour terminer cette section, il faut noter que ce n'est pas tout problème de dégénérescence qui peut conduire à un cyclage.

Exemple

Max 10 x1 + 9x2

Sc 7/10x1 + x2 £ 630

1/2 x1 +5/6x2 £ 480

x1 + 2/3x2 £ 708

1/10 x1 +1/4x2 £ 135

x1 ,, x2 ³ 0

Essayer de résoudre ce programme par la méthode de simplexe (choisir en cas de deux quotients égaux, celui qui se trouve dans la ligne supérieure).

 

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