EPFL RECHERCHE OPÉRATIONNELLE
Institut de Mathématiques SC
L. Pournin AUTOMNE 2007
SÉRIE D’EXERCICES 8
Problème 1
Une commune veut offrir des possibilités de connexion à haut débit par câble dans ses nouveaux
lotissements. Les liaisons envisageables entre les lotissements (numérotés de 1 à 7), ainsi que les
estimations des coûts de construction sont donnés dans le graphe ci-dessous :
2 4 7
7
1 4 7 8 12
5
3 6 5 10 6
8
9 11
13 4
Actuellement, seul le lotissement numéro 1 est relié au réseau à haut débit.
Déterminer les liaisons à mettre en place de manière à connecter tous les lotissements au réseau
tout en minimisant les coûts de construction. Expliquer votre démarche et préciser les étapes
intermédiaires de votre résolution.
Problème 2
Soit le réseau R = (V, E, c) ci-dessous :
v2
-6
-5
-2 v3
-2 -1
v1 -1 0 -2 v6
-4
v5
-4 -1
v4 -3 -5
Déterminer un plus long chemin du sommet v1 au sommet v6 . Préciser la méthode utilisée ainsi
que les étapes de la résolution.
1
Problème 3
Anne habite à HomeCity et travaille à ImaCity. Elle effectue donc l’aller et retour chaque jour
en voiture. Ayant énormément de peine à se lever, elle 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’elle peut emprunter pour se rendre de HomeCity à ImaCity.
a 15 10
d
f
5 6
3 8
11
b 6
HomeCity e ImaCity
1
8
2 6
c 14
g
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
ImaCity.
Déterminer le chemin qu’Anne doit emprunter lui permettant de partir le plus tard de chez elle
et d’arriver à l’heure à ImaCity. À qu’elle heure doit-elle partir ?
Justifier la solution trouvée à l’aide d’un algorithme et vérifier ses hypothèses d’application.
Problème 4
C’est bientôt nouvel an. Christine et Eric ont décidé d’organiser une petite fête déguisée pour
l’occasion. Ils doivent tout prévoir du thème du déguisement au transport des invités, car la fête
aura lieu un peu en dehors de Lausanne. Ils ont énuméré les tâches qu’ils doivent effectuer pour
que la fête soit belle.
Tâche Description Précédences Durée [jours]
A Fixer le budget 1/2
B Louer la salle A 1/2
C Faire la liste des invités A 1
D Acheter les cartons d’invitation A, C 1
E Faire imprimer le texte sur les cartons C, D 2
F Envoyer les invitations C, D, E 1/2
G Penser à un thème de déguisement 3
H Acheter le nécessaire pour le déguisement G 2
I Confectionner le déguisement G, H 4
J Récolter le nombre de réponses positives F 2
K Acheter la vaisselle en plastique nécessaire J 1/2
L Acheter les décorations pour la salle B, J 1/2
M Décorer la salle I, L, N 1
N Organiser le transport des invités J, K 2
2
a) Représenter le graphe de précédences des tâches pour l’organisation de la fête.
b) Effectuer une numérotation des sommets compatible avec le rang.
c) Calculer les dates de début au plus tôt et au plus tard de chacune des tâches.
d) Donner la durée minimale de l’organisation.
e) Déterminer le chemin critique et les tâches critiques.
f) Sachant que l’imprimeur du quartier est toujours très demandé, Christine et Eric doutent de
la durée de la tâche E. S’il faut 3 jours au lieu de 2 pour imprimer les cartons, devront-ils
commencer plus tôt pour être prêts le jour de la fête ? Si oui, de combien de jours ?
Problème 5
Un groupe d’étudiants désire partir skier une semaine à la montagne. Pour l’organisation, ils
ont établi un tableau résumant l’ensemble des tâches à exécuter avec les durées prévisibles de
chaunes d’entre-elles.
Tâche Description Précédences Durée [jours]
A Établissement d’un cahier des charges C 15
B Recherche de sponsors C 90
C Déterminer le nombre de candidats potentiels 15
D Choix du mode de transport A 3
E Choix de l’entreprise de transport D, J 20
F Inscription des étudiants E, G, I, H, B 15
G Recherche du logement J 30
H Recherche de fournisseurs pour la nourriture D, J 30
I Négociation des forfaits de ski J 5
J Choix de la station de ski A 5
Après avoir ajouté les tâches α et ω de début et fin des travaux, on obtient le graphe de
précédences suivant :
3
D H
15
3 E
A 5
5 30
20
15 15 5
J G 30
5 15
0 5 F ω
α C I
15 90
B
Un tri topologique de ce graphe a permis d’obtenir la numérotation compatible suivante :
Tâche α A B C D E F G H I J ω
Numéro k 1 3 4 2 5 7 11 8 10 9 6 12
a) Déterminer pour chaque activité, les dates de début au plus tôt et au plus tard.
b) Calculer la durée minimale du projet.
c) Donner l’ensemble des tâches critiques.
d) Déterminer le (les) chemin(s) critique(s).
22 novembre 2007 – lp/gh
