Contrôle : Recherche Opérationnelle. Durée : 01h40. Professeur : A.

El Maliki

Nom et Prénom :. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

L’usage de tout document et du téléphone portable est rigoureusement interdit.

Exercice 1 (8 points).
Soit le programme linéaire (PL) suivant, qui modélise la fabrication des pièces détachées P1 et P2 , en quantités
respectives x1 et x2 , dans trois ateliers F, M et T.
max
 Z = 50x1 + 40x2 (Profits)

 1x1 + 1x2 ≤ 7 (nombre d’heures dans l’atelier F)
2x1 + 1x2 ≤ 12 (nombre d’heures dans l’atelier M)

(P.L) s.c

 1x1 + 3x2 ≤ 15 (nombre d’heures dans l’atelier T)
x1 , x2 ≥ 0


1. Donner la signification des nombres 50 et 15 qui figurent dans le programme linéaire (PL) ?
.........................................................................................................
.........................................................................................................
.........................................................................................................
.........................................................................................................
2. a. Résoudre graphiquement ce problème (Expliquer vos démarches).
b. Donner la solution optimale et le profit maximal.
c. À l’optimum, quelles sont les ressources qui sont complètement utilisées et celles qui ne le sont pas ?
d. Combien y a-t-il de points extrêmes (sommets) dans la région admissible ? Indiquer-les sur le graphique
par des lettres capitales (O, A, ...).

.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................
.........................................................................................................
.........................................................................................................
.........................................................................................................
.........................................................................................................
.........................................................................................................
.........................................................................................................
.........................................................................................................
.........................................................................................................

1
 3. Quelles seraient les conséquences sur la valeur de la fonction objectif et sur la solution optimale si le profit
unitaire du produit P2 diminuait de 5$ ?
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................

4. Si on ajoutait la contrainte (x1 ≤ 4) au modèle initial. Quel serait l’impact sur la région admissible et sur
la valeur de la solution optimale et la valeur du profit maximal (donner ces valeurs).
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................

Exercice 2 (8 points).

Considérer le programme linéaire suivant (P) repré-

max z= 6x1 + 5x2 + 8x3
sentant le problème d’une entreprise produisant des
3x1 + x2 + 2x3 ≤ 64 (main d’oeuvre)
meubles de trois types : bibliothèques (en quantité


x1 + x2 + x3 ≤ 20 (métal)

x1 ), bureaux (en nombre x2 ) et chaises (en quantité s.c
x1 + 2x2 + 3x3 ≤ 30 (bois)
x3 ). Trois ressources sont utilisées : la main d’oeuvre,


x1 , x2 , x3 ≥ 0

le métal et le bois.
On désigne par s1 , s2 , s3 les variables d’écart des trois contraintes de (P).
1. a. Quelle est l’utilité de la forme standard d’un programme linéaire ?
b. Expliquer brièvement comment on obtiendra le second tableau du simplexe à partir du premier tableau
(sans aucun calcul, ne pas dessiner ces tableaux) ?
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................

2. Après quelques itérations de l’algorithme du simplexe , on arrive au tableau du simplexe suivant :

a. Quelle est la solution optimale ? Quel est le profit maximal ? B z x1 x2 x3 s1 s2 s3 bi

b. Indiquer les ressources qui sont complètement utilisées ? s1 0 0 - 32 0 1 - 27 1
2 9
1 3
c. Quelle est l’activité non rentable ? Quel profit faut-il exiger x 1 0 1 2 0 0 2 - 21 15
1
pour la rendre rentable ? x3 0 0 2 1 0 - 21 1
2 5
d. La solution optimale trouvée est-elle unique ? Justifier. z -1 0 -2 0 0 -5 -1 -130

2
 ......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
3. - Écrire le dual (D) du primal (P) ? - Donner et interpréter les valeurs des variables duales ?
- Donner et interpréter la valeur de l’objectif du programme dual Wmin .
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
4. Afin d’augmenter son produit, la société voudrait augmenter dans la quantité d’une ressource. Pour quelle
ressource investiriez-vous en premier ? Justifier.
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
5. a. Montrer que la solution optimale de (P) ne changera pas si on remplace la fonction objectif par
Z = 4x1 + 5x2 + 8x3 ? Dans ce cas, donner le nouveau profit maximal ?
b. Est-ce que les prix optimaux des trois ressources changeront ? Justifier.
c. Si la réponse est oui, calculer ces nouveaux prix ?
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................

3
Exercice 3 (4 points).
L’entreprise DR fabrique des bicyclettes pour enfants. Les prévisions de ventes en milliers d’unités pour l’année
à venir sont données dans le tableau 3. La capacité de production de l’entreprise est de 30 000 bicyclettes par mois.
Elle peut produire davantage en demandant à ses employés de travailler en heures supplémentaires. Mais le coût
de revient d’une bicyclette est alors plus élevé : 160$ par unité au lieu de 130$.

Tableau 3. : Prévisions de ventes pour l’année à venir en milliers d’unités

Janvier Février Mars Avril Mai Juin Juillet Août Septembre Octobre Novembre Décembre
30 15 15 25 33 40 45 45 26 14 25 30

- Actuellement, il y a 2000 bicyclettes en stock.

- On peut calculer les coûts de stockage en considérant une valeur de 20$ par unité contenue dans le stock en fin
de mois.
- On considère que les capacités de stockage sont virtuellement illimités : ceci signifie que la capacité réelle, bien
qu’évidemment, n’est pas limitante ici.
Nous sommes le premier janvier. Quelles quantités doivent être fabriquées et stockées dans les douze prochains
mois, pour respecter les demandes prévisionnelles tout en minimisant les coûts ?
Formuler le problème par un programme linéaire ?
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................