Université IBN Tofail
Faculté des Sciences
Département Informatique
Recherche Opérationnelle :
Programmation liniéaire
TD1
Author: Filière:
Pr. Khalil IBRAHIMI Licence SMI, S5
October 28, 2021
FSK, SMI, S5 TD1 Programmation linéaire
1 Questions de cours
Q1: Donner un exemple de fonction linéaire?
Q2: Donner un exemple de fonction non linéaire?
Q3: Que veut dire un programmme linéaire?
Q4: Dans la forme standard générale d’un programme linéaire, quels sont les
éléments suivants d’un programme liniéaire N, B, A, c, v?
2 Exercices d’application
Exercice 1:Convertir le programme en forme canonique
Maximiser
2x1 + 5x2
Sous les contraintes
x1 + 2x2 = 1
2x1 + x2 ≤ 2
x1 ≥ 0.
Construire par des substitutions un système équivalent.
Exercice 2: 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: 2021-2022
FSK, SMI, S5 TD1 Programmation linéaire
3. Donner la forme standard du P.L.
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 optimale précédent en exécutant l’algorithme Sim-
plexe. Précisier pour chaque itération les valeurs de la nouvelle forme
standard.
Exercice 3: On considère la forme standard d’un PL suivant:
M ax z = x1 + 3x2 + 5x3 + x4 + 4x5
x 1 + x2 − x3 + x 4 = 1
2x1 + 4x3 + 2x4 + x5 = 7
x1 + 6x2 + x3 + 2x5 = 19
xi ≥ 0 pourtout 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. Ecrire sous forme matricielle la forme standard.
4. Trouver la solution optimale par Simplexe.
Exercice 4: Soit le programme linéaire suivant :
maximiser
10x1 + 30x2
Sous les contraintes
x1 + x2 ≤ 5
−2x1 + 2x2 ≥ 12
Les contraintes de positivités.
1. Trouver sa forme standard
2. Trouver la solution optimale via la méthode du grand M.
Pr. Khalil IBRAHIMI 2 a.u: 2021-2022
FSK, SMI, S5 TD1 Programmation linéaire
Exercice 5: Résoudre le programme linéaire suivant en utilisant simplexe.
Maximiser
18x1 + 12.5x2
Sous les contraintes
x1 + x2 ≤ 20
x1 ≤ 12
x2 ≤ 16
x1 , x2 ≥ 0.
Exercice 6: Résoudre le programme linéaire suivant en utilisant 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 6:
1. Montrer que le dual du dual est le primal (proposer un exemple).
Pr. Khalil IBRAHIMI 3 a.u: 2021-2022
