Recherche opérationnelle TD1 Programmation linéaire
Exercice 1: Trouver le plan optimal du programme linéaire suivant par la
méthode des droites parallèles.
Maximiser
18x1 + 12.5x2
Sous les contraintes
x1 + x2 ≤ 20
x1 ≤ 12
x2 ≤ 16
x1 , x2 ≥ 0.
Convertir ce programme en forme standard, puis donner sa forme condensée
matricielle.
Exercice 2
1. Convertir le programme linéaire ci-dessous en forme canonique
Maximiser
2x1 + 5x2
Sous les contraintes
x1 + 2x2 = 1
2x1 + x2 ≤ 2
x1 ≥ 0.
2. Construire par des substitutions un système équivalent.
Exercice 3: Un atelier fabrique deux types de produits A et B avec 3
matières premières M1, M2 et M3.
La fabrication d’une unité du produit A nécessite 1Kg de la matière M1, 3kg
de la matière M2 et 1Kg de la matière M3.
La fabrication d’une unité du produit B nécessite 1Kg de la matière M1, 1kg
de la matière M2.
Les matières premières sont disponibles en quantités limitées :
- 20Kg/Jour pour la matière M1.
- 30Kg/Jour pour la matière M2.
- 7Kg/Jour pour la matière M3.
La vente d’une unité du produit A rapporte un bénéfice de 30dh et la vente
d’une unité du produit B rapporte un bénéfice de 20dh.
1. Formuler le problème en un programme linéaire sous forme canonique.
2. Déterminer en utilisant la méthode géométrique le plan optimal de
fabrication.
Pr. Khalil IBRAHIMI 1 a.u: 2022-2023/uit
Recherche opérationnelle TD1 Programmation linéaire
3. Convertir le P.L en forme standard.
4. Trouver la solution de base initiale réalisable.
5. Quelles sont les valeurs des paramètres N, B, A, c, v à l’initialisation.
6. Confirmer le plan optimal précédent en exécutant l’algorithme Sim-
plexe. Précisier pour chaque itération les valeurs de la nouvelle forme
standard. Dans combien d’itérations l’algorithme converge.
Exercice 4: On considère la forme standard d’un PL ci-dessous à une
itération du Simplex:
M ax z = x1 + 3x2 + 5x3 + x4 + 4x5
x 1 + x2 − x3 + x4 = 1
2x1 + 4x3 + 2x4 + x5 = 7
x1 + 6x2 + x3 + 2x5 = 19
xi ≥ 0 pour tout i = 1, 2, 3, 4, 5.
1. Montrer que la solution de base (0, 2, 1, 0, 3) est réalisable.
2. Déterminer la valeur de la fonction objectif pour cette solution.
3. Exprimer les variables de bases en fonction des variables hors base à
cette itération.
4. Trouver la solution optimale par Simplexe.
Exercice 5: Soit le programme linéaire suivant :
maximiser
10x1 + 30x2
Sous les contraintes
x1 + x2 ≤ 5
−2x1 + 2x2 ≥ 12
Les contraintes de positivités.
1. Transformer le programme linéaire ci-dessus en forme canonique.
2. Convertir la forme canonique à la forme standard.
3. Trouver la solution optimale du programme linéaire.
Pr. Khalil IBRAHIMI 2 a.u: 2022-2023/uit
Recherche opérationnelle TD1 Programmation linéaire
Exercice 6: Résoudre le programme linéaire suivant en utilisant la méthode
algorithmique du simplexe.
maximiser
−5x1 − 3x2
Sous les contraintes
x1 − x2 ≤ 1
2x1 + x2 ≤ 2
x2 ≤ 16
x1 , x2 ≥ 0.
Exercice 7: Soit le programme linéaire primal suivant:
maximiser
3x1 + x2 + 2x3
Sous les contraintes
3x1 + x2 + 3x3 ≤ 30
2x1 + 2x2 + 5x3 ≤ 24
4x1 + x2 + 2x3 ≤ 36
x1 , x2 , x3 ≥ 0
1. Donner les coefficients de la fonction objectif et les membres de droite.
2. Formuler le programme dual du programme primal.
3. Quelle est la solution optimale du dual et du primal. Que peut-on conclure.
Exercice 8 : Méthode des deux phases
max
z = x1 − x2 + x3
sc
2x1 − x2 + 2x3 ≤ 4
−2x1 + 3x2 + x3 ≥ 5
x1 − x2 + 2x3 ≥ 1
xi ≥ 0
1. Trouver la forme canonique du programme ci-dessus
2. Trouver la forme standard
3. Montrer que la solution de base (0, 0, 0) est iréalisable
4. Formuler le programme auxiliaire et trouver sa valeur optimale.
5. Trouver la solution optimale du problème original par la méthode algo-
rithmique du Simplex.
Pr. Khalil IBRAHIMI 3 a.u: 2022-2023/uit
