INDEX

CHAPITRE 4

Problèmes de Minimisation et Problèmes Irréguliers


I. Introduction

Dans le chapitre précédent tous les programmes linéaires qu’on a traité sont du type : Maximiser une fonction linéaire sous contraintes de type inférieur ou égale (et avec un second membre positif).

Or dans beaucoup de problèmes réels, on peut retrouver des contraintes de type supérieur ou égale et/ou de type égale, ainsi que des problèmes où on a à minimiser au lieu de maximiser.

Dans ce chapitre, on étudiera les modifications à apporter à la méthode du simplexe pour qu’elle puisse résoudre tous ces types de programmes.

II. Les variables artificielles

Considérons le programme linéaire suivant :

Max 5x1 + 6x2

S.c -x1 + x2 £ 4

5x1 + 3x2 = 60

x2 ³ 5

x1 ³ 0 , x2 ³ 0

L'introduction des variables d'écart dans le programme linéaire donne

Max 5x1 + 6x2 + 0S1 + 0S2

S.c -x1 + x2 + S1 = 4

5x1 + 3x2 = 60

x2 - S2 = 5

x1³ 0 , x2³ 0, S1³ 0, S2³ 0

Afin de générer une solution réalisable de base initiale pour la méthode de simplexe, on a annulé les variables de décision x1 et x2 . Ceci nous permet de commencer à partir de l’origine O. Or, on vérifie bien que l’origine n’est pas une solution réalisable. La question qui se pose est comment nous allons réécrire le programme de manière qu’on puisse construire le tableau de simplexe initial à l’origine.

Pour arriver à cette fin, on doit ressortir une astuce mathématique qui se résume à l’introduction de nouvelles variables, dite variables artificielles A1 et A2.

Ces variables n’ont aucune interprétation, comme leur nom l’indique, ils sont conçus artificiellement pour nous aider à utiliser la procédure de simplexe et à formuler le tableau initial à partir de l'origine.

Si on ajoute ces deux variables artificielles A1 et A2 respectivement à la 2ème et 3ème contrainte, le programme devient le suivant.

Max 5x1 + 6x2 +...

S.c -x1 + x2 + S1 = 4

5x1 + 3x2 + A1 = 60

x2 -S2 + A2 = 5

x1³ 0, x2³ 0, S1³ 0, S2³ 0 , a1 ³ 0, a2³ 0

Maintenant on peut obtenir une solution initiale de base du système d’équations, si on pose x1 = x2 = 0.

La solution initiale est

x1 = 0

x2 = 0

S1 = 4

S2 = 0

A1 = 60

A2 = 5

Cette solution n’est pas réalisable puisque x2 n’est pas supérieur à 50. Ainsi, il est important de distinguer entre une solution réellement réalisable et une solution du programme linéaire réécrit pour la procédure du simplexe. Certes, une solution réalisable du problème réel reste toujours une solution réalisable pour le programme linéaire transformé, le contraire n’est pas toujours vrai.

On peut conclure que tant que les variables artificielles restent dans la base, la solution demeure non réalisable réellement pour notre programme.

Une manière pour garantir que ces variables artificielles sortent de la base avant d’atteindre la solution optimale est de leur associée un grand coût -M dans la fonction objectif. Ainsi, si ces variables restent dans la base ils vont causer une diminution importante de la valeur de la fonction objectif. Ce qui nous contraignent à les faire sortir le plutôt possible de la base.

La fonction objectif s’écrit donc :

Max z = 5x1 + 6x2 - M A1 - M A2

avec M un très grand nombre (exemple: M ³ 1010) .

En appliquant de ces modifications, le tableau de simplexe initial est

 

 

 

5

6

0

0

-M

-M

 

 

 

x1

X2

S1

S2

A1

A2

0

S1

4

-1

1

1

0

0

0

-M

A1

60

(5)

3

0

0

1

0

-M

A2

5

0

1

0

-1

0

1

De la même manière que précédemment essayons de retrouver la variable entrante te la variable sortante :

 

 

 

5

6

0

0

-M

-M

 

 

 

 

x1

x2

S1

S2

A1

A2

 

0

S1

4

-1

1

1

0

0

0

-4


-M

A1

60

(5)

3

0

0

1

0

12

-M

A2

5

0

1

0

-1

0

1

¥

 

 

 

-5M

-4M

0

M

-M

-M

 

 

 

 

5+5M

6+4M

0

-M

0

0

 

­

La variable entrante est x1 (5 +5M ³ 6 + 4M avec M assez grand) et la variable sortante est A1 . Le tableau de simplexe qui suit est :

 

 

 

5

6

0

0

-M

-M

 

 

 

 

x1

x2

S1

S2

A1

A2

 

0

S1

16

0

8/5

1

0

1/5

0

10

5

x1

12

1

3/5

0

0

1/5

0

20


-M

A2

5

0

(1)

0

-1

0

1

5

 

 

 

5

3-M

0

M

1

-M

 

 

 

 

0

3+M

0

-M

-M-1

0

 

­

Le tableau de simplexe après la deuxième itération indique que la variable sortante est A2.

Remarque: Simplification du tableau

Les deux première itérations on fait sortir de la base les variables artificielles A1 et A2. Leurs effets nets est maintenant négatif et très élevé, elles ne pourront donc pas être sélectionnées à l’itération suivante, ni même ultérieurement comme on peut facilement le constater. Donc on peut supprimer du tableau la colonne relative à A1 et A2.

En appliquant la règle ci-dessus, on obtient le tableau de simplexe suivant :

 

 

 

5

6

0

0

 

 

 

 

x1

x2

S1

S2

 


0

S1

8

0

0

1

8/5

5

5

x1

9

1

0

0

3/5

15

6

x2

5

0

1

0

-1

-5

 

 

 

5

6

0

-3

 

 

 

 

0

0

0

3

 

­

 

 

 

5

6

0

0

 

 

 

x1

x2

S1

S2

0

S2

5

0

0

5/8

1

5

x1

6

1

0

-3/8

0

6

x2

10

0

1

5/8

0

 

 

 

5

6

15/8

0

 

 

 

0

0

-15/8

0

Le tableau ci-dessus est optimal car tous les effets nets sont négatifs ou nuls. Donc la solution optimale est :

x1 = 6

x2 = 10

S1 = 0

S2 = 5

Remarque: cas où le second membre négatif

Le problème qui peut se poser est que l’une des variables du second membre soit négative. Par exemple supposons que lors de la formulation on trouve une contrainte de ce type :

x1 - x2 ³ -4

La condition qu’il faut vérifier avant de se lancer dans la réécriture de cette contrainte, en vue de construire le programme standard, est la nonégativité du second membre.

Ainsi, on doit modifier la contrainte avant de commencer la standardisation et la réécrire comme suit :

-x1 + x2 £ 4

Exercice :

Réécrire convenablement ces contraintes:

(1) x1 + 3x2 - 5x3 = - 20

(2) -x1 + 3x2 ³ - 5

(3) 5x1 - 2x2 £ - 10

 

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