Université Ibn Zohr A.
U : 2019 - 2020
Faculté des Sciences d’Agadir
Filière : SMI-5
Matière : Recherche Opérationnelle
Série de TD N° 4
Programmation Linéaire : Dualité – variables artificielles
Règle de Bland: Lorsque plusieurs variables sont susceptibles d’entrer ou de sortir de la base, on
choisit toujours celle qui a l’indice le plus petit.
N.B Pour appliquer la règle de Bland, nommer toutes les variables (d’écart et artificielle) xi
I. Dualité
Exercice 1:
Min x1 + x2
Sc
2x1 + x2 ≥ 12
5x1 + 8x2 ≥ 74
x1 + 6x2 ≥ 24
x1 , x 2 ≥ 0
- Ecrire le programme dual correspondant.
- Résoudre le PL dual via la méthode de simplexe ?
- Comparer les tableaux finaux du primal et dual, conclusion ?
Exercice E2: [2 points][~ 10 minutes]
Soit programme linéaire suivant :
Max P(x1,x2,x3,x4,x5)= 3x1 + 2x2 + 4x3 + 6x4 + 4x5
Sous contraintes
2x1 + 3x2 + x3 + x4 ≤ 32
x1 + 2x2+ 3x3 ≤ 25
x2 + 5x3 + 4x4 ≤ 40
3x2 - x3 - x4 ≤ 15
x5 ≤ 45
x 1, x2 , x 3 , x 4 , x 5 ≥ 0
1. Écrire le programme dual correspondant.
2. Sachant que le tableau ci-dessous représente le tableau final du programme primal, donner en
justifiant votre réponse:
a) La valeur de la fonction objectif du Primal et les coordonnées correspondantes
b) La valeur de la fonction objectif du Dual et les coordonnées correspondantes
x1 x2 x3 x4 x5 e1 e2 e3 e4 e5
e1 0 17/12 -9/4 0 0 1 -2/3 -1/4 0 0 16/3
x1 1 2/3 1 0 0 0 1/3 0 0 0 25/3
x4 0 1/4 5/4 1 0 0 0 1/4 0 0 10
e4 0 13/4 1/4 0 0 0 0 1/4 1 0 25
x5 0 0 0 0 1 0 0 0 0 1 45
P 0 -3/2 -13/2 0 0 0 -1 -3/2 0 -4
Exercice 3:
Deux produits P1 et P2 fabriqués en quantité x1 et x2, nécessitant trois ressources disponibles en
quantités données. L’entreprise cherche à maximiser le bénéfice total provenant de la vente des 2
produits.
Max [F(x1, x2) = 6x1 + 4x2]
3x1 + 9x2 ≤ 270
4x1 + 5x2 ≤ 360
2x1 + x2 ≤ 20
x1, x2 ≥ 0
RO - TD N°4. Dualité – Variables Artificielles Page 1 / 3
Université Ibn Zohr A.U : 2019 - 2020
Faculté des Sciences d’Agadir
Filière : SMI-5
Matière : Recherche Opérationnelle
Supposons à présent qu’un acheteur se présente pour acheter toutes les ressources de l’entreprise. Il
propose à l’entreprise les prix unitaires y1, y2, y3 pour chacune des ressources.
L’entreprise acceptera de lui vendre toutes ses ressources uniquement si elle obtient pour chaque
produit un prix de vente au moins égal au profit qu’elle ferait en vendant ses produits.
De son côté, l’acheteur cherche à minimiser ses dépenses.
1. Ecrire la proposition de l’acheteur sous forme d’un PL.
2. Trouver la solution optimale ainsi que les coordonnées correspondantes.
II. Algorithme de simplexe : M-Méthodes
Exercice 4:
Résoudre le PL suivant en utilisant la M-méthode.
Max Z = 4x + y
SC
3x + y ≥ 3
4x + 3y ≥ 6
x + 2y ≤ 4
x,y ≥ 0
Exercice 5: [5 points][~ 35 minutes]
Deux substances S et T, contiennent chacune deux types d’ingrédients I et F. Une livre (unité de
masse) de S contient 5 mesures (1 mesure = 30g) de I et 8 mesures de F. Une livre de T contient 4
mesures de I et 2 mesures de F. Un fabricant projette de combiner les deux substances pour obtenir
un mélange qui contienne au moins 540g de I et 960g mesures de F. Le coût de S est de 8 um la livre et
le coût de T de 5 um la livre.
L’objectif est de calculer la quantité (en mesures) de chaque substance qu’il faudrait utiliser pour
maintenir les coûts au minimum ?
1. Modéliser le problème sous forme de PL.
2. Résoudre graphiquement le PL.
3. Résoudre le PL en utilisant la M-méthode.
III. Algorithme de simplexe en 2 phases
Exercice 6: Résoudre le PL suivant en utilisant le simplexe en 2 phases.
Min x1 + x2
Sc
2x1 + x2 ≥ 12
5x1 + 8x2 ≥ 74
x1 + 6x2 ≥ 24
x1 , x 2 ≥ 0
Exercice 7: Algorithme de simplexe en 2 phases [6 points][~ 45 minutes]
Soit programme linéaire suivant :
Max Z = 5x1 + 7x2
SC
x1 + x2 ≥ 40
2x1 + 3x2 ≥ 95
x1 ≤ 40
x2 ≤ 30
x1 , x2 ≥ 0
RO - TD N°4. Dualité – Variables Artificielles Page 2 / 3
Université Ibn Zohr A.U : 2019 - 2020
Faculté des Sciences d’Agadir
Filière : SMI-5
Matière : Recherche Opérationnelle
1. Représenter graphiquement le problème en hachurant l’espace de solutions réalisables. Les
coordonnées des sommets doivent appartenir au schéma.
2. Pour utiliser l’algorithme de simplexe en deux phases :
2.1. Résoudre la phase 1 en indiquant à chaque itération la valeur de la fonction objectif ainsi
que les coordonnées relatives.
En déduire les coordonnées du lancement de la phase 2.
2.2. Résoudre la phase 2 en indiquant à chaque itération la valeur de la fonction objectif ainsi
que les coordonnées relatives.
2.3. En déduire la valeur optimale de la fonction objectif Z ainsi que les coordonnées relatives.
Exercice 8:
Résoudre les PLs suivants en utilisant la méthode de simplexe en 2 Phases :
Min z = 4x1 + x2
SC
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1, x2 ≥ 0
Max z = 9x1 + 2x2
SC
2x1 + x2 ≥ 5
x1 ≥ 1
x1 + x2 ≤ 2
x1, x2 ≥ 0
Max z = 5x1 + 7x2
SC
x1 + x2 ≥ 6
x1 ≥ 4
x2 ≤ 3
x1, x2 ≥ 0
RO - TD N°4. Dualité – Variables Artificielles Page 3 / 3
