Ecole Mohammadia d’Ingénieurs Lundi 4 février 20081ère AnnéeContrôle de recherche opérationnelleDurée : Une heure et demie Documents non autorisésExercice 1: La société EVENEMENT SPORTIF S.A. souhaite lancer une nouvelle course cycliste. Elle choisit de gérer la mise au point et le lancement de celle-ci sous la forme d’un projet. Elle a donc recensé les tâches nécessaires pour mener à bien les diverses actions à réaliser. Puis elle a évalué les délais nécessaires à la réalisation de chaque tâche. L’ensemble de ces informations est synthétisé dans le tableau ci-dessous : 

N° tâche Nom tâcheDurée

(en jours)Prédécesseurs

1 Choix du lieu et de la date de la course 1  2 Obtention des autorisations nécessaires 20 13 Engagements des sponsors 12 14 Création des différents formulaires 15 35 Commande des maillots 9 36 Recrutement des bénévoles nécessaires 3 3 , 57 Inscription des participants 25 4 , 2 , 68 Numérotation des dossards 4 79 Réalisation du parcours et de la course 5 810 Aménagement des zones de départ et d’arrivée 5 811 Remise des prix 1 9 , 1012 Nettoyage du site 3 1113 Clôture de la course 1 12

 1/ Représenter le réseau potentiels-tâches correspondant à ce problème d’ordonnancement, déterminer la durée minimum du projet et donner un calendrier d’exécution des tâches qui permette de minimiser la durée du projet. Quelles sont les marges des tâches?2/ Donner un réseau PERT aussi compact que possible et donner une interprétation des différents sommets. Que se passe-t-il (au niveau de la durée minimum du projet) si la durée de la tâche 10 passe à 6 jours au lieu de 5? Même question si la durée de la tâche 10 passe de 5 à 4 jours.

Exercice 2: On désire installer au moindre coût un réseau de communication entre divers sites. Les coûts de connections inter-sites sont donnés dans le tableau symétrique ci-dessous (où seule la partie triangulaire inférieure est remplie)

1. Quel est le modèle vu en classe auquel s'apparente ce problème?2. Déterminer une solution optimale.

Exercice 3 : Pour cet exercice, dans le cas où vous ne trouvez pas la réponse à la question 1., vous pouvez passer à la question 2. en considérant le réseau obtenu en remplaçant chaque arête par deux arcs opposés, en prenant comme poids sur les arcs le temps nécessaire à l'envoi d'un paquet sur le lien correspondant à cet arc et en supprimant les nombres portés en regard des sommets La figure ci-dessous représente une proposition de réseau informatique destiné à connecter plusieurs ordinateurs sur un campus. Chaque sommet correspond à un ordinateur et chaque arête e représente un câble en fibre optique reliant les ordinateurs correspondant aux extrémités de e.

Le designer veut à présent déterminer comment router les e-mails du sommet 1 (qui est la passerelle internet) aux autres sommets et vice-versa. Par exemple un e-mail destiné au sommet 4 peut être transmis par 1 à 6, ensuite répété par 6 pour 5 et enfin répété par 5 pour 6. L'objectif du designer est bien entendu de déterminer un routage des e-mails de manière à minimiser le temps de transmission à partir du sommet 1 et vers le sommet 1. Le nombre porté en regard d'un sommet représente le temps minimum (en nanosecondes) requis par l'ordinateur correspondant pour transmettre ou recevoir un message. Le temps nécessaire à l'envoi d'un paquet sur un lien est égal au maximum des temps nécessaires aux deux ordinateurs associés aux extrémités de ce lien.

1. Montrer que le problème du designer se ramène à un problème de plus court chemin dans un graphe que l'on précisera (sommets, arcs, poids sur les arcs).

2. Appliquer l'algorithme de Djikstra pour résoudre le problème.

Exercice 4: Le réseau ci-dessous permet d'aller de s à t. Déterminer le nombre minimum de liaisons défectueuses susceptible d'isoler s de t.

1

2 37

4 9

10856

3

11

6 305

18 23

25148