Ecole Supérieur des Techniques Avancées Année 2022-2023

(E.S.T.A) SIR2

Travaux Dirigés de Recherche Opérationnelle

EXERCICE1
On se propose d’étudier la circulation d’informations professionnelles
entre les différents services, notés S1 , S2 , S3 , S4 , S5 , S6 et S7 , d’une même
entreprise.
n Le graphe G défini par :
G = (S1 , S2 ), (S7 , S1 ), (S2 , S3 ), (S7 , S2 ), (S3 , S4 ), (S7 , S3 ), (S4 , S5 ), (S7 , S4 ),
o
(S5 , S6 ), (S7 , S5 ), (S6 , S1 ), (S7 , S6 )
indique de quels services vers quels autres doivent circuler les informa-
tions. Ainsi la circulationd’informations est prévue du service Sa vers le
service Sb si le couple (Sa , Sb ) appartient à G.
1 Donner le dictionnaire des précédents et le dictionnaire des suivants de ce
graphe.
2 Peut-on ordonnancer ce graphe par niveau ? justifier la réponse.
3 Donner une représentation sagittale claire de ce graphe.

EXERCICE2
Un laboratoire de produits pharmaceutiques a obtenu l’autorisation de
mise sur le marché d’un nouveau médicament, qui sera commercialisé sous
deux formes :
• un sirop conditionné en flacon de 200 millilitres,
• des comprimés de 1,5 gramme chacun.
Le lancement de la fabrication nécessite un certain nombre d’opérations
préalables. Le tableau suivant donne la liste de ces opérations, ainsi que les
opérations antérieures et leurs durées en mois.

Opérations Opérations antérieures Durées

A D, F 4
B - 5
C A 1
D E 3
E - 3
F B 2
G D 5

1 Représenter cette succession de tâches par un graphe MPM et par un

graphe PERT.
2 a) Déterminer la durée minimale de réalisation de l’ensemble des opérations
b) Donner la tâche critique et le chemin critique.
c) Donner dans un tableau, les dates de début et de fin au plus tôt et
au plus tard de chaque opération, ainsi que les marges totales et les
marges libres.

EXERCICE3
Monsieur ZABRE, expert en multimédias, veut installer un atelier d’in-
formatique. Les tâches à réaliser pour son projet sont les suivantes :

T aches Code Duree en jours anterieur

Information des commerciaux A 20 -
Embauche d’un technicien B 30 -
Formation d’un technicien C 3 B
Formation des commerciaux D 10 A, C
Aménagement de la salle E 2 A
Commande et livraison des ordinateurs du mobilier F 5 E
Livraison des ordinateurs et des imprimantes G 1 F
Installation du matériel H 1 G, D
Installation des logiciels I 1 H
Tests et mise en route J 2 I

1 Modélisez par le réseau MPM le projet de Monsieur ZABRE.

2 Indiquez le délai minimum de mise en route du système.
3 Quel est le retard maximum que l’on peut admettre au démarrage de la
tâche A sans remettre en cause la date de début au plus tôt d’aucune
autre tâche ?
4 Construisez le réseau PERT qui modélise ce projet.
5 Le fournisseur du mobilier a en fait indiqué deux délais possibles selon
l’état des stocks à la commande : 5 jours si les meubles sont en magasin
et 25 jours si les meubles doivent être commandés. On suppose que les
meubles doivent être commandés. Déterminer la nouvelle durée du
projet en utilisant le réseau PERT construit à la question 4.

EXERCICE4
Partie A
Dans le cadre de son projet, la société Matinfo a procédé à la définition
d’un certain nombre de tâches à effectuer et à l’évaluation de leur durée.
Les conditions d’antériorité liant ces tâches, et les durées en semaines de
celles-ci, sont rassemblées dans le tableau ci-dessous :

2
 Tâches Tâches antérieures Durées
a - 10
b d 14
c b, h 14
d a 8
e a 12
f d 22
g f 25
h i 18
i d, e 6

1 Représenter cette succession de tâches par un graphe (PERT ou MPM).

