Maths Graphes Noob .pdf


À propos / Télécharger Aperçu
Nom original: Maths-Graphes-Noob.pdf

Ce document au format PDF 1.4 a été généré par Writer / OpenOffice 4.1.3, et a été envoyé sur fichier-pdf.fr le 14/10/2017 à 19:59, depuis l'adresse IP 86.244.x.x. La présente page de téléchargement du fichier a été vue 383 fois.
Taille du document: 79 Ko (8 pages).
Confidentialité: fichier public


Aperçu du document


Martinet Rémi
Guérault Yanis
Niphon Killian
SIO 2
Exercice Graphes
La production de la web-série Noob souhaite produire un film. Ne disposant pas d'assez d'argent
pour faire un auto-investissement, elle souhaite donc faire un crownfunding afin de pouvoir se
financer. La production vous fourni une liste de tâches afin de réunir les fonds et réaliser le film et
vous demande de les éclaires sur le sujet.
Tâches à réaliser

Repère

Durée en mois

Tâches précédentes

Levée de fond

A

2

Répartition de l'argent
et envoi des cadeaux

B

1

A

Création des costumes

C

2

A

Créations des
accessoires

D

1

A

Tournage

E

6

B,C,D

Création des musiques

F

2

B

De-Rush

G

1

E

Montage

H

1

E,F

Post-prod

I

1

G

Mise en ligne

J

1

H,I

Promotion

K

3

J

1°) Déterminer le niveau de chacun des sommets du graphe
2°) Donner le tableau des successeurs
3°) Construire le graphe d'ordonnancement du projet (méthode MPM) et déterminer pour chaque
tâche les dates au plus tôt et au plus tard ainsi que leurs marges totales et libres.
4°) En déduire le chemin critique et la durée minimale de réalisation du projet.

Page 1/8

Correction
1°)
Niveau 0

A

Niveau 1

B,C,D

Niveau 2

E,F

Niveau 3

G,H

Niveau 4

I

Niveau 5

J

Niveau 6

K

2°)
Sommet

A

B

Successeur B,C,D E,F

C

D

E

F

G

H

I

J

K

E

E

G,H

H

I

J

J

K



4°) Le chemin critique est A-C-E-G-I-J-K.
La durée minimale du projet est donc de 16 jours.

Page 2/8

3°)

D
2 3
1 1 1

2

E

G

4 4 6 10 10
Début
0 0
0 0

0

A

2

0 0
0 0

C

2

0 0

2 2
0 0

1

F

6

0 0 1

B
2 3
1 0

1

6 5

J

K

Fin

11 11 1 12 12 1 13 13 3 16 16
H

3 9 2 10 11
2

I

1 1

0 0
1

0 0

0 0

0 0

Explications
1°) Dans un graphe sans circuit, le niveau d'un sommet x est la longueur du plus long chemin
d'extrémité x.
La détermination des niveaux se fait à partir du dictionnaire des précédents:
Niveau 0 :
Sommet

Tâches Prédécesseurs

A
B

A

C

A

D

A

E

B,C,D

F

B

G

E

H

E,F

I

G,H

J

H,I

K

J

Le niveau 0 est déterminer par les sommets
n'ayant pas de prédécesseurs
Ici l'on voit que le sommet A n'en as pas, cela
donne donc la première ligne de notre tableau.
(CF tableau niveau correction)

Niveau 1 :
Sommet

Prédécesseurs

A
B

A

C

A

D

A

E

B,C,D

F

B

G

E

H

E,F

I

G,H

J

H,I

K

J

Le niveau 1 est déterminer en enlevant dans les
prédécesseurs les sommets de niveau inférieur.
Ici lorsque l'on enlève le sommet A qui est le seul
sommet de niveau inférieur, on voit que B,C,D
sont de niveau 1, ce qui nous donne la deuxième
ligne du tableau.
(CF tableau niveau correction)

Niveau 2 :
Sommet

Prédécesseurs

A
B

A

C

A

D

A

E

B,C,D

F

B

G

E

H

E,F

I

G,H

J

H,I

K

J

Le niveau 2 est déterminer en enlevant dans les
prédécesseurs les sommets de niveau inférieur.
Ici lorsque l'on enlève les sommets B,C,D en plus
de A qui sont les sommets de niveau 1, ce qui
nous donne la troisième ligne du tableau.
(CF tableau niveau correction)

Niveau 3 :
Sommet

