Département d’informatique 3ième Année LMD 22 Mars 2021
Documents et téléphones portables non autorisés Durée : 1 Heure 10 mn
Nom : …………………………………………………………………………….. Groupe :…………
Prénom : ……………………………..………………………………………..
EMD Programmation linéaire
Exercice 1 (8 pts) : Un grossiste doit livrer 24 unités d’un produit déterminé P à 3 détaillants D1 , D2 et D3
tout en respectant les contraintes de marché suivantes :
1-La quantité de P livrée à chacun des détaillants D2 et D3 n’excède pas 9 unités.
2-La quantité de P livrée au détaillant D1 doit être au moins égale à deux fois la quantité expédiée au
détaillant D2 augmentée de 6 unités.
3-Les couts de livraison d’une unité de P s’élèvent à 4000 DA pour D1, 2000 DA pour D2 et 3000 DA pour
D3. Dans ces conditions, le grossiste cherchera les quantités qu’il doit envoyer à chacun des détaillants tout
en précisant son objectif.
1/ Ecrire le programme linéaire modélisant ce problème.
Modélisation :
2/ Ecrire le dual du programme linéaire suivant :
Max Z = x1 + 2x2
Sc x1 + x2 – x3 ≤ 3 Dual
2x1 + 3x2 + 5x3 = 6
x1 ≥ 0 , x2 ϵ R , x3 ≥ 0
Exercice 2 (12pts) : On considère le programme linéaire suivant :
Max Z = 3x1 + 2x2
Sc x1 + x2 ≤ 12
x1 - 6x2 ≤ 6
x2 ≤ 10
x1 ≥ 0 , x2 ≥ 0
-Résoudre ce programme linéaire en utilisant la méthode graphique puis confirmer le résultat obtenu par
la méthode du simplexe tableaux.
Résolution graphique :
Partie calculs
X2
O 1 2 3 4 5 6 7 8 9 10 …… …… X1
Solution optimale :
Confirmation du résultat obtenu par la méthode du simplexe tableaux :
Tableau initial (du programme linéaire sous la forme standard)
Tableau initial Tableau n°….
Cj 3 2 0 0 0 b cj 3 2 0 0 0 b
Xj X1 X2 X3 X4 X5 Xj X1 X2 X3 X4 X5
CB XB CB XB
0 x3 1 1 1 0 0 12
0 x4 1 -6 0 1 0 6
0 x5 0 1 0 0 1 10
Zj - Cj Z= Zj - Cj Z=
Tableau n°…. Tableau n°….
Cj 3 2 0 0 0 b cj 3 2 0 0 0 b
Xj X1 X2 X3 X4 X5 Xj X1 X2 X3 X4 X5
CB XB CB XB
Zj - Cj Z= Zj - Cj Z=
