TRAVAUX DIRIGÉS
Programmation linéaire
TD Programmation linéaire 1 / 24
Chapitre II
Méthode graphique
TD Programmation linéaire 2 / 24
Méthode graphique
Exercice 1
Reprendre les Exercices 1, 2 et 3 de la feuille de TD1, et trouver
les solutions optimales à l’aide de la méthode graphique.
TD Programmation linéaire 3 / 24
Méthode graphique
Solution de l’exercice 1
Le problème de l’exercice 1 de TD1 est :
max z = 20x1 + 40x2
2, 5x1 + x2 6 10
3x1 + 3x2 6 15
x1 + 2x2 6 8
x1 > 0, x2 > 0
TD Programmation linéaire 4 / 24
Méthode graphique
Solution de l’exercice 1
20
18
16
14
12 Ex.1.1
10
8
6
4
2
0 2 4 6 8 10 12 14 16 18 20
TD Programmation linéaire 5 / 24
Méthode graphique
Solution de l’exercice 1
Le point optimal est le point :
(x1 , x2 ) = (4, 6)
et la valeur optimale est :
z∗ = 20 × 4 + 40 × 6 = 320
TD Programmation linéaire 6 / 24
Méthode graphique
Solution de l’exercice 1
Le problème de l’exercice 2 de TD1 est :
min z = 120x1 + 60x2
3x1 + x2 > 15
x1 + 5x2 > 20
3x1 + 2x2 > 24
x1 > 0, x2 > 0
TD Programmation linéaire 7 / 24
Méthode graphique
Solution de l’exercice 1
20
18
16
14
12 Ex.1.2
10
8
6
4
2
0 2 4 6 8 10 12 14 16 18 20
TD Programmation linéaire 8 / 24
Méthode graphique
Solution de l’exercice 1
Le point optimal est le point :
(x1 , x2 ) = (2, 9)
et la valeur optimale est :
z∗ = 120 × 2 + 60 × 9 = 780
TD Programmation linéaire 9 / 24
Méthode graphique
Solution de l’exercice 1
Le problème de l’exercice 3 de TD1 est :
max z = 4x1 + 6x2
5x + x 6 60
1 2
x1 + 10x 2 6 110
x1 > 0, x2 > 0
TD Programmation linéaire 10 / 24
Méthode graphique
Solution de l’exercice 1
20
18
16
14
12 Ex.1.3
10
8
6
4
2
0 2 4 6 8 10 12 14 16 18 20
TD Programmation linéaire 11 / 24
Méthode graphique
Solution de l’exercice 1
Le point optimal est le point :
(x1 , x2 ) = (10, 10)
et la valeur optimale est :
z∗ = 4 × 10 + 6 × 10 = 100
TD Programmation linéaire 12 / 24
Méthode graphique
Exercice 2
On considère le programme linéaire suivant :
max z = 2x1 + 6x2
x1 + x2 6 8
x1 − x2 6 3
−x1 + 4x2 6 16
x1 > 0, x2 > 0
1◦ Tracer les contraintes et déterminer la région réalisable.
2◦ La région réalisable comporte combien de points extrêmes ?
3◦ Déterminer la solution optimale avec la méthode graphique.
4◦ Quelles sont les contraintes qui sont satisfaites avec une
stricte égalité ?
TD Programmation linéaire 13 / 24
Méthode graphique
Solution de l’exercice 2
1◦ Région réalisable
12
10
0 2 4 6 8 10 12
TD Programmation linéaire 14 / 24
Méthode graphique
Solution de l’exercice 2
2◦ La région réalisable comporte 5 points extrêmes
10
6
bb
bb
4
bb
bb bb
0 2 4 6 8 10 12
TD Programmation linéaire 15 / 24
Méthode graphique
Solution de l’exercice 2
3◦ La solution optimale est le point A.
10
6
A
4
0 2 4 6 8 10 12
TD Programmation linéaire 16 / 24
Méthode graphique
Solution de l’exercice 2
4◦ Les contraintes qui sont satisfaites avec une stricte égalité à
l’optimum sont : (
x1 + x2 6 8
−x1 + 4x2 6 16
Ainsi, le point A vérifie
(
x1 + x2 = 8
−x1 + 4x2 = 16
Soit
16 24
A= ,
5 5
TD Programmation linéaire 17 / 24
Méthode graphique
Exercice 3
On considère le programme linéaire suivant :
min z = 4x1 + 2x2
4x1 + x2 > 10
2x1 + x2 > 7
x1 + 6x2 > 9
x1 > 0, x2 > 0
1◦ Déterminer la solution optimale avec la méthode graphique.
2◦ Est-ce que la solution optimale est unique ?
TD Programmation linéaire 18 / 24
Méthode graphique
Solution de l’exercice 3
1◦ La solution optimale est :
10
6
B
4
2
A
0 2 4 6 8 10
TD Programmation linéaire 19 / 24
Méthode graphique
Solution de l’exercice 3
2◦ Sur la figure, comme la droite d’isovaleur z = 15 est tangente
à la deuxième contrainte, il n’y a pas de solution optimale
unique.
En effet, tout point situé sur cette droite entre les sommets A
et B est optimal.
TD Programmation linéaire 20 / 24
Méthode graphique
Exercice 4
On considère le programme linéaire suivant :
max z = 4x1 + 6x2
3x1 + 2x2 > 12
−x1 + x2 6 8
x1 − x2 6 0
x1 > 0, x2 > 0
1◦ Tracer les contraintes et déterminer la région réalisable.
2◦ Combien existe-t-il de points extrêmes ?
3◦ Peut-on déterminer une solution optimale finie au programme
linéaire ?
TD Programmation linéaire 21 / 24
Méthode graphique
Solution de l’exercice 4
1◦ Contraintes et la région réalisable
10
0 2 4 6 8 10
TD Programmation linéaire 22 / 24
Méthode graphique
Solution de l’exercice 4
2◦ La région réalisable comporte 3 points extrêmes
10
0 2 4 6 8 10
TD Programmation linéaire 23 / 24
Méthode graphique
Solution de l’exercice 4
3◦ Ce programme linéaire admet solution optimale infinie. En
effet, le point
(x1 , x2 ) = (α, α)
12
est réalisable pour α > .Ainsi, la valeur
5
z = 4x1 + 6x2 = 10α
peut prendre une valeur assez grande que l’on veut.
TD Programmation linéaire 24 / 24
