Chapitre IV
Méthode du simplexe (II)
Mohamed Hachimi TD Programmation linéaire 2 / 29
Méthode du simplexe (II)
Exercice 1
Résoudre le programme suivant en utilisant la méthode du
simplexe
max z = 10x1 + 15x2
5x1 + 2x2 6 80
x1 + x2 6 20
x1 + 2x2 6 30
x1 > 0, x2 > 0
Mohamed Hachimi TD Programmation linéaire 3 / 29
Méthode du simplexe (II)
Solution de l’exercice 1
La forme standard du programme est
max z = 10x1 + 15x2
5x1 + 2x2 + x3 = 80
x1 + x2 + x4 = 20
x1 + 2x2 + x5 = 30
x1 > 0, x2 > 0, x3 > 0, x4 > 0, x5 > 0
Mohamed Hachimi TD Programmation linéaire 4 / 29
Méthode du simplexe (II)
Solution de l’exercice 1
Le premier tableau de simplexe est :
B b x1 x2 x3 x4 x5
x3 80 5 2 1 0 0
x4 20 1 1 0 1 0
x5 30 1 2 0 0 1
z 0 10 15 0 0 0
Comme deux nombres de la dernière ligne sont positifs (10 et 15),
cette solution de base réalisable n’est pas optimale.
Mohamed Hachimi TD Programmation linéaire 5 / 29
Méthode du simplexe (II)
Solution de l’exercice 1
D’après la procédure de détermination de la variable entrante et
celle sortante, on a :
x2 entre en base (plus grand coefficient positif de z)
x5 sort de base (plus petit rapport positif de bi /ai2 )
Dans le premier tableau, nous avons entouré le pivot, qui est égal
à 2 par un petit cercle.
Mohamed Hachimi TD Programmation linéaire 6 / 29
Méthode du simplexe (II)
Solution de l’exercice 1
Construisons donc le deuxième tableau de simplexe
B b x1 x2 x3 x4 x5
x3 50 3 0 1 0 −1
x4 5 1/2 0 0 1 −1/2
x2 15 1/2 1 0 0 1/2
z −225 5/2 0 0 0 −15/2
Comme il y a encore, dans la dernière ligne, un nombre positif
(5/2), cette solution de base réalisable n’est pas optimale.
Mohamed Hachimi TD Programmation linéaire 7 / 29
Méthode du simplexe (II)
Solution de l’exercice 1
Nous devons continuer à rechercher une nouvelle meilleure
solution. On a :
x1 entre en base (plus grand coefficient positif de z)
x4 sort de base (plus petit rapport positif de bi /ai1 )
Dans le deuxième tableau, nous avons entouré le pivot, qui est
égal à 1/2 par un petit cercle.
Mohamed Hachimi TD Programmation linéaire 8 / 29
Méthode du simplexe (II)
Solution de l’exercice 1
Construisons donc le troisième tableau de simplexe
B b x1 x2 x3 x4 x5
x3 20 0 0 1 −6 2
x1 10 1 0 0 2 −1
x2 10 0 1 0 −1 1
z −250 0 0 0 −5 −5
deux tous les nombres de la dernière ligne sont positifs, la
solution obtenue
x1 = 10, x2 = 10, x3 = 20, x4 = x5 = 0
est optimale, et la valeur maximale de z est 250.
Mohamed Hachimi TD Programmation linéaire 9 / 29
Méthode du simplexe (II)
Exercice 2
Résoudre le programme suivant en utilisant la méthode du
simplexe
max z = 120x1 + 108x2 + 75x3
x1 + x2 + x3 6 12
x1 6 5
8x1 + 7x2 + 5x3 6 145
x1 > 0, x2 > 0, x3 > 0
Mohamed Hachimi TD Programmation linéaire 10 / 29
Méthode du simplexe (II)
Solution de l’exercice 2
La forme standard du programme est
max z = 120x1 + 108x2 + 75x3
x1 + x2 + x3 + x4 = 12
x1 + x5 = 5
8x1 + 7x2 + 5x3 + x6 = 145
x1 > 0, x2 > 0, x3 > 0, x4 > 0, x5 > 0, x6 > 0
Mohamed Hachimi TD Programmation linéaire 11 / 29
Méthode du simplexe (II)
Solution de l’exercice 2
Premier tableau de simplexe
B b x1 x2 x3 x4 x5 x6
x4 12 1 1 1 1 0 0
x5 5 1 0 0 0 1 0
x6 145 8 7 5 0 0 1
z 0 120 108 75 0 0 0
Comme trois nombres de la dernière ligne sont positifs (120, 108
et 75), cette solution de base réalisable n’est pas optimale.
Mohamed Hachimi TD Programmation linéaire 12 / 29
Méthode du simplexe (II)
Solution de l’exercice 2
D’après la procédure de détermination de la variable entrante et
celle sortante, on a :
x1 entre en base (plus grand coefficient positif de z)
x5 sort de base (plus petit rapport positif de bi /ai1 )
Dans le premier tableau, nous avons entouré le pivot, qui est égal
à 1 par un petit cercle.
Mohamed Hachimi TD Programmation linéaire 13 / 29
Méthode du simplexe (II)
Solution de l’exercice 2
Construisons donc le deuxième tableau de simplexe
B b x1 x2 x3 x4 x5 x6
x4 7 0 1 1 1 −1 0
x1 5 1 0 0 0 1 0
x6 105 0 7 5 0 −8 1
z −600 0 108 75 0 −120 0
Comme il y a encore, dans la dernière ligne, deux nombres po-
sitifs (108 et 75), cette solution de base réalisable n’est pas opti-
male.
Mohamed Hachimi TD Programmation linéaire 14 / 29
Méthode du simplexe (II)
Solution de l’exercice 2
Nous devons continuer à rechercher une nouvelle meilleure
solution. On a :
x2 entre en base (plus grand coefficient positif de z)
x4 sort de base (plus petit rapport positif de bi /ai2 )
Dans le deuxième tableau, nous avons entouré le pivot, qui est
égal à 1 par un petit cercle.
Mohamed Hachimi TD Programmation linéaire 15 / 29
Méthode du simplexe (II)
Solution de l’exercice 2
Construisons donc le troisième tableau de simplexe
B b x1 x2 x3 x4 x5 x6
x2 7 0 1 1 1 −1 0
x1 5 1 0 0 0 1 0
x6 56 0 0 −2 −7 −1 1
z −1356 0 0 −33 −108 −12 0
Comme tous les nombres de la dernière ligne sont négatifs ou
nuls, la solution obtenue
x1 = 5, x2 = 7, x3 = x4 = x5 = 0, x6 = 56
est optimale, et la valeur maximale de z est 1356.
Mohamed Hachimi TD Programmation linéaire 16 / 29
Méthode du simplexe (II)
Exercice 3
Résoudre le programme suivant en utilisant la méthode du
simplexe
max z = x1 − x2
2x1 − x2 > −4
x1 − x2 6 4
x1 + x2 6 10
x1 > 0, x2 > 0
Mohamed Hachimi TD Programmation linéaire 17 / 29
Méthode du simplexe (II)
Solution de l’exercice 3
La forme standard du programme est
max z = x1 − x2
−2x1 + x2 + x3 = 4
x1 − x2 + x4 = 4
x1 + x2 + x5 = 10
x1 > 0, x2 > 0, x3 > 0, x4 > 0, x5 > 0
Mohamed Hachimi TD Programmation linéaire 18 / 29
Méthode du simplexe (II)
Solution de l’exercice 3
Le premier tableau de simplexe
B b x1 x2 x3 x4 x5
x3 4 −2 1 1 0 0
x4 4 1 −1 0 1 0
x5 10 1 1 0 0 1
z 0 1 −1 0 0 0
Mohamed Hachimi TD Programmation linéaire 19 / 29
Méthode du simplexe (II)
Solution de l’exercice 3
Le deuxième tableau de simplexe
B b x1 x2 x3 x4 x5
x3 12 0 −1 1 2 0
x1 4 1 −1 0 1 0
x5 6 0 2 0 −1 1
z −4 0 0 0 −1 0
Comme tous les nombres de la dernière ligne sont négatifs ou
nuls, la solution obtenue
x1 = 4, x2 = 0, x3 = 12, x4 = 0, x5 = 6
est optimale, et la valeur maximale de z est 4.
Mohamed Hachimi TD Programmation linéaire 20 / 29
Méthode du simplexe (II)
Solution de l’exercice 3
La solution optimale correspond au sommet S1 défini par
S1 = (x1 , x2 ) = (4, 0), avec z S1 = 4.
Notez que la dernière ligne contient un nombre nul (n’est pas
négatif) correspondant à une variable hors base, qui est x2 .
Par suite, x2 peut entrer en base, ce qui conduit à une nouvelle
solution de base optimale, soit un deuxième sommet S2 optimale.
Ce changement de base n’affecte pas la valeur optimale puisque
la dernière ligne contient un 0 dans la colonne pivot, d’où :
z S2 = z S1 = 4.
Mohamed Hachimi TD Programmation linéaire 21 / 29
Méthode du simplexe (II)
Solution de l’exercice 3
Le troisième tableau de simplexe
B b x1 x2 x3 x4 x5
x3 15 0 0 1 3/2 1/2
x1 7 1 0 0 1/2 1/2
x2 3 0 1 0 −1/2 1/2
z −4 0 0 0 −1 0
Comme tous les nombres de la dernière ligne sont négatifs ou
nuls, la solution obtenue
x1 = 7, x2 = 3, x3 = 15, x4 = x5 = 0
est optimale, et la valeur maximale de z est −4.
Mohamed Hachimi TD Programmation linéaire 22 / 29
Méthode du simplexe (II)
Solution de l’exercice 3
Donc, on a deux sommets optimaux S1 et S2 . Par suite, tous les
points réalisables appartenant à la droite passant par S1 et S2 sont
optimaux.
Ainsi, l’ensemble des solutions optimale est le segment
[S1 , S2 ]
Mohamed Hachimi TD Programmation linéaire 23 / 29
Méthode du simplexe (II)
Exercice 4
Résoudre le programme suivant en utilisant la méthode du
simplexe
max z = 10x1 + 14x2
x1 + x2 > 12
x1 > 8
x2 6 6
x1 > 0, x2 > 0
1◦ Montrer que x̄ = (12, 0) est un sommet de la région réalisable.
Mettre le programme sous forme standard, puis donner la so-
lution de base réalisable ȳ associée à x̄.
2◦ Résoudre ce programme par la méthode du simplexe en pre-
nant comme point de départ ȳ.
Mohamed Hachimi TD Programmation linéaire 24 / 29
Méthode du simplexe (II)
Solution de l’exercice 4
1◦ Le point x̄ = (12, 0) vérifie comme égalités deux contraintes :
soit x1 + x2 = 12 et x2 = 0 (contrainte de non négativité).
Le point x̄ est à l’intersection de deux droites sur la frontière
de la région réalisable, ce qui correspond bien à un sommet.
le programme sous forme standard
max z = 10x1 + 14x2
x1 + x2 − x3 = 12
(P) x1 − x4 = 8
x2 + x5 = 6
x1 > 0, x2 > 0, x3 > 0, x4 > 0, x5 > 0
Mohamed Hachimi TD Programmation linéaire 25 / 29
Méthode du simplexe (II)
Solution de l’exercice 4
En reportant les coordonnées du sommet x̄, soit (x1 , x2 ) =
(12, 0), dans le système
x1 + x2 − x3
= 12
x1 − x4 = 8
x2 + x5 = 6
on obtient
x3 = 0, x4 = 4, x5 = 6
Donc, la solution de base réalisable ȳ associée à x̄ est :
ȳ = (12, 0, 0, 4, 6)
Mohamed Hachimi TD Programmation linéaire 26 / 29
Méthode du simplexe (II)
Solution de l’exercice 4
2◦ La base associée au sommet x̄ est B = {1, 4, 5}. Exprimons
les variables de base et la fonction objectif en fonction des
variables hors base x2 et x3 :
x1 = 12 − x2 + x3 = 12 − x2 + x3
x = 8 − x = 8 − (12 − x + x ) = 4 − x + x
4 1 2 3 2 3
x5 = 6 − x2 = 6 − x 2
z = 10x1 + 14x2 = 120 + 4x2 + 10x3
Mohamed Hachimi TD Programmation linéaire 27 / 29
Méthode du simplexe (II)
Solution de l’exercice 4
Donc le programme (P) peut s’écrire sous la forme :
max z = 120 + 4x2 + 10x3
x1 + x2 − x3 = 12
(P) x2 − x3 + x4 = 4
x2 + x5 = 6
x1 > 0, x2 > 0, x3 > 0, x4 > 0, x5 > 0
On a donc une solution de base réalisable initiale :
(x1 , x2 , x3 , x4 , x5 ) = (12, 0, 0, 4, 6)
Mohamed Hachimi TD Programmation linéaire 28 / 29
Méthode du simplexe (II)
Solution de l’exercice 4
Un tableau de simplexe initial est :
B b x1 x2 x3 x4 x5
x1 12 1 1 −1 0 0
x4 4 0 1 −1 1 0
x5 6 0 1 0 0 1
z −120 0 4 10 0 0
On remarque que les coefficients de la colonne de la variable
hors base x3 sont négatifs ou nuls. On peut donc augmenter
la valeur de x3 autant que l’on vent sans que les valeurs des
variables de base deviennent négatives.
Donc, la solution du problème est infinie.
Mohamed Hachimi TD Programmation linéaire 29 / 29
