Recherche Opérationnelle S7, TD n◦ 2
Exercice 1. Les deux tableaux T et T 0 suivants sont respectivement, le tableau initial et le
tableau final (optimal) d’un programme linéaire P, obtenus à l’aide de la méthode simplexe.
Tableau initial T .
x1 x2 x3 x4 x5 x6
x4 1 1 2 1 0 0 2
x5 2 3 4 0 1 0 3
x6 6 6 2 0 0 1 8
8 9 5 0 0 0 0
Tableau final T 0 .
x1 x2 x3 x4 x5 x6
x4 0 0 5
3
1 0 −1 6
2
3
x2 0 1 10
3
0 1 −1 3
1
3
x1 1 0 -3 0 -1 12 1
0 0 -1 0 -1 -1 -11
1. S’agit-il d’un problème de maximisation ou de minimisation ?
2. (a) Pour chaque tableau, quelles sont les variables de base et les variables hors base ?
(b) Quelle est la solution de base admissible initiale et quelle est la solution optimale ?
(c) Quelles sont les valeurs des variables d’écart dans le tableau final T 0 ? quelle est
l’interprétation économique de ces valeurs ?
3. Déterminer la forme standard du programme linéaire P, en déduire sa forme canonique.
Exercice 2. Soit le programme linéaire P suivant :
M ax (z) = 20x1 + 10x2 + 15x3
3x1 + 2x2 + 5x3 ≤ 55
2x1 + x2 + x3 ≤ 26
x1 + x2 + 3x3 ≤ 30
5x1 + 2x2 + 4x3 ≤ 57
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Résoudre le programme P par la méthode du simplexe.
Exercice 3. Donner les duales des programmes linéaires primales suinants :
Pr. Elouali AAILAL 1 ENCG Dakhla RO S7 2024/2025
Exercice 4. Soit le programme linéaire P suivant :
M in (z) = 4x1 + 6x2 + 18x3
x1 + 3x3 ≥ 3
x2 + 2x3 ≥ 5
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
1. Donner le programme dual P 0 du programme primal P .
2. Résoudre le programme dual P 0 par la méthode du simplexe.
3. En déduire la solution optimale du programme primal P .
Exercice 5. Une entreprise produit des Poupées et se prépare pour Aachoura, par l’embauche
d’une équipe de 30 ouvriers occasionnels. Cette entreprise fabrique deux tailles differentes des
Poupées. Le profit, le temps de production et la matière première utilisé suivant la taille de
Poupées, sont résumés au tableau suivant.
Les ouvriers travaillent 8 heures par jour et il y a 2000 kg de matière première disponible quo-
tidiennement.
Petite poupée Grande poupée
1 3
Temps de production (heure) 10 10
Matière première (kg) 1 2
Prix unitaire (Dh) 3 8
1. Modéliser ce problème en un programme linéaire P .
2. Résoudre le programme P par la méthode du simplexe.
3
3. La solution optimale changera-t-elle si le profit sur les petites poupées augmente de 4
Dh ? La valeur optimale de la fonction objectif changera-t-elle ?
4. La solution optimale changera-t-elle si on augmente la quantité de la matière première
d’un Kilogramme par jour ? La valeur optimale de la fonction objectif changera-t-elle ?
Pr. Elouali AAILAL 2 ENCG Dakhla RO S7 2024/2025