2 Déterminer le chemin critique et préciser en quel nombre minimum de
semaines le projet pourra être réalisé.
3 Donner dans un tableau, pour chacune des tâches, les dates de début au
plus tôt et les dates de fin au plus tôt, ainsi que les dates de début au
plus tard et les dates de fin au plus tard.
On rapelle que :
date de fin au plus tôt = (date de début au plus tôt) + (durée de la tâche)
date de fin au plus tard = (date de début au plus tard) + (durée de la tâche)
Partie B
Si les durées des tâches a, b, c, d, e, h, i indiquées dans le tableau précédent
sont considérées comme certaines, celles des tâches f et g sont des durées
moyennes.
Soient Xf et Xg les variables aléatoires «durées respectives des tâches f et g».
On suppose que Xf et Xg sont des variables aléatoires continues indépendantes,
Xf suivant la loi normale de moyenne 22 et de variance 9, Xg la loi normale
de moyenne 25 et de variance 16.
1 Calculer la probabilité de réaliser la tâche g en plus de 30 semaines.
2 On note Y la variable aléatoire «somme des durées de f et g».
a) Quelle est la loi suivie par Y ? justifier.
b) Le projet est-il réalisable en 58 semaines ? justifier la réponse.
c) Déterminer la probabilité de réaliser le projet en 60 semaines au
plus.
On donne : Π(1, 25) = 0, 8944 et Π(1) = 0, 8413 où Π est la fonction de
répartition de la loi normale centrée et réduite.

EXERCICE5
A l’approche des fêtes de fin d’année, la pâtisserie du FASO décide de
confectionner des gâteaux au chocolat.
En allant inspecter ses réserves, le gérant de la pâtisserie constate qu’il lui

3
reste 18 kg de cacao, 8 kg de noisette et 14 kg de lait.
La pâtisserie propose deux spécialités : gâteau cérémonial et gâteau maison.
Un gâteau cérémonial nécessite 1 kg de cacao, 1 kg de noisette et 2 kg de
lait. Un gâteau maison nécessite 3 kg de cacao, 1 kg de noisette et 1 kg de
lait. Elle réalisera un profit de 20 FCFA en vendant un gâteau cérémonial
et de 30 FCFA en vendant un gâteau maison.
La pâtisserie désire déterminer la confection de gâteaux cérémonial et gâteaux
maison permettant de maximiser son profit.
On note x le nombre de gâteaux cérémonial et y le nombre de gâteaux
maison .
1 Ecrire la forme canonique du programme répondant à cet objectif.
2 Ecrire la forme standard du programme.
3 Déterminer par la méthode du simplexe, la production optimale. Inter-
preter ces résultats.

EXERCICE6
Un touriste désire se rendre de la ville A à la ville J. Les différentes étapes
et leurs distances en kilomètres sont données dans le tableau suivant :
Arrivée
A B C D E F G H I J
A 12 6
B 22
C 7 8
D 42
Départ E 12
F 6
G 15 14
H 7
I 17
J
1 Etablir le dictionnaire des précédents et déterminer les niveaux.
2 Tracer le graphe ordonné par niveau.
3 Le touriste est pressé, quel est le chemin le plus économique lui permettant
d’aller de A à J.
4 Le touriste a cette fois-ci le temps de visiter et veut connaı̂tre le chemin
le plus long pour aller de A à J. Quel est-il ?

EXERCICE7
La société Boly et frère fabrique deux produits P1 et P2 à partir de trois
matières premières A, B et C à raison de 3 kg de A, 3 kg de B et 7 kg de C

4
par unité de P1 fabriquée, et de 6 kg de A, 1 kg de B et 6 kg de C par unité
de P2 fabriquée.
Les disponibilités en matières premières sont limitées à 3000 kg de A, 1500
kg de B et 4200 kg de C. Le bénéfice net réalisé est de 30 FCFA par unité
de P1 et 50 FCFA par unité de P2 .
Travail à faire :
1 Donnez la formulation mathématique, sous forme canonique, du présent
programme linéaire ;
2 Déterminez graphiquement la production optimale ;
3 Quelle est l’interprétation économique de ces résultats ?
4 Écrivez le programme primal sous forme standard ;
5 Le passage de la forme canonique à la forme standard se fait par l’ajout des
variables d’écart. Quelle est l’interprétation économique de chacune
d’entres elles ?
6 Retrouvez la production optimale via l’algorithme de simplexe.

EXERCICE8

La production de cette société doit être acheminée vers la ville H d’un