Prédécesseurs

A
B

A

C

A

D

A

E

B,C,D

F

B

G

E

H

E,F

I

G,H

J

H,I

K

J

Le niveau 3 est déterminer en enlevant dans les
prédécesseurs les sommets de niveau inférieur.
Ici lorsque l'on enlève les sommets E,F en plus de
ce de niveau 2,1 et 0, ce qui nous donne la
quatrième ligne du tableau.
(CF tableau niveau correction)

Niveau 4 :
Sommet

Prédécesseurs

A
B

A

C

A

D

A

E

B,C,D

F

B

G

E

H

E,F

I

G,H

J

H,I

K

J

Le niveau 4 est déterminer en enlevant dans les
prédécesseurs les sommets de niveau inférieur.
Ici lorsque l'on enlève les sommets G,H en plus de
ce de niveau 3,2,1 et 0, ce qui nous donne la
cinquième ligne du tableau.
(CF tableau niveau correction)

Niveau 5 :
Sommet

Prédécesseurs

A
B

A

C

A

D

A

E

B,C,D

F

B

G

E

H

E,F

I

G,H

J

H,I

K

J

Le niveau 5 est déterminer en enlevant dans les
prédécesseurs les sommets de niveau inférieur.
Ici lorsque l'on enlève le sommet I en plus de ce
de niveau 4,3,2,1 et 0, ce qui nous donne la
sixième ligne du tableau.
(CF tableau niveau correction)

Niveau 6:
Sommet

Prédécesseurs

A
B

A

C

A

D

A

E

B,C,D

F

B

G

E

H

E,F

I

G,H

J

H,I

K

J

Le niveau 6 est déterminer en enlevant dans les
prédécesseurs les sommets de niveau inférieur.
Ici lorsque l'on enlève le sommet J en plus de ce
de niveau 5,4,3,2,1 et 0, ce qui nous donne la
sixième ligne du tableau.
(CF tableau niveau correction)

2°) Afin de déterminer le tableau de successeurs. Pour chaque sommet on vérifie ou il est présent
dans les prédécesseurs, et on détermine ainsi avec sa présence ces successeurs. Les successeurs du
sommet X sont tous les sommets qui ont pour prédécesseurs X.

Sommet

Tâches Prédécesseurs

A
B

A

C

A

D

A

E

B,C,D

F

B

G

E

H

E,F

I

G,H

J

H,I

K

J

Exemple : Les successeurs du sommet A sont tous
les sommets qui ont pour prédécesseurs A.
Les successeurs de A sont donc B,C,D
Les successeurs du sommet B sont tous les
sommets qui ont pour prédécesseurs B, donc E et
F

3°) La marge totale d’une tâche est le retard maximum que l’on peut observer sur le démarrage de
cette tâche, sans retarder la fin du projet. Elle est définie par :
MT(J) = t(J)-T(j)
t(J) est la date au plus tard de la tâche J
T(J) est la date au plus tôt de la tâche J
La marge libre d’une tâche est le retard maximum que l’on peut observer sur le démarrage de cette
tâche, sans retarder le démarrage des tâches qui la suivent. Elle est définie par :
T(K)-T(J)-d(J)
K est une tâche succédant immédiatement à J
T(K) et T(J) sont les dates au plus tôt de chaque tâche
d(J) est la durée de la tâche J
Exemple avec la tâche F :
Marge totale : t(J)-T(j) = 9-3 = 6
Marge libre : T(K)-T(J)-d(J) = 10-3-2 = 5
4°) Le chemin critique est le chemin ou les tâches ont la tâche au plus tôt et la tâche au plus tard
identiques.
Le durée minimale est la tâche au plus tôt de la FIN.


Aperçu du document Maths-Graphes-Noob.pdf - page 1/8

 
Maths-Graphes-Noob.pdf - page 2/8
Maths-Graphes-Noob.pdf - page 3/8
Maths-Graphes-Noob.pdf - page 4/8
Maths-Graphes-Noob.pdf - page 5/8
Maths-Graphes-Noob.pdf - page 6/8
 




Télécharger le fichier (PDF)




Sur le même sujet..





Ce fichier a été mis en ligne par un utilisateur du site. Identifiant unique du document: 00550696.
⚠️  Signaler un contenu illicite
Pour plus d'informations sur notre politique de lutte contre la diffusion illicite de contenus protégés par droit d'auteur, consultez notre page dédiée.