Recherche opérationnelle TD1 Programmation linéaire
Exercice 1: Soit un programme linéaire avec des variables (x1 , x2 ≥ 0).
Maximiser
18x1 + 12x2
Sous les contraintes
x1 + x2 ≤ 20
x1 ≤ 12
x2 ≤ 16
- Trouver le plan optimal du programme linéaire par la méthode géométrique
(trouver les points extrêmes)
- Confirmer la solution précédente par la méthode des droites parallèles.
- Convertir ce programme en forme standard
- Transformer le programme en forme matricielle.
Exercice 2
1. Convertir le programme linéaire ci-dessous en forme canonique en con-
struisant un système équivalent par substitution (x1 ≥ 0).
Maximiser
2x1 + 5x2
Sous les contraintes
x1 + 2x2 = 1
2x1 + x2 ≤ 2
2. Transformer la forme canonique en forme standard.
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.
Pr. Khalil IBRAHIMI 1 a.u: 2022-2023/uit
Recherche opérationnelle TD1 Programmation linéaire
2. Convertir le programme linéaire en forme standard.
3. Trouver la solution de base initiale réalisable.
4. Quelles sont les valeurs des paramètres N, B, A, c, v à l’initialisation.
5. Trouver le plan optimal via la méthode algorithmique du Simplexe.
Précisier pour chaque itération les valeurs de la nouvelle forme stan-
dard. Dans combien d’itérations l’algorithme converge.
Exercice 4: On considère la forme standard d’un progralme linèaire avec
des variables de décision (xi ≥ 0 pour i = 1, 2, 3, 4, 5.):
Maximiser
z = x1 + 3x2 + 5x3 + x4 + 4x5
Sous les contraintes
x1 + x2 − x3 + x4 = 1
2x1 + 4x3 + 2x4 + x5 = 7
x1 + 6x2 + x3 + 2x5 = 19
1. Montrer que la solution de base (0, 2, 1, 0, 3) est réalisable et la valeur
de l’objectif est 23.
2. Formuler le programme linéaire équivalent avec la méthode de la Phase
I du simplexe.
3. Montrer que la valeur de l’objectif de la phase I est nulle (dans combien
d’itérations).
4. Appliquer la phase II du simplexe pour déterminer la valeur optimale
du programme original.
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 des variables de décision.
1. Transformer le programme linéaire ci-dessus en forme canonique.
2. Trouver la forme standard du programme linéaire.
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 (x1 , x2 ≥ 0).
Maximiser
−5x1 − 3x2
Sous les contraintes
x1 − x2 ≤ 1
2x1 + x2 ≤ 2
x2 ≤ 16
Comparer avec la solution géométrique.
Exercice 7: Nous considérons le programme linaire ci-dessous avec les vari-
ables de décision (x1 , x2 , x3 ≥ 0)
Maximiser
3x1 + x2 + 2x3
Sous les contraintes
3x1 + x2 + 3x3 ≤ 30
2x1 + 2x2 + 5x3 ≤ 24
4x1 + x2 + 2x3 ≤ 36
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 : Soit un problème de maximisation dont les variables de décisions
(xi ≥ 0)
Maximiser
z = x1 − x2 + x3
Sous les contraintes
2x1 − x2 + 2x3 ≤ 4
−2x1 + 3x2 + x3 ≥ 5
x1 − x2 + 2x3 ≥ 1
1. Trouver la forme standard
2. Montrer que la solution de base (0, 0, 0) est iréalisable
3. Formuler le programme auxiliaire et trouver sa valeur optimale.
4. Trouver la solution optimale du problème original.
Pr. Khalil IBRAHIMI 3 a.u: 2022-2023/uit