pays en voie d’émergence. Le réseau de transport des produits entre
les villes de ce pays est représenté par le graphe G = (X, U ) suivant :
X = {A, B, C, D, E, F, G, H}
U = {(A, D); (A, G); (B, A); (B, C); (C, A); (C, D); (D, E); (D, F ); (D, H) ;
(E, H); (F, H); (G, E)}
Les prix (en euros) pratiqués par les transporteurs entre les villes sont
donnés par le tableau suivant :
Liaisons (A, D) (A, G) (B, A) (B, C) (C, A) (C, D)
Prix 28 35 55 25 25 50
Liaisons (D, E) (D, F) (D, H) (E, H) (F, H) (G, E)
Prix 20 25 30 20 15 10
Déterminer la solution la plus économique pour aller de la ville B à la
ville H.

EXERCICE9

La construction d’un entrepôt se décompose en 9 tâches reliées entre

elles par des contraintes d’antériorité. Le dictionnaire des précédents
est communiqué :
Code tâche A B C D E F G H I
Durée en semaines 2 2 6 5 2 3 6 2 2
tâches Antérieures - A A B, C D D D E, G E

5
1 Déterminer les niveaux.
2 Représenter cette succession de tâches par un graphe MPM. Indi-
quer le chemin critique. Vérifier.
3 Représenter cette succession de tâches par un graphe PERT. Indi-
quer le chemin critique. Vérifier.
4 Calculer les marges totales et les marges libres.

EXERCICE10
Soit le problème d’ordonnancement suivant :

Code tâche A B C D E F G H I J
Durée en jours 4 2 1 1 2 2 2 10 4 1
tâches Antérieures - - A A, B A B, C D, F E G H, I
Construire le grahe MPM et le grahe PERT relatif à ce projet.

EXERCICE11
La réalisation d’un projet nécessite l’exécution de 9 tâches dont les
durées ainsi que les contraintes d’antériorités sont résumées dans le
tableau suivant :
tâches A B C D E F G H I
tâches Antérieures - A A A B C C, E D B, H
Durée en semaines 1 2 5 4 3 1 2 1 3
I. Approche «potentiel-tâche» ou méthode MPM
1 Tracer le graphe MPM de cet ordonnancement, sur lequel on fera
apparaitre le calendrier d’exécution (date de début au plus tôt et
au plus tard) des différentes tâches.
2 Quel est le chemin critique ? Quelle est sa durée ? Quelle est la si-
gnification de cette durée ?
3 Calculer le retard maximum que l’on peut admettre au démarrage
de la tâche B sans remettre en cause les dates de début au plus
tôt d’aucune autre tâche.
4 Est-il possible sans augmenter la durée totale d’exécution des tra-
vaux, d’exécuter la tâche C en 6 semaines et la tâche G en 3
semaines.
II. Approche «potentiel-étapes» ou méthode PERT
1 Tracer le réseau PERT associé à cet ordonnancement.
2 Quel est le nombre d’étapes de ce projet ?
3 À la suite d’un changement d’équipe, la durée de la tâche G est
devenue inconnue noté x. Déterminer la valeur maximale de x
qui ne retardera pas la fin du projet prévue dans 9 semaines.

6
EXERCICE12

La société DEMO SA veut lancer une nouvelle gamme de crêmes fa-

briquées à partir de deux matières premières : la lanoline et la glycérine.
Ces matières premières sont fournies à la société par trois fornisseurs.
Pour des raisons techniques, chaque fournisseur propose un lot de deux
pots indissociables : un pot de lanoline et un pot de glycérine. Les
offres des différents fournisseurs se distinguent par les poids respectifs
des deux pots et par le prix du lot.
Les livraisons auront lieu systématiquement au début de chaque cycle
de fabrication. Tout cycle de fabrication nécessite au moins 120 g de la-
noline et au moins 90 g de glycérine. Trois fournisseurs sont pressentis
pour livrer ces matières. Voici les propositions :

Fournisseurs Prix d’achat du Pot de lanoline Pot de glycérine

lot de deux pots
Fournisseur 1 120 6g 2g
Fournisseur 2 132 6g 4g
Fournisseur 3 60 2g 2g
On veut calculer le nombre de lots qu’il faut acheter à chaque fournis-
seur pour minimiser le coût d’approvisionnement (CA).
1 Ecrire la forme canonique du programme (P) répondant à cet ob-
jectif.
2 Ecrire le programme dual (D), en prenant W comme la fonction
économique, u et v comme variables.
3 Déterminer la solution optimale du primal, en sachant que celle du
dual est : u = 6 ; v = 24.
4 En déduire le nombre de lots qu’il faut acheter à fournisseur et le
coût minimum d’approvisionnement.