Université de Bordj Bou-Arreridj.
Faculté de mathématiques et Informatique.
Département de Recherche Opérationnelle.
Niveau : Master 1(RO).
Examen Final
(Unité : Programmation Linéaire)
Année universitaire : 2021/2022. Durée : 1h30.
Exercice 1[7 points].
Une entreprise assemble deux types de climatiseurs tropical et économique. Tous les climatiseurs as-
semblés passent par deux départements de vérification A et B où chacun peut vérifier jusqu’à 150
climatiseurs par semaine. Un climatiseur tropical nécessite 2 heures dans le département A et 3 heures
dans B et un climatiseur économique nécessite 3 heures dans le département A et 2 heures dans B.
Pour satisfaire sa demande, l’entreprise doit vérifier au moins 30 climatiseurs par semaine.
L’entreprise souhaite maximiser le nombre de climatiseurs à vérifier.
1. Modéliser ce problème sous forme d’un programme linéaire.
2. Résoudre graphiquement ce programme linéaire.
3. Suite à la crise sanitaire due au COVID-19, la vente des climatiseurs se voit à la baisse et l’en-
treprise devrait minimiser la vérification de ces climatiseurs. Dans ce cas quelle sera la solution
optimale ? est-elle unique ? que peut-on dire ?
4. Montrer que si x, y sont deux solutions optimales pour un programme linéaire alors toute solution
t = λx + (1 − λ)y, ∀λ ∈ [0, 1] est aussi optimale.
Exercice 2[6 points].
Soit le programme linéaire suivant
max Z = 2x1 + x3
x1 − x2 ≤ 2
(P) 2x1 + x3 ≥ 4
x1 + x2 + x3 = 3
x1 , x2 , x3 ≥ 0
Résoudre (P) par l’algorithme de simplexe en deux phases.
Exercice 3 [7 points].
En utilisant le théorème des écarts complémentaires, montrer que la solution x1∗ = 1, x2∗ = 0, x3∗ = 1 est
optimale pour le programme linéaire suivant
min Z = 2x1 − 4x2 + 3x3
x − 2x2 + x3 ≥ 2
1
(P)
x 1 − x3 ≤ 0
−x2 + x3 = 1
x , x ≥ 0, x s.r.s
1 2 3
Bon courage
Le responsable de l’unité : M.Ramdani Zoubir
[email protected]
