Contrôle : Recherche Opérationnelle (14 Décembre 2022). Durée : 02h00. 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).
Une petite entreprise fabrique 2 types de crème glacée C1 et C2, en quantités respectives x1 et x2 , en utilisant
trois matières de base : cacao, lait et sucre. Les crèmes glacées C1 et C2 rapportent respectivement un profit unitaire
de 12$ et 20$. Le programme linéaire (PL) qui modélise ce problème est donné par :
max z = 12x1 + 20x2
 (.....; .....), (.....; .....)

 (1x 1 + 3x 2 ) ≤ 18 (Cacao ) (.....; .....), (.....; .....)
2x1 + 1x2 ≤ 14 (Lait ) (.....; .....), (.....; .....)

s.c

 2x 1 + 2x 2 ≤ 16 (Sucre ) (.....; .....), (.....; .....)
x1 , x2 ≥ 0


1. Que représente (1x1 + 3x2 ) qui figure(en gras) dans la contrainte 1 ?

.........................................................................................................
.........................................................................................................
2. a. Résoudre graphiquement ce programme linéaire.
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 sommets réalisables ? Vérifier que le point (4.8; 4.4) est un sommet non réalisable ?

.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
...............................................................................................................
...............................................................................................................
...............................................................................................................
...............................................................................................................
...............................................................................................................
...............................................................................................................
3. Quelles seraient les conséquences sur la solution optimale et sur la valeur de la fonction objectif si le profit
unitaire du produit C2 diminuait de 6$ ? Donner cette solution et la veleur de l’objectif ?

1
 ......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
4. L’entreprise a décidé de revendre 2 litres de lait en stock pour une autre entreprise. Dans ce cas, la solution
optimale changera-t-elle ? Le profit total diminuera-t-il ? discutez.
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
5. Ecrire le dual de ce problème. Déduire la valeur optimale des variables duales(en utilisant les règles de complé-
mentarité).
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................

Exercice 2 (8 points).

Une boulangerie industrielle produit du pain, de la max

 z = 4x1 + 6x2 + 10x3
brioche et des croissants en quantités respectives 
 2x1 + 2x2 + 4x3 ≤ 160
x1 , x2 , x3 . Pour cela, elle utilise trois matières de 2x1 + 1x2 + 4x3 ≤ 140

s.c
base M1, M2 et M3. Le programme linéaire (P) 
 1x1 + 2x2 + 2x3 ≤ 120
qui modélise ce problème est donné par : x1 , x2 , x3 ≥ 0


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 ?
b. Quelle condition doit-on imposer pour avoir l’équivalene entre la forme canonique et la forme standard ?
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
2. Après quelques itérations de l’algorithme du simplexe , on arrive au tableau du simplexe suivant :

............. ............. ............. ............. ............. ............. ............. ............. ............. .............
B z x1 x2 x3 s1 s2 s3 bi
x2 0 0 1 0 -1/2 0 1 40
x3 0 1/2 0 1 1/2 0 -1/2 20
s2 0 0 0 0 -3/2 1 1 20
z -1 -1 0 0 -2 0 -1 -440

a. Dites pourquoi le tableau ci-dessus est optimal ? Quelle est la solution optimale ? Quel est le profit maximal ?
b. Indiquer les ressources qui sont complètement utilisées et celles qui ne le sont pas ?
c. Quelle est l’activité la plus rentable ? expliquer
d. Existe-elle une autre alternative (solution optimale) pour la boulangerie ? Justifier

2
 ......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
3. - Quelle est l’utilité de la dualité en programmation linéaire ?
- Sans calculs, donner les valeurs des variables duales (yi ) et la valeur de l’objectif du programme dual (Wmin ) ?
- La boulangerie veut élargir ses activités. Dans ce cas, interpréter les valeurs des variables duales ?
- Expliquer les valeurs obtenues de y2 , x1 et e1 (surplus) ?

......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
4. Dans quel intervalle la solution primale reste-t-elle optimale si on fait varier le coefficient c3 de x3 dans l’objectif
(Z = 4x1 + c2 x2 + 10x3 ) ? Si le profit unitaire de l’activité 3 devient c2 = 8 , quelle sera l’impact sur la solution
optimale du problème et sur le profit total ?
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
5. a. Supposons que la société ajoute 10 unités supplémentaires de M3. Quel est le nouveau profit ?
b. Est-ce que la solution optimale du primal changerait ? Justifier.
c. Si oui, retrouver la nouvelle solution optimale ?
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................

3
Exercice 3 (4 points).
EcoCity étudie la possibilité d’introduire un système de bus pour le transport en commun qui atténuerait le
problème du smog en réduisant la conduite de voiture en ville. Le programme de EcoCity vise à trouver le nombre
minimal d’autobus pouvant répondre aux besoins de transport. Après avoir recueilli les informations nécessaires,
l’ingénieur de la ville a constaté que le nombre minimum d’autobus requis fluctuait en fonction de l’heure du jour
et que le nombre exigé d’autobus pouvait être approché par des nombres constants sur des périodes de 4 heures. La
figure suivante résume les conclusions de l’ingénieur.

Pour effectuer la maintenance quotidienne requise, chaque bus ne peut fonctionner que 8 heures consécutives
ou 12 heures consécutives. Si un bus circule pendant 12 heures consécutives, le conducteur doit être payé pour
les heures supplémentaires à 150 % du salaire horaire normal. Déterminez le nombre de bus en service dans chaque
équipe qui répondra à la demande minimale tout en minimisant le nombre total de bus en service.
Formuler le problème par un programme linéaire ?
Indication : xi est le nombre de bus (circulant 8 heures consécutives) qui commencent au début du période i
yi est le nombre de bus (circulant 12 heures consécutives) qui commencent au début du période i.
debut du période=(12 :01A.M, 4 :01A.M, 8 :01A.M, 12 :01P.M, 4 :01P.M, 8 :01P.M)
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................