Théorie des graphes : Exercice graphe tramway casa
Télécharger PDFEcole Nationale des Sciences Appliqu ́
ees de F` es
M09: Th ́eorie des graphes
G.Inf.1&G.S.E.II.1
TD 2
Exercice 1L’inauguration du nouveau tramway de Casa ́etait pr ́evue le 1 juillet 2019. On suppose qu’au
cours de l’ann ́ee 2018 la Communaut ́e Urbaine de Casa a lanc ́e un appel d’offres pour des
travaux pr ́evus en 2019. Suite `a cet appel d’offres, neuf entreprises d ́esign ́ees par les lettres
A,B,C, etc., ont ́et ́e retenues. Le tableau suivant indique les ant ́eriorit ́es pour les diff ́erents
travaux `a effectuer ainsi que leur dur ́ee, exprim ́ee en semaines.
Code des entreprisesAnt ́eriorit ́esDur ́ee(en semaines)A5 BA4CA6 DB3
EB - C2FC4 HD - E8
KE - F5
NH - K4
1. D ́eterminer le niveau des onze sommets du grapheG.
2. Construire le grapheGen ordonnant les sommets par niveau croissant.
3. (a) Calculer, en appliquant l’algorithme de Ford, les dates de d ́ebut au plus tˆot pour
chaque entreprise.
(b) D ́eterminer le chemin de poids maximal entred(d ́ebut) etf(fin) et en d ́eduire le
chemin critique.
4. L’entrepriseAa commenc ́e `a travailler le mardi 1 janvier 2019. Si tout se passe bien,
l’inauguration pourra-t-elle avoir lieu comme pr ́evu ?
5. L’entrepriseE, suite `a un incident impr ́evu, a mis trois semaines pour effectuer son travail.
L’inauguration a-t-elle pu avoir lieu le lundi 1 juillet 2019?
Exercice 2Un projet informatique a ́et ́e d ́ecoup ́e en 8 sous-programmes A, B, C, D, E, F, G, H tel que
chaque sous-programme est assign ́e `a un d ́eveloppeur. Les contraintes de precedence et les
dur ́ees de d ́eveloppement de ces sous-programmes sont donn ́ees dans le tableau suivant
sous-programmedur ́eesous-programmes pr ́ec ́edentsA6 B5
C7A, BD4C E14B
F4D, EG7A H7D, G
S. ELHAJ-BEN-ALI12019-2020 ́
Ecole Nationale des Sciences Appliqu ́
ees de F` es
M09: Th ́eorie des graphes
G.Inf.1&G.S.E.II.1
1. Mod ́elisez ce projet par un graphe.
2. D ́eterminez la dur ́ee minimale du projet, les dates au plus tˆot, dates au plus tard des
diff ́erents sous-programmes.
3. Quels sont les ”sous-programmes” critiques?
4. Le d ́eveloppeur en charge du sous-programme G est indisponible; celui en charge du
sous-programme C prend alors son travail `a la suite du sien. Quelle sera alors la dur ́ee
minimale du projet? Les sous-programmes critiques sont-ils les mˆemes?
Exercice 3Une entreprise d ́ecide de commercialiser un nouveau produit. La planification de ce lancement
fait apparaˆıtre les tˆaches reprises au tableau ci-dessous avec leur dur ́ee (en semaines) et leurs
pr ́ealables.N ◦
TˆacheDur ́eeTˆaches pr ́ealables
AS ́election des ́equipements1-
BChoix de la m ́ethode de production2A
CProc ́edures de contrˆole de qualit ́e2B
DChoix des mati`eres premi`eres2A
ER ́eception des ́equipements7A
FCommande des mati`eres premi`eres1D
GR ́eception des mati`eres premi`eres3F
HEssais de production2E, C et G
IPremi`ere fourniture aux magasins6H et K
JConception du conditionnement4A
KProduction du conditionnement5J
LR ́eunion des vendeurs1K
MFormation des vendeurs1L
1. Tracer le graphe correspondant `a la m ́ethode PERT.
2. Calculez les dates de d ́ebut au plus tˆot, au plus tard, les marges et le chemin critique.
3. L’entreprise voudrait r ́eduire la dur ́ee totale d’ex ́ecution des travaux. Pour cela, il est
possible de r ́eduire la dur ́ee des tˆaches 5 et 11 d’une ou deux semaines au prix d’un coˆut
suppl ́ementaire de 100 000,00 DH par semaine de r ́eduction pour la tˆache 5 et de 200000
DH par semaine pour la tˆache 11. De combien peut-on r ́eduire la dur ́ee totale des travaux
et `a quel coˆut ?
S. ELHAJ-BEN-ALI22019-2020