Ecole Nationale des Sciences de l'Informatique
Examen de Recherche Opérationnelle
Classe: Ill Date: Juin 2004
Documents: Autorisés Durée: 2H
Enseignants: N.Chaouachi; N.Elloumi;L.Horchani Nbre de pages : 3
EXERCICE1:(3 pts)
I- Algorithme de construction de la composante connexe:
(i) Marquer + le sommet x
(ii) Marquer +, tout sommet adjacent â un sommet marqué + Jusqu'à ce qu'on ne puisse plus marquer de sommets .
Les sommets marqués sont ceux de la composante connexe de x
II- Algorithme de -construction de la composante fortement connexe:
(i) Marquer + et - le sommet x
(ii) Marquer - tout sommet précédent d'un sommet marqué - ; Marquer + tout sommet suivant d'un sommet marqué + Jusqu'à ce qu'on ne puisse Plus marquer de sommets.
1. Ce graphe est-il connexe; Justifier.
2. Déterminer la composante fortement connexe du sommet 2. 3. Ce graphe est-il fortement connexe ; Justifier.
EXERCICE 2 :(6 pts)
Un professeur habite â HomeCity et enseigne â UniverCity . II effectue donc l'aller et le retour chaque jour en voiture. Ayant énormément de peine â se lever, il aimerait trouver le chemin lui permettant de repousser le plus tard possible l'heure de son départ tout en arrivant au travail à 8h00. Voici le réseau des routes qu'il peut emprunter pour se rendre de HomeCity â. UniverCity.
Les sommets représentent les carrefours, les arcs les rues â sens unique et les arêtes les rues â double sens. Les valeurs â côté des arcs et des arêtes représentent le temps de parcours nécessaire en minutes pour rejoindre deux carrefours dans un sens ou dans l'autre (s'il est permis). De plus, il y a une attente de 3 minutes en chaque carrefour, sauf en ceux de HomeCity et de UniverCity.
1. Donner l'algorithme de Moore-Dijkstra et préciser le nombre d'itérations néssaires pour déterminer le plus court chemin de HomeCity â UniverCity
2. Appliquer l'algorithme de Moore-Dijkstra pour déterminer le chemin que le professeur doit emprunter lui permettant de partir le plus tard de chez lui et d'arriver â l'heure â UniverCity.
3. A qu'elle heure doit-il partir?
4. Pour des raisons de précaution, le professeur souhaite savoir l'itinéraire le plus long de Home- City â UniverCity .
a- Qu'elle est la modification â apporté au graphe pour déterminer â l'aide de l'algorithme de Moore-Dijkstra le plus long chemin de HomeCity â UniverCity.
b-Déterminer â l'aide de l'algorithme de Moore-Dijkstra le plus long chemin de HomeCity â UniverCity.
EXERCICE 3 :(5 pts)
Un traiteur doit utiliser des serviettes de table chaque jour, pendant une durée de trois jours.Celles-ci peuvent être achetées neuves , à 6 euros la pièce , ou bien lavées pour être réutilisées;dans ce dernier cas, on a le choix entre le lavage rapide ( serviettes réutilisables le lendemain ), â 3 euros la pièce ou le lavage normal ( serviettes réutilisables le surlendemain ), i 2 euros la pièce.Le traiteur cherche â minimiser le coût total de l'opération, sachant qu'il a besoin de 100 serviettes le premier jour , de 70 serviettes le deuxième jour et de 130 serviettes le troisième jour .
En considérant les sommets suivants:
A : achat de serviettes;
L : le lavage des serviettes (service rapide et normal ) Ln :le lavage service rapide des serviettes
avec i = 1, 2, 3 respectivement le 1" le 2' et le 3ème jour.
1.A L'aide d'un graphe ,formuler le problème comme un problème de flot maximal à. coût minimal
2.Afin de minimiser le coût total de l'opération,appliquer l'algorithme de Busacker et Gowen pour résoudre ce problème.
EXERCICE 4 :(6 pts)
La réalisation d'un petit projet fait intervenir les tâches suivantes:
|
Tâches |
A.- |
B |
C |
D |
E |
F |
G |
H |
|
Durée en semaines |
3 |
6 |
2 |
4 |
2 |
7 |
4 |
3 |
|
Tâches anterieures |
- |
- |
- |
A |
A |
A |
B,D |
C,F |
1. Déterminer le rang de chaque tâches.
2. Construire le graphe potentiels-tâches .
3. Calculer les dates de début d'exécution au plus tôt et au plus tard ainsi que les marges de chaque tâche.
4. Donner la définition d'un chemin critique et déterminer un chemin critique de ce problènie
5. Comment modifier le graphe si , en plus des contraintes précédentes, on veut que la tâche G ne commence pas avant 8 semaines ? Donner la conséquence de cette modification
6. Comment modifier le graphe si , en plus des contraintes précédentes, on veut que: -F ne doit pas commencer avant la moitié de réalisation de G.
- Et F doit suivre immédiatement A ? .
Donner la conséquence de cette modification.
Rappels:
— la contrainte : j ne peut commencer qu'après la date b,, se représente par un arc (a, j) de longueur b,.
 |
bi
— la contrainte : j ne doit pas commencer avant la moitié de la réalisation de la tâche i, se représente par un arc (i, j) supplémentaire de longueur d,/2.
di/2
— la contrainte : j doit suivre immédiatement la tâche i, s'écrit t, + d = t, et se représente par un arc (i, j) de longueur d et un arc (j,ei) de longueur – d,.
di