Examen d’Optimisation Linéaire

Durée de l’interrogation : 1 Heure et 30 minutes

Documentation : Non autorisée
Calculatrice : Autorisée
Téléphone, Ordinateur : Non autorisés

Exercice N ◦ 1 : 8points = 1 + 2 + 2 + 1 + 2
L’entreprise HAMMOUD Boualam produit trois types de Boissons, Type A, Type B, Type
C. Les prix de vente, les quantités requises de concentré de jus et d’arômes ainsi que le nombre
d’heures de fabrication sont différents pour chaque type et sont résumés dans le tableau suivant :

Type A Type B Type C

Temps de Fabrication [min] 4 2 12
Quantité de Concentré de Jus [ml] 100 150 100
Quantité d’Arômes [g] 20 10 40
Prix de vente [DZD] 48 36 90

Pour sa fabrication hebdomadaire, l’entreprise dispose de :

- 3000 minutes de travail
- 100 Litres de concentré de jus
- 12 kg d’arômes.
Questions :
1. Formuler un programme linéaire aidant la fabrique à déterminer une production maximi-
sant son chiffre d’affaires.
2. Donner le programme linéaire dual du problème précédent.
3. Résoudre le programme primal.
4. Donner la solution optimale du programme dual.
5. Si la fabrique pouvait augmenter la quantité de ressources en concentré de jus ou en arôme,
dans laquelle de ces deux ressources serait-il conseillé d’investir en premier ? (Justifiez
votre réponse).

1
Exercice N ◦ 2 : 8points = 2 + 2 + 2 + 2
Soit le programme linéaire :



 2x1 + 3x2 = Z(M ax)
 x1 + x2 ≥ −5


(P ) : −6x1 + 7x2 ≤4
x1 + x2 = 10




x1 ≥ 0, x2 ∈ <.


1. Mettre le programme linéaire sous forme canonique.

2. Mettre le programme linéaire sous forme standard.
3. Déterminer le problème dual de (P ).
4. Résoudre Graphiquement le problème (P )

Exercice N ◦ 3 : 4points = 1 + 1 + 1 + 1
Pour chacun des tableaux de simplexe suivants : (Les tableaux sont indépendants entres
eux, justifiez toutes vos réponses)
base x1 x2 x3 x4 x5 x6 b base x1 x2 x3 x4 x5 x6 b
x6 1 0 -3 -1 0 1 -1 x6 0 0 -6 − 23 1 1 2
1
T ab1 : x5 -1 0 -2 2 1 0 − 2 T ab2 : x1 1 0 4 0 1 0 3
x2 4 1 1 -4 0 0 0 x3 0 1 2 -3 -2 0 1
3
-Z -3 0 -6 0 0 0 -9 -Z 0 0 0 2 − 2 0 -12

base x1 x2 x3 x4 x5 x6 b base x1 x2 x3 x4 x5 x6 b
3
x1 1 3 2 0 1 0 2 x2 1 1 2
3 0 0 -2
1 1
T ab3 : x4 0 4 3
1 1 0 3 T ab4 : x5 2
0 1 1 1 0 3
3 3
x6 0 2 2 0 2 1 1 x6 2
0 3 2
0 1 -1
-Z 0 -1 − 23 0 − 23 0 -8 −Z -1 0 -2 -1 0 0 -5

ö Déterminer si le tableau est : Réalisable, Optimal, Non-borné, Dégénéré.

Bon courage !