statistiques, algorithme de Fulkerson, diagramme de PERT
Ce document contient 2 exercices corrigés de niveau licence sur l'élaboration de statistiques.
[...] Techniques statistiques et applications Exercice 1 Pour représenter la situation par un graphe, on doit définir un début et une fin puis relié les tâches selon leur(s) dépendance(s). Ici, on va pourvoir commencer par les tâches A et B que ne nécessitent pas de sous programmes préalables. Le graphe se lit de gauche à droite et le chiffre indique la durée de réalisation de la tâche d'où provient le trait (avec des flèches, cela est peut-être plus lisible). Ce graphe est dit graphe potentiel (on aurait aussi pu représenter sous la forme d'un graphe PERT). [...]
[...] Pour ne pas avoir plus de flot que la capacité, il faut donc prendre le minium soit 1 ce qui donne un flot entre A et F est donc de 10. On ne peut plus trouver de chaîne améliorante car peut importe le chemin emprunté, on doit passer entre C et E ou entre D et F et aucune de ses routes n'a plus de capacité disponible (différence entre le flot et la capacité maximale). On a ainsi trouvé un flot maximal de 10 entre A et F. [...]
[...] Le même cheminement donne pour respectivement D et F les dates au plus tôt à 17 et 19 unités de temps. Pour ce qui est des dates au plus tard, cela revient à partir de la fin du projet et à remonter l'arbre en sens inverse. On trouve alors cette date en prenant le chemin de durée maximale (car il faut aussi avoir le temps d'exécuter la tâches suivantes). Sachant que le temps total est de 24 unités de temps, on trouve immédiatement les dates au plus tard de H et F à 17 et 20 unités de temps. [...]
[...] Pour les nœuds composant le chemin, si on a un flot égal à la capacité maximale de chaque chemin, on a ceci : noeuds BCDEayant départs 42+4+2=865+2=7 et arrivées 3+2=574+2+2=84 Pour C et E on a bien départ>=arrivées mais pas pour B et D. Mettons alors en œuvre l'algorithme de Ford Fulkerson, on note en rouge les flots initialement nuls : Considérons alors par exemple le chemin F. Le potentiel d'augmentation du flot partant de A est de celui de C de 4 et celui de E de 5. Pour ne pas avoir plus de flot que la capacité, il faut donc prendre le minium soit 4 ce qui donne un flot entre A et F est donc de 4. [...]
[...] Ainsi, les sous programmes critiques sont le D et H. La contrainte de l'énoncé revient à considérer que C devient un sous-programme nécessaire au commencement de G ce qui donne un nouveau graphe : On va une nouvelle fois comparer les différents trajets possibles soit : AGHACGHACDHACDFBCGHBCDHBCDFBEF il n'y a que 2 chemin nouveaux les durées sont respectivement 6+7+7+7=275+7+7+7=26 Ainsi, la nouvelle durée minimale du projet est de 27 unités de temps et les sous programmes critiques ont changés et sont maintenant G et G. [...]
Source aux normes APA
Pour votre bibliographieLecture en ligne
avec notre liseuse dédiée !Contenu vérifié
par notre comité de lecture