Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

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 - S 2 = 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.

Cours de recherche opérationnelle Slim GUERMAZI 33

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

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

Cours de recherche opérationnelle Slim GUERMAZI 34

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

ci 5 6 0 0 -M -M
Cout base base
Base 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 :
ci 5 6 0 0 -M -M
Cout base base
Base 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 :
ci 5 6 0 0 -M -M
Cout base base
Base 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 :

Cours de recherche opérationnelle Slim GUERMAZI 35

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

ci 5 6 0 0
Cout base base
Base 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


ci 5 6 0 0
Cout base base
Base 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

Cours de recherche opérationnelle Slim GUERMAZI 36

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

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 :

Cours de recherche opérationnelle Slim GUERMAZI 37

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

ci 5 6 0 0 0 M M M
Cout basebase Base 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 :
ci 5 6 0 0 0
Cout base base Base
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érifié 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 Pour la fonction objectif d’un problème de

est Maximisation Minimisation
I- de type «  » Attribuer un coefficient nul pour la variable d’écart
Ajouter une variable
d’écart
II- de type « = » Attribuer un coefficient -M Attribuer un coefficient M
Ajouter une variable pour variable artificielle pour la variable artificielle
d’écart et une
variable artificielle
III- de type «  » Attribuer un coefficient nul Attribuer un coefficient nul
Ajouter une variable pour la variable d’écart et un pour la variable d’écart et
artificielle et une coefficient - M pour variable un coefficient M pour
variable d’écart avec artificielle variable artificielle
un signe "-"

Cours de recherche opérationnelle Slim GUERMAZI 38

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

Le tableau suivant résume les étapes de la méthode de simplexe relatif aux

problèmes de maximisation et minimisation :

Etape Maximisation Minimisation

1 Formuler un programme linéaire Formuler un programme linéaire
pour le problème réel. pour le problème réel.
2 Vérifier que le second membre du Vérifier que le second membre du
programme linéaire est positif sinon programme linéaire est positif sinon
modifier les contraintes modifier les contraintes
3 Ecrire le programme linéaire sous Ecrire le programme linéaire sous
une forme standard une forme standard
4 Construire le premier tableau de Construire le premier tableau de
simplexe simplexe
5 Choisir comme variable entrante Choisir comme variable entrante
dans la base celle qui admet le plus dans la base celle qui admet le plus
grand effet net positif cj-zj. petit effet net négatif cj-zj.
6 Choisir la variable sortante de la Choisir la variable sortante de la
base celle qui admet le plus petit base celle qui admet le plus petit
ratio supérieur à zéro. ratio supérieur à zéro.
7 Construire le nouveau tableau en Construire le nouveau tableau en
utilisant la règle de pivot utilisant la règle de pivot
8 Faire le test d’optimalité. Si Faire le test d’optimalité. Si
(cj-zj)  0 pour toutes les variables (cj-zj)  0 pour toutes les variables
(hors base) donc la solution obtenue (hors base) donc la solution obtenue
est optimale. Sinon retourner à est optimale. Sinon retourner à
l’étape 5. 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.

Cours de recherche opérationnelle Slim GUERMAZI 39

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

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

Cours de recherche opérationnelle Slim GUERMAZI 40

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

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 + S 2 = 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

Cours de recherche opérationnelle Slim GUERMAZI 41

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

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
x2 3 0 1 0 1 

2
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 , x 2 , x3  0
La solution optimale de ce problème est :
x1 = 1 x2 = 0 x3 = 2 z =5

Cours de recherche opérationnelle Slim GUERMAZI 42

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

La forme standard du programme linéaire est

Max 2x1 + 0 x2 + 3/2x3 + 0 S1 + 0 S2 + 0 S3
Sc x1 - x2 + S 1 = 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
S1 2 1 -1 0 1 0 0 2

0
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

Cours de recherche opérationnelle Slim GUERMAZI 43

Chapitre 4 : Problème de Minimisation et Problèmes irréguliers

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).

Cours de recherche opérationnelle Slim GUERMAZI 44