Centre universitaire de Mila Année universitaire 2024/2025
Matière : Programmation linéaire 3° Année informatique
Série de TD N°2 (Algorithme du simplexe)
Exercice 1.
Considérons le programme linéaire (Pl ) suivant :
Max Z= x1+2x2
{
−3 x 1+2 x 2 ≤2
−x 1+ 2 x 2≤ 4
x 1+ x 2 ≤5
x∧1 , x 2 ≥ 0
1. Résoudre le programme linéaire (Pl ) en utilisant la méthode graphique.
2. Résoudre le programme linéaire (Pl ) en utilisant la méthode du simplexe.
Exercice 2.
Résoudre avec la méthode du simplexe :
Max z =2x1+x2
{
x 1−2 x 2+ x 3=2
−2 x 1+ x 2+ x 4=2
x 1,x 2,x 3,x 4≥0
Exercice 3.
Une usine fabrique trois produits A, B et C. Chaque produit est traité séquentiellement par les
machines Χ, Y et Ζ comme suit :
Produit Α : traité par les machines Χ et Z
Produit B : traité par les machines Χ, Y et Z
Produit C : traité par les machines Y et Z
X Z B
Y
C
Représentation graphique du processus de fabrication
Chaque unité du produit nécessite une unité de capacité de la machine. Les capacités
journalières des machines sont : X =100, Y=200 et Z=400. Les demandes pour les produits
1/2
A et C sont illimites mais la demande sur B est limite par 80 unités par jour.
Les bénéfices pour chaque unité de Α, Β et C sont 3, 4, 2, respectivement.
1- Donner la formulation mathématique de processus de fabrication qui donnera le profit
maximum à cette usine.
2- Résoudre le programme linéaire obtenu afin de déterminer le plan optimal de
fabrication.
Exercice 4.
Résoudre le problème linéaire suivant par la méthode du simplexe.
Max Z= 3x1+2x2+4x3
{
x 1+ x 2+2 x 3 ≤ 4
2 x 1+ 3 x 3 ≤5
2 x 1+ x 2+3 x 3 ≤ 7
x∧1 , x 2 , x 3 ≥ 0
Exercice 5.
Considère le programme linéaire suivant :
Max Z= -5x1+5x2+13x3
{
−x 1+ x 2+3 x 3 ≤ 20
12 x 1+ 4 x 2+10 x 3 ≤ 90
x∧1 , x 2 , x 3 ≥ 0
1- Résoudre le problème à l’aide de l’algorithme du simplexe.
2- Si on augmente le second membre de la première contrainte de 20 à 30. Quelle sera la
solution optimale en dessous de cette valeur.
3- Quel est l’intervalle de validité de la base optimale du problème, en changeant le se-
cond membre de la première contrainte ?
2/2
